Recognition in 2D Images of 3D Objects from Large Model Bases Using Prediction Hierarchies

1. Introduction

Object recognition is a central aspect of the process of un­ derstanding visual information, helping us to relate what we are seeing to what we have experienced in the past . In spite of much progress in this area, there are crucial ·problems that have not received adequate attention. One problem is that of represent­ ing information about 3D objects in a way that makes match­ ing them to 2D image data efficient and reliable. That is, the geometric analysis required to relate an arrangement of 2D im­ age features to the structure and pose of 3D objects should be sufficient for recognition and yet not involve massive amounts of computation during the time-critical recognition task. An­ other problem is ensuring that the storage and time complexity grows only slowly with respect to the size of the model base and the complexity of the models. We emphasize efficiency for model-based vision because of the remarkable ability of humans to rapidly recognize a large number objects from a range of view­ points [Biederman85]. Also, while there are other sources of information that seem to be important, specifically scene con­ text [Biederman85, Weymouth86J and model-independent un­ derstanding of 3D structure [Marr82], these useful cues may quite often be unavailable, unreliable, or merely a first step towards a full interpretation.

Techniques for relating 3D model information to 2D image data can be partitioned into two basic apl>roaches: prediction

This research was supported In part by the by the Air Force Office of Scientific Research under contract number AFOSR-86-0021. Thanko to AI Hanson, Ed Rioeman Michael Boldt and John Dolan for comments, support and help with the figures.

RECOGNITION IN 2D IMAGES OF 3D OBJECTS FROM LARGE MODEL BASES USING PREDICTION ffiERARCHIES

J. Brian Burns Leslie J. Kitchen

Computer and Information Science Department University of Massachusetts Amherst, Massachusetts, 01003

cycling and pre-recognition view analysis. In the former, rep­ resented by [Brooks81J, the system iteratively cycles through a process of prediction·, deciding which projected model structure to search for in the image and what it looks like; observation, searching for image data that match the prediction; and back con1training, using additional properties of the matched data to further constrain the possible 3D poses and structural vari­ ations in the object. This approach could be computationally inefficient for large model bases since the prediction step would involve computing what is common about the projections of a large and possibly complex class of objects from a range of view­ points. Similarly, manipulation of partially constrained poses during the back"constraining step can be involved [Lowe85].

In the alternative approach, pre-recognition view analysis, all expectations of what to look for in the image are generated be­ fore the actual recognition task. Recognition 'then becomes a 2D matching problem followed by object pose analysis and verifica­ tion. The characteristic-view based schemes of Chakravarty [82], the property spheres of Fekete [84], the SCERPO system of Lowe [85], the principal views of Cooper [87] and the image-based de­ scriptions of the VISIONS system developed in [Weymouth86] all roughly follow this method. Additionally, this approach has similarities with the photometric stereo interpretation system of Ikeuchi [87].

Another basic idea incorporated into our design is the use of IS-A and PART-OF hierarchical representations ([Marr82), [Brooks81], [Mulder85] and [Weymouth86]). We developed a sin­ gle, combined IS-A and PART-OF hierarchy called a prediction hierarchy. The nodes in this hierarchy are partial descriptions that are common to views and hence constitute shared process­ ing subgoals during matching. Many of the problems encoun­ tered with large model bases and complex models are reduced by subgoal sharing: projections with similarities explicitly share the representation and recognition of their common aspects.

The original contribution of this paper is the automatic com­ pilation, from a 3D model base, of a prediction hierarchy that can be used to recognize objects. A prototype system based on these ideas is demonstrated using a set of polyhedral objects and projections from an unconstrained range of viewpoints. A fuller treatment can be found in [Burns87] .

2. Overview

The problem currently being studied is the compilation and use of a prediction hierarchy to recognize polyhedral objects us­ ing straight-line segments detected in the image. The actual objects used to demonstrate the design are shown in Figure 1. The objects have differences and similarities in various dimen­ sions and part of the problem is to take advantage of both. The similarities in their visual structure, such as occurrences of paral­ lelograms or of certain types of line junctions, must be utilized by the recognizer to make the search for a match efficient. The dif­ ferences in visual structure, such as height-to-width proportions, must be utilized to discriminate between the objects. Additionally, the variations in visual appearance caused by variations in the camera must be taken into account while doing the structural analysis .

The camera geometry used is as follows . The viewpoint of the camera is taken to be the position of the image origin in the object coordinate system. Currently, the projection is taken to be normal perspective [Brooks81], i.e. orthographic projection with scaling. Also, since the objects are expected in any pose, all predictions generated are invariant to re-scaling, translation and rotation in the image plane. This means that there are only two degrees of camera variation that have a significant effect on the projections being described by the predictions: the two angular components of the viewpoint that sweep out a viewing sphere about the object.

A top-level view of the algorithm is as follows:

• Compile the prediction hierarchy from the set of 3D models given, before the recognition task begins. The hierarchy is compiled by starting with a small set of simple and very general structural predictions and then iteratively search­ ing for commonly occurring combinations or specializations of these predictions across all objects and views, eventu­ ally isolating predictions that characterize the projections of fairly specific objects from a range of views .
• Match predictions to input image. During the recognition phase, look for matches between segment descriptions and actual sets of image segments by a combined search of the prediction hierarchy and image data base. The hierarchy is used as an organized network of recognition subgoals .
• Refine the pose estimate. For each promising match, calcu­ late the pose more precisely given the image-model map­ ping and an initial estimate of the pose implied by the prediction matched (i.e., some typical viewpoint from the set of those that could satisfy the prediction matched) . For pose estimation refinemel)t, the iterative method described in [Lowe85] is used.

The integration of these three processes could be more so­ phisticated. However, the pressing issue at this point concerns the basic design of these steps; investigating further how they might fit together is outside the scope of this paper.

Following a description of the nature of the predictions and their representation (Section 3), the processes that compile them and use them for matching are discussed {Sections 4 and 5) .

~. Predictions and Their Representation

A prediction is a statement concerning some structural aspect of the image of an object. For example, this may be as simple and general as an assertion that there exists a pair of parallel segments in the projection; or as complex as a description of an image unique to some object. A prediction is represented here as a relational graph; the elements in the graph are projected straight-line segments. The relations associated with arcs in the graph mutually constrain the orientations, positions and sizes of pairs of segments.

A relation between a pair of projected segments used in the predictions is represented by ranges of four relational measures, u, v, a and s . Call one segment s1 and the other s2. The vector

( u, 11) is the position of segment 82 relative to 81 : it is the dis­ placement of an endpoint of s2 from an endpoint of s1 measured along -'I and normal to 81, divided by the length of 81 . The angle between them, a , is measured counterclockwise from s1 to s2; and 8 is the relative scale or length ratio of 82 over s1. A relation is defined as an extent box, i.e. a set of ranges in u, u, a and s, in order to capture the variation over ranges in viewpoint . For instance, projecting a pair of parallel object segments over all possible viewpoints will generate a set of measurements that have a single value (zero) in the a dimension but some extent in the others. Similarly, the family of projections of a pair of object segments that share an endpoint can be represented by a relation that has the value zero in both position components (u, v) . A relation between projected segments is considered useful if it is valid over a wide range in viewpoints and its extent box is small in volume (for example, consider the two view-invariant relations just mentioned). The latter property is important if the relation is to help characterize an object's projection with a specificity sufficient to discriminate the object from a large number of other objects and from chance arrangements of image segments. Al­ though invariant relations are clearly useful [Lowe85] , they alone are in general not enough to fully characterize projections. For instance, proportions are often strong characterizations of ob­ ject structure, but the length measurement ratios that represent them are often not strictly view invariant . For example, the tall box in Figure 1 has a height io width ratio that is significantly different from the cube over a large range in views; no other property can be used to differentiate them.

It should be clear from the above discussion that a prediction may be valid only over a restricted set of views for a given object . A prediction instance is a set of model segments, a mapping from the model segments to the segments of the prediction's relational graph and the range of viewpoints from which the prediction is valid for these segment bindings . For a given model base, each prediction has a set of such instances and a cumulative visibility, the total area of all their visibility regions on the viewing sphere, across all objects.

Any given prediction in the prediction hierarchy is impliCitly some relational graph, but explicitly it is almost always described as some combination or specialization of other predictions (see Figure 2). In such cases, it is a derivative of the other predictions. A prediction is a specialization of another if it can be described by adding new relations or narrowing the extent boxes of exist­ ing ones. For example, the square can be described by adding a relation between the bottom and side segments of the more general parallelogram prediction that constrains th~ir ratio of length to one. A prediction is a combination of other predictions if it can be described as a conjunction of these other predic­ tions. Predictions may be combined in various ways, depending on the segment mappings between the whole prediction and its parts. See, for example, the triangular prism prediction of Fig­ ure 2. The mappings are collectively called the arrangement of the combination.

4. Prediction Hierarchy Compiler

The compiler attempts to build a ·prediction hierarchy that is composed of predictions that are commonly occurring combina­ tions or specializations ·of other predictions. An added prediction should occur commonly enough that its satisfaction tends to di­ chotomize the instances of the prediction it is derivative of; and thus allow the recognizer to efficiently search for matches to ob­ jects and views. A useful way to build such a structure is by starting with a small set of simple and very general structural predictions and then iteratively searching for the commonly oc­ curring combinations or specializations, eventually isolating pre­ dictions that characterize the projections of specific objects. By using this iterative construction approach we limit the combina- · torial complexity, and hence processing time, to a manageable level. This is because the system is never performing subgraph isomorphism analysis over large graphs: it is always comparing combinations of small numbers of parts.

For the experiments reported here , parallelism and endpoint coincidence are used as the initial set of simple and general pre­ dictions ; and the iterative process is stopped when all of t he predictions without derivatives (the ones at the top of the hi­ erarchy) are either associated with single objects or, if they are satisfied by projections of more than one object , there are no de­ scribable differences between their projections. The prediction hierarchy compiler implemented iteratively combines predictions and then follows this up with specialization of the prediction to discriminate between objects that cannot be distinguished by parallel and end-point coincidence relations alone.

For each iteration of the combination process, the system iso­ lates frequent combinations by (1) finding predictions that often appear together in the same projections and then (2) character­ izing and representing the arrangement of the combination. The co-occurrences are found in the following fashion . All instances of all predictions are stored in data st ructures called visibility maps. Ther~ is a visibility map for each object; th~ maps are ar­ r~ys of cells m?exed by the two viewpoint parameters , making a discrete samphng of the view sphere about the object . Each cell lists prediction instances visible from the associated viewpoint and object; and with each prediction is a list of cells that contain it . To find frequent co-occurrences between some prediction p and ~ther predictions, the system looks for predictions that ap­ pear m the same cells as P and accumulates the total number of cells for each that do. To keep the number of combinations anal­ ys~d ?own to a manageable size, we consider only co-occurring patr6 m whose arrangements the part-to-whole mappings overlap for at least one whole segment .

The combinations selected during a given iteration are those that are frequently occurring. Additionally, a heuristic is used to throw out predictions whose satisfaction during recognition creates dead ends in the matching process. The details of this heuristic can be found in [Burns87] . Very briefly, it dictates that the compiler adds· a given prediction P only if, when P is satisfied by the projection of some object, that satisfaction almost always leads to a match of a derivative of P that is unique to that object .

The prediction hierarchy compiler design was tested on the models in Figure I. The resulting hierarchy is shown in Figure 3.

There are six levels of the hierarchy; the average path length be­ tween the initial nodes and goal nodes (object matches) is 3.9. The total number of nodes (predictions represented) is fifteen . Considering that the hierarchy is capable of being used to dis­ tinguish five objects from almost all viewpoints (with an average of 8 segments per view) - and t he predictions are represented efficiently as combinations of simpler ones, this appears to be a reasonable result .

The iterative combination left the tall box and cube objects indistinguishable. This was corrected by the specialization pro­ cess by adding segment length-ratio relations between two pairs of segments. This conjunction of two proportional relations was satisfied by the tall box projections over most of the view sphere, and satisfied by none of t he projections of the cube.

5. Reco~nition

The object recognizer finds correspondences between seg­ ments detected in a given image and the segments of some model in the model base by an organized search of the prediction hierar­ chy and image data base. Like parsing and other interpretation problems, there are many ways to perform such a search (e.g., top-down, bot tom-up or some combination of both). A fairly straight-forward method of search was implemented for the pur-. pose of demonstrating the usefulness of the prediction hierarchy. The search proceeds in a bottom-up fashion by iteratively select­ ing a previously satisfied prediction (an image-prediction match), attempting to find additional evidence in the image to satisfy its derivative predictions (i .e., testing new constraints on already matched image segments for specializations and searching for parts for combinations), and storing any new image-prediction matches for further expansion. Figure 4 shows the ·results of this matching process using the hierarchy in Figure 3 and a synthet­ ically generated set of image segments.

6. Conclusion

An object recognit ion system is presented that is designed to handle the computational complexity posed by a large model base, an unconstrained viewpoint and t he structural detail in­ herent in a single view by extensive view analysis and the organi­ zation of predicted data into a PART-OF / IS-A structure called a prediction hierarchy. The original contribution of this paper is the automatic compilation, from a 3D model base, of a prediction hierarchy that can be used to recognize polyhedral objects. This research has been done in conjunction with studies of the visual properties of continuous surfaces [Callahan85] for the purpose of recognizing objects . with curved parts and convexities. Further experiments will involve larger model bases, more complex mod­ els, and image noise. Current design refinements are centered on the cost/benefit analysis of adding a prediction to the hier­ archy and the matching control" strategies ([Weymouth86] and [Draper87]), including the use of image context for match selec­ tion.