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 is in space, the vectors , and belong to the same plane. Call the coordinates of point in the left eye's reference frame and call the coordinates of in the right eye's reference frame and call the rotation and translation between the two reference frames s.t. is the relationship between the coordinates of in the two reference frames. The following equation always holds because the vector generated from is orthogonal to both and :
Because , we get
.
Replacing with , we get
Observe that may be thought of as a matrix; Longuet-Higgins used the symbol to denote it. The product is often called essential matrix and denoted with .
The vectors are parallel to the vectors and therefore the coplanarity constraint holds if we substitute these vectors. If we call the coordinates of the projections of 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 . It consists of three steps. 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. 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 is
for corresponding image points represented in normalized image coordinates . The problem which the algorithm solves is to determine 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 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
and and
the constraint can also be rewritten as
or
where
and
that is, represents the essential matrix in the form of a 9-dimensional vector and this vector must be orthogonal to the vector which can be seen as a vector representation of the matrix .
Each pair of corresponding image points produces a vector . Given a set of 3D points this corresponds to a set of vectors and all of them must satisfy
for the vector . Given sufficiently many (at least eight) linearly independent vectors it is possible to determine in a straightforward way. Collect all vectors as the columns of a matrix and it must then be the case that
This means that is the solution to a homogeneous linear equation.
Step 2: Solving the equation
A standard approach to solving this equation implies that is a right singular vector of corresponding to a singular value that equals zero. Provided that at least eight linearly independent vectors are used to construct it follows that this singular vector is unique (disregarding scalar multiplication) and, consequently, and then can be determined.
In the case that more than eight corresponding points are used to construct 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 which minimizes
when . The solution is to choose as the left singular vector corresponding to the smallest singular value of . A reordering of this back into a matrix gives the result of this step, here referred to as .