15  Epipolar Geometry

Epipolar geometry is the mathematical language of two-view computer vision. It describes the projective constraints that must hold when two image points are projections of the same 3D point. This chapter develops the fundamental matrix, the essential matrix, epipolar lines, the eight-point algorithm, robust estimation, and uncertainty in a clean way for MA Applied Mathematics and MS Statistics students.

15.1 Learning goals

After reading this chapter, students should be able to:

  1. explain why a point in one image determines a line, not a point, in a second image;
  2. define epipoles, epipolar planes, and epipolar lines geometrically;
  3. derive the epipolar constraint \[ x_2^T F x_1=0; \]
  4. distinguish the fundamental matrix \(F\) from the essential matrix \(E\);
  5. derive \[ E=[t]_\times R \] for calibrated cameras;
  6. estimate \(F\) using the normalized eight-point algorithm;
  7. explain the rank-two constraint and why it matters;
  8. compute algebraic, geometric, and Sampson-style residuals;
  9. use RANSAC-style robust estimation for outlier-contaminated matches;
  10. connect two-view geometry to stereo vision, structure from motion, visual SLAM, and modern AI systems.

15.2 14.1 Why two-view geometry is different from one-view geometry

In Chapter 12, a calibrated or uncalibrated camera was modeled as a projective map

\[ x \sim P X, \]

where \(X\in \mathbb{P}^3\) is a 3D homogeneous point and \(x\in \mathbb{P}^2\) is an image point. A single image point \(x\) does not determine a unique 3D point. It determines a back-projection ray through the camera center.

Now suppose the same 3D point is observed by two cameras:

\[ x_1 \sim P_1 X, \qquad x_2 \sim P_2 X. \]

The pair \((x_1,x_2)\) is not arbitrary. Once \(x_1\) is fixed, the 3D point \(X\) must lie somewhere on the ray through the first camera center and \(x_1\). Project that entire ray into the second image. A 3D line generally projects to a 2D line. Therefore, the corresponding point \(x_2\) must lie on a particular line in the second image.

That line is called the epipolar line corresponding to \(x_1\).

The basic two-view idea is: one image point determines a 3D ray; the second image sees that ray as an epipolar line.

The fundamental matrix is the matrix representation of this geometric rule.

Interactive 14.1. Epipolar line from a point. A selected point in image 1 determines a line in image 2. In the ideal noise-free model, its true match must lie on that line.

15.3 14.2 Geometry of two camera centers

Let \(C_1\) and \(C_2\) be the two camera centers. Let \(X\) be a 3D point visible in both cameras. The three points

\[ C_1, \quad C_2, \quad X \]

define a plane in 3D, assuming they are not collinear in a degenerate way. This plane is called the epipolar plane associated with \(X\).

The epipolar plane intersects the first image plane in a line \(\ell_1\) and the second image plane in a line \(\ell_2\). These are the corresponding epipolar lines.

The line through the two camera centers is called the baseline. The images of the opposite camera centers are called epipoles:

\[ e_1 \sim P_1 C_2, \qquad e_2 \sim P_2 C_1. \]

Every epipolar line in image 1 passes through \(e_1\), and every epipolar line in image 2 passes through \(e_2\).

Epipolar geometry in one sentence. The epipolar geometry of two cameras is the projective incidence structure induced by the baseline, the two camera centers, and the family of epipolar planes.

15.4 14.3 Points and lines in the projective plane

A homogeneous image point is represented as

\[ x=\begin{pmatrix}u\\v\\1\end{pmatrix} \in \mathbb{P}^2. \]

A homogeneous image line is represented as

\[ \ell=\begin{pmatrix}a\\b\\c\end{pmatrix}, \]

and the point \(x\) lies on the line \(\ell\) precisely when

\[ \ell^T x=0. \]

In Cartesian coordinates, this is

\[ au+bv+c=0. \]

Because lines and points are homogeneous, scaling does not change the geometric object:

\[ x \sim \lambda x, \qquad \ell \sim \mu \ell, \qquad \lambda,\mu \ne 0. \]

The cross product gives the algebraic relation between points and lines:

  • the line through two points \(x\) and \(y\) is \[ \ell=x\times y; \]
  • the intersection of two lines \(\ell\) and \(m\) is \[ x=\ell \times m. \]

This point-line duality makes epipolar geometry especially clean.

15.5 14.4 The fundamental matrix

The epipolar correspondence rule can be written as a linear map from points in one image to lines in the other image:

\[ \ell_2 = F x_1. \]

Here

\[ F\in \mathbb{R}^{3\times 3} \]

is the fundamental matrix. Since \(x_2\) must lie on its corresponding epipolar line \(\ell_2\), we obtain

\[ x_2^T \ell_2=0. \]

Substituting \(\ell_2=F x_1\) gives the central equation of this chapter:

\[ x_2^T F x_1=0. \]

This is called the epipolar constraint.

The same matrix also maps a point in image 2 to a line in image 1:

\[ \ell_1=F^T x_2. \]

Therefore \(F\) represents both directions of epipolar incidence.

Important interpretation. The fundamental matrix does not map a point to its matching point. It maps a point to the line on which its matching point must lie.

15.6 14.5 Degrees of freedom and rank

A general \(3\times 3\) matrix has \(9\) entries. Since \(F\) is homogeneous, multiplying it by a nonzero scalar gives the same epipolar constraint:

\[ F \sim \lambda F. \]

This removes one degree of freedom, leaving \(8\) projective degrees of freedom.

But a valid fundamental matrix must also satisfy

\[ \det(F)=0. \]

Equivalently,

\[ \operatorname{rank}(F)=2. \]

This removes one additional degree of freedom. Thus a fundamental matrix has \(7\) degrees of freedom.

Why rank two? The epipole \(e_2\) lies on every epipolar line in image 2. Since every line has the form \(F x_1\), we must have

\[ e_2^T F x_1 = 0 \quad \text{for all } x_1. \]

Hence

\[ e_2^T F=0. \]

So \(F\) has a nontrivial left null vector. Similarly,

\[ F e_1=0. \]

Thus \(F\) is singular.

The epipoles are null vectors of the fundamental matrix: \(F e_1=0\) and \(F^T e_2=0\).

Interactive 14.2. Rank-two geometry. A valid fundamental matrix has a right null vector \(e_1\) and a left null vector \(e_2\). The plot visualizes epipolar lines that all pass through a common epipole.

15.7 14.6 Deriving the essential matrix for calibrated cameras

The fundamental matrix applies to pixel coordinates and uncalibrated cameras. When camera intrinsics are known, we can use normalized camera coordinates.

Let

\[ \hat x_1=K_1^{-1}x_1, \qquad \hat x_2=K_2^{-1}x_2. \]

Assume the first camera coordinate system is the world coordinate system. Then a 3D point has first-camera coordinates \(X\). In the second camera, the same point has coordinates

\[ X_2=R X+t, \]

where \(R\in SO(3)\) and \(t\in \mathbb{R}^3\) are the relative rotation and translation from camera 1 to camera 2.

The normalized image points satisfy

\[ \hat x_1 \sim X, \qquad \hat x_2 \sim RX+t. \]

The vectors \(\hat x_2\), \(t\), and \(R\hat x_1\) lie in the same epipolar plane. Therefore their scalar triple product is zero:

\[ \hat x_2^T(t\times R\hat x_1)=0. \]

Define the skew-symmetric matrix \([t]_\times\) by

\[ [t]_\times= \begin{pmatrix} 0 & -t_3 & t_2\\ t_3 & 0 & -t_1\\ -t_2 & t_1 & 0 \end{pmatrix}, \]

so that

\[ [t]_\times a=t\times a. \]

Then

\[ \hat x_2^T [t]_\times R \hat x_1=0. \]

The matrix

\[ E=[t]_\times R \]

is the essential matrix.

Thus calibrated epipolar geometry is

\[ \hat x_2^T E \hat x_1=0. \]

15.8 14.7 Relating \(F\) and \(E\)

Since

\[ \hat x_1=K_1^{-1}x_1, \qquad \hat x_2=K_2^{-1}x_2, \]

the essential constraint becomes

\[ (K_2^{-1}x_2)^T E (K_1^{-1}x_1)=0. \]

Equivalently,

\[ x_2^T K_2^{-T} E K_1^{-1} x_1=0. \]

Therefore

\[ F=K_2^{-T} E K_1^{-1}. \]

Conversely,

\[ E=K_2^T F K_1. \]

Fundamental versus essential matrix.

  • \(F\) acts on pixel coordinates and depends on intrinsics and relative pose.
  • \(E\) acts on normalized camera coordinates and depends only on relative pose.
  • \(F\) is projective two-view geometry.
  • \(E\) is calibrated metric two-view geometry.

15.9 14.8 Algebraic form of the epipolar equation

Let

\[ x_1=(u_1,v_1,1)^T, \qquad x_2=(u_2,v_2,1)^T. \]

Write

\[ F= \begin{pmatrix} f_{11} & f_{12} & f_{13}\\ f_{21} & f_{22} & f_{23}\\ f_{31} & f_{32} & f_{33} \end{pmatrix}. \]

Then \(x_2^T F x_1=0\) expands to

\[ u_2u_1f_{11}+u_2v_1f_{12}+u_2f_{13} +v_2u_1f_{21}+v_2v_1f_{22}+v_2f_{23} +u_1f_{31}+v_1f_{32}+f_{33}=0. \]

This equation is linear in the unknown entries of \(F\). Define

\[ f=(f_{11},f_{12},f_{13},f_{21},f_{22},f_{23},f_{31},f_{32},f_{33})^T. \]

Each correspondence gives one linear equation

\[ a_i^T f=0, \]

where

\[ a_i=(u_2u_1,u_2v_1,u_2,v_2u_1,v_2v_1,v_2,u_1,v_1,1)^T. \]

Stacking \(n\) correspondences gives

\[ Af=0, \qquad A\in \mathbb{R}^{n\times 9}. \]

In exact noise-free data, one can solve this homogeneous linear system. In noisy data, one finds a unit vector \(f\) minimizing

\[ \|Af\|^2 \quad \text{subject to} \quad \|f\|=1. \]

The solution is the right singular vector of \(A\) associated with the smallest singular value.

Interactive 14.3. Eight-point linear system. Each correspondence contributes one row to a homogeneous linear system. Normalization improves conditioning before the SVD solve.

15.10 14.9 The normalized eight-point algorithm

The classical eight-point algorithm estimates \(F\) from at least eight correspondences. In practice, it should be used with coordinate normalization.

Given correspondences

\[ \{(x_{1i},x_{2i})\}_{i=1}^n, \qquad n\ge 8, \]

the normalized eight-point algorithm is:

  1. Normalize points in each image using similarity transforms \(T_1\) and \(T_2\) so that points have centroid near zero and average distance around \(\sqrt{2}\).
  2. Build the design matrix \(A\) from normalized correspondences.
  3. Solve \(Af=0\) by SVD and reshape \(f\) into a matrix \(\tilde F\).
  4. Enforce rank two by projecting \(\tilde F\) onto the set of rank-two matrices.
  5. Denormalize: \[ F=T_2^T \tilde F T_1. \]
  6. Optionally rescale \(F\) so that \(\|F\|_F=1\) or \(F_{33}=1\) if numerically safe.

The normalization step is not cosmetic. Pixel coordinates may be hundreds or thousands in magnitude. Without normalization, the columns of \(A\) can have very different scales, making the SVD unstable.

15.10.1 Rank-two projection

Let the SVD of the unconstrained estimate be

\[ \tilde F=U\operatorname{diag}(\sigma_1,\sigma_2,\sigma_3)V^T, \qquad \sigma_1\ge \sigma_2\ge \sigma_3\ge 0. \]

The nearest rank-two matrix in Frobenius norm is

\[ \tilde F_2=U\operatorname{diag}(\sigma_1,\sigma_2,0)V^T. \]

This is an application of the Eckart–Young theorem.

The eight-point algorithm is linear algebra plus geometry: solve a homogeneous least-squares problem, then project the result onto the rank-two variety.

15.11 14.10 Seven-point algorithm and minimal solvers

Because a fundamental matrix has \(7\) degrees of freedom, seven point correspondences are enough in a generic noise-free setting. With seven correspondences, the matrix \(A\) has a two-dimensional nullspace:

\[ F(\alpha)=\alpha F_1+(1-\alpha)F_2. \]

The rank constraint requires

\[ \det(F(\alpha))=0. \]

This is a cubic equation in \(\alpha\), so it can have up to three real solutions.

The seven-point algorithm is useful inside robust estimation methods such as RANSAC because it uses a minimal sample. The eight-point algorithm is simpler and often better as a final least-squares estimate after inliers have been identified.

Statistical tradeoff. Minimal solvers use fewer points and are efficient for hypothesis generation. Overdetermined solvers use more points and are better for stable final estimation.

15.12 14.11 Essential matrix constraints

The fundamental matrix only satisfies rank two. The essential matrix has stronger constraints. If

\[ E=[t]_\times R, \]

then \(E\) has singular values

\[ \sigma,\sigma,0. \]

Thus an estimated essential matrix should have two equal nonzero singular values and one zero singular value.

Given an unconstrained estimate

\[ \tilde E=U\operatorname{diag}(\sigma_1,\sigma_2,\sigma_3)V^T, \]

a common projection is

\[ E=U\operatorname{diag}(s,s,0)V^T, \qquad s=\frac{\sigma_1+\sigma_2}{2}. \]

This projection enforces the calibrated two-view geometry.

15.13 14.12 Recovering relative pose from the essential matrix

The essential matrix encodes the relative rotation \(R\) and the translation direction \(t\), but not the absolute translation scale. This scale ambiguity is unavoidable from two images alone.

Given

\[ E=U\operatorname{diag}(s,s,0)V^T, \]

define

\[ W=\begin{pmatrix} 0 & -1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}. \]

Then candidate rotations are

\[ R_1=UWV^T, \qquad R_2=UW^T V^T. \]

The translation direction is determined by the third column of \(U\):

\[ t \sim u_3. \]

There are four candidate relative poses:

\[ (R_1,t),\quad (R_1,-t),\quad (R_2,t),\quad (R_2,-t). \]

The physically valid solution is chosen by the cheirality condition: reconstructed points should lie in front of both cameras.

Interactive 14.4. Essential matrix and pose ambiguity. The essential matrix determines relative pose only up to four candidates and an unknown translation scale. Cheirality selects the physically valid configuration.

15.14 14.13 Distance from a point to an epipolar line

The algebraic residual for one correspondence is

\[ r_i=x_{2i}^T F x_{1i}. \]

This residual is easy to compute but depends on the arbitrary scale of \(F\) and on coordinate units. A more geometric residual uses the distance from \(x_{2i}\) to the epipolar line

\[ \ell_{2i}=F x_{1i}. \]

If

\[ \ell_{2i}=(a_i,b_i,c_i)^T, \]

then the Euclidean distance from \(x_{2i}=(u_{2i},v_{2i},1)^T\) to the line is

\[ d(x_{2i},\ell_{2i})= \frac{|a_i u_{2i}+b_i v_{2i}+c_i|}{\sqrt{a_i^2+b_i^2}}. \]

A symmetric epipolar distance is

\[ d_{\text{sym}}^2(x_1,x_2;F) = \frac{(x_2^T F x_1)^2}{(F x_1)_1^2+(F x_1)_2^2} + \frac{(x_2^T F x_1)^2}{(F^T x_2)_1^2+(F^T x_2)_2^2}. \]

This measures distance in both images.

15.15 14.14 Sampson approximation

The true geometric reprojection error requires nonlinear optimization over corrected image points satisfying the epipolar constraint. A widely used first-order approximation is the Sampson error:

\[ d_S^2(x_1,x_2;F) = \frac{(x_2^T F x_1)^2} {(F x_1)_1^2+(F x_1)_2^2+(F^T x_2)_1^2+(F^T x_2)_2^2}. \]

This approximation comes from linearizing the constraint function

\[ g(x_1,x_2)=x_2^T F x_1 \]

with respect to the four inhomogeneous coordinates \((u_1,v_1,u_2,v_2)\).

Residual choice matters. Algebraic error is convenient for linear estimation. Sampson or geometric error is more meaningful for model selection, robust estimation, and nonlinear refinement.

Interactive 14.5. Algebraic versus geometric residuals. Points with the same algebraic residual can have different geometric distances if the epipolar line coefficients have different norms.

15.16 14.15 Noise model and likelihood

Suppose the measured feature locations have independent Gaussian noise:

\[ z_i = z_i^\star + \varepsilon_i, \qquad \varepsilon_i\sim N(0,\sigma^2 I). \]

Here \(z_i\) collects the four coordinates

\[ z_i=(u_{1i},v_{1i},u_{2i},v_{2i})^T. \]

The ideal noiseless correspondences satisfy

\[ g(z_i^\star;F)=0. \]

Maximum likelihood estimation would minimize the squared geometric correction needed to move noisy observed correspondences onto the epipolar manifold. This leads to nonlinear optimization. Linear eight-point estimation is better understood as a computationally efficient initialization.

For students in statistics, this is an important distinction:

  • algebraic least squares is a convenient estimator;
  • geometric least squares is closer to the Gaussian measurement likelihood;
  • robust methods are needed when correspondences include outliers.

15.17 14.16 Outliers and RANSAC

In real images, feature matching produces many incorrect correspondences. These outliers do not satisfy the epipolar geometry. Ordinary least squares can be badly corrupted by even a moderate number of outliers.

A common robust strategy is RANSAC:

  1. Randomly sample a small subset of correspondences.
  2. Estimate a candidate \(F\) or \(E\) from that subset.
  3. Score the model by counting inliers using a residual threshold.
  4. Repeat many times.
  5. Re-estimate the model using all inliers.
  6. Optionally refine by nonlinear optimization.

If the inlier probability is \(w\), the sample size is \(s\), and we want success probability \(p\), the number of iterations \(N\) should satisfy

\[ 1-(1-w^s)^N \ge p. \]

Solving gives

\[ N \ge \frac{\log(1-p)}{\log(1-w^s)}. \]

For the seven-point algorithm \(s=7\); for the eight-point algorithm \(s=8\); for calibrated essential-matrix minimal solvers one often uses \(s=5\).

Interactive 14.6. RANSAC iteration count. The number of required iterations grows rapidly when the inlier rate decreases or the minimal sample size increases.

15.18 14.17 Degenerate configurations

Epipolar estimation can fail or become unstable in degenerate configurations.

15.18.1 Planar scenes

If all 3D points lie on a plane, correspondences are also explained by a homography:

\[ x_2 \sim H x_1. \]

The homography model may fit the data as well as or better than a fundamental matrix. In such cases, recovering general 3D structure from two views is ambiguous.

15.18.2 Pure rotation

If the camera undergoes pure rotation with no translation, the baseline length is zero. There is no meaningful triangulation from parallax. The essential matrix becomes zero because

\[ E=[t]_\times R=0. \]

Correspondences are better described by a rotational homography.

15.18.3 Small baseline

If the baseline is very small relative to scene depth, epipolar geometry may be estimable, but triangulated depth is poorly conditioned. Tiny image localization errors can create large depth uncertainty.

15.18.4 Repeated texture

Repeated patterns can produce ambiguous matches. The geometry may reject many wrong correspondences, but if wrong matches are self-consistent, robust estimation can still fail.

Model comparison. In practice, one often compares a fundamental-matrix model to a homography model. If a homography explains most correspondences, the scene may be planar or the camera motion may be close to pure rotation.

15.20 14.19 Uncertainty propagation

Suppose a point correspondence has measurement covariance \(\Sigma_z\). For a residual function

\[ g(z;F)=x_2^T F x_1, \]

a first-order approximation gives

\[ \operatorname{Var}(g(z;F)) \approx J_z \Sigma_z J_z^T, \]

where

\[ J_z=\frac{\partial g}{\partial z}. \]

This gives a statistically normalized residual

\[ \rho_i=\frac{g(z_i;F)^2}{J_i\Sigma_iJ_i^T}. \]

If the Gaussian model is reasonable, \(\rho_i\) behaves like an approximate squared standardized residual. This provides a principled way to choose inlier thresholds when localization noise is known.

For anisotropic feature uncertainty, line distance should not be measured only in Euclidean pixel units. The covariance direction matters.

15.21 14.20 Nonlinear refinement

Linear algorithms provide an initial estimate. A better final estimate is often obtained by nonlinear optimization.

For example, one can minimize Sampson error:

\[ \min_F \sum_{i\in \mathcal{I}} d_S^2(x_{1i},x_{2i};F) \quad \text{subject to } \operatorname{rank}(F)=2. \]

For calibrated cameras, one can optimize directly over relative pose:

\[ \min_{R,t} \sum_{i\in \mathcal{I}} \left(\hat x_{2i}^T [t]_\times R \hat x_{1i}\right)^2, \qquad R\in SO(3), \quad \|t\|=1. \]

This formulation exposes two important mathematical constraints:

  • \(R\) lies on the nonlinear Lie group \(SO(3)\);
  • \(t\) is known only up to scale, so it lies on a sphere or projective sphere.

A more complete geometric reconstruction jointly optimizes camera poses and 3D points by bundle adjustment, which is the topic of Chapter 17.

15.22 14.21 Epipolar geometry and learned vision models

Modern computer vision often uses neural networks, but epipolar geometry remains important.

15.22.1 Self-supervised depth and pose

A self-supervised monocular depth system may predict depth \(D_1\) from image \(I_1\) and pose \((R,t)\) between \(I_1\) and \(I_2\). The predicted depth and pose define a warp from one image to the other. The training loss includes a photometric term:

\[ \mathcal{L}_{\text{photo}} =\sum_p \rho\left(I_1(p)-I_2(w(p;D_1,R,t))\right). \]

The warp uses the same projective camera geometry behind the essential matrix.

15.22.2 Feature matching networks

Learned matchers can produce correspondences. Epipolar geometry can then be used as a differentiable consistency loss:

\[ \mathcal{L}_{\text{epi}} =\sum_i d_S^2(x_{1i},x_{2i};F). \]

This can regularize matches even when explicit 3D supervision is unavailable.

15.22.3 Visual SLAM and robotics

Visual odometry estimates camera motion from image sequences. Consecutive frame pairs use essential-matrix constraints; longer sequences use bundle adjustment and loop closure.

15.22.4 Foundation models

Large vision foundation models can produce strong descriptors and matches, but geometric verification is still essential. A feature match can look semantically plausible while violating epipolar geometry.

AI lesson. Learned features propose correspondences. Geometry checks whether those correspondences can come from a physically consistent two-camera scene.

15.23 14.22 Python example: estimating a fundamental matrix by SVD

The following example shows the core eight-point linear algebra without relying on a specialized computer vision library.

import numpy as np


def normalize_points(x):
    """Normalize homogeneous image points for the eight-point algorithm."""
    x = x / x[:, [2]]
    centroid = x[:, :2].mean(axis=0)
    centered = x[:, :2] - centroid
    mean_dist = np.sqrt((centered ** 2).sum(axis=1)).mean()
    scale = np.sqrt(2) / mean_dist
    T = np.array([
        [scale, 0.0, -scale * centroid[0]],
        [0.0, scale, -scale * centroid[1]],
        [0.0, 0.0, 1.0]
    ])
    x_norm = (T @ x.T).T
    return x_norm, T


def enforce_rank_two(F):
    U, S, Vt = np.linalg.svd(F)
    S[-1] = 0.0
    return U @ np.diag(S) @ Vt


def eight_point(x1, x2):
    """Estimate F from homogeneous point correspondences."""
    x1n, T1 = normalize_points(x1)
    x2n, T2 = normalize_points(x2)

    u1, v1 = x1n[:, 0], x1n[:, 1]
    u2, v2 = x2n[:, 0], x2n[:, 1]

    A = np.column_stack([
        u2 * u1, u2 * v1, u2,
        v2 * u1, v2 * v1, v2,
        u1,      v1,      np.ones_like(u1)
    ])

    _, _, Vt = np.linalg.svd(A)
    F = Vt[-1].reshape(3, 3)
    F = enforce_rank_two(F)

    # Denormalize.
    F = T2.T @ F @ T1
    return F / np.linalg.norm(F)

15.24 14.23 Python example: synthetic two-view data

import numpy as np

rng = np.random.default_rng(7243)

# Intrinsics.
K = np.array([
    [800.0, 0.0, 320.0],
    [0.0, 800.0, 240.0],
    [0.0, 0.0, 1.0]
])

# Camera 1: P1 = K [I | 0].
P1 = K @ np.hstack([np.eye(3), np.zeros((3, 1))])

# Camera 2: small translation and rotation.
t = np.array([0.4, 0.02, 0.0])
t = t / np.linalg.norm(t)
angle = np.deg2rad(4.0)
R = np.array([
    [np.cos(angle), 0.0, np.sin(angle)],
    [0.0, 1.0, 0.0],
    [-np.sin(angle), 0.0, np.cos(angle)]
])
P2 = K @ np.hstack([R, t.reshape(3, 1)])

# Random 3D points in front of the cameras.
N = 60
X = np.column_stack([
    rng.uniform(-1.0, 1.0, size=N),
    rng.uniform(-0.7, 0.7, size=N),
    rng.uniform(3.0, 6.0, size=N),
    np.ones(N)
])


def project(P, X):
    x = (P @ X.T).T
    x = x / x[:, [2]]
    return x

x1 = project(P1, X)
x2 = project(P2, X)

# Add pixel noise.
sigma = 0.8
x1[:, :2] += rng.normal(0, sigma, size=(N, 2))
x2[:, :2] += rng.normal(0, sigma, size=(N, 2))

F_hat = eight_point(x1, x2)
residuals = np.sum(x2 * (F_hat @ x1.T).T, axis=1)
print("mean absolute algebraic residual:", np.mean(np.abs(residuals)))
print("estimated rank:", np.linalg.matrix_rank(F_hat, tol=1e-8))

15.25 14.24 Python example: Sampson error and inlier scoring

import numpy as np


def sampson_error(F, x1, x2):
    Fx1 = (F @ x1.T).T
    Ftx2 = (F.T @ x2.T).T
    numer = np.sum(x2 * Fx1, axis=1) ** 2
    denom = Fx1[:, 0] ** 2 + Fx1[:, 1] ** 2 + Ftx2[:, 0] ** 2 + Ftx2[:, 1] ** 2
    return numer / np.maximum(denom, 1e-12)

errors = sampson_error(F_hat, x1, x2)
threshold = 2.0 ** 2
inliers = errors < threshold
print("number of inliers:", inliers.sum(), "out of", len(inliers))
print("median Sampson error:", np.median(errors))

15.26 14.25 Python example: a simple RANSAC wrapper

import numpy as np


def ransac_fundamental(x1, x2, n_iter=1000, threshold=2.0, rng=None):
    if rng is None:
        rng = np.random.default_rng()

    n = len(x1)
    best_inliers = None
    best_F = None
    best_count = -1

    for _ in range(n_iter):
        idx = rng.choice(n, size=8, replace=False)
        try:
            F_candidate = eight_point(x1[idx], x2[idx])
        except np.linalg.LinAlgError:
            continue

        err = sampson_error(F_candidate, x1, x2)
        inliers = err < threshold ** 2
        count = int(inliers.sum())

        if count > best_count:
            best_count = count
            best_inliers = inliers
            best_F = F_candidate

    # Refit on all inliers.
    if best_inliers is not None and best_inliers.sum() >= 8:
        best_F = eight_point(x1[best_inliers], x2[best_inliers])

    return best_F, best_inliers

15.27 14.26 TensorFlow example: differentiable epipolar loss

A differentiable epipolar loss is useful when a network predicts feature correspondences, camera motion, or dense matches.

import tensorflow as tf


def skew(t):
    t1, t2, t3 = tf.unstack(t, axis=-1)
    zeros = tf.zeros_like(t1)
    row1 = tf.stack([zeros, -t3, t2], axis=-1)
    row2 = tf.stack([t3, zeros, -t1], axis=-1)
    row3 = tf.stack([-t2, t1, zeros], axis=-1)
    return tf.stack([row1, row2, row3], axis=-2)


def essential_from_rt(R, t):
    return tf.matmul(skew(t), R)


def epipolar_sampson_loss(x1, x2, E):
    # x1, x2: shape (batch, n, 3), normalized homogeneous coordinates.
    Ex1 = tf.einsum("bij,bnj->bni", E, x1)
    Etx2 = tf.einsum("bji,bnj->bni", E, x2)
    x2tEx1 = tf.reduce_sum(x2 * Ex1, axis=-1)
    denom = Ex1[..., 0] ** 2 + Ex1[..., 1] ** 2 + Etx2[..., 0] ** 2 + Etx2[..., 1] ** 2
    err = x2tEx1 ** 2 / tf.maximum(denom, 1e-8)
    return tf.reduce_mean(err)

15.28 14.27 AI-assisted study components

Use AI tools carefully as mathematical assistants, not as authorities.

15.28.1 Prompt 1: explain the geometry

Ask:

Explain epipolar geometry using only projective points, projective lines, camera centers, and planes. Then translate the explanation into the equation \(x_2^T F x_1=0\).

Check whether the response correctly distinguishes a point-to-line map from a point-to-point map.

15.28.2 Prompt 2: debug an eight-point implementation

Ask:

Here is my implementation of the normalized eight-point algorithm. Find numerical or mathematical mistakes. In particular, check normalization, design matrix ordering, rank-two enforcement, and denormalization.

Then verify every suggested correction by running synthetic data.

15.28.3 Prompt 3: compare residuals

Ask:

Compare algebraic epipolar residual, point-to-line distance, symmetric epipolar distance, and Sampson error. Which one is best for linear estimation, inlier classification, and nonlinear refinement?

A good answer should say that algebraic error is convenient but not geometrically meaningful, while Sampson error is a useful first-order approximation to geometric error.

15.28.4 Prompt 4: connect to modern AI

Ask:

How can epipolar geometry be used as a loss or consistency check in learned feature matching, self-supervised depth, and visual odometry?

Check whether the response includes the role of calibrated coordinates and the essential matrix.

15.29 14.28 Common mistakes

  1. Mistake: Thinking \(F x_1\) is the matching point in image 2.
    Correction: \(F x_1\) is an epipolar line.

  2. Mistake: Forgetting that \(F\) is homogeneous.
    Correction: \(F\) and \(\lambda F\) define the same geometry.

  3. Mistake: Estimating \(F\) without normalizing image coordinates.
    Correction: Use similarity normalization before solving by SVD.

  4. Mistake: Ignoring the rank-two constraint.
    Correction: Project the estimated matrix onto rank two.

  5. Mistake: Treating all feature matches as inliers.
    Correction: Use robust estimation, usually RANSAC or a modern variant.

  6. Mistake: Confusing \(F\) and \(E\).
    Correction: \(F\) is for pixel coordinates; \(E\) is for calibrated normalized coordinates.

  7. Mistake: Expecting metric scale from two images.
    Correction: The essential matrix gives translation direction but not translation magnitude.

15.30 14.29 Summary

Epipolar geometry is the foundation of two-view computer vision. Its central constraint is

\[ x_2^T F x_1=0. \]

For calibrated cameras, the corresponding constraint is

\[ \hat x_2^T E \hat x_1=0, \qquad E=[t]_\times R. \]

The fundamental matrix maps points to epipolar lines, has rank two, and contains the epipoles as null vectors. The essential matrix adds calibration and metric pose constraints. Estimation combines linear algebra, robust statistics, and nonlinear optimization.

The chapter also prepares the next major topic: stereo depth. Once epipolar lines are known, correspondence search becomes one-dimensional, and disparity can be converted into depth under rectified geometry.

15.31 Exercises

15.31.1 Conceptual exercises

  1. Explain why a point in one image corresponds to a line in the other image.
  2. What is an epipole? Why do all epipolar lines pass through it?
  3. Why is the fundamental matrix singular?
  4. Explain the difference between \(F\) and \(E\).
  5. Why does pure camera rotation not produce useful triangulation?
  6. Explain why a planar scene can be degenerate for fundamental-matrix estimation.

15.31.2 Mathematical exercises

  1. Let \(\ell=Fx_1\). Prove that \(x_2^T F x_1=0\) is equivalent to \(x_2\) lying on \(\ell\).
  2. Show that if \(F e_1=0\), then \(e_1\) is the point in image 1 whose corresponding epipolar line in image 2 is undefined up to the zero vector.
  3. Derive the design matrix row \[ (u_2u_1,u_2v_1,u_2,v_2u_1,v_2v_1,v_2,u_1,v_1,1) \] from the equation \(x_2^T F x_1=0\).
  4. Prove that setting the smallest singular value of \(F\) to zero gives the closest rank-two matrix in Frobenius norm.
  5. Starting from \(X_2=RX+t\), derive \(E=[t]_\times R\).
  6. Derive the Sampson error by first-order linearization of \(g(x_1,x_2)=x_2^T F x_1\).
  7. Derive the RANSAC iteration formula \[ N \ge \frac{\log(1-p)}{\log(1-w^s)}. \]

15.31.3 Python exercises

  1. Implement the normalized eight-point algorithm and test it on synthetic data.
  2. Compare estimates with and without coordinate normalization.
  3. Add outliers and implement RANSAC.
  4. Plot epipolar lines in image 2 for selected points in image 1.
  5. Compute algebraic residual, point-to-line distance, symmetric distance, and Sampson error for the same correspondences.
  6. Estimate an essential matrix from normalized coordinates and project it onto the essential-matrix singular-value constraint.
  7. Use OpenCV or another library to compare your implementation with a standard implementation.

15.31.4 AI/modeling exercises

  1. Use an AI assistant to generate an eight-point algorithm implementation. Audit the code for normalization and denormalization errors.
  2. Ask an AI assistant to explain why \(E=[t]_\times R\). Identify whether the explanation correctly uses the scalar triple product.
  3. Give an AI assistant a noisy correspondence set and ask it to recommend a robust estimation strategy. Critique whether it accounts for outliers and degenerate cases.
  4. Design a neural feature-matching loss that includes a Sampson epipolar penalty.
  5. Explain how a vision-language or foundation model could produce semantically plausible but geometrically impossible matches.

15.32 Notes and further reading

The standard mathematical treatment of epipolar geometry is Hartley and Zisserman’s Multiple View Geometry (Hartley and Zisserman 2004). Faugeras (Faugeras 1993) and Ma, Soatto, Kosecka, and Sastry (Ma et al. 2004) provide complementary geometric viewpoints. The normalized eight-point algorithm is associated with Hartley’s normalization work (Hartley 1997). RANSAC was introduced by Fischler and Bolles (Fischler and Bolles 1981). Minimal solvers and robust two-view estimation are central in practical structure from motion and visual SLAM.

Faugeras, Olivier. 1993. Three-Dimensional Computer Vision: A Geometric Viewpoint. MIT Press.
Fischler, Martin A., and Robert C. Bolles. 1981. “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography.” Communications of the ACM 24 (6): 381–95.
Hartley, Richard I. 1997. “In Defense of the Eight-Point Algorithm.” IEEE Transactions on Pattern Analysis and Machine Intelligence 19 (6): 580–93.
Hartley, Richard, and Andrew Zisserman. 2004. Multiple View Geometry in Computer Vision. 2nd ed. Cambridge University Press. https://www.robots.ox.ac.uk/~vgg/hzbook/.
Ma, Yi, Stefano Soatto, Jana Kosecka, and Shankar S. Sastry. 2004. An Invitation to 3-d Vision: From Images to Geometric Models. Springer.