Revision 40066463c55876a006b6a80a1c199385f4f15a3e (click the page title to view the current version)

Eight-point algorithm Lecture

Changes from 40066463c55876a006b6a80a1c199385f4f15a3e to da3b05b1224de00d36215968811f2f2051d35006

---
title: Eight-point algorithm (Lecture)
categories: lecture
---

# Eight-Point Algorithm

**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
+ need eight pairs of points to solve uniquely up to a scalar factor
+ the scalar factor cannot be avoided

## 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]$$

+ 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$.
    + sometimes called the *fundamental matrix*
+ 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 (Section 5.2.2)

+ Depth scales $\lambda_1,\lamda_2$ (for each object point)
+ 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 (Section 5.2.3)

Noise is everywhere

+ error in $(R,T)$
+ no consistent 3D reconstruction from noisy image points

- in the epipolar constraint: ideal co-ordinates
- measurements: only noisy co-ordinates