Recognizing 3-D Motion

1 Introduction

Since computer vision is considered as one of the main subfields of Artificial Intelligence (AI) 1 , it has been ad­ dressed in the first years since its appearance using the general AI-methodology. The main emphasis in AI­ research has been the finding of general purpose method­ ologies and general purpose representations that preserve as much information as possible. A three-step approach for solving any problem has been taken for granted. The conversion of external data (sensor data, actuator com­ mands, decision making, etc.) into an internal repre­ sentation and vice versa has been separated from the phase of developing algorithms to perform computations on internal data. Most research has been devoted on pro­ cessing the internal data, and as a consequence different subfields such as planning, machine learning, knowledge­ based data bases and many more appeared. Therefore it is not surprising that the first influential theory of computational vision [Marr, 1982] mainly concentrated on the computational and representational aspects. Im­ portant results have been achieved at the level of com­ putational theories and development of algorithms deal­ ing with internal representations. Nevertheless, it has to be admitted that vision and AI in general, are far from the ultimate goal of building a machine possessing capabilities of living organisms. Critics of the general AI-philosophy argue that the study of intelligence can­ not be separated from the study of the system's interac­ tion with its environment [Aloimonos et a/., 1988; Aloi­ monos, 1990; Bajcsy, 1988; Bajcsy and Campos, 1992; Ballard, 1991].

· Department for Pattern Recognition and Image Pro­ cessing, Institute for Automation, Technical University of Vi­

enna, Treitlstrafie 3, A-1040 Vienna, Austria

1 About 40 % of the human brain is devoted to visual processing.

Taking this point of view, allows us to pose any prob­ lem in vision, or perception in general, as a problem of recognition as opposed to recovery (or reconstruc­ tion). Researchers usually taxonomize visual probl~ms into three basic categories: problems related to object recognition, to navigation and to manipulation. The first ones are obviously problems of recognition . It can easily be demonstrated that visuomotor coordina­ tion tasks (novigation and manipulation) can be for­ mulated as problems of recognition. For example, the problem of obstacle avoidance can be addressed through depth recovery and possive ranging techniques [Bhanu and (editors), 1992], but also through the recognition of "time-to-collision" values below a threshold, where the choice of the threshold is related to the reaction time of the agent [Nelson and Aloimonos, 1989]. Similarly, the problem of detecting independent motion by a mov­ ing observer may be addressed through techniques for segmenting optic flow fields-which work only in model­ based approaches [Koller et a/., 1992]-or through the recognition of non-rigid flow fields for a moving ob­ server partially knowing its motion [Aloimonos, 1990;

Nelson, 19l:>1]. In the same way, the problem of hand/eye coordination can be dealt with using stereo and other techniques to compute the depth map and then solve the inverse kinematics problem in order to move the arm. While the arm is moving, the system is blind [Brady et a/., 1983]. However, the same problem can be solved through the creation of a mapping from image features to the robot's joints; then, positioning of the arm is achieved by recognizing the image features [Herve et a/., 1991].

In general , navigation and manipulation tasks, since they inherently involve metric relationships between the observer and the environment, have been considered as subproblems of a general visual reconstruction problem, the so called "structure from motion" problem (see next section) . In this paper we consider a very general, cel­ ebrated navigational problem that has been at the core of the reconstructionist school of thought, the problem of egomotion estimation from dynamic imagery. It has usually been considered as a numerical analysis prob­ lem, where sophisticated techniques (such as singular value decomposition, simulated annealing, Kalman fil­ tering, maximum likelihood estimation, etc.) have been employed in order to estimate 3-D motion from the ge­ ometric and photometric constraints which relate local image motion to the 3-D world . In this study we take a different approach to this problem by introducing new global constraints, which take the form of patterns in the image plane. Estimating motion amounts then to recog­ nizing particular patterns on the image through a simple search in spaces of low dimensionality. Since 3-D rigid motion consists of a translation and a rotation, finding the axes of translation and rotation, in our approach , amounts to recognizing the points where these axes in­ tersect the image plane. It is these points/locations that are recognized by recognizing the location of patterns in the image plane.

Previous work along these lines is due to [Horn and Weldon, 1987], who treated the case of only translational motion and [Aloimonos and Brown, 1984J, who treated the pure rotational case.

2 The problem : Overview

For years 3-D motion interpretation has been approached through studying the "structure from motion" problem. The goal is to recover from dynamic imagery the 3-D motion parameters and the structure of the objects in view. The suggested strategy involves to carry out the problem in two stages. First accurate image displace­ ments between consecutive frames have to be computed, either in form of point correspondences or as dense mo­ tion fields (optical flow fields) and then the 3D-motion and the structure is computed from the equations relat­ ing it to the 2-D image velocity. (For an overview see [Aggarwal and Nandhakumar, 1988]) . The "structure from motion" approach has been uncritically accepted and as a result most studies on visual motion perception are to be found at the algorithmic level of the problem; addressing either the estimation of image motion or the recovery of 3-D motion and structure from image motion.

Here we do not consider the general problem of "structure from motion", but the problem of "passive naviga­ tion", i.e. the determination of the rigid 3-D motion of an observer moving in a static environment (its direc­ tion of translation and its rotation). The method does not require the computation of exact 2-D motion. In general, the estimation of optical flow is an ill-posed problem and additional assumptions must be made in order to estimate it . If these assumptions hold, as in the case of some model-based approaches [Burt et a/., 1989; Koller et a/., 1992), optical flow can be computed ac­ curately and in the sequel correct 3-D motion can be derived. In the general case, however, any algorithm will produce imperfect output. Therefore, we use as rep­ resentation for image motion the so-called normal flow, i.e. the prection of the flow on the gradient direction ((I,, ly) · (u, v) = -It) . Recovering 3-D motion from noisy flow fields has turned out to be a a problem of extreme sensitivity with researchers reporting very large amount of errors in the motion parameter estimation un­ der small perturbations in the input . Even optimal al­ gorithms [Spetsakis and Aloimonos , 1988] perform quite poorly in the presence of moderate noise. Although a for­ mal proof is still lacking, it has been argued [Adiv, 1985), that the estimation of 3-D motion from image motion is itself ill-posed, because it does not continuously depend on the input . Thus , in order to estimate 3-D motion in a robust way, we have to consider the fact, that no flow measurement (neither optical flow, nor normal flow) can be perfect. In this study new global constraints of ge­ ometric nature, which relate 3-D motion to 2-D image measurements are introduced. In our approach, we first find the rotation axis and the direction of translation . After having found the axis of rotation and the direction of translation further constraints are considered, and the complete set of motion parameters is obtained .

3 Geometric constraints

If the coordinate system is fixed to the observer with the center being the nodal point of the camera and f the fo­ cal length, then the equation relating the normal flow Un at a point (x, y)- i.e. the projection of the image velocity (u, v) on a unit vector (n,, ny)along the image gradient direction at (x, y)-to the 3-D velocity ((U, V, W) trans­ lational and (a, {J, 1) rotational) and the depth z of the corresponding scene point, is:

The above equation demonstrates the difficulties of motion computation using normal flow. A monocular observer not being able to measure depth is confronted with a motion field of five unknown motion parameters and one scaled depth component (W/Z) at every point .

3.1 Motion field interpretation

A motion field is composed of a translational and a rota­ tional component. If the observer undergoes only trans­ lational motion, all points in the 3D scene move along parallel lines. Translational motion viewed under per­ spective results in the image plane in a motion field , where every point moves along a line through one van­ ishing point . This point constitutes the intersection of the image plane and the parallel line passing through the nodal point . Its image coordinates are xo = U f IW and Yo = V f IW, the flow there is of value zero. In cases where the sensor is approaching the scene all vectors are emanating from the vanishing point, then called Focus of Expansion (FOE).

In cases of purely rotational motion every point in 3D moves along a circle in a plane perpendicular to the axis of rotation. The perspective image of the circular path is the result of an intersection of the image plane with the cone which the circle defines with the rotation axis. Depending on the relation of the opening angle of the cone for a specific image point and the angle the image plane forms with the rotation axis, the field lines of the rotational vector field (i .e the lines which have the prop­ erty that at each point the rotational flow is tangential) form different second order curves: ellipses, hyperbolas, parabolas and even circles when the rotation axis and the optical axis coincide. The specific conic sections due to a rotational motion are defined by the axis of rotation . A rotation axis, given by the two parameters ( f!.) and ( ~ ), . ~ ~ defines the family M(~ , *; x , y) of conic sections as:

Specifically, for a rotation around the Z-axis the sec­ ond order curves are circles with center 0; we call them -y-circles (Figure 1a) . If the rotation axis is the X- or Y­ axis the conic sections are hyperbolas whose axes coin­ cide with the coordinate axes of the image plane. For the case of rotation around the X-axis the hyperbolas' major axis is the x-axis and they are called a-hyperbolas (1b) . For rotation around the Y-axis the major axis is the y-axis and we call the conic sections ;3-hyperbolas. (Figure 1c}.

4 Global motion constraints

In this section we study the sign of the normal flow in certain directions and the localization of normal flow vec­ tors of equal sign. Vectors which are perpendicular to rotational vector field lines are considered. For these vectors we find that the FOE and the axis of rotation separate the normal flow values in the image according to their sign by a second order curve and a straight line.

4.1 Selection of values

The normal flow vector u-;. is the projection of the optical flow vector ii on the gradient direction and the value of the normal flow is therefore defined by the scalar product of the optical flow vector and the unit vector in gradi­ ent direction . The flow vector can be decomposed in its translational and single rotational components and the right hand side of equation (1) can be written as a sum of scalar products.

All the normal flow vectors that form right angles with the -y- circles do not contain a component due to rotation around the Z-axis. Similarly, there is no motion compo­ nent due to rotation around the X-axis for the normal flow vectors perpendicular to the a-hyperbolas, and no component due to rotation around theY-axis for vectors perpendicular to the ;3-hyperbolas. The motion estima­ tion problem becomes easier when analyzing only the normal flow vectors perpendicular to one of these fami­ lies of conic sections. It is reduced by one parameter for these subsets of the normal flow vectors .

We call these three subsets of the normal flow vectors the a-, ;3-, and-y-vectors. It is convenient to agree upon conventions for the vectors' orientations. A -y-vector at point (x, y) is said to have positive orientation if it is pointing in the direction (x , y) ; otherwise, its orientation is said to be negative. Similarly, we call an a-vector (or a ;3-vector) originating from a point (x , y) positive if it points in the direction ( -{!2 + y2), xy) (or (xy, -{!2 + x 2 ))) (see Figure 1) .

4.2 Properties of the subsets

Let us first concentrate on the -y-vectors. These vectors do not contain a component due to rotation around the Z-axis. Along the positive direction, the two remaining rotational components contribute

Vrot(r, ¢) = -a(r 2 If+ f) sin¢+ ;3(r 2 If+ f) cos¢ , where r is distance from the image center and the angle ¢ is measured from the x-axis. Thus, the rotational com­ ponent of the normal flow along a vector pointing away from the image center can be described by a trigono­ metric function with amplitude max( a , ;3) and period 27r . Along the line which passes through the image cen­ ter and makes angle ¢ = arctan(J) I a) with the x-axis the values are zero. This line divides the plane into two halves . In one half the vectors point in the positive di­ rection, and in the other half they point in the negative direction ; in the future we simply refer to them as posi­ tive and negative vectors (Figure 2a) .

The translational component of the motion field is characterized by the location of the FOE in the image plane. The -y-vectors lie on lines passing through the

Figure 2:

a: The 1-vectors due to rotation separate the image plane in a halfplane of positive values and a halfplane of negative values. b: The 1 vectors due to translation are negative, if they lie within the circle defined by the FOE and the image center and are positive at all other locations. c: A general rigid motion defines an area of positive ~­ vectors and an area of negative 1-vectors. The rest of the image plane is not considered.

image center and the optical flow values due to trans­ lation lie on lines passing through the FOE. These two lines are at right angles for all points on a circle which has the the FOE and the image center as diametrically opposite points. At these points the 1 vectors' transla­ tional components vanish. Thus, the geometric locus of all points on the 1-hyperbolas where there is zero transla­ tional normal flow, is a circle. The diameter of this circle is the line segment connecting the image center and the FOE. At all points inside this circle the two lines enclose an angle greater than 90° and the normal flow along the 1-vector therefore has a negative value. The normal flow values outside the circle are positive (Figure 2b ).

In order to investigate the constraints associated with a general motion, the geometrical relations derived from rotation and from translation have to be combined. A circle separating the plane into positive and negative val­ ues and a line separating the plane into two halfplanes of opposite sign always intersect (in two points or one point in case the line is tangential to the circle), because both the line and the circle pass through the origin. This splits the plane into areas of only positive, of only nega­ tive 1-vectors, and into areas in which the rotational and translational flows have opposite signs. In the latter ar­ eas, unless we make depth assumptions, no information is derivable (Figure 2c).

We thus obtain the following geometrical result for the case of general motion. Points in the image plane at which the gradient direction is perpendicular to cir­ cles around the image center can be separated into two classes. For a given FOE, and for a line through the image center which represents the quotient of two of the three rotational parameters, there are two geometrically defined areas in the plane, one containing positive and one containing negative values. We call this structure on the 1-values the 1-pattern. It depends on the three parameters xo, Yo and ~ ·

Similar relations can be derived when eliminating the motion components due to rotation around the X- and Y- axes . The a- and ,8-vectors due to rotation are also separable into positive and negative vectors. In both cases the locus of zero normal flow which separates the two classes is a line. For the a-hyperbolas the line is parallel to the x-axis and is defined by the equation y = ~, for the ,8-hyperbolas it is parallel to the y-axis and is defined by x = ¥· The translational components of the a- and ,8-vectors are separated by hyperbolas . The a-vectors, which are perpendicular to lines through the FOE, and which therefore have zero normal flow lie on a hyperbola of the form

When h(x0 , y0 ) > 0, the normal flow values are positive; in the other part of the plane they are negative. Sym­ metrical relations hold for the ,8-vectors. The curve of zero normal flow is defined by

and in areas of positive g( xo, Yo) the ,8-vectors are posi­ tive.

The superposition of translational and rotational val­ ues again defines patterns in the plane each of which consists of a negative and a positive area. These pat­ terns, called a- and ,8-patterns, are uniquely described by three parameters: x0 and y0 , the coordinates of the FOE and the quotients * (and ~) (Figure 3) .

The a- ,8- and -y-patterns are obtained as special cases from a more general pattern concept defined for normal flow vectors in all directions [Fermiiller, 19921

5 Motion recognition: The technique

In this section we describe a search technique, which utilizes the geometrical constraints on the a- , ,8- and /­ vectors to recognize the direction of translation ( xo, Yo) and the axis of rotation ( ~· * ). By fitting a small num­ ber of patterns to the normal flow field, candidate solu­ tions for the axis of translation and the direction of the rotation axis are obtained. In this fitting process the in­ put is used in a qualitative way, since only the sign of the normal flow is employed. The search for motion-patterns forms the core of our motion recognition strategy. The whole motion recognition technique requires two more processes: the ones of "detranslation" and "derotation"; additional constraints are checked, which estimate the third rotational component and narrow down the solu­ tion space to a unique 3-D motion vector.

5.1 Pattern fitting: Search in 3D parameter spaces

The geometrical constraints developed in the last sec­ tion are used in a search process to estimate the direc­ tions of the translation and the rotational axis. Finding these two directions is a four-dimensional problem, but through selection of values and use of geometrical con­ straints the problem is reduced in dimensionality. With each subset of the normal flow vectors is associated a three-dimensional parameter space that spans the pos­ sible locations of the FOE and of a line defined by the quotient of two of the three rotational parameters. In­ stead of searching a four-dimensional space, three three­ dimensional subspaces are searched for the solution .

The search in the three-dimensional subspaces is ac­ complished by checking the patterns which the sub­ spaces' parameter triples define on selected values of the normal flow field. The u-patterns are fitted to the a­ vectors; this provides possible solutions for the coordi­ nates of the fC>E: X 0 , Y0, and the quotient ~ - Simi­ larly, the fittwg of the f.- or r-patterns yields solutions for X0 , Yo and ~or !!: , The objective is to find the t0ur 1 ., parameters defining the directions of the translational and rotational axes which give rise to three successfully fitted patterns. Therefore the three subspaces' patterns are combined and the parameter quadruples which define possible solutions are determined. Since only subsets of the normal flow values are considered in the fitting pro­ cess, the fitting does not uniquely define the motion, but just constitutes a necessary condition. Usually a number of parameter quadruples {xo,Yo,ah,/3/r} are selected as candidate solutions through pattern fitting.

The range of values for the coordinates of the FOE and for ~and ~ is [-oo, +oo) . To cope with all possible cases a coordinate transformation on the sphere is per­ formed, in which case the coordinates are expressed by two angles.

5.2 Detranslation

Proper selection of normal flow vectors also makes it pos­ sible to eliminate the normal flow's translational compo­ nents. If the location of the FOE is given the directions of the translational motion components are also known. The optical flow vectors lie on lines passing through the FOE. The normal flow vectors perpendicular to these lines do not contain translational components; they have only rotational components. For each of the possible solutions computed by pattern fitting, the normal flow vectors perpendicular to the lines passing through the FOE have to be tested to determine if they are really only due to rotation This results in solving an overde­ termined system of linear equations. Since two of the ro­ tational parameters are already computed, there is only one unknown. If the chosen normal flow vectors are due only to rotation then the solution to the overdetermined system gives the r value. Usually "detranslation" will not result in only one solution, but will provide a set of possible parameter quintuples.

5.3 Derotation

The computational steps described so far considered only subsets of the normal flow vectors. In order to eliminate all motion parameters which are not consistent with the given normal flow field, every normal flow vector has to be checked.

This check is performed using a "derotation" tech­ nique. For every parameter quintuple derived so far, a possible FOE and a rotation is defined. The three ro­ tational parameters are used to derotate the normal flow vectors by subtracting the rotational component. At ev­ ery point the flow vector ( uder, vder) is computed:

If the parameter quintuple defines the correct solu­ tion, the remaining normal flow is purely translational. Thus the corresponding optic flow field consists of vec­ tors that all point away from one point, the FOE. Since the direction of optical flow for a given FOE is known, the possible directions of the normal flow vectors can be determined. The normal flow vector at every point is confined to lie in a half plane (see Figure 4) . The tech­ nique checks all points for this property and eliminates solutions that cannot give rise to the given normal flow field . It may happen that more than one solution is pos­ sible, since in general normal flow fields do not uniquely define 3-D motion.

6 Experiments

Several experiments have been performed on synthetic and real data. For different 3D motion parameters nor­ mal flow fields have been generated, where the depth value within an interval and the gradient direction are chosen randomly. In all experiments on noiseless data the correct solution is found as the best one. Figure 5 shows the optical flow field and the normal flow field for one of the generated data sets: The image size is

100 x 100, the focal length is 150, the image coordinates of the FOE are ( -5, +30) and the relationship of the rotational components is a : f3 : 1 = 10 : 11 : 150. In figure 6 the fitting of the circle and the hyperbolas to the a- f3 and 1-vectors. ~) is displayed. Points with positive normal flow values are rendered in light color and points of negative value are dark . Since only the sign of the normal flow is utilized in the pattern fitting step for finding the axes of rotation and translation, the procedure can handle errors of up to 100 percent .

As a natural scene the NASA-Ames sequence 2 has been chosen. The camera undergoes only translational motion, and we added different amounts of rotation : For all points at which translational motion can be found the rotational normal flow is computed, the new position of each pixel is evaluated. The "rotated" image is then generated by computing the new greyvalues through bi­ linear interpolation. The images were convolved with a Gaussian of kernel size 5 x 5 and standard deviation u = 1.4. The normal flow was computed by using 3 x 3 large Sobel operators to estimate the spatial derivatives in x- and y-directions and by subtraction of the 3 x 3 box-filtered values of co~secutive images for the tempo­ ral derivatives.

When adding rotational normal flow in the order of a third to three times the amount of translational flow the exact solution always has been found among the best fit­ ted parameter sets. In figure 7 the computed normal flow vectors and the fitting of the a-, {3- and 1-vectors for one of the "rotated" images is shown. Areas of negative nor­ mal flow vectors are marked by horizontal lines and areas of positive values with vertical lines . The ground truth for the FOE is ( -5 ,-8) , the focal length is 599 pixels and the rotation between two image frames is a = 0.0006, f3 = 0.0006 and 1 = 0.004. The algorithm computed the solution exactly.

7 Conclusion

We argue that every vision problem can be formulated as a recognition problem with two questions to be solved. The first question, what to recognize , is related to the task , which the visual system is supposed to perform and the second question how to recognize is concerned with Figure 6:

2 This is a calibrated motion sequence made public for the Workshop on Visual Motion, 1991

a,b ,c: Positive and negative a- , {3- and 1-vectors for syn­ thetic data.

d,e,f: Fitting of a-, {3- and 1-patterns .

1-pattern

Figure 7: Real scene: Normal flow field and fitting of a­ .8- and 1-vectors.

the computational approach to be taken . Our position is that any visual problem should be addressed in a robust , non-local and qualitative manner . As an example we treated the celebrated problem of passive navigation as a recognition problem.

We presented geometric constraints on normal flow fields due to rigid motion, which take the form of pat­ terns in the image plane. These constraints were ex­ ploited to solve the problem of recognizing the 3D­ motion of an observer relative to the scene in a robust way.