Stereo & disparity

A single camera measures direction and throws away range. Two cameras a known distance apart recover it by triangulation — but only after solving a hard correspondence problem for every pixel, roughly a million times per frame, under a real-time budget. This page works through the geometry that reduces the search to one dimension, the matching costs and the smoothness model that makes dense matching possible, and the $Z^2$ law that governs every stereo error budget ever written.

Symbols used on this page are defined in the Nomenclature → camera & multi-view geometry.

The single-camera model everything here rests on — intrinsics, extrinsics, distortion and calibration — is derived on the camera model page. Triangulation in general is developed on the structure-from-motion page; the learned matchers referenced in §8 connect to Deep Learning.

1 · Geometry

1.1 The canonical configuration

Take two identical pinhole cameras with parallel optical axes, separated by a baseline $B$ along the $x$-axis, focal length $f$ in pixels. A world point at depth $Z$ and lateral offset $X$ projects to

$$ u_L = f\frac{X}{Z} + c_x, \qquad u_R = f\frac{X - B}{Z} + c_x , $$

so the horizontal difference — the disparity — is

$$ d \;=\; u_L - u_R \;=\; \frac{fB}{Z} \qquad\Longleftrightarrow\qquad \boxed{\; Z = \frac{fB}{d} \;} $$

Disparity is inversely proportional to depth. Nearby points shift a lot between the two images, distant points shift little, and a point at infinity has zero disparity. Note also that $v_L = v_R$ — the vertical coordinates are identical. That is the property that makes dense stereo tractable.

1.2 The epipolar constraint

Real cameras are never perfectly aligned, so the general statement is the epipolar constraint. For corresponding homogeneous image points $\tilde{\mathbf x}_L, \tilde{\mathbf x}_R$,

$$ \tilde{\mathbf x}_R^\top\, \mathbf F\, \tilde{\mathbf x}_L = 0 , \qquad \mathbf F = \mathbf K_R^{-\top}\,\mathbf E\,\mathbf K_L^{-1}, \qquad \mathbf E = [\mathbf t]_\times \mathbf R . $$

Geometrically: a point in the left image, its optical centre, and the right optical centre define a plane, and the match must lie where that plane cuts the right image — a line. This collapses the search from two dimensions ($10^6$ candidates) to one ($10^2$), a four-orders-of-magnitude reduction, and it is the only reason dense stereo is computationally possible.

1.3 The two cameras as projection matrices

Section 1.1 assumed the canonical configuration. It is worth writing the general setup in the language of the camera model, because that is what calibration actually gives you and what rectification consumes. Two cameras, each with its own intrinsics and distortion, related by a rigid transform:

$$ s_L\,\tilde{\mathbf x}_L = \mathbf K_L\left[\mathbf I \mid \mathbf 0\right]\tilde{\mathbf X}, \qquad s_R\,\tilde{\mathbf x}_R = \mathbf K_R\left[\mathbf R \mid \mathbf t\right]\tilde{\mathbf X}, $$

taking the left camera frame as the reference. Here $(\mathbf R, \mathbf t)$ are the stereo extrinsics: the pose of the left camera as seen from the right. Stereo calibration estimates $\mathbf K_L, \mathbf K_R$, both distortion vectors, and $(\mathbf R, \mathbf t)$ together, typically by calibrating each camera and then refining the pair jointly on reprojection error in both images.

In the ideal rectified configuration these collapse to

$$ \mathbf R = \mathbf I, \qquad \mathbf t = \begin{bmatrix}-B \\ 0 \\ 0\end{bmatrix}, \qquad \mathbf K_L = \mathbf K_R = \mathbf K , $$

and the baseline is $B = \|\mathbf t\|$. Substituting into the two projections reproduces $u_L - u_R = f B / Z$ from §1.1 and, importantly, $v_L = v_R$. Rectification (§1.4) is the process of warping real images so that this idealisation holds.

A useful sanity check on any stereo calibration: $\mathbf t$ should be almost exactly along the camera's $x$-axis with magnitude equal to the physical baseline you can measure with a ruler, and $\mathbf R$ should be within a degree or two of identity for a rigid, well-built rig. Large values mean the cameras are genuinely misaligned, or — more often — that the extrinsic direction convention has been inverted.

1.4 Rectification

Searching along an arbitrary slanted line is cache-hostile and awkward to vectorise. Rectification warps both images so that the epipolar lines become corresponding horizontal scanlines — restoring the canonical configuration of §1.1 in software. The search then runs along a row, which is contiguous in memory and trivially SIMD-friendly.

Rectification is a resampling step, so it interpolates. That costs a little high-frequency texture — exactly the signal matching depends on — which is one reason calibration quality shows up directly in disparity quality. A vertical misalignment of even half a pixel after rectification violates the $v_L = v_R$ assumption and systematically degrades every match on the row.

1.5 The rectifying transform, concretely

Rectification computes a pair of homographies that map the original images onto a common plane with aligned rows. The construction (Bouguet's method, which is what OpenCV's stereoRectify implements) builds a new rotation whose first axis is the baseline direction:

$$ \hat{\mathbf e}_1 = \frac{\mathbf t}{\|\mathbf t\|}, \qquad \hat{\mathbf e}_2 = \frac{\left[-t_y,\; t_x,\; 0\right]^\top}{\sqrt{t_x^2+t_y^2}}, \qquad \hat{\mathbf e}_3 = \hat{\mathbf e}_1 \times \hat{\mathbf e}_2 , $$ $$ \mathbf R_{\text{rect}} = \begin{bmatrix} \hat{\mathbf e}_1^\top \\ \hat{\mathbf e}_2^\top \\ \hat{\mathbf e}_3^\top \end{bmatrix}. $$

Forcing the first row to be the baseline direction is what makes the epipolar lines horizontal: the epipole is sent to infinity along $x$. The relative rotation is then split evenly between the two cameras so neither is warped more than necessary, giving per-camera rotations $\mathbf R_L = \mathbf R_{\text{rect}}\,\mathbf R^{1/2}$ and $\mathbf R_R = \mathbf R_{\text{rect}}\,\mathbf R^{-1/2}$, and the image-plane warps are

$$ \mathbf H_L = \mathbf K'\,\mathbf R_L\,\mathbf K_L^{-1}, \qquad \mathbf H_R = \mathbf K'\,\mathbf R_R\,\mathbf K_R^{-1}, $$

with $\mathbf K'$ a new, common intrinsic matrix for both rectified images. In practice the two warps are composed with undistortion into a single lookup map per camera (initUndistortRectifyMap), so each frame costs one interpolated remap rather than two passes.

1.6 Reprojecting disparity to 3-D: the Q matrix

Once rectified, the map from a pixel plus its disparity to a 3-D point is a single linear operator in homogeneous coordinates:

$$ \mathbf Q = \begin{bmatrix} 1 & 0 & 0 & -c_x \\ 0 & 1 & 0 & -c_y \\ 0 & 0 & 0 & f \\ 0 & 0 & 1/B & \dfrac{c_x - c_x'}{B} \end{bmatrix}, \qquad \mathbf Q \begin{bmatrix} u \\ v \\ d \\ 1\end{bmatrix} = \begin{bmatrix} X \\ Y \\ Z \\ W \end{bmatrix}, $$

and the metric point is $(X/W,\; Y/W,\; Z/W)$. Dividing out gives exactly the expected result:

$$ Z = \frac{fB}{d + (c_x - c_x')}, \qquad X = \frac{(u - c_x)\,Z}{f}, \qquad Y = \frac{(v - c_y)\,Z}{f} . $$

The term $c_x - c_x'$ is the principal-point offset between the two rectified images, and it is zero only when the rectification happens to align them. This is the source of a persistent small depth bias when a pipeline hardcodes $Z = fB/d$ instead of using the calibrated $\mathbf Q$. Note also that $X$ and $Y$ are obtained by scaling the pixel offset by $Z/f$ — so lateral error inherits the depth error, and a point 30 m away with 25% depth error also has 25% error in its lateral position.

$\mathbf Q$ is the inverse of the projection for the special rectified case, and it is what reprojectImageTo3D applies. Because it is a single $4\times4$ matrix multiply per pixel, the whole disparity map becomes a point cloud in one pass — one of the reasons rectification is worth the resampling cost.

1.7 Choosing the baseline

Baseline is the central design trade, and it pulls in opposite directions:

A useful way to write the trade: the disparity budget. Requiring depth out to $Z_{\max}$ with at least $d_{\min}$ pixels of disparity, and depth in to $Z_{\min}$ within a search range $d_{\max}$, gives

$$ B \;\ge\; \frac{d_{\min} Z_{\max}}{f}, \qquad d_{\max} \;\ge\; \frac{fB}{Z_{\min}} , $$

and since cost scales with $d_{\max}$, the two requirements compete directly for compute.

2 · The error model

2.1 The $Z^2$ law

Differentiate $Z = fB/d$:

$$ \frac{dZ}{dd} = -\frac{fB}{d^2} = -\frac{Z^2}{fB} \qquad\Longrightarrow\qquad \boxed{\;\sigma_Z = \frac{Z^2}{fB}\,\sigma_d\;} $$

This is the most important equation in stereo vision. A fixed disparity accuracy produces a depth error that grows quadratically with range. Doubling the distance quadruples the error.

Computed for $f = 800$ px, $B = 0.20$ m. At 80 m the depth estimate is a suggestion, not a measurement — and this is with sub-pixel matching working perfectly. This table is why automotive stereo is usually fused with radar or LiDAR for long range rather than trusted alone.

2.2 Depth quantisation: the shells

There is a second, distinct consequence of the reciprocal relationship. Matching returns integer disparities, and because $Z = fB/d$ is nonlinear, those integers do not sample depth uniformly — each one defines a depth shell, and the spacing between consecutive shells is

$$ \Delta Z(d) = \frac{fB}{d} - \frac{fB}{d+1} = \frac{fB}{d(d+1)} \;\approx\; \frac{Z^2}{fB} \quad \text{for large } d . $$

Near the camera the shells are millimetres apart; at long range they are metres apart. This is the origin of the "layered" or "stair-stepped" appearance of a raw stereo point cloud, and it is a quantisation artefact rather than noise — which is precisely why subpixel refinement (§2.3) recovers so much: it interpolates between shells that integer matching cannot resolve.

The simulation draws the shells directly in a plan view and overlays the $\pm\sigma_Z$ band on the $Z(d)$ curve. Two things to try: reduce the baseline and watch the shells spread out toward the far field; and raise the disparity search range, which pulls the near limit $Z_{\min} = fB/d_{\max}$ closer while costing compute proportionally (§7).

2.3 Subpixel refinement

Integer disparity quantises depth into a discrete set of shells, visible as "staircase" artefacts in a point cloud. Since $\sigma_d$ appears linearly in the error, subpixel estimation is the cheapest available accuracy improvement. Fit a parabola through the winning cost $C(d^\star)$ and its two neighbours:

$$ \delta = \frac{C(d^\star-1) - C(d^\star+1)} {2\left[C(d^\star-1) - 2C(d^\star) + C(d^\star+1)\right]}, \qquad \hat d = d^\star + \delta . $$

This typically takes $\sigma_d$ from roughly 0.5 px (quantisation-limited) to 0.1–0.25 px, i.e. a 2–5× improvement in depth accuracy for a handful of flops per pixel. Two caveats: the parabola is only a model of the cost shape, and it introduces a mild bias toward integer values known as pixel-locking — visible as banding in a smooth surface. Symmetric cost functions and equiangular fitting reduce it.

3 · Matching costs

3.1 The candidates

Every dense algorithm needs a per-pixel, per-disparity dissimilarity. The choice determines robustness to the two things that actually differ between the cameras: gain/exposure and noise.

3.2 Why census transform is the workhorse

The census transform replaces each pixel by a bit string encoding whether each neighbour is brighter or darker than the centre:

$$ \mathcal{C}(\mathbf x) = \bigotimes_{\mathbf y \in W(\mathbf x)} \mathbb{1}\!\left[\,I(\mathbf y) \lt I(\mathbf x)\,\right] , \qquad \text{cost} = \operatorname{Hamming}\!\left(\mathcal{C}_L, \mathcal{C}_R\right). $$

Because it records only order, it is invariant to any monotonically increasing intensity transformation — so different exposure, gain, gamma or vignetting between the two cameras cost nothing. It is also robust to outliers: a single blown-out pixel flips at most one bit, whereas in SAD it can dominate the whole window. And the comparison is a Hamming distance, which is an XOR and a population count — one of the cheapest operations available on FPGA or SIMD. Robust, cheap, and hardware-friendly is a rare combination.

3.3 The window-size trade

Aggregating cost over a window is what disambiguates a single pixel, and the size is a direct trade:

The failure worth naming is foreground fattening: a window straddling a depth discontinuity contains two surfaces, and the nearer, better-textured one usually wins the vote — so the foreground object appears to bleed outward by roughly half the window. This is the fundamental limitation of fixed-window local methods, and it is the specific problem that semi-global matching solves by replacing the window vote with a global smoothness model.

4 · Semi-global matching

4.1 The energy

Hirschmüller's SGM poses disparity estimation as energy minimisation over the whole image: a data term plus a penalty for disagreeing with neighbours.

$$ E(D) = \underbrace{\sum_{\mathbf p} C\!\left(\mathbf p, D_{\mathbf p}\right)}_{\text{data}} + \underbrace{\sum_{\mathbf p}\sum_{\mathbf q \in N_{\mathbf p}} P_1\,\mathbb{1}\!\left[\left|D_{\mathbf p}-D_{\mathbf q}\right| = 1\right]}_{\text{slanted surfaces}} + \underbrace{\sum_{\mathbf p}\sum_{\mathbf q \in N_{\mathbf p}} P_2\,\mathbb{1}\!\left[\left|D_{\mathbf p}-D_{\mathbf q}\right| \gt 1\right]}_{\text{discontinuities}} $$

The two-level penalty is the key modelling insight. $P_1$ is small, so a gradual change of one disparity step is nearly free — this lets slanted and curved surfaces be reconstructed smoothly. $P_2$ is large but constant regardless of jump size, so a genuine depth discontinuity is charged a fixed toll rather than a growing one. A quadratic penalty would make real object boundaries prohibitively expensive and smear them; a constant penalty preserves them.

4.2 Path aggregation

Minimising $E$ exactly in 2-D is NP-hard. SGM's approximation — the "semi" in the name — is to solve it exactly along many 1-D paths through each pixel by dynamic programming, then sum the results. Along direction $\mathbf r$:

$$ L_{\mathbf r}(\mathbf p, d) = C(\mathbf p, d) + \min\begin{cases} L_{\mathbf r}(\mathbf p - \mathbf r,\, d) \\ L_{\mathbf r}(\mathbf p - \mathbf r,\, d \pm 1) + P_1 \\ \min_{k} L_{\mathbf r}(\mathbf p - \mathbf r,\, k) + P_2 \end{cases} \;-\; \min_k L_{\mathbf r}(\mathbf p - \mathbf r,\, k) $$

The trailing subtraction is a numerical necessity, not part of the model: without it the accumulated cost grows without bound along the path and overflows a 16-bit accumulator. Subtracting the previous row's minimum keeps the values bounded while leaving the argmin unchanged. The aggregated cost is then $S(\mathbf p, d) = \sum_{\mathbf r} L_{\mathbf r}(\mathbf p, d)$ over 8 (or 16) directions, and the disparity is its argmin.

A common refinement makes $P_2$ adaptive: divide it by the local intensity gradient, so a discontinuity is cheaper where the image also has an edge. This aligns depth boundaries with visible object boundaries and is nearly free to compute.

4.3 Why aggregating many 1-D problems works

A single scanline DP is the classic stereo method and its weakness is notorious: it enforces smoothness along rows but nothing across them, producing horizontal streaking. SGM's insight is that summing several independent 1-D solutions through different orientations approximates the 2-D smoothness term well enough, at a fraction of the cost of a true 2-D optimisation. It is a genuinely excellent engineering trade, which is why SGM has been the practical standard for dense stereo for two decades and is what ships in most FPGA and ASIC stereo pipelines.

4.4 The sim

The left panel shows the cost curve for one pixel and the effect of aggregation; the right panel plots the $Z^2$ error law. The experiment to run: drop the texture contrast and watch the raw cost (amber) flatten into near-ties so that winner-take-all picks the wrong minimum — often the repeated-texture decoy — while the aggregated cost (blue) still finds the correct disparity. That is SGM earning its keep. Then sweep depth and watch the error curve climb quadratically.

5 · Post-processing

A raw disparity map is not usable output. The standard chain, each step targeting a specific failure:

6 · Where stereo fails

• Textureless surfaces. A blank wall, clear sky, a painted floor. The cost curve is flat and there is genuinely no information; the correct output is "unknown", and any specific answer is a fabrication. This is the fundamental limit — and the reason active projected-texture stereo exists.
• Repetitive texture. Brick, railings, keyboards, chain-link fence. The cost curve has multiple equally deep minima one period apart, so the match can be confidently off by exactly one period. The smoothness term helps by propagating from unambiguous neighbours, which is why a global model matters more here than a better local cost.
• Occlusion. Points visible in one camera only. There is no correct disparity; these must be detected (left-right check) rather than estimated.
• Specular and transparent surfaces. A highlight moves with the viewpoint, so the two cameras see different "features" and match them to a wrong depth. Glass and water can produce reflections that match consistently at the mirrored depth — confidently wrong.
• Thin structures. Wires, poles, railings smaller than the aggregation window get absorbed into the background.
• Calibration drift. Thermal expansion and vibration change the extrinsics. A small vertical misalignment breaks the rectification assumption; a small baseline or focal error is worse because it biases every depth by a scale factor. Any long-lived stereo system needs online self-calibration or periodic recalibration.
• Motion and rolling shutter. If the two cameras are not synchronised to well under the motion timescale, they image different moments and the disparity is contaminated by scene motion. Hardware sync is not optional.

7 · Compute cost

The cost volume has $W \times H \times d_{\max}$ entries, and this dominates everything:

$$ \text{cost volume} = W\,H\,d_{\max}, \qquad \text{SGM aggregation} \approx 8\,W\,H\,d_{\max}\ \text{(8 paths)} . $$

At 30 fps the 1080p case needs ~96 G path updates per second — which is why production stereo runs on FPGAs, ASICs or GPUs rather than a CPU. The standard mitigations: process at reduced resolution and upsample; use a hierarchical coarse-to-fine search so $d_{\max}$ can be small at full resolution; restrict $d_{\max}$ using a known minimum working distance; and aggregate over 4 or 5 paths instead of 8, which costs modest quality for a large saving. Memory bandwidth, not arithmetic, is usually the binding constraint.

8 · Learned stereo

Deep networks changed stereo in a specific, limited way. Understanding what they did and did not change is the useful part.

The architectural lineage is worth knowing: MC-CNN replaced only the matching cost and kept SGM; GC-Net and PSMNet made the whole pipeline end-to-end differentiable with a 3-D-convolution cost-volume aggregator; GA-Net put a learned, differentiable version of SGM's aggregation back inside a network; RAFT-Stereo replaced expensive 3-D convolutions with recurrent lookups into an all-pairs correlation volume, which is both more accurate and cheaper.

9 · Practical checklist

• Hardware-synchronise the cameras. Non-simultaneous exposure is an unfixable error.
• Calibrate carefully, and monitor for drift. Check residual vertical disparity on a known target as a health metric — it is a direct measure of rectification validity.
• Size the baseline from the disparity budget (§1.4) rather than by convention.
• Use census cost unless there is a specific reason not to; it is robust and cheap.
• Use SGM rather than a fixed-window local method; foreground fattening is otherwise unavoidable.
• Always do the left-right consistency check and keep the validity mask all the way through.
• Do subpixel refinement — it is the cheapest accuracy available.
• Filter in inverse depth, not depth, when feeding an estimator (§2.1).
• Publish per-pixel uncertainty from $\sigma_Z = Z^2\sigma_d/(fB)$, so consumers can weight near and far points correctly.
• Test the failure scenes deliberately: blank wall, brick wall, backlit scene, wet road, glass door.

10 · Further reading

• Hartley & Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., chapters 9–11. The definitive treatment of epipolar geometry and rectification.
• Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., chapter 12. The best single overview of dense stereo, freely available online.
• Scharstein & Szeliski (2002), "A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms," IJCV 47. The paper that organised the field into the cost/aggregation/optimisation/refinement decomposition used above.
• Hirschmüller (2008), "Stereo Processing by Semiglobal Matching and Mutual Information," IEEE TPAMI 30(2). SGM in full.
• Zabih & Woodfill (1994), "Non-parametric Local Transforms for Computing Visual Correspondence." The census transform.
• Hirschmüller & Scharstein (2009), "Evaluation of Stereo Matching Costs on Images with Radiometric Differences." Why census wins in practice.
• Žbontar & LeCun (2016), "Stereo Matching by Training a Convolutional Neural Network to Compare Image Patches," JMLR. MC-CNN.
• Kendall et al. (2017), "End-to-End Learning of Geometry and Context for Deep Stereo Regression." GC-Net and the soft-argmin.
• Chang & Chen (2018), "Pyramid Stereo Matching Network" (PSMNet).
• Lipson, Teed & Deng (2021), "RAFT-Stereo: Multilevel Recurrent Field Transforms for Stereo Matching."
• Middlebury and KITTI stereo benchmarks — for the current leaderboard and, more usefully, for the failure-case galleries.

Related pages: Structure from motion · PnP · ICP & registration · Perception stack · Deep Learning