Stereo Matching

Stereo matching finds, for each pixel of one image of a rectified stereo pair, the pixel in the other image that shows the same scene point. Because rectification places corresponding points on the same row, the answer at each pixel is a single number, the disparity, and the result is a dense disparity map that stereo vision converts to depth. Matching is the hard part of stereo: the geometry is fixed by calibration, while the correspondences must be inferred from image appearance.

Problem Definition

Given a rectified pair with left image $I_L$ and right image $I_R$, find a disparity map $d(x, y)$ such that the left pixel $(x, y)$ and the right pixel $(x - d(x, y), y)$ are projections of the same 3D point. Disparities are searched in a range $[d_\text{min}, d_\text{max}]$ set by the nearest and farthest depths of interest. The left image is usually the reference; computing a second map with the right image as reference is common for consistency checking.

Most methods rest on two assumptions. A photo-consistency assumption, a form of brightness constancy, says that corresponding pixels look alike. A smoothness assumption says that disparity varies slowly over most of the image, because scenes are made of surfaces, except at object boundaries where it jumps. Pixels visible in only one image, the occlusions, satisfy neither and have no correct disparity at all.

Input and Output

• Input: a rectified image pair, gray or color, and a disparity search range. Calibration (focal length, baseline, principal-point offset) is needed only to convert the result into depth.
• Output: a disparity map at the resolution of the reference image, usually with sub-pixel values, often with a validity mask that marks occluded or unreliable pixels, and sometimes with a per-pixel confidence.

Variants

• Dense versus sparse. This article concerns dense matching. Sparse stereo triangulates only distinctive points found by feature matching.
• Multi-view stereo searches depth hypotheses in many calibrated views at once, using plane-sweep cost volumes.
• Optical flow is the unconstrained version of the problem, with a 2D displacement per pixel, covered under optical flow estimation.

Challenges

• Occlusions. Near every depth discontinuity, a strip of background seen by one camera is hidden from the other. Its width equals the disparity jump.
• Textureless regions. Uniform walls, sky, and road surfaces match equally well at many disparities, so the data alone cannot decide.
• Repetitive patterns. Fences, tiles, and windows produce several equally good matches at different disparities.
• Specularities and transparency. Reflections move with the viewpoint and do not belong to the surface, and transparent objects such as glass carry two depths at once.
• Radiometric differences. The two cameras may differ in exposure, gain, vignetting, and response, so corresponding pixels need not have equal intensities.
• Thin structures and discontinuities. Poles, wires, and object edges are only a few pixels wide; matching windows straddle foreground and background there and enlarge foreground objects, the “edge-fattening” effect.
• Slanted surfaces. A fronto-parallel window assumes constant disparity inside it, which roads, floors, and walls seen at an angle violate.

Approaches

Scharstein and Szeliski (2002) observed that dense stereo algorithms perform subsets of four steps: matching cost computation, cost aggregation, disparity computation or optimization, and disparity refinement. The steps operate on a cost volume of matching costs indexed by pixel and disparity. Their taxonomy still organizes the field, and deep networks largely learn the same steps.

Local methods

Local methods compute a matching cost such as the sum of absolute differences, normalized cross-correlation, or the census transform, aggregate it over a support window, and choose the lowest-cost disparity at each pixel (winner-take-all). They are fast, but a window must be large enough to be distinctive in weak texture and small enough not to straddle a depth boundary, and no fixed size satisfies both; adaptive windows and color-based support weights relax this conflict. The cost volume article works through the costs and the edge-fattening trade-off.

Global energy minimization

Global methods write the whole disparity map as the minimizer of an energy over a pixel grid,

$$E(d) = \sum_{\mathbf{p}} C(\mathbf{p}, d_\mathbf{p}) + \sum_{(\mathbf{p}, \mathbf{q}) \in \mathcal{N}} V(d_\mathbf{p}, d_\mathbf{q}),$$

where $C$ is the matching cost and the smoothness term $V$ penalizes disparity differences between neighboring pixels, usually with a capped or constant penalty so that real discontinuities remain affordable. Minimizing such energies exactly is NP-hard even for the simplest discontinuity-preserving penalty. Boykov, Veksler, and Zabih (2001) introduced graph-cut algorithms that change the labels of large sets of pixels at once, through swap and expansion moves; for the Potts penalty, which charges a constant for any label change, the expansion algorithm’s result is guaranteed to be within a factor of two of the global minimum. Loopy belief propagation on the same kind of Markov random field was the other main optimizer of that period. Global methods handle textureless regions much better than local ones, at a higher computational cost.

Semi-global matching

Semi-global matching (Hirschmüller, 2008) approximates the 2D energy by one-dimensional dynamic programming along 8 or 16 paths through each pixel and sums the results; the recursion is given in the cost volume article. The original paper paired it with a mutual-information cost to handle radiometric differences, and later implementations often use census. Its running time is linear in the number of pixels and disparities, and its regular structure suits GPUs and FPGAs, which made it a common choice in practical systems.

PatchMatch and slanted planes

PatchMatch Stereo (Bleyer, Rhemann, and Rother, 2011) attacks the fronto-parallel bias of local windows. It estimates a 3D plane at every pixel and projects the support window onto that plane, so the window follows slanted surfaces. Since the set of possible planes is infinite, it adapts the randomized PatchMatch correspondence algorithm: random initial planes are refined by propagating good planes to neighbors, between the left and right views, and, in video, across frames. The same propagate-and-test idea was later carried over to multi-view stereo.

Learned matching costs and end-to-end networks

Deep learning entered stereo by replacing the first step: Žbontar and LeCun’s MC-CNN trained a convolutional network to classify patch pairs as matching or not, used its output as the matching cost, and kept a classical pipeline after it, including semi-global matching and a left-right check. End-to-end networks such as GC-Net and PSMNet then learned every step, regularizing a feature volume with 3D convolutions and regressing disparity with a differentiable soft argmin; these designs and their memory costs are described under cost volume.

RAFT-Stereo (Lipson, Teed, and Deng, 2021) carried the iterative design of the optical flow network RAFT over to stereo. It restricts RAFT’s all-pairs correlation to pixels on the same row, giving a 3D volume computed by one matrix multiplication, and refines the disparity field with convolutional GRUs that keep hidden states at several resolutions. Using only 2D convolutions lets it process megapixel images directly, and the authors reported strong cross-dataset generalization when trained only on synthetic data.

Post-processing

Most pipelines, classical and learned, finish with refinement steps that Scharstein and Szeliski grouped under disparity refinement:

• Left-right consistency check. A second disparity map is computed with the right image as reference. A left pixel whose disparity, followed into the right map, does not lead back to roughly the same disparity is marked invalid. Such pixels are mostly occlusions and mismatches.
• Sub-pixel interpolation. Fitting a parabola or similar curve to the costs around the integer minimum yields fractional disparities, which matters because depth error grows quickly at small disparities. It works only where intensities vary smoothly and the window lies on one surface.
• Hole filling. Invalidated pixels are filled from neighbors, usually from the background side, since occluded pixels belong to the farther surface.
• Filtering. A median filter removes isolated mismatches without blurring edges, and edge-preserving filters such as the bilateral filter align disparity edges with image edges.

Practical Example

The code matches a synthetic rectified pair, a textured rectangle at disparity 12 in front of a textured background at disparity 4, with $5 \times 5$ block matching in both directions, and then applies a left-right consistency check. Matching is kept deliberately simple; the point is the check.

import numpy as np
from scipy import ndimage

rng = np.random.default_rng(1)
H, W, D = 80, 120, 20
d_bg, d_fg = 4, 12                # background and foreground disparities
top, bot, a, b = 20, 60, 50, 80   # foreground rectangle in the left image
x = np.arange(W)

# Synthetic rectified pair: left pixel (x, y) shows the same point as right pixel (x - d, y).
bg = ndimage.gaussian_filter(rng.random((H, W + D)), 1.0)
fg = ndimage.gaussian_filter(rng.random((H, W + D)), 1.0)
left = bg[:, x].copy()
left[top:bot, a:b] = fg[top:bot, a:b]
right = bg[:, x + d_bg].copy()
right[top:bot, a - d_fg:b - d_fg] = fg[top:bot, a:b]
gt = np.full((H, W), d_bg)
gt[top:bot, a:b] = d_fg

# True occlusions: background pixels of the left image hidden behind the foreground in the right image.
occ = np.zeros((H, W), bool)
occ[top:bot] = (x - d_bg >= a - d_fg) & (x - d_bg < b - d_fg) & (gt[top:bot] == d_bg)

def wta_disparity(ref, other, sign, win=5):
    """Winner-take-all SAD block matching; the match of ref(x) is other(x + sign * d)."""
    cost = np.full((H, W, D), 1e3)
    for d in range(D):
        if sign < 0:
            cost[:, d:, d] = np.abs(ref[:, d:] - other[:, :W - d])
        else:
            cost[:, :W - d, d] = np.abs(ref[:, :W - d] - other[:, d:])
    cost = ndimage.uniform_filter(cost, size=(win, win, 1), mode="nearest")
    return cost.argmin(axis=2)

disp_L = wta_disparity(left, right, sign=-1)    # left as reference
disp_R = wta_disparity(right, left, sign=+1)    # right as reference

# Left-right consistency: follow each left disparity into the right map and compare.
xr = np.clip(x[None, :] - disp_L, 0, W - 1)
disp_R_at_match = np.take_along_axis(disp_R, xr, axis=1)
inconsistent = np.abs(disp_L - disp_R_at_match) > 1

inner = np.zeros((H, W), bool)
inner[4:-4, D + 4:-4] = True                    # ignore borders without full search range
err = np.abs(disp_L - gt) > 1
print(f"occluded pixels:            {occ[inner].sum()}")
print(f"flagged by left-right check: {inconsistent[inner].sum()}")
print(f"occluded pixels flagged:     {np.mean(inconsistent[inner & occ]):.1%}")
print(f"bad pixels (>1 px) before:   {np.mean(err[inner]):.2%}")
print(f"bad pixels among kept:       {np.mean(err[inner & ~inconsistent]):.2%}")
print(f"pixels kept:                 {np.mean(~inconsistent[inner]):.1%}")

Output:

occluded pixels:            320
flagged by left-right check: 365
occluded pixels flagged:     91.6%
bad pixels (>1 px) before:   4.24%
bad pixels among kept:       0.46%
pixels kept:                 94.5%

The occluded strip is 8 pixels wide, the difference between the two disparities, over the rectangle’s 40 rows. Block matching assigns those pixels some disparity anyway, and they account for about four fifths of the 4.2% bad pixels. The left-right check flags over 90% of them, plus about 70 other pixels, most within three pixels of the foreground’s edges, and the bad-pixel rate among the remaining 94.5% of pixels drops below 0.5%. The flagged pixels are what hole filling would then fill from the background.

Datasets and Benchmarks

• Middlebury: indoor scenes with high-accuracy ground truth, from the 2002 taxonomy’s test images to structured-light datasets of several megapixels with disparities of hundreds of pixels.
• KITTI: 2012 and 2015 stereo benchmarks from a driving platform, with sparse laser-derived ground truth and, in 2015, moving vehicles.
• ETH3D offers a two-view stereo benchmark with indoor and outdoor scenes, and large synthetic datasets such as the SceneFlow collection are used to pretrain deep networks.

Evaluation Metrics

• Bad-pixel percentage. The fraction of pixels whose disparity error exceeds a threshold. Scharstein and Szeliski (2002) used 1 pixel and defined it over all pixels and over non-occluded, textureless, and near-discontinuity regions, comparing algorithms mainly on the last three. KITTI 2015 counts a pixel as an outlier (D1) when its error exceeds both 3 pixels and 5% of the true disparity.
• Average disparity error and RMS error, the one-dimensional counterparts of endpoint error in optical flow.
• Running time and memory, reported by most benchmarks alongside accuracy, because practical systems often run under tight budgets.

Applications

• Depth for robots and vehicles, from obstacle detection to free-space estimation, often on embedded hardware.
• Aerial and satellite photogrammetry, producing digital surface models.
• Depth cameras based on active stereo, and depth sensing on headsets and multi-camera phones.
• 3D reconstruction and view synthesis, where dense disparities feed meshing, rendering, and multi-view fusion.

Open Problems

• Generalization across domains. Networks trained on one domain often degrade on another with different lighting, cameras, or scene content. Training on large synthetic datasets and designing architectures that generalize zero-shot are active directions.
• Real-time high-resolution matching. Disparity ranges grow with resolution, and 3D cost volumes grow with them; methods must trade accuracy against latency and memory, especially on embedded processors.
• Ill-posed regions. Reflective, transparent, and textureless surfaces, and occluded pixels, have no reliable photo-consistent match, so their disparity must come from priors.
• Calibrated uncertainty. Downstream planning needs to know where a disparity can be trusted, which most methods do not estimate reliably.