Determination of Matrices

The Essential matrix can be derived in closed form by knowing the relative poses between the sensors, and with the knowledge of the intrinsic parameters of the involved cameras, it is possible to obtain the Fundamental matrix.

The most widespread application of the Essential (or Fundamental) matrix is to derive the relative pose between cameras, given a set of corresponding points. By knowing the intrinsic parameters, one can obtain the Essential matrix (and from this, derive the Fundamental matrix), or alternatively, one can derive the Fundamental matrix without any knowledge of the camera parameters.

Eight-Point Algorithm

The criterion for obtaining the matrix $\mathbf{F}$ can be formalized as a 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$$ (9.48)

under additional constraints that pertain this time to the structure of $\mathbf{F}$.

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

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

by utilizing the compact syntax provided by the Kronecker product $\otimes$ or alternatively

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

in a 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}$$ (9.51)

with $\mathbf{p}_{1,i}=(x_1,y_1)$ and $\mathbf{p}_{2,i}=(x_2,y_2)$. With this formalism, it is possible to highlight a technique that allows the derivation of the elements of $\mathbf{F}$ as the solution to a homogeneous linear system formed by constraints as in equation (9.50).

Collecting all the constraints $\mathbf{u}_i$, we obtain a homogeneous system of the form

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

consisting of $n$ equations in 9 unknowns.

To derive the Essential matrix, the discussion is analogous and it is the solution of a system $\mathbf{n}_i \mathbf{e}=0$ in 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}$$ (9.53)

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

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

. In fact, by using homogeneous coordinates, the systems (9.51) and (9.53) are algorithmically equivalent.

To the constraints expressed in these homogeneous systems, an additional one must always be added, for example $\Vert \mathbf{f} \Vert =1$, which is typically already satisfied by linear solvers of homogeneous systems. This algorithm is therefore referred to as the eight-point algorithm since the solution to the problem requires at least 8 points to be determined. Additional constraints, in order to achieve the actual degrees of freedom of the matrices, cannot be expressed in linear form.

Strengthening of Constraints

Due to noise, the matrices obtained from the linear system typically do not meet the requirement of having rank 2 (and in the case of the Essential matrix, therefore having a large number of degrees of freedom, which do not belong precisely to the subspace of Essential matrices). A possible solution to this problem is to search for the matrix that is closest to the one returned by the linear system while still satisfying the rank constraint. This result can be achieved, for example, by using an SVD decomposition followed by a composition, 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}$$ (9.55)

This procedure is referred to as constraint enforcement. The Essential matrix, in contrast to the Fundamental matrix, has the additional constraint of having its two non-zero singular values equal:

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

If the singular values (following an SVD) of the matrix are 1, the matrix is referred to as a normalized essential matrix. The Essential matrix obtained by setting $\mathbf{D}' = \diag (1, 1, 0)$ is the normalized essential matrix closest to the given one, in accordance with the Frobenius norm. The Essential matrix generated through equation (9.56) 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$$ (9.57)

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

The matrices obtained through this reinforcement procedure satisfy all the requirements to be considered Fundamental or Essential matrices, but they do not represent an algebraic minimization, nor a geometric one, of the original constraints.

Seven-Point Algorithm

Algorithms that utilize fewer than 8 points to extract an Essential or Fundamental matrix are largely based 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 certain typical constraints of the problem at hand are enforced.

In a nonlinear manner, it is relatively easy to obtain a Fundamental matrix with only 7 points, considering that the matrix $\mathbf{U}$, formed by the elements of equation (9.51), must be of rank 7, as there are indeed 7 degrees of freedom in the Fundamental matrix.

By solving the system (9.51) formed by (at least) 7 points, a subspace of dimension 2 is obtained, consisting of two bases $\mathbf{f}_1$ and $\mathbf{f}_2$, to which two matrices $\mathbf{F}_1$ and $\mathbf{F}_2$ are associated: in the space of possible solutions, it is necessary to find a matrix $\mathbf{F} = \alpha \mathbf{F}_1 + (1 - \alpha) \mathbf{F}_2$ such that it has rank 2, which is achieved by imposing $\det \mathbf{F} = 0$, a nonlinear third-degree equation in $\alpha$.

In this case, the real solutions of $\alpha$ can be either 1 or 3: in the case of 3 real solutions, all three must be evaluated against the data to identify the most plausible one.

Five-Point Algorithm

With fewer than 7 points, there are only algorithms available to determine the Essential matrix. The Essential matrix is indeed composed of only 5 degrees of freedom and can theoretically be estimated through the analysis of correspondences among just 5 points (Nis04). The five-point algorithm is essentially the standard for estimating the essential matrix; however, its implementation is extremely complex.

Utilizing only 5 correspondences, the matrix $\mathbf{N}$ of the system (9.54) has a rank deficiency of 4. Therefore, the Essential matrix must be formed as a linear combination of the last 4 columns of the matrix $V$ obtained from the SVD, namely:

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

where $\left(\mathbf{X}, \mathbf{Y}, \mathbf{Z}, \mathbf{W}\right)$ represents the last 4 columns of eigenvectors of the matrix $V$ and $(x,y,z)$ are the unknowns. To obtain 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}$$ (9.59)

which is equivalent to a problem of 10 cubic polynomials in the 3 unknowns.

The request to solve a non-linear system, however, diminishes the advantages compared to the solutions proposed in section 9.4.2.

System Conditioning

The generation of the Essential and Fundamental matrices through the SVD technique, followed by the regularization of these matrices by enforcing the singular values to be equal, is a process that is highly sensitive to noise.

The matrix (9.51) is ill-conditioned: this occurs when attempting to solve a linear system where the known terms consist of numbers with differing orders of magnitude. The method proposed by Hartley (Har95) suggests improving the solution by normalizing the coordinates of the points.

The coordinates $\mathbf {p}_1$ and $\mathbf {p}_2$ are translated separately to achieve a zero centroid and rescaled to have an average value of $1$ (or $\sqrt{2}$ as the average value of the modulus) 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}$$ (9.60)

.

In this way, it is 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$$ (9.61)

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