Eight-point algorithm

The two view structure is equivalent to the fundamental matrix. Since the fundamental matrix ${\bf F}$ is a $3 \times 3$ matrix determined up to an arbitrary scale factor, 8 equations are required to obtain a unique solution. The simplest way to compute the fundamental matrix consists of using Equation (3.26). This equation can be rewritten under the following form:

$$\left[ \begin{array}{ccccccccc} x x' & y x' & x' & x y' & y y' & y' & x & y & 1 \end{array} \right] {\bf f} = 0$$ (D6)

with ${\tt m}=[x \, y \, 1]^\top,{\tt m'}=[x' y' 1]^\top$ and ${\bf f}=[F_{11} F_{12} F_{13} F_{21} F_{22} F_{23} F_{31} F_{32} F_{33} ]^\top$ a vector containing the elements of the fundamental matrix ${\bf F}$. By stacking eight of these equations in a matrix ${\bf A}$ the following equation is obtained:

$${\bf A} {\bf f}= 0$$ (D7)

This system of equation is easily solved by Singular Value Decomposition (SVD) [58]. Applying SVD to ${\bf A}$ yields the decomposition ${\bf USV}^\top$ with ${\bf U}$ and ${\bf V}$ orthonormal matrices and ${\bf S}$ a diagonal matrix containing the singular values. These singular values $\sigma_i$ are positive and in decreasing order. Therefore in our case $\sigma_9$ is guaranteed to be identically zero (8 equations for 9 unknowns) and thus the last column of ${\bf V}$ is the correct solution (at least as long as the eight equations are linearly independent, which is equivalent to all other singular values being non-zero).

It is trivial to reconstruct the fundamental matrix ${\bf F}$ from the solution vector ${\bf f}$. However, in the presence of noise, this matrix will not satisfy the rank-2 constraint. This means that there will not be real epipoles through which all epipolar lines pass, but that these will be ``smeared out'' to a small region. A solution to this problem is to obtain ${\bf F}$ as the closest rank-2 approximation of the solution coming out of the linear equations.