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.
One may express the epipolar geometry of two cameras and a point in space with an algebraic equation.
onto the left and right image planes, then the coplanarity constraint may be written as The basic eight-point algorithm is here described for the case of estimating the essential matrix
First, it formulates a homogeneous linear equation, where the solution is directly related to
, 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.
Each pair of corresponding image points produces a vector
it follows that this singular vector is unique (disregarding scalar multiplication) and, consequently,
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
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.
The solution to the problem is given by first computing a singular value decomposition of
is the resulting estimate of the essential matrix provided by the algorithm.
The basic eight-point algorithm can in principle be used also for estimating the fundamental matrix
are the homogeneous representations of corresponding image coordinates (not necessary normalized).
in a similar way as for the essential matrix and solve the equation for
In practice, however, the resulting fundamental matrix may not be useful for determining epipolar constraints.
In practice, however, some of the non-zero singular values can become small relative to the larger ones.
Consequently, the solution of the homogeneous linear system of equations may not be sufficiently accurate to be useful.
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.
are the transformations (translation and scaling) from the old to the new normalized image coordinates.
The epipolar constraint based on the fundamental matrix can now be rewritten as where
, constructed from the normalized image coordinates, in general, has a better condition number than
Each point pair contributes with one constraining equation on the element in
has five degrees of freedom it should therefore be sufficient with only five point pairs to determine
David Nister proposed an efficient solution to estimate the essential matrix from set of five paired points, known as the five-point algorithm.
