Determination of the Matrices

The Essential Matrix can be obtained in closed form when the relative poses between the sensors are known and, given the intrinsic parameters of the cameras involved, the Fundamental Matrix can be obtained.

The most widespread application of the Essential (or Fundamental) Matrix, however, is to recover the relative pose between the cameras given a set of corresponding points: if the intrinsic parameters are known, the Essential Matrix can be recovered (and the Fundamental Matrix can then be obtained from it); alternatively, the Fundamental Matrix can be recovered without any knowledge of the camera parameters.

The 8-point algorithm

The criterion for obtaining matrix $\mathbf{F}$ can be formalized as the minimization of a cost function

$$\min_\mathbf{F} \sum_{i=1}^n \left( \mathbf{p}^{\top}_{2,i} \mathbf{ F } \mathbf{p}_{1,i} \right)^2$$ (10.52)

subject to additional constraints, this time concerning the structure of $\mathbf{F}$.

It can be observed that the epipolar constraint (10.48) can also be rewritten as

$$(\mathbf{p}_1 \otimes \mathbf{p}_2)^{\top} \operatorname{vec}(\mathbf{F}) = 0$$ (10.53)

by exploiting the compact notation provided by the Kronecker product $\otimes$^10.3, or alternatively

$$\mathbf{u}_i \mathbf{f} = 0$$ (10.54)

in more explicit form, by defining

$$\begin{array}{rl} \left( \mathbf{p}_1 \otimes \mathbf{p}_2 \... ...,3} , f_{3,1} , f_{3,2} , f_{3,3} \right)^{\top} \end{array}$$ (10.55)

where $\mathbf{p}_{1,i}=(x_1,y_1,1)^\top$ and $\mathbf{p}_{2,i}=(x_2,y_2,1)^\top$ are expressed in normalized homogeneous coordinates. With this formulation, it is possible to highlight a technique for obtaining the elements of $\mathbf{F}$ as the solution of a homogeneous linear system formed by constraints such as the one in equation (10.54).

After collecting all the constraints $\mathbf{u}_i$, one obtains a homogeneous system of the form

$$\mathbf{U} \mathbf{f} = 0$$ (10.56)

with $n$ equations in 9 unknowns.

The procedure for obtaining the Essential Matrix is analogous: it is the solution of a system $\mathbf{n}_i \mathbf{e}=0$ of the form

$$\begin{array}{l} \mathbf{n}_i = ( x_{1} x_{2}, y_{1} x_{2... ..._{2,2} , e_{2,3} , e_{3,1} , e_{3,2} , e_{3,3} ) \end{array}$$ (10.57)

with $\mathbf{m}_{1,i}=(x_1,y_1,z_1)$ and $\mathbf{m}_{2,i}=(x_2,y_2,z_2)$. Including all the constraints $\mathbf{n}_i$, this is a homogeneous system of the form

$$\mathbf{N} \mathbf{e} = 0$$ (10.58)

In fact, when homogeneous coordinates are used, systems (10.55) and (10.57) are algorithmically equivalent.

An additional constraint must always be added to the constraints expressed in these homogeneous systems, for example $\Vert \mathbf{f} \Vert =1$, which is normally already satisfied by linear homogeneous-system solvers. This algorithm is therefore called the eight-point algorithm, since at least 8 points are required to determine the solution. Additional constraints needed to attain the actual degrees of freedom of the matrices cannot, however, be expressed in linear form.

Constraint enforcement

Because of noise, the matrices obtained from the linear system normally do not satisfy the requirement of having rank 2 and, in the case of the Essential Matrix, do not satisfy the constraint that two singular values be equal and the third zero.

One possible solution to this problem is to seek the matrix closest to the one returned by the linear system that nevertheless satisfies the rank constraint. This result can be obtained, for example, using an SVD decomposition followed by reconstruction, as suggested by Tsai, Huang, and Hartley:

$$\begin{array}{rl} \mathbf{F} &= \mathbf{U}\diag (r,s,t)\ma... ...bf{F}' &= \mathbf{U}\diag (r,s,0)\mathbf{V}^{\top} \end{array}$$ (10.59)

This procedure is called constraint enforcement. Compared with the Fundamental Matrix, the Essential Matrix has the additional constraint that its two nonzero singular values must be equal. Denoting by

$$\mathbf{E} = \mathbf{U}\diag (r,s,t)\mathbf{V}^{\top}$$ (10.60)

the SVD decomposition of the estimate obtained, the admissible Essential Matrix closest in the Frobenius norm is

$$\mathbf{E}' = \mathbf{U} \diag \!\left( \frac{r+s}{2}, \frac{r+s}{2}, 0 \right) \mathbf{V}^{\top}.$$ (10.61)

Since the Essential Matrix is defined up to a scale factor, it is often normalized in the form

$$\mathbf{E}' = \mathbf{U} \diag (1,1,0) \mathbf{V}^{\top},$$ (10.62)

known as the normalized Essential Matrix.

The Essential Matrix generated through equation (10.59) satisfies the cubic trace-constraint (Demazure, 1988)

$$\mathbf{E}\mathbf{E}^{\top} \mathbf{E} - \frac{1}{2} \trace \left( \mathbf{E}\mathbf{E}^{\top} \right) \mathbf{E} = 0$$ (10.63)

This constraint is a necessary condition for the matrix under analysis to be an Essential Matrix.

The matrices obtained through this enforcement procedure satisfy all the requirements for being Fundamental or Essential Matrices, but they do not represent an algebraic, let alone geometric, minimization of the original constraints.

The 7-point algorithm

Algorithms that use fewer than 8 points to extract an Essential or Fundamental Matrix are all based more or less on the same principle: the multidimensional kernel of $\mathbf{U}$ or $\mathbf{N}$ is extracted, since the Fundamental or Essential Matrix must belong to an element of this space, and some constraints specific to the problem are enforced.

In the nonlinear case, it is relatively easy to obtain a Fundamental Matrix from only 7 points, given that matrix $\mathbf{U}$, formed from the elements of equation (10.55), must have rank 7, since the Fundamental Matrix has 7 degrees of freedom. Solving system (10.55) formed from at least 7 points yields a two-dimensional subspace, spanned by two basis vectors $\mathbf{f}_1$ and $\mathbf{f}_2$, to which two matrices $\mathbf{F}_1$ and $\mathbf{F}_2$ are associated: within the space of possible solutions, it is necessary to find a matrix $\mathbf{F} = \alpha \mathbf{F}_1 + (1 - \alpha) \mathbf{F}_2$ having rank 2, that is, by imposing $\det \mathbf{F} = 0$, a third-degree nonlinear equation in $\alpha$. In this case, the real solutions of $\alpha$ may number 1 or 3; when there are 3 real solutions, all three must be evaluated on the data to identify the most plausible one.

The 5-point algorithm

With fewer than 7 points, only algorithms for determining the Essential Matrix exist. The Essential Matrix has only 5 degrees of freedom and can therefore, in theory, be estimated by analyzing correspondences between just 5 points (Nis04). The 5-point algorithm is in fact the standard method for estimating the Essential Matrix; its implementation, however, is extremely complex.

Using only 5 correspondences, matrix $\mathbf{N}$ of system (10.58) has rank 5, and therefore its null space has dimension 4. The Essential Matrix must therefore be formed as a linear combination of the last 4 columns of matrix $V$ obtained from the SVD, namely:

$$\mathbf{E} = x \mathbf{X} + y \mathbf{Y} + z \mathbf{Z} + \mathbf{W}$$ (10.64)

where $\left(\mathbf{X}, \mathbf{Y}, \mathbf{Z}, \mathbf{W}\right)$ are the last 4 columns of the eigenvector matrix $V$ and $(x,y,z)$ are unknowns. To determine these unknowns, it is necessary to satisfy the constraints

$$\begin{array}{l} \det \mathbf{E} = 0 \\ \mathbf{E}\mathbf... ...thbf{E}\mathbf{E}^{\top} \right) \mathbf{E} = 0 \\ \end{array}$$ (10.65)

which is equivalent to a system of 10 third-degree polynomials in the 3 unknowns.

The need to solve a nonlinear system nevertheless reduces the advantages over the solutions proposed in section 10.4.2.

System conditioning

Generating the Essential and Fundamental Matrices through SVD and subsequently enforcing their constraints by forcing the singular values to be equal is highly sensitive to noise.

Matrix (10.55) is ill-conditioned: this occurs when one attempts to solve a linear system whose known terms contain numbers with different orders of magnitude. The method proposed by Hartley (Har95) improves the solution by normalizing the point coordinates.

Coordinates $\mathbf {p}_1$ and $\mathbf {p}_2$ are translated separately so that their centroid is zero and rescaled so that their mean value is $1$ (or $\sqrt{2}$, the mean magnitude) in the new coordinate systems $\tilde{\mathbf{p}}_1$ and $\tilde{\mathbf{p}}_2$, respectively. We therefore define two transformation matrices $\mathbf{T}_1$ and $\mathbf{T}_2$ such that

$$\begin{array}{l} \tilde{\mathbf{p}}_1 = \mathbf{T}_1 \math... ...ilde{\mathbf{p}}_2 = \mathbf{T}_2 \mathbf{p}_2 \\ \end{array}$$ (10.66)

thus making it possible to determine the compatible Fundamental Matrix $\tilde{\mathbf{F}}$

$$\mathbf{p}^{\top}_{2} \mathbf{ F } \mathbf{p}_1 = \tilde{\m... ...thbf{p}}_2^{\top} \tilde{\mathbf{F}} \tilde{\mathbf{p}}_1 = 0$$ (10.67)

from which the original matrix $\mathbf{F} = \mathbf{T}^{\top}_2 \tilde{\mathbf{F}} \mathbf{T}_1$ can then be recovered.

Footnotes

...#tex2html_wrap_inline17666#^10.3

For convenience, here $\operatorname{vec}(\mathbf F)$ denotes the row-by-row vectorization of the matrix.