To reconstruct a three-dimensional world from two-dimensional images, a system must determine which point in one image corresponds to the same physical point in another. This is the correspondence problem. While it sounds simple, it is the central bottleneck of stereo vision. As F. Roecker and A. Kiessling noted in Methods For Analyzing Three Dimensional Scenes, identifying these "conjugate points" is a massive computational hurdle that often prevents real-time interaction.
The Geometry of Ambiguity
The fundamental difficulty arises because a single pixel in a 2D image represents a ray in 3D space. Any object along that ray projects to the same pixel. When we introduce a second camera, we look for that same object along an "epipolar line." However, in complex scenes, many points might look identical along that line—a phenomenon known as the "false targets problem."
Donald B. Gennery demonstrated in A Stereo Vision System for an Autonomous Vehicle that noise, lack of texture, and lighting changes make simple pixel-matching unreliable. If a system matches the wrong points, it calculates an incorrect depth, creating "ghost" obstacles or "false surfaces" that do not exist, as described in TINA: The Sheffeild AIVRU Vision System.
Resolving Ambiguity with Geometric Constraints
One of the most elegant solutions to this ambiguity is adding more cameras. Nicholas Ayache and Francis Lustman pioneered Trinocular Stereovision, which uses a third "witness" camera. Instead of searching for a match, the system predicts where a point should appear in the third image based on the first two. If the point isn't there, the match is rejected. This transforms a complex search into a simple geometric verification.
Similarly, Charles V. Stewart and Charles R. Dyer developed the Trinocular General Support Algorithm, which uses a connectionist network to let neighboring matches "support" each other. This leverages the intuition that physical surfaces are usually continuous; if a group of nearby points all suggest a similar depth, they are likely correct.
Structural and Statistical Matching
When individual points are too ambiguous, researchers look at higher-level structures. Gang Xu suggested a Region-Based Stereo Algorithm that matches large, statistically unique image patches rather than single pixels. By projecting random patterns onto a scene, even featureless surfaces become easy to match.
Other researchers have used topological constraints. Charles E. Thorpe and Steven A. Shafer showed in Correspondence in Line Drawings that the way lines meet at vertices provides a "conservation" rule that can track features across viewpoints without needing precise camera calibration. For more rigorous statistical handling, Anand S. Bedekar and Robert M. Haralick treated correspondence as a Bayesian hypothesis test, using a chi-squared test to determine the likelihood that two 2D points originated from the same 3D source.
Learning the Constraints
In the 1990s, the field shifted toward letting systems "learn" the rules of stereo vision. Alireza Khotanzad and Ying-Wung Lee demonstrated that neural networks could learn the constraints of stereopsis from random-dot patterns, outperforming hand-coded algorithms in noisy environments.
This evolution culminated in the work of Yann LeCun and Jure Zbontar, who replaced manual similarity measures (like comparing pixel brightness) with Convolutional Neural Networks. By training a network to recognize what "matching" patches look like across different perspectives, they achieved a level of robustness to lighting and distortion that traditional geometric methods could not reach.
Why It Works
The correspondence problem is solvable because the physical world is constrained. Objects are rigid, surfaces are continuous, and light behaves predictably. Whether through the geometric rigor of trinocular systems, the chromatic constraints proposed by Alan Bovik, or the linear subspaces identified by Ronen Basri, every successful approach works by narrowing the search space from "any pixel" to "the most physically plausible pixel."