A Robust Algorithm for Determining the Translation of a Rigidly Moving Surface without Correspondence, for Robotics Applications

1. Introduction

The potential of motion estimation in such applica­ tions as image coding, tracking and robot vision has long been appreciated and demonstrated. Up to now there have been three approaches to the solution of this prob­ lem:

1. The first method assumes the dynamic image to be a three dimensional function of two spatial arguments and a temporal argument. Then, if this function is locally well behaved and its spatiotemporal gradients are computable, the image velocity or optical flow may be computed [1].
2. The second method considers the cases where the motion is "large" and the previous technique is not applicable. In these instances the measurement tech­ nique relies upon isolating and tracking highlights or . feature points in the image through time[2].
3. In the third method, the three-dimensional motion parameters are directly computed from the spatial and temporal derivatives of the image intensity func­ tion. In other words, if f is the intensity function and ( u, v) the optic flow at a point, then the equation fz u + / 11 v + ft = 0 holds approximately [6,9].

As the problem has been formulated over the years one camera is used, and so the three-dimensional motion parameters that have to be and can be computed are five in number (two for the direction of translation and three for the rotation). In our approach, four cameras are used to recover the three translation parameters, instead of only the direction of translation.

2. Motivation and previous work

The basic motivation for this research is the fact that optical flow (or discrete displacements) fields pro­ duced from real images by existing techniques are cor­ rupted by noise and are partially incorrect [5]. Most of the algorithms in the literature that use the retinal motion field to recover three-dimensional motion fail when the input (retinal motion) is noisy.

Some researchers have developed sets of nonlinear equations[7] with the three dimensional motion parame­ ters as unknowns, which are solved by iteration and ini­ tial guessing. These methods are very sensitive to noise. Others, developed linear equations[SJ, but the sensitivity did not Improve.

Several other authors use the optic flow field and its first and second spatial derivatives at corresponding points to obtain the motion parameters. But these deriva­ tives seem 'to be unreliable in the presence of noise, and there is no known algorithm that can determine them reliably in real images.

Even if we had some way however to compute reti­ nal motion in a reasonable fashion, with at most an error of 10% for example, all the algorithms proposed to date that use retinal motion as input (and one camera) would still produce non-robust results.

So, a natural question arises: is it possible to recover three dimensional motion from images without having to go through the very difficult correspondence problem? And if such a thing is possible, how immune to noise will the algorithm be? In this paper, as in [3, 9] we prove that if we combine stereo and motion in a certain way and we avoid any static or dynamic correspondence by using four cameras, then we can compute the three dimensional translation of a moving object.

3. Technical prerequisites

Consider a coordinate system OXYZ fixed with respect to the camera, where 0 is the nodal point of the eye and the image plane is perpendicular to the Z axis, that is, pointing along the optical axis. Let us represent points on the image plane with small letters (x,y) and points in the world with capital letters (X, Y,Z). Let a point P = (X 1, Y 1,Z 1) in the world have perspective

/XI JY1 . image (xl,yi), where XI= -z and Yi = z· With I I I

the focal length (see Figure 1 ).

where (AX,A Y,AZ) is the three dimension~) tr~nsla­ tional translation, and P' has the perspective Image (x 2 ,y 2 ), then it can be easily shown that

\

4. The model

Let OXYZ be a Cartesian coordinate system, fixed with the Z-axis pointing along the optical axis, and con­ sider the image plane plane Im1 perpendicular to the Z­ axis at a point (0,0,1) (focal length=/). This is obviously the model of a camera. Furthermore, consider three more cameras with image planes 1m 2 , 1m 3 , Im 4 with nodal points (ox '0 '0) ' (ox ' oy '0), and (0, oy '0) respectively (see Figure 2).

On each of the image planes a coordinate system is defined exactly as it was done for Im1· From now on, coordinates of three dimensional points will be denoted by (X, Y,Z), while coordinates of points in each of the images will be denoted by (x1 , y 1 ),(x2 , y 2 ),(x3 , y3 ),(x4 , y4 ), respectively. C~r­ dinates of image points in the second dynamic frame (1.e. projections of three-dimensional points after the motion) will be denoted by the same symbols as before the motion, but primed (i.e. (x' 1 , y' 1 ), etc.). Consider a set A = {(X; , Y; , Z; ) :i = 1, .. ,n} of points in the world, which translates tigidly along the vector (~X.~ Y,~Z) to form a new set A 1 = {(X'; , Y'; , Z'; ) : i = 1, .. ,n }, where X';= X;+ ~X, Y'; = Y; + ~y and Z'; = Z; + ~z. fori = 1, .. ,n.

Let the projections of the set A on the four image planes be {(x1; ,rli ), i = 1, ... ,n }, {(x 2 ; ,y 2 ; ),i - 1, ··. ,n }, · {(x3; ,y3; ),i = 1, .·. ,n }, {(x(i ,y 4 ; ),i = 1, ... ,n }, respectively, and the projec­ tions of the set A 1 be {(x'1; ,y'1i ) , i = 1, ... ,n }, We now prove the following propositions. Proposition 1: Using the aforementioned nomenclature, the quantity

is directly computable from the projections of the points of the set A on lm 1 and 1m 2 ·

Proof: Consider a point P = (X; , Y; , Z; ) E A and its projections P 1 = (x1; , y1i) and P 2 = (x 2 ; , y 2 i) on lm1 and 1m2 respectively. Then

Therefore,

Corollary 1: The quantity . E },. is also directly com· - 1 I putable from the projections of the set A 1 on Im 1 and 1m 2 ·

" 1li Propoaltlon Ia The quantity . E z. Is directly com'-1 · putable from the projections of A on Im 1 and 1m 2 · Proof: From equation (4.1.1) we have

But corresponding points in lm 1 and 1m 2 have the same y coordinates, and so

Equation (4.3.1) proves Proposition 2.

· " X . Proposition 3: The quantity . E ; .· , is directly com·- 1 I putable from the projections ot the set A on Im 1 and · Im 4 ·

Proof: Similar to proposition 2.

6. Recovering three dimensional translation without corr-pondence

Consider the projections of the sets A and A 1 on · Im1· From Section 3 we have

If we write equation (5.1) for all pairs of corresponding points and we sum up these equations, we get

Assuming that the motion in depth is small with respect to the depth, (5.3) can be approximated by

Similarly, with equation (5.2) we obtain

If we apply the same procedure for the projections of the sets A and A 1 on 1m2 we get two more equations. One of them Is the same as (5.5) and the other is

Equations (5.4) through (5.6) constitute a linear system in the unknowns t::.X, t::. Y, t::.Z (we will call this system E from now on ) which always has a unique solution, given by

Note that the denominators in the expressions through (5.9) are always different from zero 8x8y~O). (5.7) (for

We now proceed with an error analysis and imple­ mentation issues.

6. Theoretical error analysis

6.1. Error due to assumptions in the development of the constraints

Equation · (5.3) is exact, but equation (5.4), used in the subsequent analysis, is an approximation of equation (5.3). It seems that the approximation used is

But this is not the case, as we show in the sequel. Let the three-dimensional points be

z. where d = mJn (fl.~ ).

A similar analysis can be carried out for the compu­ tation of

The above equation (which is exact) becomes equf!,tion (5.4) (which is used in the algorithm) neglecting 0( d-2 ) terms, hence the accuracy of the algorithm depends on the assumptions that ( t::.Z ) 2 is negligible. z,.

6.2. Error due to small perturbation of the points

It is observed that when random noise is added to the image points, the equations remain consistent [4] (details omitted due to lack of space.)

6.3. Error due to the addition and deletion of ran­ dom noise points

Unlike random perturbation of points, throwing in points at random makes the estimators based on the image points inconsistent[4]. However, from actual experi­ ments it is observed that the effect of this error is not significant if we consider a window around the object of interest.

6,4. Stability of the solution of the linear system E

From our analysis(4], the necessary and sufficient condition for the system not to be critically ill­ conditioned ( and therefore for its solution to be stable) is

where B = (b;j ) = E-1.

It is worth stating at this point that discretization noise is enough to destroy many algorithms in the literature that do dynamic analysis ( measurement of motion) [8]. However, we have the following proposition.

Proposition 4: A sufficient condition for critical ill­ conditioning not occuring in our model under discretiza­ tion error is

where HM(Z) denotes the harmonic mean of the depths of the world points corresponding to the image points.

Proof: For proof see [4]. (deleted here for lack of space).

7. Experiments

Here we only describe one experiment with real images. Note that we have eight frames in all, four before the motion and four after the motion. When we say that we have an error of /3% in the translation, we mean

where (~X , ~ Y , ~Z) is the actual translation (with (~X~ Y ~Z~O), and (~X,~ Y, ~Z~O) is the com­ puted one.

The experiments were carried out using images of a circuit board. Image acquisition was accurately controlled using a "American Robot" arm and a VICOM processor. Figure 4 shows the result of the point extraction operator on the images obtained after motion. The number of points extracted in the four frames were respectively 1767, 1643, 1665, 1687 before motion and 1491, 1547, 1578, 1529 after motion. The actual motion was (60.0, -60.0, -30.0) and the estimated translation was (63.5, -63.1, -35.2). The error is due to the factors that were explained in the paper and to the fact that our actual measurements (ground truth) were not perfect (cameras set up, calibration and motion).

Due to lack of space several proofs and experiments were omitted. The interested reader is refered to [4].