Epipolar Geometry

Epipolar geometry describes the geometric relationship between two views of the same scene. It is encoded in the fundamental matrix $F$ (for pixel coordinates) or the essential matrix $E$ (for normalized coordinates). These matrices are central to stereo vision, visual odometry, and structure from motion.

Fundamental Matrix

Problem Statement

Given: $N$ point correspondences $\{({\mathbf{p}}_i,{\mathbf{p}}_i^{\prime })\}$ in pixel coordinates from two views.

Find: Fundamental matrix $F\in {\mathbb{R}}^{3\times 3}$ satisfying ${\mathbf{p}}^{\prime T}F\mathbf{p}=0$ for all correspondences.

Properties of $F$:

• Rank 2 (by the epipolar constraint)
• 7 degrees of freedom (9 entries, scale ambiguity, rank constraint)
• Maps a point in one image to its epipolar line in the other: ${\mathbf{l}}^{\prime }=F\mathbf{p}$

8-Point Algorithm

The simplest method, requiring $N\ge 8$ correspondences.

Derivation: The constraint ${\mathbf{p}}^{\prime T}F\mathbf{p}=0$ expands to:

$$u^{\prime }u{f}_{11}+u^{\prime }v{f}_{12}+u^{\prime }{f}_{13}+v^{\prime }u{f}_{21}+v^{\prime }v{f}_{22}+v^{\prime }{f}_{23}+u{f}_{31}+v{f}_{32}+f_{33}=0$$

Each correspondence gives one linear equation in the 9 entries of $F$.

Algorithm:

1. Normalize both point sets using Hartley normalization
2. Build $N\times 9$ design matrix $A$ where each row is: $$[u^{\prime }u,u^{\prime }v,u^{\prime },v^{\prime }u,v^{\prime }v,v^{\prime },u,v,1]$$
3. Solve $A\mathbf{f}=0$ via SVD; $\mathbf{f}$ is the last column of $V$
4. Enforce rank 2: Decompose $F=U\Sigma V^T$ and set ${\sigma }_3=0$: $$F=U\cdot \text{diag}({\sigma }_1,{\sigma }_2,0)\cdot V^T$$
5. Denormalize: $F=T_2^T\cdot F_{\text{norm}}\cdot T_1$

The rank-2 enforcement is critical: without it, the epipolar lines do not intersect at a common epipole.

7-Point Algorithm

A minimal solver using exactly 7 correspondences, producing 1 or 3 candidate matrices.

Derivation: With 7 equations for 9 unknowns (modulo scale), the null space of $A$ is 2-dimensional. Let the null space basis be $F_1$ and $F_2$. The fundamental matrix is:

$$F=F_1+t\cdot F_2$$

for some scalar $t$. The rank-2 constraint $\det (F)=0$ gives a cubic equation in $t$:

$$\det (F_1+t{F}_2)=0$$

This cubic has 1 or 3 real roots, each giving a candidate $F$.

Essential Matrix

Problem Statement

Given: $N$ point correspondences in normalized coordinates $\{({\hat{\mathbf{p}}}_i,{\hat{\mathbf{p}}}_i^{\prime })\}$ where $\hat{\mathbf{p}}=K^{-1}[\mathbf{p},1{]}^T$.

Find: Essential matrix $E$ satisfying ${\hat{\mathbf{p}}}^{\prime T}E\hat{\mathbf{p}}=0$.

Properties of $E$:

• $E=[t{]}_{\times }R$ where $R$ is the relative rotation and $\mathbf{t}$ is the translation direction
• Has exactly two equal non-zero singular values: ${\sigma }_1={\sigma }_2$, ${\sigma }_3=0$
• 5 degrees of freedom (3 rotation + 2 translation direction)

5-Point Algorithm (Nister)

The minimal solver, producing up to 10 candidate matrices.

Algorithm:

1. Normalize both point sets using Hartley normalization
2. Build $5\times 9$ matrix $A$ (same form as 8-point)
3. Null space: SVD of $A$ gives a 4-dimensional null space. The essential matrix is: $$E=x{\mathbf{e}}_1+y{\mathbf{e}}_2+z{\mathbf{e}}_3+{\mathbf{e}}_4$$ for unknowns $(x,y,z)$, where $\{{\mathbf{e}}_i\}$ are the null space basis vectors
4. Polynomial constraints: The essential matrix constraint $E{E}^{T}E-\frac{1}{2}\text{tr}(E{E}^T)E=0$ (9 equations) and $\det (E)=0$ (1 equation) generate polynomial equations in $(x,y,z)$
5. Action matrix: These constraints are assembled into a polynomial system solved via the eigenvalues of a $10\times 10$ action matrix
6. Extract real solutions: Each real eigenvalue $z$ determines $(x,y)$ and thus $E$

Up to 10 candidate essential matrices may be returned.

Decomposing $E$ into $R,\mathbf{t}$

Given $E=U\text{diag}(\sigma ,\sigma ,0)V^T$, there are 4 possible decompositions:

$$R_1=UW{V}^T,R_2=U{W}^T{V}^T$$ $${\mathbf{t}}_1=+U_3,{\mathbf{t}}_2=-U_3$$

where $W=\left[\begin{array}{ccc}0& -1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]$ and $U_3$ is the third column of $U$.

Chirality check: Of the 4 candidates $(R_i,{\mathbf{t}}_j)$, only one places all triangulated points in front of both cameras. This is verified by triangulating a test point and checking that $Z>0$ in both views.

Coordinate Conventions

The relationship is: $E=K^{\prime T}FK$.

RANSAC

Both solvers have RANSAC wrappers for outlier rejection:

#![allow(unused)]
fn main() {
let (F, inliers) = fundamental_8point_ransac(&pts1, &pts2, &opts)?;
}

Currently, only the 8-point fundamental matrix solver has a RANSAC wrapper. The 5-point essential matrix solver (essential_5point) returns multiple candidates and is used directly.

OpenCV equivalence: cv::findFundamentalMat (8-point and 7-point), cv::findEssentialMat (5-point with RANSAC).

References

• Nister, D. (2004). "An Efficient Solution to the Five-Point Relative Pose Problem." IEEE TPAMI, 26(6), 756-770.
• Hartley, R.I. (1997). "In Defense of the Eight-Point Algorithm." IEEE TPAMI, 19(6), 580-593.