Fundamental Matrix

The fundamental matrix $F$ is the algebraic form of epipolar geometry for two uncalibrated views. It is a $3 \times 3$ matrix of rank 2 such that any pair of corresponding image points $\mathbf{x} \leftrightarrow \mathbf{x}'$ satisfies

$$\mathbf{x}'^\top F \mathbf{x} = 0.$$

$F$ can be computed from point matches alone, without knowing either camera’s intrinsic parameters, which makes it the standard model for verifying matches between two views of a 3D scene and the starting point of uncalibrated reconstruction. When the intrinsics are known, $F$ reduces to the essential matrix, which also yields the relative camera pose.

Definition

Notation, shared with the epipolar geometry and essential matrix articles: $\mathbf{x}$ and $\mathbf{x}'$ are corresponding points in the first and second image, as homogeneous pixel coordinates. The cameras are $P = K[\,I \mid \mathbf{0}\,]$ and $P' = K'[\,R \mid \mathbf{t}\,]$, so that a point $\mathbf{X}$ in first-camera coordinates becomes $R\mathbf{X} + \mathbf{t}$ in the second camera’s frame. Normalized coordinates are $\hat{\mathbf{x}} = K^{-1}\mathbf{x}$ and $\hat{\mathbf{x}}' = K'^{-1}\mathbf{x}'$, the essential matrix is $E = [\mathbf{t}]_\times R$ with $\hat{\mathbf{x}}'^\top E \hat{\mathbf{x}} = 0$, and $[\mathbf{a}]_\times$ denotes the cross-product matrix, $[\mathbf{a}]_\times \mathbf{b} = \mathbf{a} \times \mathbf{b}$.

The fundamental matrix is the unique (up to scale) $3 \times 3$ matrix of rank 2 with $\mathbf{x}'^\top F \mathbf{x} = 0$ for all corresponding points. It maps a point in the first image to its epipolar line in the second, $\mathbf{l}' = F\mathbf{x}$, and a point in the second image to its epipolar line in the first, $\mathbf{l} = F^\top\mathbf{x}'$.

Intuition

The epipolar constraint says that the match of $\mathbf{x}$ lies on a line, and that line depends linearly on $\mathbf{x}$. Any linear map from points to lines in the projective plane is a $3 \times 3$ matrix, so the whole two-view geometry fits in nine numbers. Because every epipolar line passes through the epipole, the map cannot be invertible: all points on one epipolar line in the first image map to the same line in the second. That collapse of a whole line to one line is why $F$ is singular.

$F$ is bilinear in the two points, so each correspondence gives one linear equation in the nine entries of $F$. That is what makes it estimable from matches alone, and it is also why the constraint is weak: a correspondence pins $\mathbf{x}'$ to a line, not a point.

Formal Definition

Derivation from the cameras

Hartley and Zisserman (2004, §9.2) derive $F$ for general cameras by back-projecting $\mathbf{x}$ to the point $P^+\mathbf{x}$ on its ray, where $P^+$ is the pseudo-inverse of $P$, and joining its image $P'P^+\mathbf{x}$ to the epipole $\mathbf{e}' = P'\mathbf{C}$:

$$F = [\mathbf{e}']_\times P' P^+ .$$

For the cameras above, the second camera’s frame relates rays by $\hat{\mathbf{x}}' \propto R\hat{\mathbf{x}}\,Z + \mathbf{t}$, where $Z$ is the depth in the first camera. Taking the cross product with $\mathbf{t}$ and then the dot product with $\hat{\mathbf{x}}'$ eliminates the depth and gives $\hat{\mathbf{x}}'^\top [\mathbf{t}]_\times R\, \hat{\mathbf{x}} = 0$. Substituting $\hat{\mathbf{x}} = K^{-1}\mathbf{x}$ gives

$$F = K'^{-\top} [\mathbf{t}]_\times R\, K^{-1} = K'^{-\top} E\, K^{-1}.$$

Properties

Hartley and Zisserman (2004, §9.2.4) list the following properties.

• Rank 2. $\det F = 0$, because $[\mathbf{t}]_\times$ has rank 2.
• Seven degrees of freedom. Nine entries, minus one for the overall scale, minus one for the determinant constraint.
• Epipoles are null vectors. $F\mathbf{e} = \mathbf{0}$ and $F^\top\mathbf{e}' = \mathbf{0}$: the epipole has no epipolar line, and every epipolar line passes through the epipole, $\mathbf{e}'^\top F\mathbf{x} = 0$ for all $\mathbf{x}$.
• Transpose. If $F$ is the fundamental matrix of the pair $(P, P')$, then $F^\top$ is that of $(P', P)$.
• Projective invariance. $F$ depends only on the image projections, so cameras $(PH, P'H)$ for any invertible $4 \times 4$ $H$ give the same $F$. From $F$ alone the cameras, and a reconstruction, can be recovered only up to such a projective transformation of space (Hartley and Zisserman, 2004, §9.5).

Estimation

Each correspondence $\mathbf{x}_i = (x_i, y_i, 1)^\top$, $\mathbf{x}_i' = (x_i', y_i', 1)^\top$ gives one linear equation $\mathbf{a}_i^\top \mathbf{f} = 0$ in the vector $\mathbf{f}$ of the nine entries of $F$ (row-major):

$$\mathbf{a}_i = (x_i' x_i,\; x_i' y_i,\; x_i',\; y_i' x_i,\; y_i' y_i,\; y_i',\; x_i,\; y_i,\; 1)^\top .$$

Stacking $n$ correspondences gives $A\mathbf{f} = \mathbf{0}$ with $A$ of size $n \times 9$.

The eight-point algorithm

With eight or more correspondences, $\mathbf{f}$ is taken as the right singular vector of $A$ for the smallest singular value, the least-squares solution of $A\mathbf{f} = \mathbf{0}$ with $\|\mathbf{f}\| = 1$. Longuet-Higgins (1981) introduced this linear method for the essential matrix of calibrated cameras; applied to pixel coordinates it estimates $F$. With noise the result is not singular, so the rank constraint is enforced afterward: with $F = U\,\mathrm{diag}(\sigma_1, \sigma_2, \sigma_3)\,V^\top$, replace $F$ by $U\,\mathrm{diag}(\sigma_1, \sigma_2, 0)\,V^\top$, the closest rank-2 matrix in Frobenius norm. Hartley (1997) credits this correction to Tsai and Huang (1984).

Normalization. Applied directly to pixel coordinates, the method is badly conditioned: entries of $\mathbf{a}_i$ range from about 1 to about $10^6$ for an image a thousand pixels wide. Hartley (1997) showed that a simple change of coordinates fixes this. In each image separately, translate the points so their centroid is at the origin and scale them so their average distance from the origin is $\sqrt{2}$, using similarity transforms $T$ and $T'$. Estimate $\tilde{F}$ from the normalized points, enforce rank 2, and undo the normalization:

$$F = T'^\top \tilde{F}\, T .$$

Hartley argued from the condition number of $A^\top A$ and reported experiments on real images in which the normalized algorithm came close to the best iterative methods of the time, against the prevailing view that the eight-point algorithm was too sensitive to noise to be useful.

The seven-point algorithm

$F$ has seven degrees of freedom, so seven correspondences suffice. Then $A$ has a two-dimensional null space spanned by $F_1$ and $F_2$, and the rank constraint

$$\det\!\big(\alpha F_1 + (1 - \alpha) F_2\big) = 0$$

is a cubic in $\alpha$, with one or three real roots and therefore one or three solutions for $F$ (Hartley and Zisserman, 2004, §11.1). The seven-point algorithm is the usual minimal solver inside RANSAC.

Robust estimation

Real correspondences from feature matching contain outliers, and a single bad match can ruin a least-squares estimate. In practice $F$ is estimated with RANSAC: repeatedly fit $F$ to a random minimal sample of seven matches (or eight, with the linear algorithm), count the matches whose epipolar error is below a threshold, keep the model with the largest support, and refit to its inliers (Hartley and Zisserman, 2004, §11.6). Because each correspondence constrains $F$ only through one equation, the residual has one degree of freedom, which sets the chi-squared threshold in RANSAC (see the RANSAC article).

Error measures and refinement

The algebraic residual $\mathbf{x}'^\top F \mathbf{x}$ has no geometric meaning; it changes with the scale of $F$ and of the coordinates. Better measures (Hartley and Zisserman, 2004, §11.4) are:

• Epipolar distance: the distance in pixels from $\mathbf{x}'$ to the line $F\mathbf{x}$, often symmetrized by adding the distance from $\mathbf{x}$ to $F^\top\mathbf{x}'$.
• Sampson distance: a first-order approximation of the geometric error, the smallest total displacement of $\mathbf{x}$ and $\mathbf{x}'$ that makes them satisfy the constraint exactly:

$$d_{\mathrm{S}}^2 = \frac{(\mathbf{x}'^\top F \mathbf{x})^2}{(F\mathbf{x})_1^2 + (F\mathbf{x})_2^2 + (F^\top\mathbf{x}')_1^2 + (F^\top\mathbf{x}')_2^2},$$

where $(\cdot)_k$ is the $k$-th entry.

• Gold standard (reprojection) error: the maximum-likelihood estimate under Gaussian image noise jointly estimates $F$ and corrected points $\hat{\mathbf{x}}_i$, $\hat{\mathbf{x}}_i'$ that satisfy the constraint exactly, minimizing $\sum_i d(\mathbf{x}_i, \hat{\mathbf{x}}_i)^2 + d(\mathbf{x}_i', \hat{\mathbf{x}}_i')^2$. It is solved by nonlinear least squares over a camera pair and 3D points, initialized from the normalized eight-point estimate.

A typical pipeline therefore runs RANSAC with a minimal solver and a Sampson threshold, refits the inliers with the normalized eight-point algorithm, and optionally refines by minimizing Sampson or reprojection error.

Degeneracies

Some configurations do not determine $F$ even with perfect, outlier-free matches (Hartley and Zisserman, 2004, §11.9).

• Planar scenes. If all points lie on one plane, the matches are related by a homography $H$, and $F = [\mathbf{e}']_\times H$ satisfies all of them for any choice of $\mathbf{e}'$, so there is a whole family of solutions. Near-planar scenes make the estimate unstable, and in RANSAC a sample of matches from a dominant plane can produce a wrong $F$ with large support.
• Pure rotation. If the camera rotates about its center, $\mathbf{t} = \mathbf{0}$ and $F = K'^{-\top}[\mathbf{0}]_\times R K^{-1}$ vanishes (Hartley and Zisserman, 2004, §9.2): there is no baseline and no epipolar geometry, and the images are related by the homography $K'RK^{-1}$.

Robust pipelines handle both by testing a homography against $F$ and choosing the model that explains the data better, or by using the calibrated five-point method when intrinsics are known.

History

Longuet-Higgins (1981) introduced the essential matrix for calibrated cameras, with the linear eight-point algorithm. Hartley and Zisserman (2004, §9.7.1) note that the realization that the same bilinear relation holds for uncalibrated cameras, as a projective relation, developed in the early 1990s and was published simultaneously by Faugeras and by Hartley and colleagues in 1992. The resulting theory shows that two uncalibrated views determine the cameras and the scene up to a projective transformation (Hartley and Zisserman, 2004, §9.5, Chapter 10). Hartley’s 1997 paper then rehabilitated the eight-point algorithm through normalization.

Examples

The NumPy code below generates 100 correspondences between two cameras with 1,000-pixel focal lengths, adds 1 pixel of Gaussian noise, and estimates $F$ with and without Hartley normalization, from the first 8 matches and from all 100. For each estimate it reports the condition number of $A$, the rank, the RMS Sampson error on the noisy matches, and the mean distance from each noise-free point $\mathbf{x}'$ to the estimated epipolar line of its noise-free partner, a measure of how close the estimate is to the true geometry.

import numpy as np
from scipy.spatial.transform import Rotation

rng = np.random.default_rng(1)

# Ground truth: two cameras with pixel coordinates in a 1280 x 960 image
K = np.array([[1000.0, 0, 640], [0, 1000.0, 480], [0, 0, 1]])
R = Rotation.from_euler("xyz", [3, -12, 2], degrees=True).as_matrix()
t = np.array([1.0, 0.1, 0.15])

def skew(v):
    return np.array([[0, -v[2], v[1]], [v[2], 0, -v[0]], [-v[1], v[0], 0]])

F_true = np.linalg.inv(K).T @ skew(t) @ R @ np.linalg.inv(K)   # F = K'^-T [t]x R K^-1

X = rng.uniform([-3, -2, 6], [3, 2, 12], size=(100, 3))
def project(Kc, R, t, X):
    x = (X @ R.T + t) @ Kc.T
    return x / x[:, 2:]
x1_true = project(K, np.eye(3), np.zeros(3), X)
x2_true = project(K, R, t, X)
noise = lambda: np.hstack([rng.normal(0, 1.0, (len(X), 2)), np.zeros((len(X), 1))])
x1, x2 = x1_true + noise(), x2_true + noise()          # 1-pixel Gaussian noise

def normalize(x):
    """Hartley normalization: centroid to origin, mean distance sqrt(2)."""
    c = x[:, :2].mean(0)
    s = np.sqrt(2) / np.linalg.norm(x[:, :2] - c, axis=1).mean()
    T = np.array([[s, 0, -s * c[0]], [0, s, -s * c[1]], [0, 0, 1]])
    return x @ T.T, T

def eight_point(x1, x2, normalized=True):
    if normalized:
        x1, T1 = normalize(x1)
        x2, T2 = normalize(x2)
    # Each match gives one row of A f = 0, from x2^T F x1 = 0
    A = np.einsum("ni,nj->nij", x2, x1).reshape(len(x1), 9)
    F = np.linalg.svd(A)[2][-1].reshape(3, 3)
    U, S, Vt = np.linalg.svd(F)                  # enforce rank 2
    F = U @ np.diag([S[0], S[1], 0]) @ Vt
    if normalized:
        F = T2.T @ F @ T1                        # undo the normalization
    return F / np.linalg.norm(F), np.linalg.cond(A)

def sampson(F, x1, x2):
    Fx1, Ftx2 = x1 @ F.T, x2 @ F
    num = np.sum(x2 * Fx1, 1) ** 2
    return num / (Fx1[:, 0]**2 + Fx1[:, 1]**2 + Ftx2[:, 0]**2 + Ftx2[:, 1]**2)

def line_dist(F, x1, x2):
    """Distance in pixels from x2 to its epipolar line l' = F x1."""
    l = x1 @ F.T
    return np.abs(np.sum(x2 * l, 1)) / np.hypot(l[:, 0], l[:, 1])

for n in (8, 100):
    print(f"--- {n} correspondences ---")
    for name, norm in (("unnormalized", False), ("normalized", True)):
        F, cond = eight_point(x1[:n], x2[:n], norm)
        print(f"{name:>12}: cond(A) = {cond:9.2e}  rank = {np.linalg.matrix_rank(F)}"
              f"  Sampson RMS (noisy, px) = {np.sqrt(sampson(F, x1, x2).mean()):6.3f}"
              f"  mean dist of true x' to line (px) = {line_dist(F, x1_true, x2_true).mean():6.3f}")
print("reference, true F: Sampson RMS (noisy, px) = %.3f" % np.sqrt(sampson(F_true, x1, x2).mean()))

Output:

--- 8 correspondences ---
unnormalized: cond(A) =  2.77e+06  rank = 2  Sampson RMS (noisy, px) = 12.096  mean dist of true x' to line (px) = 14.712
  normalized: cond(A) =  2.79e+02  rank = 2  Sampson RMS (noisy, px) =  2.225  mean dist of true x' to line (px) =  2.149
--- 100 correspondences ---
unnormalized: cond(A) =  6.25e+07  rank = 2  Sampson RMS (noisy, px) =  2.846  mean dist of true x' to line (px) =  3.007
  normalized: cond(A) =  4.02e+02  rank = 2  Sampson RMS (noisy, px) =  1.036  mean dist of true x' to line (px) =  0.250
reference, true F: Sampson RMS (noisy, px) = 1.065

Normalization lowers the condition number of $A$ by four to five orders of magnitude. With all 100 matches, the normalized estimate reaches the Sampson error of the true $F$ on the noisy data, about 1 pixel, as expected for 1-pixel noise, and its epipolar lines pass within a quarter of a pixel of the true points on average. The unnormalized estimate, from the same data, is off by about 3 pixels. With only eight matches both estimates are poor, but the unnormalized one is far worse. Both are exactly rank 2 after the SVD correction.

Common Misconceptions

• “A small algebraic residual means a good $F$.” The residual $\mathbf{x}'^\top F\mathbf{x}$ depends on the scaling of $F$ and of the coordinates. Report Sampson or epipolar distances in pixels.
• “The eight-point algorithm is too noisy to use.” Without normalization it often is. With Hartley normalization it is a reliable linear estimator and the usual initialization for nonlinear refinement.
• “If RANSAC finds many inliers, $F$ is right.” For a planar or nearly planar scene, many different $F$ fit the matches equally well. Check for a dominant homography.
• “$F$ gives the camera motion.” Without intrinsics, $F$ determines the cameras only up to a projective transformation. Metric pose needs $K$ and $K'$ and goes through the essential matrix, $E = K'^\top F K$.

Where It Is Used

• Geometric verification of putative matches between two views of a 3D scene in feature matching, image retrieval, and the first stage of structure from motion, with RANSAC to separate inliers from outliers.
• Guided matching, which searches for additional matches near the epipolar lines of a verified $F$.
• Uncalibrated stereo rectification, which computes rectifying homographies from $F$ when the intrinsics are unknown, so that stereo matching can search along image rows.
• Projective reconstruction and self-calibration, which recover camera matrices from $F$ up to a projective transformation and upgrade them to a metric reconstruction using constraints on the intrinsics.