Stereo Vision and Depth

Stereo vision estimates the depth of scene points by comparing two (or more) images taken from different, known viewpoints. The central geometric quantity is disparity: the difference in horizontal image position between the projections of the same 3D point in the left and right images of a rectified stereo pair. Rectification is a pair of image warps, computable from calibration, that make the epipolar lines horizontal and aligned, so that a point at row $y$ in the left image can only correspond to a point at the same row $y$ in the right image. This is the payoff promised by Epipolar Geometry: the correspondence search drops from two dimensions to one. Formally, for a rectified pair with baseline $B$ (the distance between the two camera centers) and focal length $f$ (in pixels, identical for both cameras after rectification), a 3D point at depth $Z$ projects to horizontal coordinates $x_L$ and $x_R$ in the left and right images satisfying

Here $d$ is the disparity. Solving for depth gives the triangulation equation

This single equation is why stereo works: disparity and depth are related by simple inverse proportionality, calibrated entirely by quantities ($f$, $B$) known in advance from Camera Calibration. The practical problem — the one that consumes the algorithmic effort — is estimating $d$ at every pixel from image content alone. That is the correspondence problem, and it is fundamentally ambiguous: a single pixel in isolation, especially in a textureless or repetitive region, may match equally well to many candidates. Resolving this ambiguity is what distinguishes local, greedy stereo algorithms from global, energy-minimizing ones.

The stereo pipeline has four stages: rectification, matching-cost computation, cost aggregation/optimization, and triangulation.

1. Rectification. Using the calibrated intrinsics and the relative pose (rotation $R$, translation $T$) between the two cameras, each image is warped by a homography so that: (a) both image planes lie in the same plane, (b) epipolar lines become horizontal, and (c) corresponding points lie on identical rows. After rectification the two virtual cameras have parallel optical axes and a purely horizontal baseline — the canonical stereo configuration.

2. Matching cost. For every pixel $(x,y)$ in the left image and every candidate disparity $d$ in a search range $[0, D_{\max}]$, compute a cost $C(x,y,d)$ measuring how well the left patch around $(x,y)$ matches the right patch around $(x-d,y)$. Common costs:

• SAD (sum of absolute differences): $\sum_{(i,j)\in W} |I_L(x+i,y+j) - I_R(x-d+i,y+j)|$
• SSD (sum of squared differences): same but squared — penalizes large errors more, more sensitive to outliers.
• Normalized cross-correlation (NCC): invariant to affine brightness changes between the two cameras (different gains/exposures).
• Census transform / Hamming distance: encodes each pixel as a bit-string of local intensity comparisons (brighter/darker than center), then compares bit-strings — highly robust to radiometric differences and a workhorse of production stereo systems.

3. Aggregation / optimization. Raw per-pixel costs are noisy. Algorithms aggregate cost over a window or globally optimize over the whole scanline/image to produce a stable disparity map. Three tiers, in increasing sophistication:

• Local (winner-take-all): for each pixel independently, pick $d^* = \arg\min_d C(x,y,d)$, possibly after box-filtering the cost volume spatially. Fast, parallelizable, but fails in textureless regions.
• Scanline dynamic programming: for each row independently, find the disparity sequence minimizing total cost plus a smoothness penalty for disparity changes, solved by DP in $O(W \cdot D)$ per row (see below). Enforces 1D smoothness and monotonicity along the scanline but produces horizontal "streaking" artifacts because rows are optimized independently.
• Global 2D optimization: minimize an energy over the whole image,

where $\mathcal{N}$ is a 4- or 8-neighborhood and $\rho$ penalizes disparity discontinuities between neighbors. Solved (approximately) via graph cuts or belief propagation; semi-global matching (SGM) approximates the 2D energy by aggregating DP-like 1D costs along many directions (typically 8 or 16) through each pixel and summing them, giving near-global quality at near-linear cost.

4. Triangulation. Once a disparity map $D(x,y)$ is produced (with sub-pixel refinement, typically by fitting a parabola to the cost curve around the integer-minimum disparity), each pixel's depth is recovered via $Z = fB/D(x,y)$, and the full 3D point is reconstructed via back-projection using the calibrated intrinsics. Below is the semi-global matching-style pipeline in pseudocode, the dominant practical algorithm balancing quality and speed. ```

# Input: rectified images I_L, I_R (H x W), max disparity D_max

# Output: disparity map D (H x W) function COMPUTE_COST_VOLUME(I_L, I_R, D_max): for y in 0..H-1: for x in 0..W-1: for d in 0..D_max: if x - d >= 0: C[y][x][d] = CENSUS_HAMMING(I_L, I_R, x, y, d) else: C[y][x][d] = INF # no valid match, out of frame return C function AGGREGATE_SGM(C, directions):

# Sum 1D dynamic-programming cost paths from several directions

# through every pixel to approximate global 2D smoothness. S = zeros_like(C) for r in directions: # e.g. 8 directions: horiz, vert, diagonals L_r = zeros_like(C) for each pixel p in scan order along direction r: for d in 0..D_max: prev = p - r # previous pixel along this path if prev is outside image: L_r[p][d] = C[p][d] continue best_prev = min_d'( L_r[prev][d'] ) L_r[p][d] = C[p][d] + min( L_r[prev][d], # same disparity: no penalty L_r[prev][d-1] + P1, # small shift: small penalty L_r[prev][d+1] + P1, min_over_all_d'(L_r[prev][d']) + P2 # large jump: big penalty ) - best_prev # normalize to avoid overflow S += L_r return S function WINNER_TAKE_ALL(S): D = zeros(H, W) for y in 0..H-1: for x in 0..W-1: D[y][x] = argmin_d( S[y][x][d] ) return D function SUBPIXEL_REFINE(D, S):

# Fit a parabola through the three cost samples around the minimum for each pixel (x, y): d = D[y][x] if 0 < d < D_max: c0, c1, c2 = S[y][x][d-1], S[y][x][d], S[y][x][d+1] D[y][x] = d + 0.5 (c0 - c2) / (c0 - 2c1 + c2) return D function TRIANGULATE(D, f, B): Z = zeros(H, W) for each pixel (x, y): if D[y][x] > 0: Z[y][x] = f * B / D[y][x] else: Z[y][x] = INF # zero disparity: point at infinity / invalid return Z

# Main C = COMPUTE_COST_VOLUME(I_L, I_R, D_max) S = AGGREGATE_SGM(C, directions = [E, W, N, S, NE, NW, SE, SW]) D = WINNER_TAKE_ALL(S) D = SUBPIXEL_REFINE(D, S) Z = TRIANGULATE(D, f, B) ``` Left-right consistency checking is typically added: compute disparity independently using the right image as reference, and invalidate any pixel where the two disparity estimates disagree by more than one pixel — this flags occluded regions cheaply.

Time complexity. Let the image be $W \times H$ pixels, the disparity range have $D$ candidate values, and the matching window (if used) be $k \times k$.

• Naive cost-volume construction with windowed SAD/SSD: $O(W H D k^2)$. Using running-sum ("integral image" or box-filter) tricks for aggregation reduces this to $O(WHD)$ — each of the $D$ disparity planes is box-filtered in $O(WH)$ regardless of $k$, since box filters admit constant-time updates via prefix sums.
• Census transform cost is $O(1)$ per pixel per disparity to compute (fixed-size bit string, Hamming distance via popcount), giving $O(WHD)$ total for the cost volume, independent of $k$.
• Winner-take-all local matching: $O(WHD)$ total — this is the whole pipeline's asymptotic floor, since every pixel must at minimum be compared against every candidate disparity once.
• Scanline dynamic programming: for each of $H$ rows independently, the DP visits $W$ columns and $D$ disparities, and each state transition considers $O(D)$ or $O(1)$ predecessor states depending on the smoothness term's structure (a Potts-like penalty allows $O(1)$ transitions via running minima). Total: $O(HWD)$.
• SGM: aggregates along $r$ directions (constant, typically 8), each an $O(WD)$ or $O(HD)$ scanline pass with $O(1)$ per-step work using the running-minimum trick. Total: $O(r \cdot WHD) = O(WHD)$ since $r$ is a constant.
• Full 2D global optimization via graph cuts (e.g., alpha-expansion for multi-label disparity): each expansion move solves a min-cut on a graph with $O(WH)$ nodes, and $O(D)$ expansion rounds are typically run, giving $O(D \cdot \text{maxflow}(WH))$ — polynomial but markedly more expensive than SGM, and without a guaranteed global optimum for more than two labels (only a strong approximation guarantee: alpha-expansion is within a constant factor of the optimum for metric smoothness costs).

So the dominant practical algorithms (WTA, SGM) run in $O(WHD)$ time and $O(WHD)$ space for the cost volume, which is why disparity range $D$ is always bounded in practice (typically 64–256 for real-time systems) — it appears as a linear multiplier on both cost dimensions.

Space complexity. The cost/aggregated-cost volume dominates: $O(WHD)$. Memory-conscious implementations stream one disparity plane at a time or use 8-bit costs to keep this volume compact ($WHD$ bytes for $D=128$, $W=1280$, $H=720$ is about 118 MB — non-trivial but standard for embedded stereo hardware).

Correctness argument. The triangulation step is exact given exact calibration and exact disparity: it follows directly from similar triangles in the rectified, axis-aligned two-camera configuration, which is precisely the configuration Epipolar Geometry and rectification guarantee. The harder question is why the matching step should recover the correct disparity at all. The underlying assumption is photo-consistency: the same 3D surface point produces similar intensity/appearance in both cameras, up to noise and modest radiometric differences. Under Lambertian reflectance and small camera baseline, this assumption is a good approximation, and the true correspondence minimizes the matching cost in expectation — so winner-take-all is a maximum-likelihood estimate under an i.i.d. Gaussian noise model for SSD, or an $\ell_1$ noise model for SAD. The deeper correctness question is why global smoothness terms help rather than hurt. The scene is assumed to be piecewise smooth: disparity varies continuously across most of a physical surface and only jumps at object boundaries. The energy

encodes exactly this prior — a Markov Random Field with a data term and a pairwise smoothness term. Minimizing it is a maximum a posteriori (MAP) estimate under this prior. The correctness of SGM's approximation rests on the fact that summing several independent 1D scanline optimizations (each of which is exactly solvable by DP, since a 1D chain-structured MRF has no loops) approximates the true 2D MRF's marginals reasonably well, though it is not an exact minimizer of the full 2D energy — it is a fast, empirically strong heuristic with no general optimality guarantee, unlike DP on an actual chain, which the Bellman equation-style recursion solves exactly for that reduced 1D problem. The two fundamental sources of irreducible error are: (1) the aperture problem — in a textureless or perfectly periodic region, many disparities yield identical or near-identical cost, so the minimum is not unique, and no purely local algorithm can distinguish them without a smoothness prior pulling information in from textured neighbors; and (2) occlusion — pixels visible in only one image have no true correspondence at all, and any cost-minimization there is meaningless by construction, which is exactly what left-right consistency checking is designed to detect and mask out.

Consider a rectified stereo pair with focal length $f = 700$ pixels and baseline $B = 0.12$ m (a typical short-baseline stereo rig). Suppose the matching stage estimates the following integer disparities for four scene points sampled along one scanline, followed by sub-pixel parabolic refinement:

Reading the table: point A has the largest disparity (112 px) and is therefore the closest surface (0.75 m), consistent with the inverse relationship $Z = fB/d$ — small $d$, large $Z$. Point D illustrates the aperture problem directly: the cost is nearly flat across neighboring disparities (6, 6, 6), so the parabola-fit denominator $c_0 - 2c_1 + c_2 \approx 0$, correctly signaling that this pixel's disparity cannot be trusted from local evidence alone. A well-built pipeline flags D as low-confidence (via a peak-sharpness or cost-curvature threshold) rather than reporting a spurious depth, and a global smoothness term (as in SGM) would instead pull D's disparity toward its textured neighbors (B or C), using the piecewise-smoothness prior described above. Note also the nonlinearity: doubling the disparity from point C (9 px) to a hypothetical 18 px would halve the depth, not linearly rescale it — a direct consequence of $Z \propto 1/d$. This is why stereo depth resolution degrades sharply at long range: at $d=9$ a one-pixel disparity error changes depth from 9.41 m to $700 \times 0.12/8 = 10.5$ m, over a meter of error, while at $d=112$ the same one-pixel error changes depth from 0.75 m to $700\times0.12/113=0.744$ m, only 6 mm of error. Longer baselines or higher-resolution sensors are the standard remedies for this range-dependent precision loss.

Stereo depth estimation underlies binocular robot vision systems used for grasping and navigation, and it is the working principle behind automotive stereo camera systems used for obstacle detection alongside or instead of lidar. Consumer depth sensing in smartphone dual/triple-camera systems (portrait-mode background blur, AR occlusion effects) relies on compact stereo or stereo-assisted depth pipelines. Aerial and satellite photogrammetry uses wide-baseline stereo triangulation to build digital elevation models of terrain. Medical and industrial machine-vision systems use calibrated stereo rigs for precise, contact-free 3D measurement. The same rectify-match-triangulate pipeline, generalized to more than two views and unknown camera poses, is exactly the foundation that Structure from Motion builds on to reconstruct entire 3D scenes from unordered photo collections, and understanding two-view stereo cleanly is the standard on-ramp to that larger problem.

Ask the tutor: How does semi-global matching's per-direction dynamic programming actually avoid the streaking artifacts of independent per-row DP?