Determination of Egomotion and Environmental Layout from Noisy Time-Varying Image Velocity in Binocular Image Sequences

1 Introduction

In this paper we present an algorithm for computing the motion and structure parameters that describe egomotion and environmen­ tal layout for a moving binocular observer viewing a stationary environment. This algorithm is an extension of the monocular algo­ rithm presented in [Barron et al 87a]; the two coincide when the left and right image sequences coincide and the temporal baselines at each time are unknown. The binocular motion and structure parame­ ters are simply the monocular motion and structure parameters, 1/, the depth scaled translational observer velocity, ot, the observer's rota­ tional velocity and 11, the normalized surface gradient of some planar surface, plus X3, the absolute depth of some point on the surface.

Our algorithm reconstructs observer motion and environmental structure by solving a nonlinear system of eguations; each equation relates image velocity at some image point, Y,.(it',t}, in either the left or right image sequence to the underlying motion and structure parameters in the left image sequence at the solution point, f.<P.t).

In general, monocular and binocular reconstruction have been considered two separate problems. Monocular reconstruction typi­ cally involves solving systems of (nonlinear) equations relating image velocity (and possibly its I" and 2"" order spatial/temporal derivatives) to the underlying motion and structure parameters describing a surface in relative motion with an observer (see [Barron 84]). The classical stereo paradigm proposes that 3-D depth be recovered by computing matching primitives in the left and right images of a stereo pair, establish correspondence between the appropriate primitives in the two images and then calculating 3-D depth using simple trigonometry. [Barnard and Fischler 82], [Jenkin 84] and [Poggio and Poggio 84] provide surveys of some of the

current stereo techniques.

We believe that monocular and binocular vision have a lot in common and can be solved in a unified way. The algorithm presented in this paper is more in the favour of monocular recon­ struction algorithms that interpret image velocity fields, for example [Longuet-Higgins and Prazdny 80] or [Waxman and Ullman 85] then in the favour of the classical stereo paradigm described above. We also interpret image velocities fields; but we do so by sampling the image velocities at many discrete times in both left and right stereo image sequences.

· Also, Canadian Institute for Advanced Research

2.2 Physical Setup

We model the left and right observation points using right hand coordinate systems as in Longuet-Higgins and Prazdny [80]. U.r{U~oU2,U,) is the translational velocity of the observer centered at the Ori_$in of the coordinate systemX .. (t). (O,O,X,) is the line ouight in !J,(t). m,.=(~.co,.co,) is the angular veloci~ ~f the observer. X,(t) and X,(t) are rigidly connected, hence, c.t,~ .. O> The ce~ter of. the two coordinate systems, the left and right observauon pomts, are separated~ a spatial baseline"Stt;t)=(s1,s2,s3) andX,(t) is rotated with respect to X 1 (t) by R8(11J 1 ,11J2,~); ljl1 ,~ and~ are Euler angles as defined by Arfken [70, pp178-180] for a right-hand coordinate system. If (IIJ~o~.~)=(O,O,O) the left and right coordinate systems are parallel; otherwise we have either a convergent or a divergent stereo setup. In addition to a spatial baseline, the observation point in either a left or right sequence at &.<t) can be separated by a temporal baseline lt.(t,t ';t) from X .. (t '). X1(0) is the inertial coordinate system.

2.3 The General Image Velocity Equation

We can write an equation relating image velocity at a point Y,(P,.,t''"J.)O the binocular motion and structure parameters at some point f,(Pu,t) as

where P ~d P, are 3-D points on the same planar surface and gen­ erally V,(P 8 ,t)lof.(P,.,t''). In a left image sequence, V,(f,(P,.,t"),t") reduces to \t,(P ·· t").t") provided we use ?-:(O,O,O), Rk=l and note that ~t,t',t";t), the spatio-temporal baseliqe, is simply"Jt(t,t";t). Complete details concerning this equation are given in [Barron 87].

The use of a spatio-temporal distribution of image velocities requires that we make assumptions about the kinds of motion the observer is undergoing. In this paper, we consider 2 specific types of motion, although we emphasize that our treatment can be general­ ized to other motions as well. The 2 types of motion considered are:

Type 1: A vehicle is moving with constant translational velocity and has a camera mounted on it that is rotating with constant angular velocity.

Type 2: A vehicle with a fixed mounted camera is moving with con­ stant translational and angular velocity.

3 Experimental Technique

In this section we discuss the implementation of our algorithm and present the details of our error analysis.

3.1 Implementation

Newton's method is used to solv.s the systems of non-linear equations. Since only 2 components of a are independent, we add an extra normalization row to the Jacobian matrix, J, to ensure the com­ puted dis normalized; hence J is a full rank 10 matrix. The 10"' value of1.,, the measured image velocities is then set to 1.

When lit is known to be zero, i.e. in the case of pure translation (type 1 and type 2 motions are equivalent here) we can use a 7x7 Jacobian instead of a 10x10 one. We compute a 10x7 Jacobian (the 3 columns corresponding to ot are not computed). We let the LU decomposition of J choose the bests 7 rows of J, with the provision that the normalization row is always one of the chosen rows.

3.2 Error Analysis

We compute an error vector, ,V., which, when added to 7.,, yields the perturbed input, i.e.

For X% random case error (2>, we compute five random 2-component unit vectors, 1. 1 , j=1, ... ,s, and then compute each i"' component of ,V., as

We usev, in the calculation of error for v,,, in 6/9.,. 6[, 911 is 0, i.e. we do not add error to the normalization constant Using 6/., for ran­ dom error we compute 6/.,... =liM., 11 ·· We use forward and inverse iteration on J <>> to compute normali~ best and worst case error directions, e8 and e.,. We compute 6[J,=e8 6[...,. as X% best case

scaled image velocity error and ,V., =e., 6f ..... as X% worst case scaled image velocity error. Both best and worst ,V., are made to be the same size as the random ,V., for comparison purposes. A last type of error involves adding worst case error to the image velocities so that the maximum error in any image velocity is X%. We call this worst case relative error.

We compute initial guess error by adding X% random error individually toft, d, lit and X,.

4 Experimental Results

In this section, we present some preliminary results obtained from testing our algorithm.

We consider 3 motions: (1) U 1 =(0,0,1000), it,=(O,O,l), ~(0, 0,0) and ~3=2000, (2) c.t, is changed to 0,0.1,0 for type 1 motion and (3) ro1=(0,0.1,0) for type 2 motion. The spatial baseline is"P(80,0,0) (meas­ ured at time 0) for a parallel setup, i.e. (1!1 1 , ~.~)=(0,0,0). Motion 1 corresponds to pure observer translation towards a wall. Motions 2 and 3 correspond to an observer translating directly towards a wall as he rotates his head to the right (type 1 motion) or moving towards the wall while turning to the right (type 2 motion). These motions are singular if all image velocities are measured at time 0. However motion and structure can be recovered from a spatio-temporal distri­ bution of image velocity. We measure 4 image velocities at points, (70,70) at time 0, (-30,70) at time t/4, (-30,-30) at time t/2 and (70,-30) at time 3tt4, i.e. at the four comers of a square centered at the solution point (20,20). Since we need 9 image velocities for our binocular algorithm, we measure the y 1 image velocity component at (20,20) at timet. The solution is computed for time 0. These image coordinates are assumed to be measured on a 256x2S6 display device and so are scaled by 256 to produce realistic f coordinates. Thus, (20,20) in pixels is scaled to (0.078125,0.78125) in f coordinates. The viewing angle of these points is computed as the maximum diagonal angle subtended by the points, i.e. 33.05". We call this the spatial extent. The tem­ poral extent, written as 0-t, refers to the five times used, i.e. 0, t/4, t/2, 3tt4 and t as above.

8x8 tables are used to display the output error for runs made by varying two quantities, say temporal extent against image velocity error. In this case table rows (from left to right) correspond to increasing temporal extent while table columns (from top to bottom) correspond to image velocity error.

Due to space limitations, we can only report a few of the results we have obtained to date. Tables 4-1a,b,c,d,e,f show the output error for runs where temporal extent is varied from 0-0.3 to 0-1 in 8 equal steps and image velocity error is varied from 0% to 1.4% in 0.2% steP& for random and worst case error directions for the three motions. The L_ condition numbers of the various Jacobian matrices are quite large; the values vary from 300,000 to 3,000,000! This indicates unsta­ bility. All 100% output error values correspond to unsolved runs; all other values, including those over 100%, correspond to solved runs. We do not show best case error results as these are effectively 0% (less than 0.2% ). Indeed, even when maximum best case error was 49% the output error was only a few percent. These best case results are quite good, especially when compared with random and worst case output. The output error in the random cases is about 1/3 to 1/2 the output error in the worst case. As we can see, increasing the tem­ poral extent significantly reduces output error; time a)>pears to

(2) Computing random image velocity error in this way prevents the error that is added to the individual velocities from being too large relative to the magni­ tudes of the velocities, i.e. the error added to each image velocity pair depends on the magnitude of that image veloCity. Since the magnitudes of the various velocities can vary greatly any technique for computing error that doesn't take this into account may end up adding very lBIJ!e error to the smaller image velo­ cities.

(3) We note that the best and worst directions so calculated are for the initial linear system of equations, iho=10 · It is possible that the actual best and worst directions for the nonlinear system of equations are different, although we ex­ pect these directions to be quite close to the computed best and worst direc­ tions.

increase robustness for these motions. The results indicate that worst case error of as little as 1.4% can produce unusable output, if we assume only output error that is less than 10%-20% is useful. It seems we need image velocity measurements to be quite accurate.

The second experiment involves using perfect image velocity data and varying teinporal extent from 0-0.3 to 0-1 as before while varying initial guess error from 0% to 100% in 8 equal steps for the 3 motions. All 100% output error values indicate unsolved runs while 0% output error indicates solved runs. For the 1" motion (Table 4-2a) most runs solved even when the initial guess error was 100%. Motions 2 and 3 (Tables 4-2b and 4-2c respectively) exhibit multiple solu­ tions C'>; all output errors not 0% or 100% represent solved runs where the computed solution differs from the correct solution. For example, using type 1 motion and a temporal extent of 0-0.9, we obtain two multiple solutions. The first occurs when an initial guess of 14.29% is used and is specified as:

with X,=1090.651. The output error is 45.47%. This solution, plus the correct solution ofit,=(0,0,0.4969759), ~=(0,0,1) and c;t,=(0,0.1,0) produce the same 4 112 image velocities at the five image points and times:

(The last v1 component for (20,20) is not used.) Except for these com­ mon image velocities, the two flow fields are distinct.

A third experiment that investigates the relationship between image velocity error and initial guess error does not produce any unexpected results; the two are usually independent. In most solved cases where the output error did not depend on image velocity error alone it was impossible to tell how much of the error was due to image velocity error and how much may have been due to the existence of a multiple solution.

As we have already seen in experiment 1, increasing temporal extent can reduce output error. The fourth experiment investigates what happens when spatial extent is varied from 7° to 70° (the full image) for a fixed temporal extent of 0-1. A spatial extent of 9° is computed by first calculating y=( 2 1 -cosa )" and then using image +2cos9

velocities measured at (y,y) at time 0, (-y,y) at time 0.25, (-y, -y) at time 0.5, (y, -y) at time 0.75 and (0,0) at time 1. The solution point for this experiment was changed to (0,0). The 1" motion is used and rela­ tive worst case image velocity error is varied from 0-1.4%. The results (Table 4.4a) show that increasing spatial extent increased out­ put error in most cases. When d, was changed to (0.707107,0,0.707107) results (Table 4.4b) showed a slight improvement in output error for increasing spatial extent. Previous results with our monocular algo­ rithm [Barron et at 87a] showed a better improvement with increas­ ing spatial extent. We also investigate what happens when the spa­ tial baseline ?is varied: s, values of -1000, -800, -80, -8, 8, 80, 800 and 1000 are used. s1 and s 3 remain 0; only horizontal disparity is used. Because co, is 0.1, -s 1 values cause the right camera to move away from the planar surface (relative to the left camera) thus result­ ing in U,>U, while +s1 has the opposite effect, i.e. U,<U,. Relative worst case image velocity error is varied from 0-1.4% and a fixed temporal extent of 0-1 is used. Results (Table 4-4c} for the 3" motion show that as fJ;s value increases relative to U1 output error is reduced. Increasing the spatial baseline does help provided the increases cause the right camera to move faster and closer to the plane.

(4) (Subbarao and Waxman 85) show uniqueness of the monocular motion and sttucture parameters over time. Their result also holds when binocular flow fields are used. However, in both cases uniqueness holds only when the whole flow field is analyzed.

In the fifth experiment, we also wary the relative orientation of the left and right cameras by varying" to have values (in radians) of -0.5, -0.25, -0.1. -0.05, 0.05, 0.1, 0.25 and 0.5. +1 .and+, remain 0; the orientation involves a simple rotation about theX1 axis. Again, rela­ tive worst case image velocity error of 0-1.4% and a fixed temporal extent of 0-1 are used. Results for the 1" motion (Table 4.5) show that both convergent and divergent stereo setups yield smaller output error than for the original parallel setup; the closer the setup becomes to being parallel, the worst the output error.

Another result not included in this paper for lack of space shows that image velocity error caused by violation of the underlying assumptions produces less output error than similarly scaled random and worst case image velocity: it seems that violation of the various assumptions is less important than the accuracy of the input image velocities.

5 Conclusions

We have formulated a binocular reconstruction algorithm that uses a stereo spatio-temporal distribution of image velocities in left and right stereo image sequences but does not require point-to-point correspondence be solved in either the individual image sequences or between stereo image pairs. We have demonstrated that the addition of a temporal distribution of image velocity may increase the numer­ ical stability of the solution technique. In addition, it allows us to analyze flow fields that may not be analyzable at one time. As well, increasing spatial extent can improve the algorithm's performance. Other results suggest that convergent/divergent stereo setups can give better results than parallel stereo setups and that increasing the spatial baseline can have a similar effect. In all cases, we are effec­ tively increasing the spatio-temporal extent. Unfortunately, the greater the spatio-temporal extent the more likely the algorithm's underlying assumptions will be violated in realistic situations. We are able to report the existence of multiple solutions, a fact that is apparently overlooked by most other researchers. Our results indi­ cate that reconstruction techniques are quite sensitive to input image velocity error (1.4% maximum input error in the image velocities will be very difficult to obtain) but relatively insensitive to initial guess error. We believe that this is the main stumbling block that reconstruction algorithms have to overcome before we can consider this part of machine vision solved.

We are investigating the relationship between error in image velocities and error in the spatio-temporal derivatives of the flow fields [Barron et al 87b] and the improvement gained when a least squares formulation is used. These and other results will be reported in future papers.

Acknowledgements

We gratefully acknowledge financial support from the National Science and Engineering Research Council of Canada and the Department of Computer Science at the University of Toronto.