Visual Recognition from Spatial Correspondence and Perceptual Organization

Introduction

The standard model for much recent research in computer vision has been based on the reconstruction of depth in­ formation from the image prior to recognition. However, in this paper we will argue that this is not the primary pathway used for most instances of recognition in human vision. Although depth measurement has an important role in certain visual problems, it is often not available and is not needed for typical instances of recognizing familiar ob­ jects. lnstead, we will propose that the primary bottom-up descriptive analysis of the image can best be performed by a process of perceptual organization. This process Ieads to the formation of significant groupings and structures di­ rectly from the two-dimensional image data. These group­ ings are partially invariant to viewpoint and can be matched directly against three-dimensional object models. The veri­ fication of these matches can be performed by spatially map-

The role of depth reeovery in human vision

A substantial fraction of recent computer vision research has been aimed at the bottom-up derivation of depth or surface orientation from image data, using information such as stereo, motion, shading or texture. This has come to be known as the "Shape from X" paradigm. Marr [12] sug­ gested that these sources of information could be combined in a representation known as the 2!-D sketch that would allow one source of information to compensate for the ab­ sence of another. The depth representation would then be used to determine correspondence with three-dimensional object representations, the assumption being that it would be easier to match a three-dimensional model to a depth representation than to two-dimensional image data.

Human vision contains many of these components for recovering depth, and they presumably have important functions. However, biological visual systems have many objectives, so it does not follow that these components are central to the problern of visual recognition. In fact, the available evidence would seem to indicate the opposite. The first problern with these methods is that depth information is often unavailable or requires an unacceptably long inter­ val of time to obtain. Stereo vision is only useful for objects within a restricted portion of the visual field and range of depths for any given degree of eye vergence, and is never useful for distant objects. Motion information is available only when there is sufficient relative motion between ob­ server and object, which in practice is also usually limited to nearby objects. Recognition times are usually so short that it seems unlikely that the appropriate eye vergence move­ ments or elapsed time measurements could be taken prior to recognition even for those cases in which they may be useful. Depth measurements from shading or texture are apparently restricted to special cases such as regions of ap­ proximately uniform refiectance or regular texture, and they Iack the quantitative accuracy or completeness of stereo or motion.

Secondly, human vision exhibits an excellent Ievel of performance in recognizing images-such as line drawings­ in which there is very little potential for the bottom-up derivation of depth information. Whatever mechanisms are being used for line-drawing recognition have presumably developed from their use in recognizing three-dimensional scenes. The common assumption that line-drawing recogni­ tion is a learned or cultural phenomena is not supported by the evidence. In a seemingly definitive experiment, Hochberg and Brooks [6] describe the case of a 19-month­ old human baby who had had no previous exposure to any kinds of two-dimensional images, yet was immediately able to recognize ordinary line drawings of known objects.

Finally, there has been no clear demonstration of the value of depth information for performing recognition, even when it is available. The recognition of objects from com­ plete depth images, such as those produced by a Iaser scanner, has not been shown tobe much easier than for systems that begin only with the two-dimensional image. This paper will describe methods for directly comparing the projection of three-dimensional representations to the two-dimensional image without the need for any prior depth information.

Of course, none of this is meant to imply that depth recovery is an unimportant problern or Iacks a significant roJe in human vision. Depth information may be crucial for the initial stages of visual learning or for acquiring certain types of knowledge about unfamiliar structures. It is also clearly useful for making precise measurements as an aid to manipulation or obstacle avoidance. However, it seems likely that the role of depth recovery in common instances of recognition has been overstated.

Matehing 3-D knowledge to the image

Although knowledge of object shape, context, and sur­ face properlies must natu.rally be represented in three­ dimensional form, this knowledge can be matched directly against the two-dimensional image through the use of pro­ jection. A major practical difficulty is in using image mea­ surements to determine the unknown projection parameters. Six parameters are needed to specify an arbitrary position and orientation of an object with respect to the camera, and there may be other unknown parameters internal to the ob­ ject. However, each match between a point in the image and a point on the object allows us to solve for two param­ eters. Therefore, only three or four hypothesized matches between the image and an object model are typically needed to solve for the projection parameters. Once these param­ eters have been determined, it is Straightforward to carry out the projection and extend the match by making accu­ rate predictions for the locations of other model features in the image. These further matches may be used to solve for any remaining model parameters, but their most important function is to provide reliable confirmation for the correct­ ness of an interpretation.

The author has previously presented a mathematical technique [7, 9] for solving for viewpoint and model pa­ rameters given some matches between image and model. Briefiy, this method linearizes the projection equations and uses Newton-Raphson iteration to solve simultaneously for the unknown parameters. Since the projection equations are very smooth (consisting of linear combinations of sin and cos functions of viewpoint), the method has quadratic con­ vergence and typically requires only 3 iterations to achieve high accuracy. This basic technique has been extended to perform Ieast-squares solution of over-determined systems, and to allow matehing of image lines to modellines (without concern for the location of line terminations). Given these methods, the problern of verification is largely solved for well-specified objects, and the remaining problems of recog­ nition are those of reducing the size of the search space to produce the few initial matches.

There is experimental evidence that human recognition also relies upon the determination of viewpoint parameters for projecting a three-dimensional object description onto the image. Cooper & Shepard [4] describe experiments in which subjects are asked to compare images at varying ori­ entations to previously memorized shapes. They found that the recognition time varied linearly in the angle of rotation between the image and the orientation of the original mem­ orized shape. In conjunction with their other work on men­ tal rotation, this would seem to indicate that recognition is performed by bringing a prior representation into spatial correspondence with image data by manipulating viewpoint parameters.

Allowing for variations in object models

The capability for recognizing objects from their two-dimen­ sional projections is possible only because of previous knowl­ edge regarding the objects. However, recognition does not imply that we must know every aspect of an object's ap­ pearance prior to recognition. Object models may be pa­ rameterized with variable sizes, angles, or articulations be­ tween components, with expected bounds given for each parameter. As already mentioned, it is possible to back­ solve for these parameters using the same methods as when solving for viewpoint. Just as important is the fact that there is no precise boundary between what is an object and what is a component. It is possible to recognize commonly­ occurring components, such as cylinders, reetangular solids, or repeated patterns, as parameterized objects in their own right. The only requirement isthat there be fewer unknown parameters to the description than there are useful measure­ ments to be made from the image data. These recognized components---even if the identification is only tentative­ can then be used to suggest the !dentity of the more specific structure of which they are a part. If the identification of the components is quite certain, then they can even be com­ bined into previously unknown or very loosely parameter­ ized relationships. Most objects can be represented both in terms of their overall shape and in terms of a combination of components, and different images can best make use of each type of description depending upon such variables as image resolution, viewpoint, and occlusion.

Previous work on model-based vision

There is a considerable body of previous research in model­ based vision. The remarkable early work of Roberts [13] demonstrated the recognition of certain polyhedral objects by precisely solving for viewpoint and object parameters. Unfortunately, this work was poorly incorporated in later vision research, .which tended to emphasize less quantita­ tive methods. The ACRONYM system of Brooks [1] used a general symbolic constraint solver to calculate bounds on viewpoint and model parameters from image measurements. These bounds could then be used to check the consistency of interpretations produced by general matehing operations, and were capable of handling wide classes of generic object descriptions. Goad [5] describes the use of automatic pro­ gramming methods to precompute a highly efficient search path and viewpoint-solving technique for each object to be recognized. This research has been incorporated in an in­ dustrial computer vision system by Silma Inc. which has the capability of performing all aspects of recognition within as little as 1 second. Because of their runtime efficiency, these precomputation techniques are likely to remain the method of choice for industrial systems dealing with small numbers of objects. Other closely related research on model-based vi­ sion has been performed by Shirai [14] and Walter & Tropf [16].

Perceptual organization in SCERPO

Unlike previous model-based systems, SCERPO makes use of perceptual organization as the central process for bottom­ up analysis of an image. Perceptual organization refers to a basic capability of the human visual system to derive rele­ vant groupings and structures from an image without prior knowledge of its contents. For example, people will im­ mediately detect clustering, connectivity, collinearity, par­ allelism, and repetitive textures when shown an otherwise randomly distributed set of image elements. This grouping capability of human vision was studied by the early Gestalt psychologists [17] and is related to research in texture de­ scription [10] . A major function of perceptual organization is to distinguish non-accidental groupings from the back­ ground of groupings that arise through accident of view­ point or random positioning [18, 8] . Those groupings that are non-accidental in origin will also be partially invariant with respect to viewpoint and be most suited to model-based recognition (see [9] for a much more detailed discussion).

In order to provide image features for input to per­ ceptual organization, the first few Ievels of image analysis in SCERPO use established methods of edge detection, as shown in Figures 1-3. The 512-by-512-pixel image shown in Figure 1 was convolved with a Laplacian of Gaussian function (er = 1.8 pixels) as suggested by the Marr-Hildreth [11] theory of edge detection. The zero-crossings of this function are shown in Figure 3. Of course, many of these zero-crossings do not correspond to significant edges in the image. We remove those corresponding to insignificant in­ tensity changes by applying the Sobel gradient operator to the 'il 2 G convolution. Only those points that are above a chosen gradient threshold and lie on a zero crossing are retained in Figure 5. These remaining zero-crossings are linked into lists of points on the basis of connectivity.

The first stage of perceptual organization is to group the linked lists of points into perceptually significant curve segments. The author has previously described a method for finding straight-line and constant-curvature segmenta­ tions at multiple scales and for measuring their significance [9, Chap. 4]. However, here we use a simplified method that selects only the single highest-significance line representa­ tion at each point along the curve. The significance of a straight line fit to a Iist of points is measured as the ratio of its length divided by the maximum deviation of a point from the line. This provides a scale-independent measure of significance that places no prior bounds on the allowable de­ viations. This is then used in a modified version of the recur­ sive endpoint subdivision method. A segment is subdivided at the point with maximum deviation from a line connect­ ing its endpoints. If the maximum significance of any of the subsegments is greater than the significance of the complete segment, then the subsegments are returned. Otherwise the single segment is returned. This procedure is applied recur­ sively until each segment contains fewer than 3 points. The procedure will return a segment covering every point along the curve, but those with a length-to-deviation ratio less than 4 are discarded. This method is implemented in only 40 lines of Lisp code, yet does a reasonable job of detecting the most perceptually significant straight line groupings in the linked point data. The results are shown in Figure 4.

The straight line segments are indexed according to endpoint locations and orientation. Then a sequence of pro­ cedures is executed to detect instances of collinearity, end­ point proximity ( connectivity), and parallelism. A region areund each endpoint or segment is examined to determine candidates for grouping. Each potential grouping is assigned a significance value that is roughly inversely proportional to the likelihood that it is accidental in origin. This is clone in a scale-independent manner (i.e., measurements of endpoint proximity or separation of parallel lines are divided by the length of the shortest of the two line segments). After the execution of this grouping process, the many groupings are ranked in order of significance. Unfortunately, it is difli­ cult to display the results of this grouping process without showing a separate image for each grouping that has been detected. Although several hundred significant groupings were detected in the line segments of Figure 4, we show in Figure 5 only the two sets of highly-ranked groupings that were actually used for successful recognition.

Evidential reasoning

Evidential reasoning refers to the combination of different sources of information or evidence in order to reach a con­ clusion with a specified Ievel of certainty. This form of reasoning has been developed for use in diagnostic expert systems, among other applications. It can be used, for ex­ ample, to calculate the likelihood that a particular disease is present given a number of symptoms. We are faced with a very similar problern in vision when we wish to calculate the likelihood that a particular object is present in an im­ age given a number of detected features and other sources of information. The performance requirements for evidential reasoning in vision are much less stringent than in medical expert systems, since we have a reliable procedure for final verification and only need to use the evidential reasoning to suggest the most eflicient erdering for our search.

In order to minimize the search time, we would like to order our consideration of hypotheses according to decreas­ ing values of Pk/Wk, where Pk is the probability that a particular hypothesis for the presence of object k is correct, and Wk is the amount of work required to verify or refute it . Evidence can come from many sources: we may have initial expectations for the presence of certain objects, con­ textual expectations resulting from the presence of already­ detected objects, and information from many f~rms of image data such as perceptual groupings, texture, color, or met­ ric measurements. The initial researchers in medical expert systems rejected the use of Bayesian methods for combin­ ing evidence [15], since they assumed that it would either require unrea!istic independence assumptions or an impossi­ bly !arge number of known statistical parameters. However, recent work by Charniak [2] has shown that it is possible to formalize the previous apparently ad-hoc methods within a Bayesian framework. The application of Charniak's meth­ ods to erdering search during recognition is discussed in [9, Chap. 6]. An important aspect of evidential reasoning is that it offers a streng basis for building learning systems in which the required statistical parameters are moved towards their correct values as the system gains experience.

The evidential reasoning component of SCERPO has not yet been developed as fully as other parts of the system. Since the system has only been used with a single object under consideration, the performance requirements for min­ imizing search have not been great. The system makes use of a Iist of perceptual groupings and the model features that could give rise to them. This Iist is entered by the user at the same time as model specification. For example, the group­ ings shown in Figure 5 consist of particular combinations of parallelism and endpoint proximity that could be matched to various parts of the object model. The probabilities of non-accidentalness for the image relations that make up a grouping are multiplied together to calculate the probabil­ ity for the grouping as a whole. This is multiplied by an estimate of the likelihood of correctness for the match (as­ suming a non-accidental grouping) that has been entered for each element of the association list, and these final values are used to order the search. We plan to explore methods for incrementally learning the required probability values in future research.

Verißcation of interpretations

The verification component of SCERPO is able to take a tentative match between a couple of image features and model features and return a reliable answer as to whether the match is correct. If the object is present, this module will extend the match as much as possible and determine the precise viewpoint.

Given the initial set of correspondences, the iterative

7.

viewpoint-solving procedure described earlier is used to de­ termine the best viewpoint that would project the model features onto the image features. The current implemen­ tation solves only for viewpoint and does not allow vari­ able model parameters. If !arge errors remain following the Ieast-squares fit, the solution is rejected as inconsistent. All edge features from the model are then projected onto the image using the calculated viewpoint, and the image data structure is searched for segments that are close to the pre­ dictions. Matches are evaluated aecording to the degree of agreement in transverse location, orientation, and length with the prediction, and according to the Iack of ambiguity between competing matches for a single object feature. This evaluation is used to rank the potential matches and only those above a high threshold value, or else the single highest­ ranked match, is selected. The selected matches are com­ bined with the original matches and the Ieast-squares view­ point determination is repeated. An estimate is maintained of the error bounds, based upon the number of matches and the Ieast-squares deviations, so that instances of ambiguity become less likely as the viewpoint estimate improves. The set of matches is repeatedly extended until no more ean be found. The final result of this process is the selection of a set of segments, as shown in Figure 6, that are consistent with a single viewpoint of the model, as shown in Figure 7.

The current verification proeess in SCERPO could clearly be extended to include many other aspeets of verifi­ cation than just the matehing of line segments. For example, the viewpoint cl.etermination for the model instance shown in Figure 8 has a small error in orientation, due to errors in image measurements and the small number of segments being used for the Ieast-squares matching. However, given this degree of reeognition, it would now be straightforward to go back to the original image data or zero-crossings and make further image measurements.

Implementation details

SCERPO is written in several different languages. The im­ age processing components are executed on a VICOM im­ age processor under the Vsh software faeility developed by Robert Hummel and Dayton Clark [3]. The VICOM can perform a 3x3 convolution against the entire image in a sin­ glevideo frame time. However, our edge detection method uses an 18xl8 eonvolution that is performed by 36 of the 3x3 eonvolutions and the appropriate image translations and ad­ ditions. The steps up to figure 5 are performed on the VI­ COM, after which the zero-erossing image is transferred to a VAX 11/750 running UNIX 4.2 for subsequent processing. A program written in C reads the original image and pro­ duees a file of linked edge points (requiring about 30 seconds of CPU time). All other eomponents are written in Franz Lisp. Segmentation into straight line segments requires 40 seconds, indexing and grouping operations require about 1 minute and the later stages of matehing and verifieation took 40 seconds for this example.

The objeet models used by the system eonsists merely of a set of straight 3-D line segments. Each segment has a simple visibility specifieation, listing viewpoint ranges over which it is visible. A full hidden-line algorithm and more eomplete object models would improve the performanee of the system.

8.

Conclueione and future reeearc:h

The current capabilities of SCERPO provide a framewerk that could be used to incorporate numerous additional ca­ pabilities, each of which would improve the generality of the system or its level of performance. A brief !ist of these pos­ sible extensions might include the following: incorporation of a wider range of perceptual grouping operations, the abil­ ity to handle variable model parametere, the recognition of object components and their subsequent combination, more complete modeling with surface information and hidden-line algorithms, the use of color and texture information, the ex­ panded use of evidential reasoning, the incrementallearning of associations and probabilities, the detection of curve seg­ ments as weil as straight lines, and more detailed verification in terms of the original image data.

Perceptual organization and the methods for achiev­ ing spatial correspondence offer an alternative to the use of depth reconstruction and matehing in three-dimensions. It has been argued in this paper that most instances of recognition in human vision also work directly from two­ dimensional data. It should be possible to provide a defini­ t ive answer to this question by designing psychophysical experiments that test human recognition capabilities with different combinations of available information. A final an­ swer to this question would carry many implications for the future design of knowledge-based vision systems.

Adtnowledgmenta

Implementation of the SCERPO system relied upon the exten­ sive facilities and software of the NYU vision laboratory, which are due to the efforts of Robert Hummel, Jack Schwartz, and many others. Robert Hummel, in particular, provided many im­ portant kinds of technical and practical assistance during the implementation process. Mike Overton provided help with the numerical aspects of the design. Much of the theoretical basis for this research was developed while the author was at the Stanford Artificial Intelligence Laboratory, with the help of Tom Binford, Rod Brooks, Chris Goad, David Marimont, Andy Witkin, and many others.

Referencea

1. Brooks, Rodney A., ·symbolic reasoning among 3-D models and 2-D images,· Artificial /ntelligence, l'T (1981), 285-348.
2. Chamiak, Eugene, ·The Bayesian basis of common sense med­ ical diagnosis,· Proceeding· of AAA/-8.9 (Washington, D.C., August, 1983), 70-73.
3. Clark, Dayton and Robert Hummel, ·vsH user's manual: an image processing environment,· Robotic· Re&earch Technical Report, Courant Institute, New York University (September 1984).
4. Cooper, Lynn A., and Roger N. Shepard, ·Tu.ming something over in the mind,· Scientific American, 251, 6 (December 1984), 106-114.
5. Goad, Chris, ·Special purpese automatic programming for 3D model-based vision,· Proceeding1 ARPA Image Under­ &tanding Work&hop (1983).
6. Hochberg, Julian E. and Virginia Brooks, ·Pictorial recogni­ tion as an unleamed ability: A study of one child's perfor­ mance,· American Journal of P&ychology, '15 (1962) , 624628.
7. Lowe, David G., ·solving for the parameters of object models from image descriptions,· Proc. ARPA Image Under&tand­ ing Work&hop (College Park, MD, April 1980), 121-127.
8. Lowe, David G. and Themas 0. Binford, ·Perceptual orga­ nization as a basis for visual recognition,· Proceeding& of AAA/-8.9 (Washington, D.C., August 1983), 255- 260.
9. Lowe, David G., Perceptual Organization and Vi&ual Recogni­ tion (Boston, Mass: Kluwer Academic Publishers, 1985) .
10. Marr, David, ·Early processing ofvisual information,· Philo­ &ophical Tran&action& of the Royal Society of London, Serie& B, 2'T5 (1976), 483-524.
11. Marr, David, and Ellen Hildreth, ·Theory of edge detection,· Proc. Royal Society of London, B, 20'T (1980), 187-217.
12. Marr, David, Vi&ion (San Francisco: W.H. Freeman and Co., 1982).
13. Roberts, L.G., ·Machine perception of three-dimensional ob­ jects,· in Optical and Electro-optical Information Proceuing, Tippet et al., Eds. (Cambridge, Mass.: MIT Press, 1966), 159-197.
14. Shirai, Y., ·Recognition of man-made objects using edge cues,· in Computer Vi&ion Sy&tem·, A. Hanson, E. lliseman, eds. (New York: Academic Press, 1978).
15. Shortliffe, Edward H. and Bruce G. Buchanan, · A model of inexact reasoning in medicine,· Mathematical Bio&cience&, 23 (1975), 355-356.
16. Walter, I. and H. Tropf, ·3-D recognition of randomly ori­ ented parts,· Proceeding· ofthe Third International Conf. on Robot Vi&ion and Semory Control& (November, 1983, Cam­ bridge, Mass.), 193-200.
17. Wertheimer, Max, ·Untersuchungen zur Lehe von der Ges­ talt 11,· P1ychol. For&ch., ~ (1923). Translated as ·Princi­ ples of perceptual organization· in Reading· in Perception, David Beardslee and Michael Wertheimer, Eds., (Prince­ ton, N.J.: 1958), 115-135.
18. Witkin, Andrew P. and Jay M Tenenbaum, ·on the role of structure in vision,· in Human and Machine Vi&ion, Beck, Hope & Rosenfeld, Eds. (New York: Academic Press, 1983), 481-543.