# Eight-Point Algorithm

Input
At least eight pairs of points $$(\mathbf{x}_1,\mathbf{x}_2)$$.
Output
The essential matrix $$E$$ (or rather an estimate)

Epipolar Constraint $\mathbf{x}_2^TE\mathbf{x}_1 = 0$

• we know $$\mathbf{x}_i$$, and want to solve for $$E$$.
• up to nine unknowns
• Eight pairs of points give eight equations
• suffices to solve up to a scalar factor
• the scalar factor cannot be avoided
• Scaling up all distances by the same factor gives the same solution

## Kronecker product

Kronecker product: $$\bigotimes$$

Serialisation of a matrix: $$(\cdot)^s$$

$(\mathbf{x}_1\bigotimes\mathbf{x}_2)^TE^s = 0$

## Preparing for the eight-point algorithm

$\mathbf{a} = \mathbf{x}_1\bigotimes\mathbf{x}_2$

$\chi = [\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n]^T$

• We can solve $$\chi E^s = 0$$ for $$E^s$$.
• With eight points, we have unique solutions up to a scalar factor.
• With additional points, we can minimise the squared errors
• $$\min_E ||\chi E^s||^2$$
• i.e. eigenvector of $$\chi^T\chi$$ of smallest eigenvalue
• The scale ambiguity is intrinsic.
• The distance $$||T||$$ cannot be determined from the images

## Projection onto the essential space

The solution is not necessarily a valid essential matrix, but we can project onto the space of such matrices and correct the sign to get positive determinant.

• Write $$F$$ for the solution of $$\chi E^s=0$$.
• Write $$F = U\Sigma_FV^T$$ for the singular value decomposition
• Use $$E=U\Sigma V^T$$ for the essential matrix, where
• $$\Sigma=\mathsf{diag}(1,1,0)$$

## Recover the transform from the essential matrix

$\begin{cases} (\hat T_1,R_1) &= (UR_Z(+\frac\pi2)\Sigma U^T, UR_Z(+\frac\pi2)V^T) \\ (\hat T_2,R_2) &= (UR_Z(-\frac\pi2)\Sigma U^T, UR_Z(-\frac\pi2)V^T) \end{cases}$ where $R_Z(+\frac\pi2) = \begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ is a rotation by $$\pi/2$$ radians around the $$z$$-axis.

## Four solutions

• Two solutions $$\pm F$$ to the equation $$\chi E^s=0$$
• Two poses from each candidate matrix
• Only one of the four solutions is in front of both cammeras

## Notes

### Number of points.

• $$(R,T)$$ only has five degrees of freedom when $$T$$ is determined up to a scalar factor.
• thus five points suffices in theory
• $$\mathsf{det}(E)=0$$ removes one degree of freedom
• linear algorithm exists for six points

### Requirements

General position We have to assume linear independence in the equation $$\chi E^s=0$$

Sufficient parallax If $$T=0$$, then $$E=0$$, hence the algorithm requires $T\neq0$ The algorithm may work even if $$T=0$$, due to noise, but the resulting estimate for $$T$$ (direction) would be meaningless.

### Variants

• Infinitesimal viewpoint change, see Section 5.4
• Multiple motion, see Chapter 7

### Scale ambiguity (Ma (2004) Section 5.2.2)

• Depth scales $$\lambda_1,\lambda_2$$ (for each object point)
• Motion scale $$\gamma=||T||$$

$\lambda_2^j\mathbf{x}_2^j = \lambda_1^jR\mathbf{x}_2^j + \gamma T$

• Recall that the scale ambiguity is intrinsic
• $$\gamma$$ cannot be determined from the images

# Optimal pose in the presence of noise

• Noise is everywhere
• Two problems
• error in $$(R,T)$$
• no consistent 3D reconstruction from noisy image points
• in the epipolar constraint: ideal co-ordinates
• measurements: only noisy co-ordinates
• Two approaches
1. Maximum likelihood
2. Minimal sum of squared errors
• We only discuss option 2.

## Optimal Pose

Sum of squared errors

$\phi(\mathrm{x},R,T) = \sum_j ||w_1^j||^2 + ||w_2^j||^2 = \sum_j|| \tilde x_1^j-x_1^j||^2 + ||\tilde x_2^j-x_2^j||^2$

Observations $$\tilde x_i^j$$

Independent variables $$x_i^j,R,T$$

Task Minimise $\phi(\mathrm{x},R,T) = \sum_j\sum_{i\in\{1,2\}} ||w_i^j||^2$ under the conditions that $x_2^j\hat TR x_1^j = 0$ and $x_1^{jT}e_3 = 1\quad\text{for } i=1,2, j=1,2,\ldots,n$

• Lagrangian optimisation

## Structure Triangulation

Goal find image point pairs which minimise the reprojection error for that particular object point.