§ 4. Two-View Geometry

Triangulation – as other problems in this tutorial – can be cast as a null-space problem. Let us consider m=u,v,1T, the projection of the 3D point M according to the perspective projection matrix P. Starting from the general projection equation (8) one obtains:

and then, in matrix form:

Hence, one point gives two homogeneous equations. Let us consider now m′=u′,v′,1T, the corresponding point of m in the second image, and let P′ be the second perspective projection matrix. Being both projectio of the same 3D pointr M, the equations provided by m and m′ can be stacked, thereby obtaining a homogeneous linear system of four equations in four unknown (including the last component of M):

The solution is the null-space of the 4×4 coefficient matrix, which muat then have rank three, otherwise only the trivial solution M=0 would be possible. In the presence of noise this rank condition cannot be fulfilled exactly, so a lest squares solution is sought, typically via SVD, as in calibration with DLT. Hartley and Sturm (1997) call this method “linear-eigen”.

This method generalizes to the case of N>2 cameras: each one gives two equations and one ends up with 2⁢N equations in four unknowns.

Triangulation is addressed in more details in (Beardsley et al.,1997; Hartley and Sturm,1997; Hartley and Zisserman,2003).

As the intrinsic parameters are known, we can switch to normalized camera coordinates: m←K-1⁢m (please note that this change of notation will hold throughout this section).

Consider a pair of cameras Pℓ and Pr. Without loss of generality, we can fix the world reference frame onto the first camera, hence:

With this choice, the unknown extrinsic parameters have been made explicit.

If we substitute these two particular instances of the camera projection matrices in Equation (23), we get

in other words, the point mr lies on the line through the points t and R⁢mℓ. In homogeneous coordinates, this can be written as follows:

as the homogeneous line through two points is expressed as their cross product, and a dot product of a point and a line is zero if the point lies on the line.

The cross product of two vectors can be written as a product of a skew-symmetric matrix and a vector. Equation (29) can therefore be equivalently written as

where t× is the skew-symmetric matrix of the vector t. Let us define the essential matrix E:

In summary, the relationship between the corresponding image points mℓ and mr in normalized camera coordinates is the bilinear form:

E encodes only information on the rigid displacement between cameras. It has five degrees of freedom: a 3-D rotation and a 3-D translation direction.

E is singular, since det⁡t×=0, and it is a homogeneous quantity.

If a sufficient number of point correspondences mℓi↔mri is given, we can use Equation (32) to compute the unknown matrix E (see Sec. 4.5.2).

The reconstruction is achieved starting from the essential matrix, which contains – entangled – the unknown extrinsic parameters.

Unlike the fundamental matrix, the only property of which is to have rank two, the essential matrix is characterised by the following theorem (Huang and Faugeras,1989).

Proof. Let E=S⁢R where R is a rotation matrix and S is skew-symmetric. Let S=t× where t=1. Then

Let U the orthogonal matrix such that U⁢t=0,0,1T. Then

The elements of the diagonal matrix are the eigenvalues of E⁢ET i.e., the singular values of E. This demonstrate one implication.

Let us now give a constructive proof of the converse. Let E=U⁢D⁢VT be the SVD of E, with D=diag⁢1,1,0 (with no loss of generality, since E is defined up to a scale factor) and U and V orthogonal. The key observation is that

where S′ is skew symmetric and R′ a rotation. Hence

Q.E.D.

This factorization is not unique. Because of homogeneity of E, we can change its sign, either by changing the sign of S′ or by taking the transpose of R′ (because S′⁢RT′=-D). In total, we have four possible factorizations given by:

The choice between the four displacements is determined by the requirement that the 3-D points must lie in front of both cameras, i.e., their depth must be positive.

The rotation R and translation t are then used to instantiate a camera pair as in Equation (27), and this camera pair is subsequently used to reconstruct the structure of the scene by triangulation.

The rigid displacement ambiguity arises from the arbitrary choice of the world reference frame, whereas the scale ambiguity derives from the fact that t can be scaled arbitrarily in Equation (31) and one would get the same essential matrix (E is defined up to a scale factor).

Therefore translation can be recovered from E only up to an unknown scale factor which is inherited by the reconstruction.

This is also known as depth-speed ambiguity (in a context where points are moving and camera is stationary): a large motion of a distant point and a small motion of a nearby point produces the same motion in the image.

The fundamental matrix can be derived in a similar way to the essential matrix. Intrinsic parameters are assumed unknown; we write therefore a more general version of Equation (27):

Inserting these two projection matrices into Equation (23), we get

which states that point mr lies on the line through er and Kr⁢R⁢Kℓ-1⁢mℓ. As in the case of the essential matrix, this can be written in homogeneous coordinates as:

The matrix

is the fundamental matrix F, giving the relationship between the corresponding image points in pixel coordinates.

Therefore, the bilinear form that links corresponding points writes:

F is the algebraic representation of the epipolar geometry in the least information case. It is a 3×3, rank-two homogeneous matrix. It has only seven degrees of freedom since it is defined up to a scale and its determinant is zero. Notice that F is completely defined by pixel correspondences only (the intrinsic parameters are not needed).

For any point mℓ in the left image, the corresponding epipolar line lr in the right image can be expressed as

Similarly, the epipolar line lℓ in the left image for the point mr in the right image can be expressed as

The left epipole eℓ is the right null-vector of the fundamental matrix and the right epipole is the left null-vector of the fundamental matrix:

One can see from the derivation that the essential and fundamental matrices are related through the camera calibration matrices Kℓ and Kr:

Consider a camera pair. Using the fact that if F maps points in the left image to epipolar lines in the right image, then FT maps points in the right image to epipolar lines in the left image, Equation (36) gives:

This is another way of writing the epipolar constraint: the epipolar line of mr FT⁢mr is the line containing its corresponding point mℓ and the epipole in the left image eℓ.

If a number of point correspondences mℓi↔mri is given, we can use Equation (39) to compute the unknown matrix F.

We need to convert Equation (39) from its bilinear form to a form that matches the null-space problem. To this end we use again the v⁢e⁢c operator, as in the DLT algorithm:

Each point correspondence gives rise to one linear equation in the unknown entries of F. From a set of n point correspondences, we obtain a n×9 coefficient matrix A by stacking up one equation for each correspondence.

In general A will have rank 8 and the solution is the 1-dimensional right null-space of A.

The fundamental matrix F is computed by solving the resulting linear system of equations, for n≥8.

If the data are not exact and more than 8 points are used, the rank of A will be 9 and a least-squares solution is sought.

The least-squares solution for v⁢e⁢c⁢F is the singular vector corresponding to the smallest singular value of A.

This method does not explicitly enforce F to be singular, so it must be done a posteriori.

Replace F by F′ such that det⁡F′=0, by forcing to zero the least singular value.

It can be shown that F′ is the closest singular matrix to F in Frobenius norm.

Geometrically, the singularity constraint ensures that the epipolar lines meet in a common epipole.

The reconstruction task is to find the camera matrices Pℓ and Pr, as well as the 3-D points Mi such that

If T is any 4×4 invertible matrix, representing a collineation of P3, then replacing points Mi by T⁢Mi and matrices Pℓ and Pr by Pℓ⁢T-1 and Pr⁢T-1 does not change the image points mℓi. This shows that, if nothing is known but the image points, the structure Mi and the cameras can be determined only up to a projective transformation.

The procedure for reconstruction follows the previous one. Given the weak calibration assumption, the fundamental matrix can be computed (using the algorithm described in Section 4.5.1), and from a (non-unique) factorization of F of the form

two camera matrices Pℓ and Pr:

can be created in such a way that they yield the fundamental matrix F, as can be easily verified. The position in space of the points Mi is then obtained by triangulation.

The matrix A in the factorization of F can be set to A=-er×⁢F (this is called the epipolar projection matrix (Luong and Viéville,1996)).

Unlike the essential matrix, F does not admit a unique factorization, whence the projective ambiguity follows.

Indeed, for any A satisfying Equation (47), also A+er⁢xT for any vector x, satisfies Equation (47).

More in general, any homography induced by a plane can be taken as the A matrix (see Sec. 4.6)

If the 3-D point M lies on a plane Π with equation nT⁢M=d, Eq. (36) can be specialized, obtaining (after elaborating):

Therefore, the collineation induced by Π is given by:

This is a three-parameter family of collineations, parametrized by n/d.

The infinite homography H∞ is the collineation induced by the plane at infinity; it maps vanishing points to vanishing points (a vanishing point is where all the lines that shares the same direction meet).

It can be derived by letting d→∞ in (55), thereby obtaining:

The infinity homography does not depend on the translation between views.

In other terms, the vanishing points are fixed under camera translation.

In general, when points are not on the plane, the homography induced by a plane generates a virtual parallax. This gives rise to an alternative representation of the epipolar geometry and scene structure (Shashua and Navab,1996).

First, let us rewrite Eq. (36), which links two general conjugate points, as:

The mapping from one point to its conjugate can be seen as composed by a transfer with the infinity homography H∞⁢mℓ plus a parallax correction term 1ζℓ⁢er.

Note that if t=0, then the parallax vanishes. Thus H∞ not only relates points at infinity when the camera describes a general motion, but it also relates image points of any depth if the camera rotates about its centre.

We want to generalize this equation to any plane. To this end we substitute

into Eq. (58), obtaining

with γ=ad⁢ζℓ, where a is the distance of M to the plane Π.

When M is on the 3-D plane Π, then mr≃HΠ⁢mℓ. Otherwise there is a residual displacement, called parallax, which is proportional to γ and oriented along the epipolar line.

The magnitude parallax depends only on the left view and the plane. It does not depend on the parameters of the right view.

From Eq. (60) we derive mrT⁢er⁢HΠ⁢mℓ=0, hence

A number of point correspondences mri↔mℓi is given, and we are required to find an homography matrix H such that

The equation (we drop the index i for simplicity) can be rewritten in terms of the cross product as

As we did before, we exploit the properties of the Kronecker product and the v⁢e⁢c operator to transform this into a null-space problem and then derive a linear solution:

These are three equations in nine unknown.

The rank of the matrix mℓT⊗mr× is two because it is the Kronecker product of a rank-1 matrix by a a rank-2 matrix. Hence, only two equations out of three are independent.

From a set of n point correspondences, we obtain a 2×n×9 coefficient matrix A by stacking up two equations for each correspondence.

In general A will have rank 8 and the solution is the 1-dimensional right null-space of A.

The projection matrix H is computed by solving the resulting linear system of equations, for n≥4.

If the data are not exact, and more than 4 points are used, the rank of A will be 9 and a least-squares solution is sought.

The least-squares solution for v⁢e⁢c⁢HT is the singular vector corresponding to the smallest singular value of A.

This is another incarnation of the DLT algorithm.