Eight-point algorithm on arvau

Wikipedia / 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 :

, we get

is often called essential matrix.

onto the left and right image planes, then the coplanarity constraint may be written as

Basic algorithm

. It consists of three steps. First, it formulates a homogeneous linear equation, 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.

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 equationhomogeneous linear equation

With

and and

the constraint can also be rewritten as

where

and all of them must satisfy

and it must then be the case that

is the solution to a homogeneous linear equation.

Step 2: Solving the equation

is a right singular vector corresponding to a singular value it follows that this singular vector is unique (disregarding scalar multiplication can be determined.

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 which minimizes

as the left singular vector corresponding to the smallest.

Step 3: Enforcing the internal constraint

of rank 2 which minimizes

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:

is a diagonal matrix should be zero, or at least small compared to the other two which should be equal. In any case, set

is given by

is the resulting estimate of the essential matrix provided by the algorithm.

Normalized algorithm

in a similar way as for the essential matrix and solve the equation

from a set of eight matching points. In practice, however, the resulting fundamental matrix may not be useful for determining epipolar constraints.

Difficulty

often is ill-conditioned, 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

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.

The origin of the new coordinate system should be centered (have its origin) at the centroid (center of gravity) of the image points. This is accomplished by a translation of the original origin to the new one.
.

are given by

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

using the basic eight-point algorithm described above.

the latter can be de-normalized 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

. David Nister proposed an efficient solution to estimate the essential matrix from set of five paired points, known as the five-point algorithm. Hartley et al. later proposed a modified and more stable five-point algorithm based on Nister's algorithm.