Motion is a powerful clue for an observer to explore and interact with the environment. It is well known that given two images of the static environment taken by a moving camera, it is possible to recover the motion of the camera (rotation and direction of translation) between two acquired images, and the relative depths of the scene points in a reference frame.

At least five pairs of matched feature points between two images are needed to determine the motion between images [18]. Furthermore, if eight or more matched points are available then a linear algorithm may be used to recover the motion [9]. While the case of eight or more matched points has been widely studied [1, 9, 14, 18], considerably less research has been done for the case where there are between five and seven matched points. The case of five point matches has been investigated by ([4], [13]), and they have shown that up to ten solutions may exist in general. Netravali et al have also given a generalisation of their algorithm for the case of six and seven point matches. When six or more point matches are available there is, in general, a unique solution for camera orientation [13], and in the case of seven point matches a closed form for the motion may be found (which requires solving a cubic equation).

In this paper, we present a simple algorithm for recovering 3D motion (rotational and translational) and relative depths when less than eight point matches are available. We formulate the problem in a new way that leads to a simpler algorithm for recovering the motion ( cf . [4, 13]). As a consequence our algorithm is easier to implement and understand, and it appears to be more stable.

The paper is organised as follows. In section two we give the necessary background to the projective transformation and introduce the essential matrix and some of its properties. In section three we give a brief review of the related work. Section four presents methods for recovering rigid motion from five, six and seven point matches. Experimental results are presented in section five. A discussion of results and possible extensions are given in section six and concluding remarks are given in the last section.

Let us consider an arbitrary point before and after the motion. The following notation is introduced and will be used throughout the paper.

Using this mapping, we can express the cross product operation of two vectors by the matrix vector multiplication:

where and are singular values of A in decreasing order.

The motion model that is assumed in this paper is a rigid motion model which can be decomposed into a rotation and a translation and is described by the following equation:

and after some rearrangement (see [19]) the following equations is obtained:

Proof: .

Lemma 2. or equivalently, eigenvalues of are 1, 1 and 0. For a proof see [7, 19].

Lemma 3. . See [18] for a proof.

Given n point correspondences, equation (3) can be rewritten as linear equations in the elements of E and we obtain

where

and

If eight or more ideal matches are available the rank of A is exactly eight (except for some degenerate cases, see [10]) and where h is the unit eigenvector asso-ciated with the zero eigenvalue of . In the presence of noise h is found as a unit vector that minimises || A h ||, and this is a unit eigenvector of associated with the smallest eigenvalue. The matrix E is then determined as

and R and T can be computed using method described in [19]. The methods that are based on solving system (3) when more than eight matches are present are known as so-called E –matrix algorithms. Their advantage is that they are linear and simple to compute, but they can not be used if the number of points is between five and seven, in which case a solution still can be found.

The motion recovery problem has been extensively studied by the computer vision community for the last fifteen years. There are two types of commonly used motion recovery algorithms – linear (described in the previous section) and non-linear. Non-linear algorithms may be broadly divided into two classes: 1) General methods based on non-linear estimation which simultaneously solve for camera orientation and relative depths through the minimisation of a non-linear cost function ( e.g . [15]); and 2) Subspace methods ( e.g. [5]), which subdivide the problem and solve separately for rotation, direction of translation and relative depths. The second class of methods is more efficient, as it usually first involves the minimisation in a two or three dimensional space to find the direction of translation or rotation, then the computation of other parameters by solving linear equations.

While both linear and non-linear algorithms have been proposed for the situation where eight or more point matches exist, the case for less than eight point matches has been investigated only in two papers ([4] and [13]). In both a complicated polynomial system needed to be solved to recover the motion.

Faugeras and Maybank [4] used two different approaches in their paper. The first one was based on the properties of essential matrix, which was introduced by [9]. They employed the fact that the set of essential matrices can be described by polynomial equations and investigated the multiplicity of solutions using algebraic geometry. A similar approach was taken by Natravaly et al [13], a set of three cubic and five linear equations need to be solved. This is even more computationally demanding to implement. The second approach of [4] employed projective geometry and was based on ideas developed by Chasles [3] and Kruppa [8]. Using this approach a high order polynomial needed to be solved. The problems with this approach are that it is difficult to understand and it is difficult to implement, as it requires extensive symbolic algebra.

Heeger and Jepson [5] (and before them [2]) assumed small rotation between two frames and have shown that in this case motion equation is bilinear what enabled them to find direction of translation through the optimisation of the cost function in the two-dimensional space (unit sphere). After that, they found rotation and relative depths by solving linear system. The main disadvantage of this method is that it assumes a small rotation, so it can not be applied in general. When the rotation is not small, the motion equation is no longer bilinear and subspace methods, at best, can be reduced to a three-dimensional optimisation.

In this paper, we propose a subspace method, which is specially designed for the case when less than eight motion correspondences are available and is based on evaluation of the essential matrix E given the constraints described in the previous section. The advantages of this method are: 1) it is simple; and 2) it requires only a minimisation in the compact two-dimensional space.

In this section we describe how to compute motion parameters when fewer than eight point matches are available. We will separately consider three cases: five, six and seven point matches. We will show that when seven point matches are available, the unique solution can be found by solving a cubic equation, and that in case of five or six point matches the camera motion can be recovered through the minimisation of two-dimensional functions defined on the unit sphere.

Our method is based on solving equation (4) with the constraints that E satisfies the properties of an essential matrix. For clarity, we will rewrite this here:

where E is related to h by equation (5).

where are the coefficients to be found. The essential matrix corresponding to h is given by

where are matrices associated with eigenvectors , and our task is to find which are solution to equation

.

This may also be formulated as a minimisation problem

.

The space of solutions for a may be further reduced in the following way. If E is an essential matrix, then according to Lemma 1 for the direction of translation T (unit vector) we have:

The cost function with the reduced search space can be defined as a function of T (hence defined over a two dimensional space) as follows:

• Pick up an arbitrary unit vector T .
• Form matrix .
• Compute a as the eigenvector of associated with its zero eigenvalue.
• Compute ; and
• Compute the cost function as

This cost function is always positive and will have minimum for those values of T for which . The search space is small (the unit hemisphere which is compact two-dimensional space) and the computational complexity of the evaluation of the cost function is low. In practice, to find all solutions, we performed the minimisation several times (the Simplex method, implemented in MATLAB, was used) with randomly chosen initial values. Usually all solutions were found. An example of typical cost function is shown in Figure 1.

When six point matches are available, matrix A has rank six and has three zero eigenvalues. The zero space of matrix is three-dimensional and the solution of equation (5) can be written as

where a= [ a ₁ a ₂ a ₁ ] ^T are coefficients to be found and are eigenvectors of associated with its zero eigenvalues. As with 5 point matches, the essential matrix cor-responding to h is given by where are matrices associated to eigenvectors . Again, using Lemma 1 we obtain

The necessary condition for above system to have a non-zero solution is rank( B ) = 2, and we can employ another constraint on T , e.g . . This equation may be written after some rearrangement as a homogenous third order polynomial in T , but is very difficult to use in practice. Therefore, for this case, we employ the same minimisation procedure as for five points. The only difference is that vector a is three-dimensional and that it is computed as the eigenvalue of B associated with its smallest eigenvalue.

With seven point matches, matrix A has rank seven and has two zero eigenvalues. The null space of matrix is two-dimensional and the solution of equation (5) can be written as

The essential matrix corresponding to h is given by where and are matrices associated to eigenvectors and . The equation to be solved is:

When five point matches are available the number of solutions corresponding to each set of point matches is up to 10. A solution is feasible if it yields a 3D reconstruction in which all the points are on the same side of the camera for both camera positions (if all the depths are negative, than we simply change the sign of translation vector and the sign of depths).

For this configuration we found all four solutions, with all of them being feasible. The results are shown in Table 1, while the cost function is shown in Figure 1. Light areas indicate a high value for the cost function, while dark areas indicate low cost. Solutions (minima) are marked as white squares with a black dot in the centre.

With six point matches, a unique solution exists in general, and in all our experiments, we were able to find this unique solution.

One set of six points is given in Table 2. The cost function associated with this set of points is shown in Figure 2. As can be seen on Figure 2. (and as obtained by our algorithm), the cost function has four minima. However, when the second criteria ( A h=0 ) is applied, only one of these solutions remains valid.

Figure 2. Cost function associated to the six point correspondences given in the Table 2. The white arrow point to the solution for which A h = 0 .

The main characteristic of our algorithm is that it employs the fact that the essential matrix corresponding to the five point matches must lie on a known four-dimensional hyperplane. Thus, if the direction of translation is known, the essential matrix (and accordingly rotation and relative depths) can be recovered using a linear algorithm. Consequently, the problem of finding camera orientation is solved through the optimi-sation of the cost function in the space of all possible directions (on the unit sphere).

If this fact were not employed, then even if the direction of translation were known, finding the rotation vector would be still complicated, and not possible in closed form. Therefore, optimisation in a higher dimensional space would have to be employed.

One immediate application of our algorithm is rigidity checking. In [12], rigidity checking was performed using six point matches by non-linear optimisation in an 11-dimensional parameter space (motion parameters and relative depths of the scene points in the reference frame). It seems that our algorithm would produce a much simpler solution to this problem. Namely, it is enough to find minima of the cost function described in Section 3.2 and check if minimum is below some threshold. This can be done using the two dimensional optimisation. Moreover, it can be readily visualised ( e.g . see Fig. 2).

Another potential application is in motion segmentation from a sequence of images taken from a calibrated camera. For motion segmentation the robust estimators such as RANSAC or Least Median of Squares can usually be successfully used [16]. These algorithms require a certain number of p -tuples ( p motion correspondences) to be randomly chosen. In the case of an uncalibrated camera p is usually seven ([16, 11]) or eight [19]. For a calibrated camera, however, this number can be five or six. This is important, as the required number of samples is exponentially related to p .

In this paper we have presented a new approach to the problem of determining the motion between two images where the number of matched points is less than eight. The main advantages of our algorithm are simplicity and low computational cost . Not only that, but the formulation of the problem is considerably simpler than previous presentations.

The algorithm was implemented and tested using simulated data. When five point correspondences were given, we usually found four solutions which is in line with observations made in [4, 6]. For those configurations that yield ten decomposable solutions, the algorithm found all solutions. For six and seven point matches, the unique solution was always found.