Eight-Point Algorithm

Definition

Each correspondence gives one equation $u_0^{T}F{u}_1=0$ that is linear in the 9 entries of $F$. With $M\ge 8$ correspondences: $Wf=0$, $W\in {\mathbb{R}}^{M\times 9}$.

The normalized 8-point algorithm

1. Normalize points: ${\bar{x}}_i=T_i{x}_i$ (centroid to origin, mean squared distance about 2)
2. Construct the $M\times 9$ matrix $W$
3. SVD $W=U\Sigma V^T$
4. $\hat{F}$ = column of $V$ for the smallest singular value, reshaped (solves ${\min }_{\Vert f\Vert =1}\Vert Wf{\Vert }^2$)
5. SVD $\hat{F}=U^{\prime }{\Sigma }^{\prime }{V}^{\prime T}$
6. $F=U^{\prime }\text{diag}({\sigma }_1^{\prime },{\sigma }_2^{\prime },0)V^{\prime T}$ (rank 2)
7. Denormalize: $F=T_0^T\bar{F}{T}_1$

Why this step?
8 points	9 unknowns up to scale
rank 2	the noisy estimate has full rank, so the epipolar lines don’t meet in one epipole
normalization	pixel values up to ~2000 make $W$ badly conditioned (entries from ~$10^6$ to 1)

Variants: 7 points suffice for $F$ (7 DoF), but not linearly. 5 points suffice for $E$ (5-point algorithm), which is preferred inside RANSAC when the intrinsics are known.

Appears in

• Lecture 3, The 8-Point Algorithm
• Lecture 3, Normalization
• Lecture 3, Incremental SfM: initialization

Related concepts

• Essential and Fundamental Matrix
• RANSAC
• Epipolar Geometry