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
  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.