Qualitative Motion Understanding

1. INTRODUCTION

Visual information about the environment is an indispens­ able clue for the operation of an autonomous land vehicle (ALV). Due to the vehicle's egomotion, however, the resulting camera image is continuously changing even in a completely stationary environment. Any change in the 2-D image is the result of some change in 3-D space, either induced by vehicle motion or by moving objects in the field of view.

The purpose of our approach is to find consistent interpre­ tations of time-varying images obtained from the camera on a moving vehicle. Specifically we are interested to deter­ mine

• how is the camera moving ?
• what is moving in the scene and how does it move ?
• what is the approximate 3-D structure of the scene ?

The original input is a sequence of images, taken at a constant rate. A reliable low-level correspondence technique4 is assumed to be available, which extracts distinct features from every image and supplies their 2-D image locations in successive frames. The correspondence algorithm labels each feature and tracks it over time by generating tupels (feature-label, time, x-location, y-location).

Previous work2 in motion analysis has concentrated mainly on numerical techniques for computing motion parameters and scene structure from image sequences. While a completely stationary environment has often been assumed for the recovery of the camera motion, the possible presence of moving objects must be accounted for in this scenario. Similarly, we cannot rely on a stationary camera setup to detect those moving objects. Clearly, some kind of common reference is required, against which the movement of the vehicle as well as the movement of objects in the scene can be related. For this purpose, a vehicle-centered Qualitative Scene Model (QSM) is constructed and maintained over time, representing the current set of feasible interpretations of the scene.

·This work was supported by the Defense Advanced Research Projects Agency under contract DACA 76-86-C-0017 and monitored by the U.S. Army Engineer Topographic Laboratories.

2.1MAGE OBSERVATIONS

The first step of our approach is to determine the vehicle's motion relative to the stationary environment between each pair of frames. If the vehicle moves along a straight line, all stationary features seem to expand from one single point in the image, the focus of expansion (FOE). Given the accu­ rate location of the FOE, the relative range of any (station­ ary) point Pin the image can be determined at timet by the relation

where Z(t) denotes the actual distance of the point from the image plane in 3-D, V(t) is the velocity dZ/dt of the vehicle perpendicular to the image plane, r(t) is the 2-D distance between the image of P and the FOE, and v(t) is the radial velocity drldt. Since V(t) is the same for any stationary point in the scene, r(t) and v(t) can be measured in the image and depth can be computed up to a common scale factor. Furth­ ermore, by knowing the vertical distance of the camera to the ground, absolute values for vehicle velocity and range can be obtained.

While the vehicle is traversing the environment, Z(t) keeps changing for every feature in the field of view. If the depth map itself was used as the scene model, the model would have to be updated continuously. The topology of the sta­ tionary part of the scene, however, should remain unchanged.

In reality the AL V does not travel along a straight line but performs small rotations, which induce an additional vector field in the image (Fig. l(a)). The fact that all the displace­ ment vectors of stationary features must intersect at a com­ mon point can be used to "derotate" the image3 and compute the vehicle's rotation and direction of translation (Fig. l(b)). Due to inertia, the direction of translation as well as the amount of rotation about either axis cannot change drastically between two frames. Thus the previous motion param­ eters can serve as a good initial guess for computing the current vehicle motion. We do not assume that the exact location of the FOE in the image plane can always be deter­ mined, but that a region can be specified, which contains the FOE with high certainty. Although this first step is done exclusively in the image plane, knowledge about the station­ ary features to be used must be available in some form. This information is supplied by the QSM which is described below.

The feature-property stationary/mobile and the closer rela­ tionship between features are the basic building blocks of the QSM. (Mobile a) means, that a has been found moving once and is not considered part of the stationary environ­ ment. A point a is said to be closer than b (closer a b), if a is closer to the camera plane than b in space. The current set of image features together with assigned properties and mutual relationships constitute an interpretation of the scene. An interpretation is feasible, as long as it is free of internal conflicts, e.g. (closer a b) and (closer b a). The QSM comprises a set of feasible interpretations of the current scene. As the vehicle proceeds, new observations in the image are incorporated into the model, while existing hypotheses inside the QSM are verified.

Since the interpretation of image motion is inherently ambiguous, different forms of visual information are employed for the construction of the QSM: geometric, spa­ tial, and semantic information. Each of these three types of knowledge is formulated as a group of rules in a Blackboard environment. The following examples shall illustrate the basic ideas:

Rule GEOMETRY-I:

if image-point a is moving toward the FOE-region

then assert (mobile a).

Rule GEOMETRY-2: An image point a is said to be inside a point b, if a,b are in some neighborhood and a is at a smaller distance from the FOE than b. D a,b(t) denotes the Euclidean distance from a to b at time t.

if (stationary a b) & (inside a b) & ( Da,b(t) > Da,b(t+I) ) then hypothesize (closer a b).

Rule GEOMETRY-3: This constraint-rule verifies that a hypothesis generated in the previous rule can be maintained over time. if (stationary a b) & ( Da,b(t) > Da,b(t+l) )

then verify ( Da,b(t+I) > Da,b(t+2) ).

While the results from geometry are valid for arbitrary configurations, certain assumptions can be made about the spatial layout of the scene which is encountered by the ALV. For example, the fact that (for an upright camera) the lower features in the image are generally closer to the vehi­ cle can be expressed in the following heuristic rule.

Rule SPATIAL-I : For any pair of image points a ,b: if (lower a b)

then hypothesize (closer a b)

As a consequence, it is very unlikely that a feature is farther away than all its surrounding neighbors.

Occlusion is another important source of spatial information, which is applicable for more complex features such as lines and regions. A feature occluding another is certainly closer to the viewer than the occluded feature.

Semqntic information becomes an important factor as soon as partial interpretations of the scene are available. For instance, if the horizon has been identified, any object above it must be in the sky and is probably not stationary. Simi­ larly, the features of an object recognized as a building would not be considered moving in an ambiguous situation.

3. INTERPRETATION AND CONFLICT RESOLUTION

Using a set of rules like the ones described in the previous section, the Qualitative Scene Model is constructed. Here we describe how the model develops over time, how new interpretations of the scene are generated, and how conflicts are resolved.

An example with a scene containing three feature points a,b,c is shown in Figure 2. Initially (at t = t0) nothing is known about the spatial relationships between these points and whether they are stationary or not. The default assump­ tion is that any point is stationary unless there is an indica­ tion that this is not true. The initial interpretation of the scene thus contains only

Interpretation A(t0) : .

(stationary a b c).

Suppose that between t0 and t 1 all three points show some amount of expansion away from the FOE, giving rise to the conclusion (e.g. by rule GEOMETRY-2) that a is closer (to the vehicle) than b, a is closer .than c, and c is closer than b. From the information gathered up to this point, the interpre­ tation of the scene at time t 1 looks like this:

Interpretation A(t 1 ) :

(stationary a .b c),

(closer a b), (closer a c), (closer c b).

At time t2 one of the rules claims that c is closer than a and tries to assert this fact into the current interpretation. Clearly, the new interpretation would contain the conflicting facts

(closer a c) and (closer c a),

which would not be a feasible interpretation. The conflict is resolved by creating two disjunct hypotheses B and C, with either a or c as mobile:

lntetpretation B(t2):

(11Wbile a)~ (stationary b c), (closer c b).

lntetpretation C(t~:

(11Wbile c), (stationary a b), (closer a b).

Notice, that when a feature is hypothesized to be 11Wbile, all its closer-relationships are removed from the intetpretation. At this point in time (t2), two feasible intetpretations of the scene are active simultaneously. All active intetpretations are pursued until they enter a conflicting state, in which case they are either branched into new intetpretations or removed from the QSM.

In our example we assume, that both intetpretations B and C are still alive at time ti. At this point some rule claims, that if b, c are both stationary, then b is closer than c. This creates a conflict in intetpretation · B, because B contains the contradictory fact (closer c b)! Again we could branch intetpretation B into two new intexpretations (D,E), with either (11Wbile b) or (11Wbile c). At this time, however, there exists another active interpretation (C), which could absorb (closer b c) without causing an internal conflict (c is 11Wbile in C). Therefore B is not branched out but removed alto­ gether from the model, and only intetpretation C survives.

In summary, the development of the QSM is controlled by the following meta-rules:

• After a ·hypothesis has been created by one of the analyzing rules, try to integrate this hypothesis as a fact into every active intetpretation.
• If the new fact is consistent with the intetpretation, make it a part of this intetpretation.
• If the new fact is not consistent with the intexpretation, and there are currently no other intetpretations active, then create a new set of intetpretations containing this fact

without conflict

• Otherwise prune the search tree by deleting the conflicting intetpretation from the model.

4. CONCLUSIONS

In this paper we presented a new approach for the problem of motion intexpretation in the scenario of an Autonomous Land Vehicle, following a qualitative line of reasoning and modeling. Different forms of visual information are com­ bined in a rule-based framework to construct and maintain a three-dimensional qualitative model of the environment Instead of refining a single numerical model a set of disjunct intetpretations of the dynamic scene are pursued simultane­ ously.

The work reported here shows the conceptual outline of our approach. While we have considered only point-features so far, the integration of lines and regions will be a natural extension. An implementation is currently under way using actual AL V imagery .1