Essential Matrix Estimation

1. Background Knowledge

The essential matrix $E$ encodes the relative pose (rotation $R$ and translation $t$, up to scale) between two calibrated cameras. For a 3D point $X$ seen in two views with normalized image coordinates $\mathbf{p}_1,$\mathbf{p}$_2 \in \mathbb{P}^2$, the epipolar constraint is

$$\mathbf{p}_2^T E \mathbf{p}_1 = 0.$$

Geometrically, this says: the point in image 2 lies on the epipolar line obtained by transferring the point from image 1 via $E$.

Algebraically, $E$ has special structure: it can be written as

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

where $[t]_\times$ is the skew-symmetric matrix of translation $t$. This implies rank 2 and two equal non-zero singular values. The 8-point algorithm is a linear method: you stack linear constraints from at least 8 point correspondences into a matrix $A$, solve $A$\mathbf{f}$=0$ (where $\mathbf{f}$ is the vectorized $E$), then project the result onto the space of valid essential matrices (rank-2 constraint via SVD). Normalizing points (centering and scaling) is crucial for numerical stability.

---

2. Algorithm/Approach

General pattern for essential (or fundamental) matrix estimation with the 8-point algorithm:

• Represent the epipolar constraint as a linear equation in the unknown entries of $E$.
• Use multiple point correspondences to build a linear system $A$\mathbf{f}$= 0$.
• Solve for $\mathbf{f}$ as the right singular vector corresponding to the smallest singular value of $A$.
• Reshape $\mathbf{f}$ to a $3 \times 3$ matrix $E$, then enforce the rank-2 constraint via SVD.
• (In practice with RANSAC) repeat on random minimal subsets, score using inliers, and keep the best $E$.

---

3. Step-by-Step Strategy

Assume you are given corresponding normalized image points $\{(x_1, y_1)\} \leftrightarrow \{(x_2, y_2)\}$ in homogeneous coordinates $\mathbf{p}_1 = (x_1, y_1, 1)^T$, $\mathbf{p}_2 = (x_2, y_2, 1)^T$.

a) Normalize points (Hartley-style normalization)

For each image separately:

• Compute centroid $(\bar{x}, \bar{y})$.
• Compute average distance $d$ of points to the centroid.
• Define scale $s =$\sqrt{2}$/ d$.
• Build normalization transform

$$T = \begin{bmatrix} s & 0 & -s\bar{x}\\ 0 & s & -s\bar{y}\\ 0 & 0 & 1 \end{bmatrix}.$$

• Transform points: \tilde{\mathbf{p}} = T \mathbf{p} for both views, giving $T_1, T_2$.

b) Build matrix $A$

For each correspondence (\tilde{\mathbf{p}}_1, \tilde{\mathbf{p}}_2) with coordinates $(x_1, y_1, 1)$ and $(x_2, y_2, 1)$, the epipolar constraint expands to:

$$x_2 x_1 e_{11} + x_2 y_1 e_{12} + x_2 e_{13} + y_2 x_1 e_{21} + y_2 y_1 e_{22} + y_2 e_{23} + x_1 e_{31} + y_1 e_{32} + e_{33} = 0.$$

Create one row of $A$ as:

$$[x_2 x_1,\ x_2 y_1,\ x_2,\ y_2 x_1,\ y_2 y_1,\ y_2,\ x_1,\ y_1,\ 1].$$

• Stack all $N \ge 8$ correspondences into an $N \times 9$ matrix $A$.

c) Solve $A$\mathbf{f}$= 0$ via SVD

• Compute SVD of $A$: $A = U \Sigma V^T$.
• Take $\mathbf{f}$ as the last column of $V$ (corresponding to smallest singular value).
• Reshape $\mathbf{f}$ into a $3 \times 3$ matrix $\tilde{E}$.

d) Enforce rank-2 constraint on $E$

• Compute SVD of $\tilde{E}$: $\tilde{E} = U_E \Sigma_E V_E^T$, with $\Sigma_E =$\text{diag}$(s_1, s_2, s_3)$.
• For an essential matrix, we need $\text{rank}(E)=2$ and two equal non-zero singular values; a simple enforcement is:
• Set $s_3' = 0$.
• Optionally set $s_1' = s_2' = (s_1 + s_2)/2$.
• Form

$$E' = U_E \cdot \text{diag}(s_1', s_2', 0) \cdot V_E^T.$$

e) Denormalize

Because you estimated $\tilde{E}$ on normalized points:

$$E = T_2^T \, E' \, T_1.$$

You now have the essential matrix $E$ relating original (calibrated) image coordinates.

---

4. Common Pitfalls

• Skipping normalization: Leads to very poor numerical stability, especially when coordinates are large (pixel units) or unevenly distributed.
• Using uncalibrated coordinates: The essential matrix assumes points are in normalized camera coordinates (after multiplying pixel coords by $K^{-1}$); otherwise you are really estimating the fundamental matrix instead.
• Too few or degenerate points:
• Need at least 8 non-degenerate correspondences (not all on a plane/line).
• Planar scenes or nearly collinear points can produce unstable or incorrect $E$.
• Incorrect SVD usage:
• Solving $A$\mathbf{f}$=0$: must take the right singular vector corresponding to the smallest singular value.
• Enforcing rank-2: must zero exactly one singular value, not more or less.
• Scale ambiguity: $E$ is defined up to a non-zero scalar; don’t rely on its absolute scale. Any downstream pose decomposition should assume this.
• In RANSAC:
• Use a geometric error (e.g., symmetric epipolar distance) to score inliers.
• Ensure you re-estimate $E$ using all inliers after RANSAC picks the best model.

---

5. Time & Space Complexity

Let $N$ be the number of correspondences.

• Building $A$:

• Time: $O(N)$.

• Space: $O(N)$ for the $N \times 9$ matrix.

• SVD of $A$:

• Since width is constant (9), SVD is $O(N)$ time in practice, with small constant factors.

• Space: $O(N)$ to store $A$ plus $O(1)$ for 9×9 matrices in the reduced SVD.

• SVD of $E$ (3×3):

• Time: $O(1)$.

• Space: $O(1)$.

Overall, time complexity is linear in the number of correspondences, $O(N)$, and space complexity is $O(N)$, dominated by storing $A$ and the input matches. In RANSAC, you multiply this by the number of iterations, but each iteration still works on constant-sized subsets for the hypothesis step.