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.

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. 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 P is in space, the vectors \overline{O_L P} , \overline{O_R P} and \overline{O_R O_L} belong to the same plane. Call X_L the coordinates of point P in the left eye's reference frame and call X_R the coordinates of P in the right eye's reference frame and call R, T the rotation and translation between the two reference frames s.t. X_R = R (X_L-T) is the relationship between the coordinates of P in the two reference frames. The following equation always holds because the vector generated from T \wedge X_L is orthogonal to both T and X_L : X_L^T T \wedge X_L - T^T T \wedge X_L = (X_L-T)^T T \wedge X_L = 0 Because I = R^T R , we get (X_L-T)^T R^T R T \wedge X_L = 0 . Replacing (X_L-T)^TR^T with X_R^T , we get X_R^T R T \wedge X_L = X_R^T R S X_L = X_R^T E X_L = 0 Observe that T \wedge may be thought of as a matrix; Longuet-Higgins used the symbol S to denote it. The product R T \wedge = R S is often called essential matrix and denoted with E . The vectors \overline{O_L p_L}, \overline{O_R p_R} are parallel to the vectors \overline{O_L P}, \overline{O_R P} and therefore the coplanarity constraint holds if we substitute these vectors. If we call y, y' the coordinates of the projections of P onto the left and right image planes, then the coplanarity constraint may be written as y'^T \mathbf{E} y = 0 (\mathbf{y}')^{T} \, \mathbf{E} \, \mathbf{y} = 0 for corresponding image points represented in normalized image coordinates \mathbf{y}, \mathbf{y}' . The problem which the algorithm solves is to determine \mathbf{E} 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 \mathbf{E} which satisfies the above constraint exactly for all points. This issue is addressed in the second step of the algorithm. \mathbf{y} = \begin{pmatrix} y_{1} \\ y_{2} \\ 1 \end{pmatrix}   and   \mathbf{y}' = \begin{pmatrix} y'_{1} \\ y'_{2} \\ 1 \end{pmatrix}   and   \mathbf{E} = \begin{pmatrix} e_{11} & e_{12} & e_{13} \\ e_{21} & e_{22} & e_{23} \\ e_{31} & e_{32} & e_{33} \end{pmatrix} the constraint can also be rewritten as y'_1 y_1 e_{11} + y'_1 y_2 e_{12} + y'_1 e_{13} + y'_2 y_1 e_{21} + y'_2 y_2 e_{22} + y'_2 e_{23} + y_1 e_{31} + y_2 e_{32} + e_{33} = 0 \, or \mathbf{e} \cdot \tilde{\mathbf{y}} = 0 where \tilde{\mathbf{y}} = \begin{pmatrix} y'_1 y_1 \\ y'_1 y_2 \\ y'_1 \\ y'_2 y_1 \\ y'_2 y_2 \\ y'_2 \\ y_1 \\ y_2 \\ 1 \end{pmatrix}   and   \mathbf{e} = \begin{pmatrix} e_{11} \\ e_{12} \\ e_{13} \\ e_{21} \\ e_{22} \\ e_{23} \\ e_{31} \\ e_{32} \\ e_{33} \end{pmatrix} that is, \mathbf{e} represents the essential matrix in the form of a 9-dimensional vector and this vector must be orthogonal to the vector \tilde{\mathbf{y}} which can be seen as a vector representation of the 3 \times 3 matrix \mathbf{y}' \, \mathbf{y}^{T} . Each pair of corresponding image points produces a vector \tilde{\mathbf{y}} . Given a set of 3D points \mathbf{P}_k this corresponds to a set of vectors \tilde{\mathbf{y}}_{k} and all of them must satisfy \mathbf{e} \cdot \tilde{\mathbf{y}}_{k} = 0 for the vector \mathbf{e} . Given sufficiently many (at least eight) linearly independent vectors \tilde{\mathbf{y}}_{k} it is possible to determine \mathbf{e} in a straightforward way. Collect all vectors \tilde{\mathbf{y}}_{k} as the columns of a matrix \mathbf{Y} and it must then be the case that \mathbf{e}^{T} \, \mathbf{Y} = \mathbf{0} This means that \mathbf{e} is the solution to a homogeneous linear equation. when \| \mathbf{e} \| = 1 . The solution is to choose \mathbf{e} as the left singular vector corresponding to the smallest singular value of \mathbf{Y} . A reordering of this \mathbf{e} back into a 3 \times 3 matrix gives the result of this step, here referred to as \mathbf{E}_{\rm est} . \mathbf{E}_{\rm est} = \mathbf{U} \, \mathbf{S} \, \mathbf{V}^{T} where \mathbf{U}, \mathbf{V} are orthogonal matrices and \mathbf{S} is a diagonal matrix which contains the singular values of \mathbf{E}_{\rm est} . In the ideal case, one of the diagonal elements of \mathbf{S} should be zero, or at least small compared to the other two which should be equal. In any case, set \mathbf{S}' = \begin{pmatrix} s_1 & 0 & 0 \\ 0 & s_2 & 0 \\ 0 & 0 & 0 \end{pmatrix} , where s_1, s_2 are the largest and second largest singular values in \mathbf{S} respectively. Finally, \mathbf{E}' is given by \mathbf{E}' = \mathbf{U} \, \mathbf{S}' \, \mathbf{V}^{T} The matrix \mathbf{E}' is the resulting estimate of the essential matrix provided by the algorithm. (\mathbf{y}')^{T} \, \mathbf{F} \, \mathbf{y} = 0 where \mathbf{y}, \mathbf{y}' are the homogeneous representations of corresponding image coordinates (not necessary normalized). This means that it is possible to form a matrix \mathbf{Y} in a similar way as for the essential matrix and solve the equation \mathbf{f}^{T} \, \mathbf{Y} = \mathbf{0} for \mathbf{f} which is a reshaped version of \mathbf{F} . By following the procedure outlined above, it is then possible to determine \mathbf{F} from a set of eight matching points. In practice, however, the resulting fundamental matrix may not be useful for determining epipolar constraints. \mathbf{y} = \begin{pmatrix} y_{1} \\ y_{2} \\ 1 \end{pmatrix} where both y_{1}, y_{2} \, lie in the range 0 to 1000–2000 for a modern digital camera. This means that the first two coordinates in \mathbf{y} vary over a much larger range than the third coordinate. Furthermore, if the image points which are used to construct \mathbf{Y} lie in a relatively small region of the image, for example at (700,700) \pm (100,100) \, , again the vector \mathbf{y} points in more or less the same direction for all points. As a consequence, \mathbf{Y} will have one large singular value and the remaining are small. \mathbf{\bar y} = \mathbf{T} \, \mathbf{y} \mathbf{\bar y}' = \mathbf{T}' \, \mathbf{y}' where \mathbf{T}, \mathbf{T}' 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 0 = (\mathbf{\bar y}')^{T} \, ((\mathbf{T}')^{T})^{-1} \, \mathbf{F} \, \mathbf{T}^{-1}\, \mathbf{\bar y} = (\mathbf{\bar y}')^{T} \, \mathbf{\bar F} \, \mathbf{\bar y} where \mathbf{\bar F} = ((\mathbf{T}')^{T})^{-1} \, \mathbf{F} \, \mathbf{T}^{-1} . This means that it is possible to use the normalized homogeneous image coordinates \mathbf{\bar y}, \mathbf{\bar y}' to estimate the transformed fundamental matrix \mathbf{\bar F} using the basic eight-point algorithm described above. The purpose of the normalization transformations is that the matrix \mathbf{\bar Y} , constructed from the normalized image coordinates, in general, has a better condition number than \mathbf{Y} has. This means that the solution \mathbf{\bar f} is more well-defined as a solution of the homogeneous equation \mathbf{\bar Y} \, \mathbf{\bar f} than \mathbf{f} is relative to \mathbf{Y} . Once \mathbf{\bar f} has been determined and reshaped into \mathbf{\bar F} the latter can be de-normalized to give \mathbf{F} according to \mathbf{F} = (\mathbf{T}')^{T} \, \mathbf{\bar F} \, \mathbf{T} In general, this estimate of the fundamental matrix is a better one than would have been obtained by estimating from the un-normalized coordinates.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371816413 under CC BY-SA 4.0; modifications have been made.