Artificial 3D Vision

1 Introduction

In this talk, we discuss the following problem: suppose we have a mobile robot moving around in an otherwise unknown man made environment. Is it possible to let the thing wander around and build incrementally, using passive Vision, a three dimensional representation which:

1. does not grow too large even if many measurements are accumulated (capability of "intelligently forget­ ting").
2. is accurate even though the motion of the robot is not accurately known (converges in time toward the "real world" description)?

We have made some progress toward the solution of this problem whose applications to the field of Robotics should be obvious.

This presentation is in three parts. In the first part we somewhat detail the basic assumptions and techniques that have allowed us to come up with efficient solutions to the problem of building a local 3D map from Stereo Vision and Structure from Motion. In the second part, we show how the motion of the vehicle can be computed accurately by Visual Motion based tech'liques. In the third part we present a purely geometric approach to the problem of cop1bining several viewpoints into a single surface and volume r~presentation of the environment. In the fourth part, we present a solution to the same problem that takes into account the Uncertainty in the visual measurements and the motion of the robot.

· This work was partially supported by Esprit Project P940

Artificial 3D Vision

0 livier D. Faugeras IN RIA

Domaine de Voluceau-Rocquencourt BP 105- 78153 Le Chesnay Cedex- France

EXTENDED ABSTRACT

In our work, we have followed two guiding lights. The first is Geometry: a Vision System is mostly a geometric engine and ours deals directly with geometric entities which are constructed from the visual inputs. The second guiding light is that of Uncertainty. Uncertainty is always present in the real world and cannot be engineered away. Therefore it must be present explicitely in the representations which are manipulated by the system.

2 Building 3D maps from passive Vision

We exploit the fact that in a man made environment many polyhedral or closely polyhedral objects are present. There­ fore, it is natural to adopt a representation that is based on linear geometric primitives: points, lines, and planes. The line primitives are computed immediatly from the input images and then used as tokens in the Stereo and Motion Matchers that compute 3D Geometry and Motion. We have developed several Stereo matchers which all use the basic paradigm of Hypothesis Prediction and Testing to match 2D line segments ]5,6] and differ by the number of cameras inputs they use. The fastest, most reliable and accurate matcher is the one using three cameras.

They all use as their basic principle the idea of work­ ing not on the images themselves to establish the matches but on symbolic representations of these images. These symbolic representations are neighborhood graphs of line segments extracted from the images. The matchers can ac­ comodate any camera geometry thanks to a powerful cal­ ibration technique described in ]11] from which the epipo­ lar geometry can be easily computed. Thanks to this, they can operate in a purely geometrical setting which increases tht>ir speed and reliability.

3 Obtaining a more accurate esti­ mation of the robot motion from passive Vision

Some information about the robot motion is available from for example, inertial guidance and/ or odometry. This in~ formation is usually not accurate enough and passive Vision is an efficient way of obtaining a more accurate estimation. Inversely, if the robot is not moving or moving with an ac­ curately known motion, then passive Vision can be used to estimate the motion of a mobile object passing by, using exactly the same methods. We have developed a number of techniques for solving this problem which are all based on a combination of three ingredients: Hypothesis Prediction and Testing to establish the token matches, representing and manipulating Uncertainty to evaluate their likelihood, and Geometry to provide the framework.

3.1 Motion from 2D points and lines

This set of techniques exposed in 17] allows us to obtain the motion of a camera by matching points in the retinas at two positions at times t and t + ~t, or lines in the retinas at two positions at times t, t + ~ti> and t + ~t2 · It therefore uses the same primitives as the ones which are used by the Stereo matcher and can be computed at Video rates. It turns out that, contrarily to what has been reported in the literature, this token matching based approach for the estimation of Motion is quite robust to noise and provides very accurate results.

3.2 Motion from Stereo

Supposing that we have computed 3D by Stereo at times t and t + ~t, by matching 3D primitives such as points, lines, and planes between the two representations, then we can reliably compute the motion of the robot . We use the same ingredients as before: Hypothesis Prediction and Testing, Uncertainty manipulation, and Geometry. This work is a generalization of some previous work 14,10] and is described in more details in 12] .

4 Combining several viewpoints: a geometric approach

The problem which is tackled here is that of producing from the previous Geometric and Kinematic data a coherent de­ scription which is both:

1. surface oriented: to allow recognition / manipulation.
2. volume oriented: to allow trajectory planning j man­ ipulation.

In order to achieve this we use our previously ~omputed es­ timates of motion to express all our local 3D data (or a sub­ set of it) in the same coordinate system. We then compute a volumetric tesselation of 3D space that is intrinsic to the measurements. This part uses heavily some recent results in Computational geometry 112]. We then exploit a sim­ ple visibility property to distinguish the tessels which are empty (their reunion provides the volume representation pf free space) from those which are not (their bord~r pro­ vides the surface representation of the objects/ obstacles). This work is described in more details in IS]. It solves the problem of building a coherent 3D description of the environment but does not completely satisfies the first re­ quirement that we set up at the beginning. Indeed, if the number of measurements increases, so does the complex­ ity of the representation (as measured for example by the number of texels) . A solution to this problem is provided in the next Section.

5 Combining several viewpoints: a probabilistic approach

If we not only represent the geometry of our primitives, but also the uncertainty that is attached to them we end up with a slightly different picture from the one of the previous Section. Our representation of the environment is made of a number of uncertain geometric primitives attached to co­ ordinate frames related by uncertain rigid motions. The more we move the robot and make visual measurements the more we increase the number of geometric primitive~ in the representation. This is clearly unsatisfactory and we must provide the system with means of "forgetting intelli­ gently" . This is achieved by exploiting the following simple idea: if a physical line segment S, for example the edge of a desk, is detected in, let us say, two positions 1 and 2 of the mobile robot, it is then present as segment S1 in the coordinate system attached to position 1 and as segment S2 in the coordinate system attached to position 2. Since we can relate by a rigid motion positions 1 and 2, by applying the correct transformation to S2 , the physical segment S is represented by two segments sl and s~ in the coordinate system attached t~ position 1. By comparing the represen­ tations of sl and s~ in terms of both their geometry and their uncertainty, our system is capable of discovering that these two segments are very likely to be instances of the same physical segment. It then proceeds to merge them into a single segment whose representation is a combina­ tion of the representations of sl and s~. It has therefore "forgotten" the two instances of S and merged them into a single "better" one, better in the sense that it is more accurate than either one. We have therefore reached two goals:

1. the accuracy of the description increases with the number of measurements.
2. its size does not grow out of control since we are ca­ pable of fusing pieces of it which are instances of the same physical event.

This part of our work is described in more details in [9,2,1,3).

6 Conclusions

The system that we have sketched in this Abstract has been fully implemented and is used to drive a mobile robot de­ signed at INRIA. This robot is used by a variety of users a:; a testbed for Vision algorithms. In a near future it will b<' equipped with video rate capabilities for computing the line segments which are at the basis of our 3D represen­ tations. All the matching algorithms that we use are very highly parallel, and this is an obvious way of improving the response time performances of the system. This ap­ proach is followed in a joint effort with a number of euro­ pean academic and industrial partners. We think that the most important contribution of our system is to provide a proof of existence that Vision theory and practice have now reached a stage where fascinating questions such as the relation of shape and function, the relation of language and our perception of the 3D world, and many others can he reasonably asked without confining them to solipsistic systems.