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