Computer Vision MT25, Multiple view geometry

Given cameras and correspondences, find a 3D reconstruction of a scene.

The baseline is the line connecting the two origins.

The epipoles are where the baseline intersects with the image plane (equivalently, the projections of the other camera in each view).

When the baseline is parallel to the image planes (the “motion parallel to image plane” case, e.g. a lateral stereo rig), the epipoles are infinitely far away and the epipolar lines are parallel.

• The epipolar plane is the plane formed by $X$, $O$ and $O'$.
• The epipolar lines connect the epipoles to the projections of $X$, or equivalently the intersection of the epipolar plane with the image plane.

Along the epipolar line corresponding to $x$.

Whenever two points $x$ and $x'$ lie on matching epipolar lines $l$ and $l'$, the visual rays corresponding to them meet in space at some point $X$ (although they do not have to be projections of the same 3D point)

• $K[I \mid 0]$
• $K'[R \mid t]$

• $x _ \text{norm} = K^{-1} x _ \text{pixel} \cong [I \mid 0] X$
• $x' _ \text{norm} = {K'}^{-1} x' _ \text{pixel} \cong [R \mid t]X$

Stating their exact relationship:

The direct transformation between $x$ and $x'$ gives

This means that $x'$, $Rx$ and $t$ are linearly dependent, so:

Using the cross product:

Since

we have:

Using the “matrix form” of the cross product:

so defining $[t _ x] R = E$ as the “essential matrix”:

Using the essential matrix:

• $l' \cong Ex$
• $l \cong E^\top x'$

• $Ee = 0$
• $E^\top e' = 0$

• Rank: $2$, so that $E$ is singular ($\det E = 0$)
  • Why? $R$ is a rotation matrix, hence invertible, so $\text{rank}(E) = \text{rank}([t] _ \times)$. The cross-product matrix $[t] _ \times$ sends $v \mapsto t \times v$, so $t \times t = 0$, the vector $t$ lies in its null space. So $[t] _ \times$ has rank at most $2$, and exactly $2$ for any non-zero $t$.
• Degrees of freedom: $5$.
  • Why? $R$ contributes 3 degrees of freedom (a rotation has three parameters), and $t$ contributes 3 degrees of freedom. The epipolar constraint $x'^\top E x = 0$ is invariant to scaling $E$ by any scalar, so $E$ is only defined up to scale, removing 1 degree of freedom.

• We assume that the calibration matrices $K$ and $K'$ of the two cameras are unknown
• This gives $x'^\top F x = 0$ where $F = (K'^{-1})^\top E K^{-1}$

• $l' \cong Fx$
• $l \cong F^\top x'$
• $Fe = 0$
• $F^\top e' = 0$

• Rank: $2$, so $F$ is singular ($\det F = 0$).
  • Why? $K$, $L'$ are upper triangular with non-zero diagonal entries (focal length, pixel scaling factors), so they’re invertible. Multiplying by invertible matrices preserves rank, so $\text{rank}(F) = \text{rank}(E) = 2$.
• Degrees of freedom: $7$.
  • Why? A $3 \times 3$ matrix has $9$ entries. Subtract $1$ for scale (since $x'^\top F x = 0$ is invariant to scaling $F$). Subtract another $1$ for the rank-2 constraint $\det F = 0$. Hence we have rank $9 - 1 - 1 = 7$.
  • Why more than $E$? $F$ absorbs the unknown calibration matrices.

Explicitly, we require for each pair of points $\pmb x, \pmb x'$

which, vectorising $f$ gives

Collecting this into a matrix equation for each of the point correspondences, we have

where

which can be solved via least squares. To enforce the fact $F$ must be rank $2$, we can take the best rank-2 approximation of the found solution using truncated SVD.

The geometric picture: a 3D point $\pmb X$ together with the two camera centres $O, O'$ defines a plane in space, the epipolar plane. The two image points $\pmb x, \pmb x'$ are by construction the projections of $\pmb X$ along the rays from $O$ and $O'$, so they also lie in this plane. Thus all five points $\{\pmb X, O, O', \pmb x, \pmb x'\}$ are coplanar. The epipolar constraint is the algebraic encoding of this single fact.

Encoding into algebra: in camera 2’s frame, the three vectors $\pmb x'$, $R\pmb x$, and $\pmb t$ (all radiating from $O'$, where $\pmb t$ is the position of $O$ in camera 2’s frame) are coplanar iff their scalar triple product vanishes: $\pmb x' \cdot (\pmb t \times R\pmb x) = 0$. Rewriting the cross product as a matrix multiplication (∆cross-product) and absorbing $[\pmb t] _ \times R$ into the essential matrix $E$ gives $\pmb x'^\top E \pmb x = 0$. The fuller algebraic derivation is in ∆essential-matrix-four-derivations.

Why this picture is the foundation of MVG:

• It is the reason matching reduces from a 2D to a 1D search: given $\pmb x$ in the first image, the matching $\pmb x'$ must lie in the epipolar plane, hence in the epipolar plane’s projection into image 2, which is exactly the epipolar line $\ell' = E\pmb x$.
• It is necessary but not sufficient for $\pmb x, \pmb x'$ to be true correspondences (∆bite-epipolar-constraint-necessary-not-sufficient): two arbitrary points on matching epipolar lines also satisfy the constraint without being projections of the same 3D point.
• It is the geometric reason for the rank-2 property of $E$ and $F$ (∆bite-essential-matrix-rank2-justification): every epipolar line passes through the epipole, so $E$ has a non-trivial null space.
• Stereo rectification, triangulation, structure-from-motion, and bundle adjustment all build on this single picture.

If all observed 3D points lie on a single plane $\Pi$, then for every pair of matching image points there is a $3 \times 3$ homography $H$ with $\pmb x' \cong H \pmb x$.

Why: a plane $\Pi$ is itself a 2D space. View 1’s projection restricted to $\Pi$ is a bijection between $\Pi$ and image 1, and similarly for view 2. Composing image-1 $\to \Pi \to$ image-2 gives a 2D-to-2D map that is linear in homogeneous coordinates, hence a homography.

Contrast with the general (non-planar) case: a general scene gives only the epipolar constraint $\pmb x'^\top F \pmb x = 0$, which pins $\pmb x'$ to a line (1 equation per point). The planar case pins $\pmb x'$ to a point $H\pmb x$ (2 equations per point), strictly stronger because the planar assumption removes one DoF.

Practical implications:

• Planar scenes need only 4 correspondences to determine the relationship (∆homography-min-correspondences), versus 8 for $F$ (∆bite-eight-point-minimum-correspondences).
• This is the implicit assumption behind SIFT’s geometric verification (∆sift-planar-assumption).
• A pure-rotation camera (about a fixed centre) is equivalent to viewing the plane at infinity, so panorama stitching is also a homography problem.

The fundamental and essential matrices are the central objects of two-view geometry because they encode the geometric relationship between two views in a single $3 \times 3$ matrix. The slogan: $F$ is “the geometry between two views”, and almost anything you want to do with two views flows from it.

Use 1, matching, reduce a 2D search to 1D. Naive correspondence search between two images is $O(N^2)$ in the number of pixels. The epipolar constraint $\pmb x'^\top F \pmb x = 0$ pins the matching $\pmb x'$ to the line $F\pmb x$ in image 2 (∆epipolar-coplanarity), so matching reduces to a 1D scan along that line. This is what makes stereo matching tractable.

Use 2, calibration-free reconstruction. $F$ can be estimated from 2D-2D correspondences alone (∆eight-point-algorithm-derivation), with no knowledge of intrinsics. This is what enables reconstruction from random internet photos taken on unknown cameras (Photo Tourism, COLMAP).

Use 3, relative camera motion. $E = [\pmb t] _ \times R$, so once $E$ is estimated (8-point on normalised coordinates, or 5-point directly), an SVD decomposition recovers the relative rotation $R$ and translation $\pmb t$ up to a 4-fold ambiguity (resolved by cheirality, i.e. requiring reconstructed points to lie in front of both cameras).

Use 4, inlier filtering for noisy matches. Real correspondences (from SIFT etc.) are noisy. Fitting $F$ via RANSAC gives a geometric model that separates true matches from spurious ones. This is what makes SfM robust in practice.

Without $F$ or $E$: no efficient matching, no relative pose recovery, no triangulation, no SfM. Every pipeline in classical multi-view reconstruction routes through this single $3 \times 3$ object.

The headline: the match for $\pmb x$ must lie on its epipolar line $\ell' = F\pmb x$ (∆matching-point-on-epipolar-line), so $F$ turns 2D matching into a 1D search. This is necessary, not sufficient (∆bite-epipolar-constraint-necessary-not-sufficient): it pins $\pmb x'$ to a line, it does not pick the point on it.

Guided matching (find a new match):

• Compute the epipolar line $\ell' = F\pmb x$ (∆fundamental-matrix-epipolar-lines-and-epipoles).
• Search only along $\ell'$ (a 1D scan, not the whole image), scoring a patch / descriptor around $\pmb x$ against candidates on the line and taking the lowest-cost one.

Verification (filter a candidate pair $(\pmb x, \pmb x')$):

• Accept iff $\pmb x'$ lies close to its epipolar line, $d(\pmb x', F\pmb x) < \tau$ (point-to-line distance, equivalently a normalised $ \vert \pmb x'^\top F \pmb x \vert $).
• This is exactly the RANSAC inlier test that both estimates $F$ and strips out false SIFT matches (∆bite-geometric-verification-ransac).

Dense version (stereo): rectify the pair so epipolar lines become corresponding horizontal scanlines (the motion-parallel-to-image-plane case, ∆bite-epipolar-geometry-three-cases); each pixel’s match is then on the same row, and the offset along it (the disparity) gives depth.

Bootstrap: you need matches to estimate $F$ in the first place (eight-point + RANSAC, ∆eight-point-algorithm-derivation), so the loop is sparse SIFT matches → RANSAC-fit $F$ → use $F$ to verify and to densify by epipolar search.

The eight-point algorithm gives an initial estimate $F _ \text{init}$ from a least-squares fit to $Uf = 0$. Because the constraint $\det F = 0$ is not directly enforced during the least-squares solve, $F _ \text{init}$ is typically full rank — but the true fundamental matrix must be rank 2.

Why rank-2 is required: $F$ has the geometric meaning that $Fx$ is the epipolar line of $x$; all epipolar lines must pass through the epipole $e'$, which means $F^\top e' = 0$, so $F$ must have a non-trivial null space, i.e. rank $< 3$. A full-rank $F _ \text{init}$ would predict epipolar lines that don’t quite converge at the epipole — physically impossible.

The fix: take the SVD of the initial estimate

zero out the smallest singular value,

and reconstruct

This gives the closest rank-2 matrix to $F _ \text{init}$ in Frobenius norm (Eckart-Young theorem), and produces an $F$ whose epipolar lines actually meet at a single epipole.

1. Converging cameras (general case): the baseline lies in front of both image planes, so the epipoles are finite points and may even be visible inside one of the images. Epipolar lines fan out from the visible epipole. Standard case.
2. Motion parallel to the image plane (e.g. a lateral stereo rig with both cameras facing forward): the baseline is parallel to both image planes, so the epipoles are at infinity, and the epipolar lines are parallel horizontal lines in both images. Stereo-rectified images are normalised to this case.
3. Motion perpendicular to the image plane (e.g. a camera moving directly forward): the epipoles coincide with the principal points of both cameras, and epipolar lines radiate outward from the principal point (the focus of expansion). Useful for monocular depth estimation from forward motion.

Necessary: If $\pmb x, \pmb x'$ are projections of the same 3D point $X$, then by construction $X, O, O'$ are coplanar (they define the epipolar plane), which translates algebraically to the epipolar constraint $\pmb x'^\top E \pmb x = 0$. So genuine correspondences always satisfy the constraint.

Not sufficient: The constraint only says $\pmb x'$ lies on the epipolar line $\ell' = E \pmb x$ — a 1D locus in the second image. There are many 3D points whose rays from the second camera all lie in the same epipolar plane and so project to different points on $\ell'$. Picking any of them gives a different $\pmb x'$ that still satisfies the constraint but corresponds to a different 3D point.

Geometrically: the epipolar constraint reduces a 2D search (the whole second image) to a 1D search (the epipolar line), but you still need a matching step (intensity, descriptor, or local cost) to find the actual corresponding point on $\ell'$.

The cross-product matrix $[t] _ \times$ has rank at most 2 for any non-zero $t$: it sends $\pmb v \mapsto t \times \pmb v$, and $t \times t = \pmb 0$, so $t$ is always in its null space — making its kernel at least 1-dimensional. For a 3D vector $t \ne 0$, the kernel is exactly 1-dimensional, so $\mathrm{rank}([t] _ \times) = 2$.

$R$ is a rotation matrix, hence orthogonal and invertible (rank 3). Multiplying $[t] _ \times$ on the right by an invertible matrix doesn’t change the rank:

Equivalently: $E^\top e' = 0$ for the epipole $e'$, so $E^\top$ has a non-trivial null space.