Spatial Object Perception from an Image

1. INTRODUCTION

Among various aspects of perception for whi ch Computer Vision is trying to find a computa­ tional theory, an intriguing one is the rnechanism by which two-dirnensional (2D) shapes are sometirnes percei ved as three- dirnensional (3D) objects. There are at least two reasons for investigating this subject. First, there is evidence that people perform spatial reasoning whenever they deal with images. If they are asked to rnatch two irnages of the same object, they rotate the object rnindly in the 3D space even if the transform occurs in the image plane. This irnplies that the interpretation space is different from the irnage plane. And second, we are interested in devising a technique for interpreting images of known things : when is it possible to retrieve the six degrees of freedorn of an object from a single view assuming that the object and the camera geornetry are known in advance ? Which are the theoretical and practical limi tations of such a method if it were implemen­ ted as a computer algorithm ? An interesting application could be the recogni tion of man made parts in an industrial environment.

In this paper we suggest on possible ap­ proach limited to objects bounded by planar faces. First we extract linear edges from an intensity image and these edges are combined to form angles and junctions which are assumed to be projections of 3D object vertices. These sets of image feaplane is defined by an image line and the focal center and it contains all the spatial interpreta­ tions of the image line. The possible directions of these spatial lines lie on a great circle, the intersection of the interpretation plane with the gaussian sphere. If we denote by P the vector normal to the interpretation plane and by L the space line direction vector, the equation of the great circle is

*r he work reported herein is supported by "Labora toire d'Electronique et de Technologie de l'Informatique", Grenoble, France.

**rhe author is now with LIFIA, B.P. 68, 38042 Saint-Martin d'Heres, France.

Similarly we can develop constraints for the spatial interpretations of image angles and junctions. The motivation for choosing these fea­ tures is that they are the projections of object vertices. Let 1 1 and ~ be two image lines forming an angle. Their spatial interpretations are denoted L1 and L 2 and their interpretation planes are denoted P1 and P2. L1 and L2 are constrained to be coplanar : they belong to a space plane S and form a space angle w. We are seeking the orientation of S when w is known. The following equations stand :

Since w is imposed, equation (3) provides a constraint for the possible orientations of the space plane S. Consider now a junction formed by three image lines, 11 , 1 2 and 1 3 whose spatial interpretation is a right vertex with edges L 1 ,L2 and L3. (There is no loss of generality in consi­ dering a right vertex ; this merely simplifies the exposition). l1 and 1 2 can be combined just as above to form an angle constraint. Notice that L3 is parallel to the vector normal to the plane formed by L1 and L2. L3 is constrained to lie on the great circle corresponding to the spatial interpretations of 1 3 . Therefore, the only possi­ ble orientations of S are the intersection of this great circle (eq. (1)) with the angle constraint (eq. (3)). Figure 4 shows the solutions for the image junction indicated by an arrow on Figure 3. Only half of the gaussian sphere is projected and shown on Figure 4 with a (horizontal) varying from lf/2 to 3lf/2 and ß (vertical) varying from -lf/2 to lf/2. The two solutions correspond to two Orienta­ tions of S, one for a concave vertex and the other for a convex one. Wi thout additional information it is impossible to decide which solution to select. This is a simplified version of the Necker's cube illusion. In (1], Kanade developed an analytical solution in the case of orthographic projection but his method requires the measurement of the skewed symmetry of all the faces forming a junction.

3. IMAGE TO OBJECT CORRESPONDENCE

The ultimate goal of a recognition procedure is to assign an object model to a set of image features and · to find the spatial parameters of each object. These parameters will be embedded in a 4x4 homogeneaus matrix that maps an object from model Coordinates to camera coordinates. Let us show now how such a transform may be computed.

We describe first a simple scheme for model­ ling objects within the context of visual recogni­ tion. Foramore complete discussion, see(7]. Such a model contains lists of those features and combinations of features that are the most likely to be detected in an image. The features are also ranked according to the contribution they can make for recognition. The model of an object bounded by planar faces provides a !ist of all faces wi th pointers from each face to i ts bounding edges and similarly each edge points back onto the two faces forming it. Another !ist contains all the vertices and each vertex points onto its three edges. Let V be one vertex and L1, L2 and L3 its edges. There is a vertex centered coordinate system whose axes are L1, L2 and the nor~al to the face bounded by these two edges. The relation between this frame and an object centered coordinate system is completely defined by the geometry of the object and i t can be expressed by a 4x4 homogeneous transform matrix, Am· This transform embeds three rotations and three translations that allow to overlap one frame onto the other.

Suppose now that we know the object assign­ ment of an image junction. That is, there is a unique correspondence between the junction's lines and the edges of the vertex. Since the backpro­ jection of the junction constraints the Orienta­ tions of the face S formed by L1 and L2 to just one direction, we can use equations (2) to deter­ mine the vectors L1 and L2. This will determine the rotation part of a matrix Ac that maps the vertex centered frame into the camera centered frame. The position of the junction in the image determines two translations. In conclusion, under a junction-to-vertex assignment five degrees of freedom are determined. Depth can be computed by triangulation if there is another junction or angle to which a vertex can be assigned. From Am and Ac one can compute the object-to-camera transform, A

The actual correspondence between the model and an image feature set is performed by a hypo­ thesize-and-test procedure. A search space is built where each node represents a junction-to­ vertex assignment. The goal is to find the largest set of nodes that are mutually compatible, i. e., they uniquely define the six degrees of freedom of the part. An object orientation and location is hypothesized from one node (excluding the depth for which initial lower and upper bounds are given). From this assignment a set of visible vertices is computed and for each such vertex its image projection is determined. This could be a junction, if two or three faces are visible or an angle if only one face is visible. For each prediction, the best image feature match is selected. Notice, however that the low level segmentation process is not perfect and the data are noisy. For these reasons some lines may be missing. If the verification step fails in finding a predicted junction or angle it checks for partial descriptions of these i tems in the line list. For each assignment a score is computed by calculating the percentage of object features predicted visible that actually overlap image features. If this score is high enough, the location of the image features as well as their spatial orientation constraints are used for refining the object locational parameters and for estimating tighter bounds for the depth. If the score is too low, the algorithm backtracks to the last choice point.

4. EXPERIMENTAL RESULTS

Figure 2 shows a digitized picture which we have used for verifying the effectiveness of the method. The picture is taken wi th a TV camera through a 25 mm lens. The orientation of the came­ ra relatively to the table top is not known. The object model comprises 24 right vertices (16 are convex and 8 are concave) but two are sufficient to uniquely identify the object. The image segmentation process comprises edge detection ( zero-crossings of the convolution of the image with the difference-of-gaussian operator), edge linking (formation of edge chains) and approxima­ tion of these chains with straight lines (piece­ wise polygonal approximation using a spli t-and­ merge control structure) . Short lines are inter­ preted as noisy data and are thrown out. Within a chain an angle is formed by two adjacent lines. For each angle we seek a third line which, if combined with the angle's lines could form a junction. Figure 3 shows the image junctions extracted by this segmentation process. Similarly there are angle and line lists. Figure 4 shows the orientation constraint for the junction indicated by an arrow. The final recognition result is shown on Figure 5 which displays wireframe projections of the object model with partial hidden line elimination. In [8] we have repeated this experi­ ment wi th a 90 mm lens ( where the perspecti ve distorsion is low) and we have obtained similar results.

5. DISCUSSION

We have discussed a method for matehing 3D object models wi th intensi ty images. To increase the efficiency of the method, i.e., to reduce the explosion of the search space, we have deri ved three-space constraints from image features using the mathematics of perspective and knowledge about the object to be located. The method is limited to a class of objects containing vertices formed by intersections of planar faces. These vertices form, by projection angles and junctions. The backprojection of junctions provides a powerful constraint that is valid, unlike the backpro­ jection of polygonal shapes (as is done in [ 5]), even in the absence of strong perspective distor­ sion. However, the method will fail in finding an object if no junction has been detected in the image for this object.

Although this technique looks attractive, it's generalisation is not straightforward. In order to deal with a wide range of realistic Si­ tuations such as missing and imperfect data, com­ plex objects and various ligthing conditions, this method should be combined wi th other techniques (stereo, motion, shading) and with other sources of information (range and tactile data).

In the future we plan to increase the set of features to include such things as ellipses and to deri ve three-space constraints from an extended catalogue of feature clusters such as combinations of ellipses and lines. We also plan to implement a program that will automatically derive percep­ tion-oriented object descriptions from a CAD-like database.

HEFERENCES

1. Kanade, T. "Recovery of the Three-Dimensional Shape of an Objet from a Single View", Arti­ ficial Intelligence, vol. 17, n° 1-3, August 1981, pp. 409-460.
2. Brady, M. and Yuille, A., "An Extremum Prin­ cip1e for Shape from Contour", I.E.E.E. Trans. on Patt. An. and Mach. Int., vol. PAMI-6, n° 3, May 1984, pp. 288-301.
3. [ 3] Chakravarty, J. , "The Use of Characteristic Views as a basis for Recogni tion of Three­ Dimensional Objects", PhD Dissertation, Image Processing Laboratory, Rensselaer Polytechnic Institue, Troy, New-York, October 1982.
4. [ 4] Stockman, G. and Esteva, J. C. , "Use of Geome­ trical Constraints and Clustering to Determi­ ne 3D Object Pose", Technical Report TR84-002 Dept. Computer Science, Michigan State Uni­ versity, East Lausing, Michigan 48824, 1984.
5. [ 5] Barnard, S. "Interpreting Perspective Images" Artificial Intelligence, vol. 21-1983, pp. 435-462.
6. Goad, C. "Special Purpose Automatie Program­ ming for 3D Model Based Vision", Proceedings Image Understanding Workshop, Arlington, Virginia, June 1983, pp. 94-104.
7. Bolles, R.C., Horaud, R., Hannah, M.J. "3DPO: A Three-Dimensional Part Orientation System", Proceedings 8th IJCAI, Kar lsruhe, Germany, August 1983.
8. [ 8] Horaud R. , "From Images to Spatial Percep­ tion", Proceedings Cognitiva, Paris, France, June 1985.

FIGURE 4: Spatial orientation constraints represented on the gaussian sphere. The two solutions correspond to a right vertex interpretation of an image junction.