Stereo depth from two cameras

The correspondence problem#

Given rectified images $I_L, I_R$, find for each pixel the disparity $d$ minimising a matching cost, subject to a smoothness prior. Formally, minimise an energy over the disparity field $D$:

$$ E(D) = \sum_{\mathbf{p}} C(\mathbf{p}, D_{\mathbf{p}}) + \sum_{\mathbf{p}}\sum_{\mathbf{q} \in N_{\mathbf{p}}} \Bigl( P_1 \, \mathbb{1}\bigl[|D_{\mathbf{p}} - D_{\mathbf{q}}| = 1\bigr] + P_2 \, \mathbb{1}\bigl[|D_{\mathbf{p}} - D_{\mathbf{q}}| > 1\bigr] \Bigr) $$

Where $C$ is the per-pixel matching cost and $N_{\mathbf{p}}$ the 4- or 8-neighbourhood. The two-level penalty is deliberate: $P_1$ is small so slanted surfaces are not over-penalised, while $P_2$ is large and — crucially — constant regardless of the jump size, so a true depth discontinuity costs no more than a two-pixel one. That is what preserves object boundaries.

Exact minimisation of this energy in 2D is NP-hard.

Semi-global matching#

Hirschmüller (CVPR 2005; TPAMI 2008), Stereo processing by semiglobal matching and mutual information, is the practical answer, and it is what StereoSGBM implements.

Instead of a 2D optimisation, aggregate costs along 8 or 16 1D paths through each pixel, each solved exactly by dynamic programming:

$$ L_{\mathbf{r}}(\mathbf{p}, d) = C(\mathbf{p}, d) + \min\bigl(L_{\mathbf{r}}(\mathbf{p}-\mathbf{r}, d),\; L_{\mathbf{r}}(\mathbf{p}-\mathbf{r}, d\pm1) + P_1,\; \min_i L_{\mathbf{r}}(\mathbf{p}-\mathbf{r}, i) + P_2\bigr) - \min_i L_{\mathbf{r}}(\mathbf{p}-\mathbf{r}, i) $$

The trailing subtraction only prevents numeric overflow and does not change the argmin. Summing $L_{\mathbf{r}}$ over all directions $\mathbf{r}$ approximates the 2D energy well, at $O(WHD)$ cost. OpenCV's default mode uses 5 paths; StereoSGBM.MODE_HH uses 8 at higher memory cost.

The single-path predecessor, scanline dynamic programming, produces the characteristic horizontal streaking artefact, because rows are optimised independently. Aggregating over multiple directions is what removes it.

Matching costs#

• SAD / SSD over a window. Fast, and assumes identical brightness.
• Census transform. Encode each pixel as the bit pattern of comparisons with its neighbours, then use Hamming distance. Invariant to any monotonic intensity change, which makes it robust to exposure and vignetting differences. It is the standard cost in embedded stereo.
• Mutual information. Hirschmüller's original, robust to arbitrary intensity mappings, expensive and iterative.
• Birchfield-Tomasi. Samples the linearly interpolated intensity, making the cost insensitive to image sampling. OpenCV's SGBM uses a BT-based cost over a small window.

Sub-pixel and the quadratic fit#

After the winner $d^$ is found, fit a parabola through the costs at $d^-1, d^, d^+1$:

$$ \delta = \frac{C(d^-1) - C(d^+1)}{2\bigl(C(d^-1) - 2C(d^) + C(d^*+1)\bigr)} $$

This is where the 0.208-pixel median error in the output comes from. It introduces a known bias, pixel-locking, where estimates cluster toward integer disparities because the cost function is not locally parabolic. Correcting it matters for high-precision metrology and rarely otherwise.

Fundamental limits#

Depth uncertainty propagates as

$$ \sigma_Z = \frac{Z^2}{fB}\,\sigma_d $$

With $\sigma_d \approx 0.2$ px, $f = 500$, $B = 0.1$ m, the standard deviation is 4 mm at 1 m and 40 cm at 10 m. No amount of algorithmic cleverness changes the $Z^2$ term; only $f$ (resolution), $B$ (rig geometry) or $\sigma_d$ (matching quality) can move.

Three failure modes are structural rather than algorithmic:

• Textureless regions. No information exists in the images. Learned methods fill these by prior, not by measurement, which is a different claim about the world.
• Occlusion. Points visible in one view only have no true disparity. Left-right consistency checking detects them; nothing recovers them.
• Repetitive structure. A brick wall gives periodic cost minima. uniquenessRatio rejects these, at the cost of holes.

Learned stereo#

End-to-end networks now dominate the KITTI and Middlebury leaderboards. The lineage: DispNet (Mayer et al., CVPR 2016) with a correlation layer; GC-Net (Kendall et al., ICCV 2017) introducing an explicit 3D cost volume with 3D convolutions and a differentiable soft-argmin; PSMNet adding spatial pyramid pooling; RAFT-Stereo (Lipson et al., 3DV 2021) applying iterative recurrent refinement to a correlation pyramid, which remains a strong and widely used baseline.

Two honest caveats before choosing one over SGBM.

• Cross-domain generalisation is the weak point. Networks trained on synthetic data or KITTI can degrade on a different sensor, baseline or scene type. SGBM has no training distribution to leave.
• Learned methods interpolate textureless regions. They produce a smooth, plausible surface where SGBM produces a hole. For a rendering task that is better. For an obstacle detector it is a hallucinated surface, and the hole was the honest answer.

Active stereo sidesteps the texture problem entirely by projecting a pattern — the approach of the Intel RealSense D400 series and the original Kinect — and remains the most reliable way to get dense indoor depth.

What to learn next#

• Monocular depth estimation — guessing depth from one image, and what that costs.
• Structure from motion — one moving camera doing the job of two.
• Camera calibration with a chessboard — the step a real stereo rig needs first.