Stereo Matching

The primary output of stereo matching is a disparity map, a per-pixel image where each value represents the horizontal shift (in pixels) between corresponding points in the left and right rectified images. This shift is inversely proportional to depth. Key concepts include:

• Rectification: A pre-processing step that aligns the stereo images to lie on the same epipolar line, simplifying the search for correspondences to a 1D horizontal scan.
• Correspondence Problem: The core challenge of identifying which pixel in the right image matches a given pixel in the left image.
• Depth Calculation: Once disparity (d) is known, depth (Z) is calculated using the camera baseline (B) and focal length (f): Z = (f * B) / d.

Stereo algorithms are broadly classified by how they enforce smoothness and resolve ambiguities in the disparity map.

• Local Methods (Window-based): Estimate disparity for each pixel independently by comparing small correlation windows (e.g., using Sum of Absolute Differences (SAD) or Normalized Cross-Correlation (NCC)) between images. They are fast but struggle in textureless or repetitive regions.
• Global Methods: Formulate disparity estimation as an energy minimization problem. They define a cost function with a data term (matching cost) and a smoothness term (penalizing disparity differences between neighboring pixels). Optimization is performed over the entire image using algorithms like Graph Cuts or Belief Propagation, yielding more accurate but computationally intensive results.
• Semi-Global Matching (SGM): A widely adopted hybrid that approximates a global smoothness constraint by aggregating matching costs along multiple 1D paths, offering a favorable accuracy-speed trade-off.

The matching cost measures the similarity or dissimilarity between pixels or patches. The choice of cost function critically impacts robustness to radiometric differences and noise.

• Pixel-wise costs: Simple but noisy. Examples include Absolute Intensity Difference and Squared Intensity Difference.
• Census Transform: A non-parametric local transform that encodes the relative ordering of pixel intensities within a window, making it robust to lighting changes.
• Mutual Information: A statistical measure based on the joint probability distribution of intensities, highly robust to complex radiometric variations between the stereo pair.
• Deep Learning Costs: Modern methods use convolutional neural networks (CNNs) to learn a feature representation and compute a cost volume, often outperforming hand-crafted costs.

Raw matching costs are noisy and must be refined to produce a coherent disparity map.

• Cost Aggregation: The process of summing or filtering matching costs over a support region (window) to improve reliability. Techniques range from simple box filters to bilateral filters that preserve edges.
• Cost Volume: A 3D array of size (height x width x disparity_range) storing the aggregated matching cost for every pixel at every possible disparity level.
• Winner-Takes-All (WTA): For local methods, the final disparity is selected as the one with the minimum cost at each pixel.
• Disparity Refinement: Post-processing steps like left-right consistency checking (to detect occlusions), sub-pixel interpolation (for increased precision), and weighted median filtering are applied to clean the raw disparity map.

Stereo matching is an ill-posed problem with several inherent challenges that limit performance.

• Occlusions: Regions visible in one camera but not the other, leading to undefined disparity. These are often handled via consistency checks.
• Textureless Regions: Areas with uniform color (e.g., white walls) provide no distinctive features for matching, causing the aperture problem.
• Repetitive Textures: Patterns like brick walls or blinds create multiple plausible matches, leading to ambiguity.
• Specularities & Non-Lambertian Surfaces: Surfaces where appearance changes with viewpoint violate the constant-brightness assumption.
• Depth Discontinuities: Sudden changes in depth at object boundaries, where matching windows incorrectly blend foreground and background information.

Stereo matching is a foundational component in numerous spatial computing and robotics systems.

• Robotics & Autonomous Vehicles: For obstacle detection, terrain mapping, and simultaneous localization and mapping (Visual SLAM).
• 3D Reconstruction: As a core component of Multi-View Stereo (MVS) pipelines, which extend the two-view case to many images.
• Augmented Reality: For real-time environment understanding and occlusion handling.
• Relation to Other Methods: It is distinct from Monocular Depth Estimation (which uses a single image and learned priors) and Active Sensing methods like Structured Light or LiDAR (which project their own light pattern). Modern Deep Stereo networks, such as GC-Net and PSMNet, use end-to-end learning to predict disparity from the raw image pair.

In specialized imaging, stereo microscopes use two optical paths to provide a 3D view. Computational stereo matching algorithms can quantify the depth and topography of microscopic samples, such as biological tissues, semiconductor wafers, or material fractures. This allows for non-contact measurement of surface features at micron-scale resolution.

• Key Use: Measuring the depth of etchings on a microchip or the height of cells in a culture.
• Benefit: Non-destructive alternative to physical profilometers.
• Precision: Can achieve sub-micron depth resolution under controlled lighting and calibration.

A depth map is a single-channel image where each pixel's intensity value represents the distance from the camera to the corresponding point in the 3D scene. It is the direct output of stereo matching after converting the disparity map using known camera geometry (baseline and focal length). Depth maps are fundamental for tasks like 3D reconstruction, object segmentation, and augmented reality occlusion.

A disparity map is the immediate, pixel-wise output of a stereo matching algorithm. For a pair of rectified stereo images, disparity is the horizontal shift (in pixels) between corresponding points in the left and right images. Key properties:

• Inversely proportional to depth: Higher disparity = closer object.
• Sparse vs. Dense: Algorithms produce semi-dense or fully dense maps.
• Primary Cost: Matching is framed as minimizing a cost function (e.g., Sum of Absolute Differences, Normalized Cross-Correlation) across possible disparities.

Epipolar geometry describes the intrinsic projective geometry between two views. It constrains the search for corresponding points, simplifying stereo matching. After image rectification, corresponding points lie on the same horizontal scanline. Core components:

• Epipolar Line: The line in one image where the corresponding point in the other image must lie.
• Fundamental Matrix (F): The algebraic representation of epipolar geometry for uncalibrated cameras.
• Essential Matrix (E): The same for calibrated cameras, from which camera pose can be extracted.

Image rectification is a pre-processing warp applied to a pair of stereo images to make their epipolar lines align perfectly with the image rows. This transforms the 2D correspondence search into a 1D search along horizontal lines, dramatically reducing computational complexity. It is a prerequisite for most efficient stereo matching algorithms.

Multi-View Stereo (MVS) is a technique that generates dense 3D geometry from multiple (often >2) calibrated images. While traditional stereo matching uses two views, MVS fuses information from many viewpoints to produce more complete and robust reconstructions, typically outputting a point cloud or mesh. It often uses the output of Structure from Motion (SfM) as its input (camera poses and sparse points).

In deep learning-based stereo matching, a cost volume is a central 3D data structure (Height x Width x Disparity). For each pixel and each possible disparity, it stores a matching cost. Networks like GC-Net and PSMNet construct a cost volume by comparing feature maps from the left and right images, then apply 3D convolutions to regularize it before selecting the disparity with the lowest cost (the winner-takes-all strategy).