Stereo depth
How it works
1) Calibration and rectification: the cameras' intrinsic and relative parameters are estimated and the images are warped so epipolar lines are horizontal (matches lie on the same rows). 2) Matching (correspondence): for each pixel a match is sought along the row in the other image by minimising a matching cost (e.g. SAD/SSD over a window, Census, or learned CNN features). 3) Disparity map: the positional difference of matched pixels forms a dense disparity map; cost aggregation (e.g. Semi-Global Matching) smooths it. 4) Triangulation: disparity is converted to depth via Z = f·B/d and then to a 3D point cloud. 5) Optional post-processing: filtering, hole filling and left-right consistency checks.
Problem solved
Lets a system measure distance and reconstruct a scene in 3D from 2D images using ordinary cameras, without an active emitter (as in ToF or structured-light scanners), so it works in bright sunlight and at longer ranges limited only by baseline and resolution.
Components
Estimating camera parameters and warping the images so corresponding points lie on the same rows (horizontal epipolar lines).
Finding, for each pixel, its match in the other image by minimising a matching cost (SAD/SSD/Census or CNN features).
A dense map of horizontal shifts between matched pixels; often smoothed by cost aggregation (e.g. SGM).
Converting disparity to depth (Z = f·B/d) and to a 3D point cloud using baseline and focal length.
Implementation
Uniform surfaces (plain walls, sky) give no unambiguous matches, producing holes and wrong disparity.
Points visible in only one camera have no match, causing errors at object boundaries.
Repeating textures (grids, fences) lead to ambiguous matches.
Inaccurate calibration breaks the horizontal-epipolar-line assumption and corrupts matching and depth scale.
Evolution
Standardised the stages of stereo matching and the Middlebury benchmark.
Practical, accurate and fast cost aggregation, widely used in real time.
First use of a learned matching cost, starting deep-learning stereo.
A complete end-to-end learned stereo pipeline with a 3D cost volume.
Recurrent multilevel disparity refinement with high accuracy.
Hyperparameters (configurable axes)
Distance between cameras; a larger baseline improves accuracy at range but raises the minimum range and occlusion areas.
Focal length in pixels; together with baseline scales the disparity-to-depth conversion.
Number of disparity levels searched; sets the nearest measurable distance and the compute cost.
Comparison window size in local methods; a larger window is more robust to noise but blurs edges.
Computational complexity
Time complexity: O(W·H·D).
Execution paradigm
Disparity is computed densely for every image pixel.
Parallelism
Cost-volume computation and per-pixel matching are highly parallel; the path aggregation in SGM introduces sequential dependencies along paths.
Hardware requirements
Learned stereo methods (e.g. PSMNet, RAFT-Stereo) benefit from GPU acceleration for convolutions and the cost volume.
Classical SGM/block matching is implemented on FPGA/ASIC and vision processors (e.g. inside depth cameras) for low-power real-time stereo.
Local block matching (e.g. OpenCV StereoBM) runs on an ordinary CPU.