Motion and Structure from Optical Flow

1. THE PROBLEM -~~=.;,

The problem addressed here is computing the surface layout of the environment, and the par­ ameters of observer's motion (egomotion) from the information on the image plane, The prob­ lem is similar (though not equivalent) to the one tackled by the workers in computer stereo vision [1),

Consider a monocular observer with his "eye" and "head" fixed, with planar "retina" 1 and moving along a smooth curvilinear path in a stationary 3D environment. Each discriminable optical element on his "retina" will possess a velocity; the whole comprising a positional velocity field, Such an observer can be viewed, instantaneously, as simultaneously rotating and translating for (again instantaneously) any 3D motion can be viewed as a rotation about some centre on some osculating plane. The instantan­ eous positional velocity field (IPVF) is then expressable as being due to the vector sum of two angular velocities due to the translational and the rotationalcomponents of the movement [2]. [3].

Given a IPVF our task is to recover the ego­ motion parameters (i.e,, the translational and rotational components of the egomotion), We do this with respect to an external, static refer­ ence frame instantaneously coincident with our egocentric reference frame (centered at 0 in Fig, 1), The actual velocity of any point Q on the image plane is given by

.iere, Vl is the magnitude of the translational component (the speed of egomotion), Vl is its direc·tion vector. And S is the distance to the centre of polar proje~tion of the environmental point P of which Q is the projection on the "retina" (see Fig. 1), Q is the position vector of the point Q in-the egocentric refer­ ence frame centered at 0, Q is the unit vector in this direction, A is the rotational angular velocity vector the components of which are to Je recovered in the first place (for more detail see [4]).

Refer to Fig. 1, As can be seen, the "retinal" velocity vector of point Q, Y" must necessarily lie in the plane spanned by Q and V', Given the IPVF1 Y' may be derived for each point Q,

since

(This follows from the equivalence of angular velocities generated by Y' and !".

Given that we know !'· we can rewrite (1) to obtain

An egocentric reference frame centered at the centre of polar projection, o, is defined, together with a planar projection surface PP. A "retinal" 2D rectangular coordinate frame centered at 0 is defined on PP.

V' and V" lie on the same plane, the unit normal of which is (V' X Q).

Refer to Fig. 2. The vector (Vl x Q) x Q lies in the plane of Vl. Given the-fact that Vl must lie in all such planes corresponding to dTffer­ ent points Q, its direction will be determined as the intersection of these planes. The direc­ tion of the line of intersection of two planes specified by their normals NI, NJ is (NI x NJ). Referring back to (3) we see that

[I=(A X QI - YI') X QI

lies in the direction of the vector normal to the plane PVl (see Fig. 2), From this, using simple vector algebra, we see that for any three distinct "retinal" points QI, QJ, and QK the relation

must hold. Here, the square brackets denote a scalar triple product of the three vectors. Equation (5); written out. is an equation of the third degree in 3 unknowns (the components of A).

A set of 3 such equations (a minimum of 5 distinct "retinal" points is needed to define such a set) does not have an analytical solu­ tion: in general the solution can be obtained only using an iterative techni~ue (a very fast and simple method reported in L5] is used in our computer implementation).

2. COMPUTER IMPLEMENTATION

The solution to a set of equations (5) can be computed locally, given some non-empty neighbo~ hood of a "retinal" point Q. In a 'real world' application one should not, however, use locally clustered points. To obtain accuracy in the presence of noise one should use points spread as widely as possible. Also, considering more points in the process of solving for A (perhaps by minimizing some suitable functTon of differences between the values of A computed at different regions locally) improves the accuracy with which A can be obtained.

A computer program incorporating the method has been written and experimented with using simu­ lated input data (no distortions or noise). The program consists esaentially of a local operator which computes A, Vl, and the surface normal corresponding to a-given image plane point. All three values are computed locally from a neigh­ bourhood of a given "retinal" point. The size of the neighbourhood is presently (due to some computational limitations) about 1 degree of arc. The surface normal produced by the opera­ tor is essentially that of the best fit planar scale at a given point. The application of the operator to the whole image results in a sur­ face-normal map.

The results are encouraging. Using the single precision arithmetic the accuracy of the surface normal map lies within the error of (approxi­ mately) 1 degree of arc,

3, DISCUSSION

Using the preceeding analysis, it seems plausible that a relatively simple process may be used to recover the instantaneous egomotion parameters and surface normal map in a stationary world. The only assumptions made were the smoothness of the movement trajectory, rigidity of the objects, and the existence of the IPVF, This latter is taken for granted and constitutes the greatest weakness of this kind of approach, There is very little known about the behaviour of the correspondence computation­ like methods suggested by Ullman [6] using real images, and these or similar mechanisms are, at present, thecnly way to generate the IPVF.

On the other hand, the above approach applies equally well to the case of a rigid 3D world of moving objects. To see this note the recipro­ city between the motion of an object and the motion of the observer; for any objection motion there is an observer motion which, assuming the object to be stationary, generates the same IPVF in the region of the object, (This is the main reason that smoothness of path was the ONLY restriction put on the observer's motion:r­ Using a si~le technique suggested by Nakayama and Loomis L3], we may compute the depth con­ tours to perform a figure-ground separation, Applying the analysis above to each separated image region leads then directly to the surface normal map corresponding to the region, It is not possible, however, to recover the object motion since absolute distances (of which the optical flow is a function) are not recoverable from IPVF's.

~. CONCLUSION

A method is outlined which is capable (at least in principle) of delivering a surface normal map from .an instantaneous positional velocity field (IPVF) generated by a curvilinearly moving observer. While the method is not as elegant and simple as the one developed in Clocksin [7] for the case of a rectilinearly moving observer, it is considerably more general,

It is possible that the analysis outlined above for the case of moving objects may offer some insights into the phenomena of position constan­ cy ("How is it possible that when we move, and thus every optical element on the retina moves, we still perceive a stationary world?"). In that case, after applying the method locally. an "egomotion map" may be constructed which maps each point on the "retina" to this "egomotion space" (spanned by the orthogonal components of A e-nd Vl). Some evaluation mechanism may be operating in this space, choosing. for example the point into which the 'majority' of image plane points maps as the stationary reference frame. All point mapping into this point (or perhaps some small neighbourhood of it) would then be regarded as projections of the station­ ary environment.

ACKNOWLEDGEMENTS

I'm in debt to Drs M. Brady and P. Hayes for many helpful suggestions, and to my wife Dasha who did the layout,