Revision 046a8e93f64d20d6da3745c0acb7098e18fc6f60 (click the page title to view the current version)

Eight-point algorithm (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

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

More (Section 5.2.2-3)