To reconstruct a three-dimensional scene from flat two-dimensional images, a computer vision system must determine where the rays of light originating from a physical object intersect in space. This requires identifying the exact same physical point across multiple viewpoints—a challenge historically known as the conjugate point or stereo correspondence problem, as discussed by F. Roecker et al. in Methods For Analyzing Three Dimensional Scenes.
If every point in the world possessed a unique color and texture, this task would be trivial: simply look for the identical pixel in the other image. However, the real world is visually ambiguous. As Ralf Haeusler et al. observe in Analysis of KITTI Data for Stereo Analysis with Stereo Confidence Measures, environments are filled with repetitive patterns, uniform textureless surfaces, specular reflections, and shifting illumination. When a system attempts to match a pixel from a blank white wall or a repeating pattern, it encounters multiple local minima—many different points appear equally valid, leading to catastrophic depth errors.
The Geometry of the Search Space
To make this search tractable, systems rely on epipolar geometry. Knowing the relative positions of two cameras allows us to project a ray from a pixel in the left image into the right image, where it forms a straight line called the epipolar line. The matching pixel must lie along this line, reducing a daunting two-dimensional search space down to one dimension.
Yet, even along a single line, ambiguity persists. Ram Nevatia points out in A Segment-Based Matching Algorithm in Trinocular Vision that when multiple similar visual features fall along the exact same epipolar line, standard binocular matching becomes fundamentally paralyzed. This is known as the "false targets" problem. Furthermore, as Gang Xu et al. demonstrate in Coarse-to-Fine Control Strategy for Matching Motion Stereo Pairs, expanding the search area to accommodate wider camera baselines or larger depth ranges exponentially increases the probability of encountering these deceptive matches.
From Greedy Matching to Cost Volumes
Early algorithms often made "greedy" decisions, selecting the pixel with the absolute lowest matching error. However, if noise or a slight reflection distorts the image, the mathematically "best" match may not correspond to physical reality. To combat this, Jasmine Banks in An accurate and reliable stereo matching algorithm incorporating the rank constraint introduced non-parametric rank constraints to filter out false positives by focusing on local intensity structures rather than absolute pixel values.
Modern architectures scale this intuition by constructing a cost volume—a three-dimensional tensor that stores the matching costs for every pixel across all possible depth hypotheses. Instead of throwing away alternative matches immediately, the system preserves the entire distribution of potential correspondences.
As Max Mehltretter et al. explain in CNN-Based Cost Volume Analysis as Confidence Measure for Dense Matching, analyzing the full topology of this cost volume allows a neural network to evaluate the confidence of a match. A sharp, isolated peak in the cost volume signifies a highly reliable match, whereas a flat plateau or multiple competing peaks indicate an ambiguous region (such as an occlusion or shadow) that requires regularization or alternative cues to resolve. Similarly, Zequn Jie et al. show in Left-Right Comparative Recurrent Model for Stereo Matching how recurrent networks can progressively resolve these ill-posed regions by checking for consistency between left-to-right and right-to-left matching passes over multiple iterations.
The Power of a Third Eye
One of the most elegant geometric solutions to the correspondence problem is the introduction of a third camera. In a standard two-camera setup, a point in the first image generates an epipolar line in the second image. Every point along that line represents a hypothesis for a 3D point, and each of those 3D hypotheses projects to a different location in a third camera view.
This is the core insight behind trinocular vision systems. As Nicholas Ayache et al. demonstrate in Trinocular Stereovision: Recent Results, a third "witness" camera transforms an ambiguous search problem into a deterministic geometric verification. To verify if a candidate match between Camera 1 and Camera 2 is correct, the system simply checks if the corresponding feature exists at the intersection of their predicted epipolar lines in Camera 3.
The authors of The Trinocular General Support Algorithm: A Three-camera Stereo Algorithm For Overcoming Binocular Matching Errors show that this additional constraint effectively eliminates matching errors caused by periodic or repeating patterns, providing a powerful structural anchor where binocular systems fail.
Embracing Uncertainty Probabilistically
When geometric constraints alone cannot resolve the ambiguity, modern paradigms shift from finding a single deterministic match to modeling the entire probability space of correspondences. In scenarios with wide baselines or significant perspective distortion, tracking features becomes highly non-linear and multi-modal.
To address this, Frank Dellaert et al. proposed a Bayesian framework using Markov Chain Monte Carlo (MCMC) sampling in Feature Correspondence: A Markov Chain Monte Carlo Approach. Instead of committing to an early, potentially erroneous data association, their approach explores the joint distribution of all possible camera poses and feature matches simultaneously.
Similarly, Anand S. Bedekar in Finding Corresponding Points Based on Bayesian Triangulation framed correspondence as a statistical hypothesis test, using Maximum A Posteriori (MAP) estimation to determine the most physically plausible 3D structure. By treating correspondence as a probabilistic distribution rather than a discrete assignment, these methods allow computer vision systems to gracefully navigate the inherent messiness and ambiguity of the three-dimensional world.
Key Foundational Work
Methods For Analyzing Three Dimensional Scenes (1975) — contributed 2 concept elements to this direction.