Eight-point algorithm

The eight-point algorithm is an algorithm used in computer vision to estimate the essential matrix or the fundamental matrix related to a stereo camera pair from a set of corresponding image points. It was introduced by Christopher Longuet-Higgins in 1981 for the case of the essential matrix. In theory, this algorithm can be used also for the fundamental matrix, but in practice the normalized eight-point algorithm, described by Richard Hartley in 1997, is better suited for this case.
The algorithm's name derives from the fact that it estimates the essential matrix or the fundamental matrix from a set of eight (or more) corresponding image points. However, variations of the algorithm can be used for fewer than eight points.
Coplanarity constraint.
One may express the epipolar geometry of two cameras and a point in space with an algebraic equation. Observe that, no matter where the point formula_1 is in space, the vectors formula_2, formula_3 and formula_4 belong to the same plane. Call formula_5 the coordinates of point formula_1 in the left eye's reference frame and call formula_7 the coordinates of formula_1 in the right eye's reference frame and call formula_9 the rotation and translation between the two reference frames s.t. formula_10 is the relationship between the coordinates of formula_1 in the two reference frames. The following equation always holds because the vector generated from formula_12 is orthogonal to both formula_13 and formula_5 :
Because formula_16, we get 
Replacing formula_18 with formula_19, we get
Observe that formula_21 may be thought of as a matrix; Longuet-Higgins used the symbol formula_22 to denote it. The product formula_23 is often called essential matrix and denoted with formula_24.
The vectors formula_25 are parallel to the vectors formula_26 and therefore the coplanarity constraint holds if we substitute these vectors. If we call formula_27 the coordinates of the projections of formula_1 onto the left and right image planes, then the coplanarity constraint may be written as
Basic algorithm.
The basic eight-point algorithm is here described for the case of estimating the essential matrix formula_30. It consists of three steps. First, it formulates a homogeneous linear equation, where the solution is directly related to formula_30, and then solves the equation, taking into account that it may not have an exact solution. Finally, the internal constraints of the resulting matrix are managed. The first step is described in Longuet-Higgins' paper, the second and third steps are standard approaches in estimation theory.
The constraint defined by the essential matrix formula_30 is
for corresponding image points represented in normalized image coordinates formula_34. The problem which the algorithm solves is to determine formula_30 for a set of matching image points. In practice, the image coordinates of the image points are affected by noise and the solution may also be over-determined which means that it may not be possible to find formula_30 which satisfies the above constraint exactly for all points. This issue is addressed in the second step of the algorithm.
Step 1: Formulating a homogeneous linear equation.
With
the constraint can also be rewritten as
or
where
that is, formula_44 represents the essential matrix in the form of a 9-dimensional vector and this vector must be orthogonal to the vector formula_45 which can be seen as a vector representation of the formula_46 matrix formula_47.
Each pair of corresponding image points produces a vector formula_45. Given a set of 3D points formula_49 this corresponds to a set of vectors formula_50 and all of them must satisfy
for the vector formula_44. Given sufficiently many (at least eight) linearly independent vectors formula_50 it is possible to determine formula_44 in a straightforward way. Collect all vectors formula_50 as the columns of a matrix formula_56 and it must then be the case that
This means that formula_44 is the solution to a homogeneous linear equation.
Step 2: Solving the equation.
A standard approach to solving this equation implies that formula_44 is a left singular vector of formula_56 corresponding to a singular value that equals zero. Provided that at least eight linearly independent vectors formula_50 are used to construct formula_56 it follows that this singular vector is unique (disregarding scalar multiplication) and, consequently, formula_44 and then formula_30 can be determined.
In the case that more than eight corresponding points are used to construct formula_56 it is possible that it does not have any singular value equal to zero. This case occurs in practice when the image coordinates are affected by various types of noise. A common approach to deal with this situation is to describe it as a total least squares problem; find formula_44 which minimizes
when formula_68. The solution is to choose formula_44 as the left singular vector corresponding to the "smallest" singular value of formula_56. A reordering of this formula_44 back into a formula_46 matrix gives the result of this step, here referred to as formula_73.
Step 3: Enforcing the internal constraint.
Another consequence of dealing with noisy image coordinates is that the resulting matrix may not satisfy the internal constraint of the essential matrix, that is, two of its singular values are equal and nonzero and the other is zero. Depending on the application, smaller or larger deviations from the internal constraint may or may not be a problem. If it is critical that the estimated matrix satisfies the internal constraints, this can be accomplished by finding the matrix formula_74 of rank 2 which minimizes
where formula_73 is the resulting matrix from Step 2 and the Frobenius matrix norm is used. The solution to the problem is given by first computing a singular value decomposition of formula_73:
where formula_79 are orthogonal matrices and formula_80 is a diagonal matrix which contains the singular values of formula_73. In the ideal case, one of the diagonal elements of formula_80 should be zero, or at least small compared to the other two which should be equal. In any case, set
where formula_84 are the largest and second largest singular values in formula_80 respectively. Finally, formula_74 is given by
The matrix formula_74 is the resulting estimate of the essential matrix provided by the algorithm.
Normalized algorithm.
The basic eight-point algorithm can in principle be used also for estimating the fundamental matrix formula_89. The defining constraint for formula_89 is
where formula_34 are the homogeneous representations of corresponding image coordinates (not necessary normalized). This means that it is possible to form a matrix formula_56 in a similar way as for the essential matrix and solve the equation
for formula_95 which is a reshaped version of formula_89. By following the procedure outlined above, it is then possible to determine formula_89 from a set of eight matching points. In practice, however, the resulting fundamental matrix may not be useful for determining epipolar constraints.
Difficulty.
The problem is that the resulting formula_56 often is ill-conditioned. In theory, formula_56 should have one singular value equal to zero and the rest are non-zero. In practice, however, some of the non-zero singular values can become small relative to the larger ones. If more than eight corresponding points are used to construct formula_56, where the coordinates are only approximately correct, there may not be a well-defined singular value which can be identified as approximately zero. Consequently, the solution of the homogeneous linear system of equations may not be sufficiently accurate to be useful.
Cause.
Hartley addressed this estimation problem in his 1997 article. His analysis of the problem shows that the problem is caused by the poor distribution of the homogeneous image coordinates in their space, formula_101. A typical homogeneous representation of the 2D image coordinate formula_102 is
where both formula_104 lie in the range 0 to 1000–2000 for a modern digital camera. This means that the first two coordinates in formula_105 vary over a much larger range than the third coordinate. Furthermore, if the image points which are used to construct formula_56 lie in a relatively small region of the image, for example at formula_107, again the vector formula_105 points in more or less the same direction for all points. As a consequence, formula_56 will have one large singular value and the remaining are small.
Solution.
As a solution to this problem, Hartley proposed that the coordinate system of each of the two images should be transformed, independently, into a new coordinate system according to the following principle.
This principle results, normally, in a distinct coordinate transformation for each of the two images. As a result, new homogeneous image coordinates formula_111 are given by
where formula_114 are the transformations (translation and scaling) from the old to the new "normalized image coordinates". This normalization is only dependent on the image points which are used in a single image and is, in general, distinct from normalized image coordinates produced by a normalized camera.
The epipolar constraint based on the fundamental matrix can now be rewritten as
where formula_116. This means that it is possible to use the normalized homogeneous image coordinates formula_111 to estimate the transformed fundamental matrix formula_118 using the basic eight-point algorithm described above.
The purpose of the normalization transformations is that the matrix formula_119, constructed from the normalized image coordinates, in general, has a better condition number than formula_56 has. This means that the solution formula_121 is more well-defined as a solution of the homogeneous equation formula_122 than formula_95 is relative to formula_56. Once formula_121 has been determined and reshaped into formula_118 the latter can be "de-normalized" to give formula_89 according to
In general, this estimate of the fundamental matrix is a better one than would have been obtained by estimating from the un-normalized coordinates.
Using fewer than eight points.
Each point pair contributes with one constraining equation on the element in formula_30. Since formula_30 has five degrees of freedom it should therefore be sufficient with only five point pairs to determine formula_30. Though possible from a theoretical point of view, the practical implementation of this is not straightforward and relies on solving various non-linear equations.
Kaveh Fathian et al. proposed algorithms for five, six and seven points that circumvent the computation of the essential matrix by computing the rotation quaternion directly.