Fundamental Matrix Estimation (8-Point Algorithm)

1. Background Knowledge

The Fundamental Matrix $F$ encodes the epipolar geometry between two uncalibrated images, capturing the projective relationship between corresponding points $x_1 = [x_1, y_1, 1]^T$ in image 1 and $x_2 = [x_2, y_2, 1]^T$ in image 2. These points satisfy the epipolar constraint:

Key concepts:

• Epipolar geometry: Projects a point from one image onto an epipolar line in the other image, reducing the 2D search to 1D.
• $F$ is a $3 \times 3$ matrix with rank 2 (determinant zero) and 7 degrees of freedom (9 elements minus 1 scale, minus 1 rank constraint).
• Homogeneous coordinates: Points are represented as $[x, y, 1]^T$, invariant to scaling.
• Uncalibrated cameras: No intrinsic parameters (K1, K2) known; $F$ relates image coordinates directly.

Prerequisites:

• Linear algebra: SVD decomposition, null space computation.
• Geometry: Projective transformations, coplanarity of rays from corresponding points.

2. Algorithm Approach

The 8-Point Algorithm is a linear method to estimate $F$ from $\geq 8$ point correspondences. It solves the homogeneous system:

where $f =$\text{vec}$(F)$ is the 9×1 vectorized $F$, and $A$ has rows from each correspondence:

Core technique: SVD

• Compute SVD: $A = U \Sigma V^T$.
• $f$ is the right singular vector corresponding to the smallest singular value (last column of $V$), ensuring $\|f\| = 1$ and minimizing $\|Af\|^2$.

Post-processing:

• Reshape $f$ to $3 \times 3$ matrix $F$.
• Normalize: $F \leftarrow F / \|F\|_F$ (Frobenius norm).

Why 8 points? $F$ has 7 DOF; 8 points provide a unique (up to scale) solution.

3. Step-by-Step Strategy

1. Input validation: Ensure $\geq 8$ point pairs, all in homogeneous form $[x, y, 1]$.

2. Construct $A \in \mathbb{R}^{N \times 9}$:

For each pair (x1,y1), (x2,y2):
A[i] = [x2*x1, y2*x1, x1, x2*y1, y2*y1, y1, x2, y2, 1]

3. SVD decomposition: $U, \Sigma, V^T =$\text{svd}$(A)$.

4. Extract $f$: $f = V[:, -1]$ (last column of $V$).

5. Reshape: $F =$\text{reshape}$(f, 3, 3)$.

6. Normalize: $F = F / \|$\text{Frobenius}$(F)\|$.

7. Round: $F_{ij} \leftarrow$\text{round}$(F_{ij}, 4)$.

Pseudocode:

import numpy as np
def eight_point_algorithm(pts1, pts2):
 assert len(pts1) >= 8
 A = np.zeros((len(pts1), 9))
 for i, ((x1,y1), (x2,y2)) in enumerate(zip(pts1, pts2)):
 A[i] = [x2*x1, y2*x1, x1, x2*y1, y2*y1, y1, x2, y2, 1]
 U, S, Vt = np.linalg.svd(A)
 F = Vt[-1].reshape(3,3)
 F = F / np.linalg.norm(F, 'fro')
 return np.round(F, 4)

4. Common Pitfalls

• Singular $A$: Fewer than 8 points or degenerate configurations (points coplanar with baseline) → add regularization or check $\text{cond}(A)$.
• Scale sensitivity: Inputs must be properly scaled; large coordinates amplify errors → normalize points (e.g., mean=0, std=1) before/after.
• Rank deficiency: Raw SVD $F$ may not have $\det(F)=0$; enforce via $\text{SVD}(F)$ and set smallest singular value to 0.
• Numerical precision: Use double precision; round only at end.
• Outliers: Algorithm assumes perfect correspondences; real data needs RANSAC wrapper.
• Frobenius norm: Compute as \sqrt{\sum F_{ij}^2}, not max norm.

5. Time & Space Complexity

• Time: $O(N \cdot 9^2 + 9^3) = O(N + 729) = O(N)$, dominated by SVD of $N \times 9$ matrix (fast for $N \ll 10^4$).
• Building $A$: $O(N)$.
• SVD: $O(N \cdot 9^2)$ via standard libraries (e.g., LAPACK).
• Space: $O(N \cdot 9 + 9 \cdot 9) = O(N)$.

Scalability: Linear in $N$; suitable for thousands of points. For refinement, non-linear methods (e.g., LM) add $O(N)$ per iteration but improve accuracy.