# Eight-point algorithm (Lecture)

# 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

**Reading** Ma (2004) Section 5.2.3

- 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**- Maximum likelihood
- 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.