Chapter 3: Epipolar Geometry & Stereo Vision

The linear system $A f = 0$ mixes entries of very different size: products of pixel coordinates near $10^5$, single coordinates near $10^2$, and a constant 1. Small noise in the large entries then swamps the information in the small ones, and the null vector found by SVD is badly perturbed. Hartley normalization moves the centroid to the origin and scales the mean distance to $\sqrt{2}$, so every entry is of order 1. In a simulation with 20 matches, the ratio of the largest to the eighth singular value fell from about $3 \times 10^5$ to about 27, and with 0.5 pixel noise the median epipolar error fell tenfold, from 3.5 to 0.35 pixels. The normalizing transforms are undone at the end with $F = T_2^T \hat{F} T_1$.

The raw $F$ from the 8-point algorithm is generally rank 3. To enforce rank 2, compute the SVD $F = U \Sigma V^T$ and set the smallest singular value to zero: $F' = U \text{diag}(\sigma_1, \sigma_2, 0) V^T$. This is the closest rank-2 matrix to $F$ in the Frobenius norm. Without this correction, the epipolar lines from $F$ do not converge to a single epipole (they form a general pencil instead of passing through a common point), which breaks stereo rectification and triangulation algorithms.

Key properties: (1) $F$ has 7 degrees of freedom and rank 2; (2) $F e_1 = 0$ and $F^T e_2 = 0$, so the epipoles are its null vectors; (3) $l_2 = F x_1$ gives the epipolar line in image 2 and $l_1 = F^T x_2$ the line in image 1; (4) $F$ is defined up to scale. For two cameras with identical intrinsics related by a pure translation, $F = K^{-T}[t]_\times K^{-1}$ is skew-symmetric, $F = -F^T$; with different intrinsics it is not. Seven degrees of freedom means seven matches suffice: the 7-point algorithm solves a cubic in one unknown and returns one or three real solutions.

The essential matrix $E$ and fundamental matrix $F$ are related by $E = K_2^T F K_1$, where $K_1, K_2$ are the camera intrinsics. While $F$ operates on pixel coordinates, $E$ operates on normalized image coordinates $\hat{\mathbf{x}} = K^{-1} \mathbf{x}$: $\hat{\mathbf{x}}_2^T E \hat{\mathbf{x}}_1 = 0$. $E$ has only 5 DOF (3 rotation + 2 translation direction, since translation scale is unrecoverable from images alone). The singular values of $E$ satisfy $\sigma_1 = \sigma_2$ and $\sigma_3 = 0$, a stronger constraint than $F$'s mere rank deficiency.

Given $E = U \Sigma V^T$, the rotation and translation are recovered as $R = U W^{(\pm)} V^T$ and $\mathbf{t} = \pm u_3$ (third column of $U$), where $W = \begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$. This yields 4 candidate solutions $(R, \mathbf{t})$. The correct one is selected by the cheirality constraint: triangulated points must have positive depth in both cameras ($Z_1 > 0$ and $Z_2 > 0$). Exactly one of the four solutions satisfies this for all visible points.

The 5-point algorithm exploits the additional constraints of $E$ (the essential matrix constraint $2EE^TE - \text{tr}(EE^T)E = 0$) to solve from the minimum number of correspondences. The algorithm uses Grobner bases to solve a system of 10 polynomial equations in 3 unknowns, yielding up to 10 solutions. Combined with RANSAC, it is the standard method for relative pose estimation from calibrated cameras: sample 5 points, compute $E$ candidates, select by most inliers. The 5-point algorithm is more robust than the 8-point because it uses fewer points (reducing the chance of including outliers in a RANSAC sample).

Without rectification, the epipolar line for a point at pixel $(u_1, v_1)$ in image 1 is an arbitrary line $l_2 = F[u_1, v_1, 1]^T$ in image 2 with slope $-l_2[0]/l_2[1]$. Searching along an arbitrary line is algorithmically complex and prevents the use of efficient scanline-based matching. Rectification applies homographies $H_1, H_2$ so that $F' = [e_2']_\times$ and epipolar lines become horizontal rows. After rectification, matching point $(u_1, v)$ in image 1 only requires scanning row $v$ in image 2 from $u_1 - d_{\max}$ to $u_1$.

Bouguet's method writes the relative rotation as a rotation vector $r$ and gives each camera half of it: camera 1 is turned by $-r/2$ and camera 2 by $+r/2$, which makes the two optical axes parallel while warping each image as little as possible. A second rotation $R_{\text{rect}}$, shared by both cameras, then turns the rotated baseline onto the image $x$-axis, so epipoles go to infinity and rows align. The final rectifying rotations are $R_{\text{rect}}$ composed with the half rotations. How evenly the warp is shared depends on the baseline as well as the rotation: when the baseline is not perpendicular to the mean viewing direction, $R_{\text{rect}}$ adds extra rotation, and one camera may turn much more than the other.

Rectification quality is measured by the $y$-disparity: the vertical difference $|v_1 - v_2|$ between matched points after rectification. Perfect rectification gives $y$-disparity $= 0$ everywhere. In practice, mean $y$-disparity $< 0.1$ pixels is excellent, $< 0.5$ is acceptable, and $> 1.0$ indicates a calibration or rectification error. The $y$-disparity can also reveal systematic problems: a non-zero slope across the image suggests residual rotation error, while a quadratic pattern suggests uncorrected lens distortion.

Block matching compares a $w \times w$ window in the left image with windows at each disparity $d \in [0, d_{\max})$ along the same row of the right image, using SAD, SSD or NCC, and keeps $d^* = \arg\min_d C(d)$. Done directly, that costs $O(W H d_{\max} w^2)$, but per-disparity window sums can be built with a running box filter, cutting the cost to $O(W H d_{\max})$, independent of $w$. OpenCV's StereoBM ran 128 disparities on a 640 by 480 pair in about 14 ms on one CPU thread for window sizes from 5 to 21. The window size therefore trades noise robustness against edge sharpness, not speed.

Along each path direction $r$, SGM computes $L_r(p, d) = C(p, d) + \min\big(L_r(p - r, d),\, L_r(p - r, d \pm 1) + P_1,\, \min_i L_r(p - r, i) + P_2\big) - \min_k L_r(p - r, k)$, where the last term only keeps values bounded. The small penalty $P_1$ allows slanted surfaces and the large $P_2$ allows true depth jumps. Summing $L_r$ over paths approximates a 2D smoothness prior that is NP-hard to optimise exactly. The cost per path is $O(W H d_{\max})$. On the same 640 by 480 pair, OpenCV's StereoSGBM took 53 ms in its default 5-path mode, 3.6 times StereoBM, and 127 ms in full 8-path mode.

A cost volume has $W \times H \times D$ entries. At 1280 by 720 with 192 disparities and 4 bytes each, that is 708 MB (675 MiB), which is why GPU stereo networks build their cost volumes at reduced resolution. The parabola through three costs has its minimum at $d_{\text{sub}} = d^* + \frac{C(d^*-1) - C(d^*+1)}{2(C(d^*-1) - 2C(d^*) + C(d^*+1))}$. The fit is biased toward whole pixels, an effect called pixel locking: with SAD costs on a smooth 1D signal, a true offset of 0.3 pixels was estimated as 0.19, and 0.1 as 0.05. Only offsets of 0 and 0.5 came out exact.

For a rectified stereo pair with baseline $b$ and focal length $f$, depth is $Z = fb/d$ where $d = u_L - u_R$ is the disparity (horizontal pixel offset between left and right projections). This inverse relationship means depth precision degrades quadratically with distance: $\Delta Z = Z^2 \Delta d / (fb)$. For $f = 700$ px, $b = 0.12$ m, and $\Delta d = 0.5$ px: at $Z = 5$ m, $\Delta Z = 0.15$ m; at $Z = 10$ m, $\Delta Z = 0.60$ m; at $Z = 50$ m, $\Delta Z = 14.9$ m. This is why stereo depth is most useful at short to medium ranges.

The minimum and maximum measurable depths are determined by the baseline and disparity range. With max disparity $d_{\max}$: $Z_{\min} = fb/d_{\max}$. With min detectable disparity $d_{\min} \approx 1$ px: $Z_{\max} = fb/d_{\min} = fb$. For $f = 700$, $b = 0.12$, $d_{\max} = 128$: $Z_{\min} = 0.66$ m, $Z_{\max} = 84$ m. Increasing the baseline increases $Z_{\max}$ linearly but also increases $Z_{\min}$. This is the fundamental baseline-range trade-off: a wider baseline resolves distant objects but creates a larger near-field blind zone.

The left-right consistency check computes disparity maps from both images and keeps a left pixel only if $\text{abs}(d_L(u) - d_R(u - d_L(u))) \le 1$. Occluded pixels, which are visible in only one view, fail it, and so do most outright mismatches. It can also reject correct pixels on thin structures, where the two maps disagree slightly. Speckle filtering then removes small connected blobs whose disparity differs from their surroundings, OpenCV's filterSpeckles. A median filter (3 by 3 or 5 by 5) removes isolated spikes. Edge-aware filters, such as weighted median or the weighted-least-squares filter, fill and smooth while keeping depth edges aligned with image edges.

The standard OpenCV stereo pipeline: (1) calibrate each camera (K, distortion), (2) stereo calibrate (R, t between cameras), (3) compute rectification maps (stereoRectify), (4) remap images (remap), (5) compute disparity (StereoBM or StereoSGBM), (6) reproject to 3D (reprojectImageTo3D using the $Q$ matrix). The $Q$ matrix maps $(u, v, d)$ to $(X, Y, Z)$: $[X,Y,Z,W]^T = Q [u,v,d,1]^T$, then divide by $W$. This is a complete, well-tested pipeline that works reliably for baselines up to $\sim 1$ meter.

Learned stereo still uses the classical structure: features, a cost volume or correlation, aggregation and a disparity readout. The learned parts make the costs and the smoothing context-aware. RAFT-Stereo correlates features at all disparities once and then runs recurrent updates that look up only a local window around the current estimate, so the cost per iteration is small and more iterations trade time for accuracy. On KITTI 2015 it reports D1-all 1.96 percent, against 10.86 for OpenCV SGBM. On Middlebury it beat the next-best method's 1-pixel error by 29 percent at publication. A real-time configuration reached 26 FPS at 1248 by 384, with a zero-shot (synthetic-trained) D1 of 5.91 percent.

Every stereo matcher assumes that a surface patch looks the same from both cameras and that it has enough texture to be found. Textureless regions give a nearly flat cost curve with no clear minimum. Repetitive texture gives several equal minima, one per period of the pattern. Specular and transparent surfaces break the same-appearance assumption, because the reflection moves with the viewpoint. Occlusions have no partner at all. Range limits add two more failures: objects closer than $fb / d_{\max}$ fall outside the search range, and far objects have disparities so small that a fraction of a pixel of error becomes metres. Active illumination, ToF or LiDAR fusion, and learned priors each address a different subset.