Epipolar Geometry

Consider two pinhole cameras with optical centers $C$ and $C'$, viewing a 3D point $X$. The three points $C$, $C'$, and $X$ define a plane in space, called the epipolar plane $\pi$. This plane intersects image plane $I$ in a line $\ell$ and image plane $I'$ in a line $\ell'$; these are the epipolar lines. Crucially, the image of $X$ in the first camera, $\mathbf{x}$, lies on $\ell$, and its correspondence $\mathbf{x}'$ in the second camera lies on $\ell'$ — for every choice of $X$ along the ray through $\mathbf{x}$. The line joining the two camera centers, called the baseline, pierces each image plane at a special point: the epipole. The epipole $e$ in image $I$ is the projection of the other camera's center $C'$; the epipole $e'$ in image $I'$ is the projection of $C$. As the 3D point $X$ varies, the epipolar plane rotates about the baseline, but every epipolar line in image $I$ still passes through the fixed epipole $e$, and likewise every epipolar line in $I'$ passes through $e'$. This gives a pencil of epipolar lines through each epipole — a one-parameter family indexed by depth of $X$. The algebraic object encoding this entire geometric picture is a $3\times 3$ matrix. When camera intrinsics are known and image coordinates are normalized (rays in camera coordinates), the relevant matrix is the essential matrix $E$, which depends only on the relative rotation $R$ and translation $t$ between the two cameras:

where $[t]_\times$ is the skew-symmetric matrix representing the cross product with $t$. When working directly in pixel coordinates (uncalibrated or unknown intrinsics), the relevant matrix is the fundamental matrix $F$, related to $E$ by the intrinsic calibration matrices $K, K'$ of the two cameras:

Both matrices satisfy the same defining relation for corresponding points $\mathbf{x} \leftrightarrow \mathbf{x}'$ (in homogeneous pixel or normalized coordinates respectively):

This is the epipolar constraint. Geometrically, $F\mathbf{x}$ is the epipolar line $\ell'$ in the second image (a line represented as a homogeneous 3-vector $(a,b,c)$ with equation $au+bv+c=0$); the constraint simply says $\mathbf{x}'$ lies on that line. The epipoles themselves are the left and right null spaces of $F$: $F e = 0$ and $e'^\top F = 0$, since the epipole lies on every epipolar line in its own image.

Estimating $F$ from correspondences: the eight-point algorithm. Given $n \geq 8$ point correspondences $(\mathbf{x}_i, \mathbf{x}_i')$, each satisfies $\mathbf{x}_i'^\top F \mathbf{x}_i = 0$. Writing $\mathbf{x} = (u,v,1)^\top$, $\mathbf{x}' = (u',v',1)^\top$, and $F = (f_{11}, \dots, f_{33})$ stacked as a 9-vector $\mathbf{f}$, this becomes one linear equation per correspondence:

Stacking $n$ such rows gives $A\mathbf{f} = 0$, an $n \times 9$ homogeneous linear system. Since $F$ is only defined up to scale, we solve for the unit vector $\mathbf{f}$ minimizing $\|A\mathbf{f}\|$ subject to $\|\mathbf{f}\| = 1$ — the solution is the right singular vector of $A$ corresponding to its smallest singular value. A raw solution from this linear system will generically have full rank 3, but a valid fundamental matrix must be rank 2 (because it maps points to lines through a fixed epipole — a rank-3 matrix would have no null space, meaning no epipole would exist). We enforce this by taking the SVD $F = U\Sigma V^\top$, zeroing the smallest singular value, and reconstructing $\hat F = U\,\text{diag}(\sigma_1,\sigma_2,0)\,V^\top$. This is the closest rank-2 matrix to $F$ in Frobenius norm (Eckart–Young theorem), so it is the best rank-2 correction consistent with the data. Numerical conditioning is not cosmetic. Raw pixel coordinates (e.g. values around 500–2000) produce columns of $A$ that differ by orders of magnitude (products like $u'u$ versus constants like $1$), making the SVD ill-conditioned. The normalized eight-point algorithm (Hartley) translates and scales points in each image so the centroid is at the origin and the average distance to the origin is $\sqrt2$, solves for $F$ in normalized coordinates, then un-normalizes. This single preprocessing step is often the difference between an unusable and a highly accurate estimate. ``` ALGORITHM: Normalized Eight-Point for Fundamental Matrix INPUT: correspondences {(x_i, x_i')}_{i=1..n}, n >= 8 OUTPUT: fundamental matrix F (3x3, rank 2) 1. Normalize points in each image independently: T = similarity transform: centroid -> origin, mean dist -> sqrt(2) T' = similarity transform for the second image x_hat_i = T x_i x_hat'_i = T' x'_i 2. Build the n x 9 measurement matrix A: for i = 1..n: (u, v) = x_hat_i[0:2] (u',v') = x_hat'_i[0:2] A[i] = [u'u, u'v, u', v'u, v'v, v', u, v, 1] 3. Solve A f = 0 via SVD(A) = U S V^T f = last column of V (smallest singular value) F_hat = reshape(f, 3, 3) 4. Enforce rank-2 constraint: U2, S2, V2^T = SVD(F_hat) S2[2,2] = 0 // zero the smallest singular value F_hat = U2 diag(S2) V2^T 5. Denormalize: F = T'^T F_hat T RETURN F ```

From $F$ or $E$ to camera motion. When intrinsics $K, K'$ are known, we recover $E = K'^\top F K$ and enforce its special structure: $E$ must have singular values $(\sigma,\sigma,0)$ for some $\sigma>0$ (equivalently, project $E$'s singular values to $(1,1,0)$ up to scale). Decompose $E = U\Sigma V^\top$; then, using

the four candidate motions are $(R,t) \in \{(UWV^\top, +u_3), (UWV^\top, -u_3), (UW^\top V^\top, +u_3), (UW^\top V^\top, -u_3)\}$, where $u_3$ is the third column of $U$ (up to overall unknown scale, since monocular two-view geometry cannot recover absolute scale). Exactly one of these four places the triangulated 3D point in front of both cameras — the chirality check — and that combination is the true relative pose.

Using the constraint for matching and verification. In practice, epipolar geometry is used two ways: (1) as a search restriction, matching a feature in image 1 only to features near the corresponding epipolar line in image 2, and (2) as a consensus test inside RANSAC, where hypothesized $F$ or $E$ matrices are scored by how many correspondences satisfy the epipolar constraint within a small tolerance (the Sampson distance or symmetric epipolar distance), rejecting mismatches from feature detectors like SIFT or ORB. ``` ALGORITHM: RANSAC for Fundamental Matrix Estimation INPUT: putative correspondences (from feature matching, contains outliers) OUTPUT: F, inlier set best_inliers = {} for iter in 1..max_iterations: sample = random 8 correspondences (or 7 for minimal solver) F_candidate = EightPoint(sample) inliers = {} for each correspondence (x, x') in all correspondences: d = SampsonDistance(F_candidate, x, x') if d < threshold: inliers.add((x, x')) if |inliers| > |best_inliers|: best_inliers = inliers best_F = F_candidate F_final = EightPoint(best_inliers) // refit on all inliers RETURN F_final, best_inliers ```

Time and space complexity. Building the $n\times 9$ matrix $A$ takes $O(n)$ time and space. The dominant cost is the SVD of $A$ (or equivalently the eigendecomposition of $A^\top A$, a $9\times 9$ matrix), which costs $O(n \cdot 9^2) = O(n)$ for forming $A^\top A$ plus a constant-time (since the matrix is fixed size $9\times9$) eigendecomposition — overall $O(n)$ for fixed small constant dimension. The rank-2 projection SVD is on a fixed $3\times3$ matrix, $O(1)$. So the raw eight-point algorithm is $O(n)$, linear in the number of correspondences — essentially the cost of one pass over the data. Under RANSAC, if the inlier ratio is $w$ and the minimal sample size is $s$ (7 or 8), the expected number of iterations to find at least one all-inlier sample with confidence $p$ is

and each iteration costs $O(s) + O(n)$ (fit + score all points), giving total RANSAC time $O(kn)$. Since $s$ is small (7–8), $w^s$ shrinks fast as outlier rate grows, which is exactly why the seven-point or eight-point minimal solvers (rather than fitting with many points per iteration) are preferred inside RANSAC — smaller $s$ means dramatically fewer iterations needed for the same confidence.

Correctness of the epipolar constraint. The relation $\mathbf{x}'^\top F \mathbf{x} = 0$ follows directly from the coplanarity of $C, C', X$. In calibrated (normalized) coordinates, $\hat{\mathbf{x}} = R^\top(\hat{\mathbf{x}}' \text{ direction related by baseline})$; more directly, the vectors $\hat{\mathbf x}$ (ray to $X$ from camera 1, in camera 1 coordinates), $t$ (baseline, camera 2 relative to camera 1), and $R\hat{\mathbf x}'$ (ray to $X$ from camera 2, rotated into camera 1's frame) are coplanar because they all lie in the epipolar plane through the two centers and $X$. Coplanarity of three vectors is exactly the vanishing scalar triple product:

which (transposing and relabeling) is the stated constraint with $E = [t]_\times R$. Since $F = K'^{-\top}EK^{-1}$ simply changes coordinates from normalized rays to pixels, the same relation holds for $F$ in pixel coordinates.

Why rank 2 is necessary and sufficient for validity. $F$ has rank 2 because $[t]_\times$ has rank 2 (it is skew-symmetric with $t$ in its null space) and $R$, $K$, $K'$ are full rank; multiplying by full-rank matrices preserves rank. Rank 2 is also sufficient in the sense that any rank-2 matrix (up to scale) is a valid fundamental matrix for some pair of cameras — this is why the SVD-based rank-2 projection step is not an approximation hack but a necessary correctness-restoring projection onto the actual solution manifold, and it is the closest such matrix in Frobenius norm by the Eckart–Young theorem.

Degrees of freedom. $F$ is a $3\times3$ matrix (9 parameters), defined up to overall scale (−1) and constrained to $\det F = 0$ (rank ≤ 2, another −1 constraint), giving $9 - 1 - 1 = 7$ degrees of freedom — hence the existence of a minimal 7-point algorithm (which yields up to 3 real solutions from a cubic constraint). $E$ has the same scale ambiguity but the additional structural constraint of two equal singular values, giving $5$ degrees of freedom (3 for rotation, 2 for translation direction, since overall scale of $t$ is unrecoverable), consistent with the standard parameterization of relative pose up to scale.

Tradeoffs. The eight-point algorithm is linear and thus fast and globally optimal for the algebraic error it minimizes, but algebraic error is not geometrically meaningful — it does not minimize reprojection error. Nonlinear refinement (minimizing Sampson distance or true reprojection error via bundle adjustment style optimization) is typically applied afterward for accuracy. The 7-point minimal solver is more efficient inside RANSAC (fewer samples needed) but requires solving a cubic and disambiguating up to three solutions, adding implementation complexity.

Consider two synthetic calibrated cameras with identity intrinsics, camera 1 at the origin looking down $+z$, and camera 2 translated by $t = (1, 0, 0)^\top$ (baseline along $x$) with no rotation ($R = I$). Then

Take a 3D point $X = (0.5, 0.2, 4)^\top$ in camera 1's frame. Its normalized image coordinate in camera 1 is $\hat{\mathbf x} = (0.125, 0.05, 1)^\top$. In camera 2's frame, $X' = X - t = (-0.5, 0.2, 4)^\top$, giving $\hat{\mathbf x}' = (-0.125, 0.05, 1)^\top$. Check the epipolar constraint:

First compute $E\hat{\mathbf x} = (0,\ -1,\ 0.05)^\top$. Then $\hat{\mathbf x}'^\top(0,-1,0.05)^\top = (-0.125)(0) + (0.05)(-1) + (1)(0.05) = -0.05 + 0.05 = 0$. ✓ The constraint holds exactly, as expected for noise-free correspondences. Now trace what the epipolar line looks like. $\ell' = E\hat{\mathbf x} = (0, -1, 0.05)^\top$, meaning the line equation in image 2 is $0\cdot u' - 1\cdot v' + 0.05 = 0$, i.e. $v' = 0.05$ — a horizontal line, matching intuition: since the baseline is purely horizontal ($t=(1,0,0)$) with no rotation, epipolar lines are horizontal, and stereo correspondence search reduces to a 1D scan along constant $v'$ (this is exactly the "rectified stereo" scenario used in Stereo Vision and Depth). The epipole $e'$ in image 2 is the projection of camera 1's center $C=(0,0,0)$ into camera 2, i.e. it lies at infinity in the direction of $t$ — here $t=(1,0,0)$ is parallel to the image plane, so $e'$ is a point at infinity along the horizontal direction $(1,0,0)^\top$ in homogeneous coordinates, consistent with all epipolar lines being horizontal (a pencil of parallel lines is a pencil through a point at infinity).

Now consider estimating $F$ from 8 noisy correspondences via the eight-point algorithm without normalization: pixel coordinates around $(800, 450)$ produce entries like $u'u \approx 640{,}000$ next to constant entries of $1$ in the same row of $A$. The condition number of $A^\top A$ becomes enormous, and the smallest singular vector — meant to capture a subtle geometric signal — gets dominated by numerical noise in the large-magnitude columns. Normalizing coordinates first (centroid at origin, average distance $\sqrt2$) rescales all columns of $A$ to comparable magnitude, typically improving the estimate's reprojection accuracy by an order of magnitude in practice, which is why every serious implementation includes this step.

The mathematical treatment of two-view geometry traces back to 19th-century projective geometry, but its modern computer vision formulation crystallized in the late 20th century as multi-view reconstruction became computationally tractable.

Epipolar geometry is the algebraic backbone of every classical multi-view 3D vision system. In stereo depth estimation, cameras are calibrated and rectified so epipolar lines become horizontal scanlines, reducing correspondence search from 2D to 1D and enabling real-time dense disparity computation used in robotics and autonomous vehicle perception stacks. In structure from motion (SfM) pipelines like COLMAP, Bundler, and VisualSFM, pairwise fundamental or essential matrix estimation (with RANSAC) is the first geometric verification step before triangulating sparse 3D points and running bundle adjustment. In visual SLAM systems (ORB-SLAM and successors), essential matrix estimation initializes monocular pose tracking from the first two keyframes. In augmented reality and photogrammetry, epipolar constraints filter feature matches before mesh reconstruction. Even modern learned correspondence and pose networks are frequently trained or evaluated against ground-truth epipolar geometry, and many hybrid systems still use classical $F$/$E$-matrix estimation as a robust geometric verification layer around learned feature matches.

Ask the tutor: Can you walk through deriving the seven-point algorithm's cubic constraint step by step?