Object Recognition Research

Randal C. Nelson
Department of Computer Science
University of Rochester

Appearance-based object recognition methods have recently demonstrated good performance on a variety of problems. However, many of these methods either require good whole-object segmentation, which severely limits their performance in the presence of clutter, occlusion, or background changes; or utilize simple conjunctions of low-level features, which causes crosstalk problems as the number of objects is increased. We are investigating an appearance-based object recognition system using a keyed, multi-level context representation, that ameliorates many of these problems, and can be used with complex, curved shapes. Pictures on this page are from a training database we have used in system tests.

Specifically, we utilize distinctive intermediate-level features in this case automatically extracted 2-D boundary fragments, as keys, which are then verified within a local context, and assembled within a loose global context to evoke an overall percept. The system demonstrates extraordinarily good recognition of a variety of 3-D shapes, ranging from sports cars and fighter planes to snakes and lizards with full orthographic invariance. We have performed a number of large-scale experiments, involving over 2000 separate test images, that evaluate performance with increasing number of items in the database, in the presence of clutter, background change, and occlusion, and also the results of some generic classification experiments where the system is tested on objects never previously seen or modeled. To our knowledge, the results we report are the best in the literature for full-sphere tests of general shapes with occlusion and clutter resistance.

The basic idea is to represent the visual appearance of an object as a loosely structured combination of a number of local context regions keyed by distinctive key features, or fragments. A local context region can be thought of as an image patch surrounding the key feature and containing a representation of other features that intersect the patch. Now under different conditions (e.g. lighting, background, changes in orientation etc.) the feature extraction process will find some of these distinctive keys, but in general not all of them. Also, even with local contextual verification, such keys may well be consistent with a number of global hypotheses. However, the fraction that can be found by existing feature extraction processes is frequently sufficient to identify objects in the scene, once the global evidence is assembled. This addresses one of the principle problems of object recognition, which is that, in any but rather artificial conditions, it has so far proved impossible to reliably segment whole objects on a bottom-up basis. In the current system, local features based on automatically extracted boundary fragments are used to represent multiple 2-D views (aspects) of rigid 3-D objects, but the basic idea could be applied to other features and other representations.

The basic recognition strategy is to utilize a database (here viewed as an associative memory) of key features embedded in local contexts, which is organized so that access via an unknown key feature evokes associated hypotheses for the identity and configuration of all known objects that could have produced such an embedded feature. These hypotheses are fed into a second stage associative memory, keyed by configurations, which lumps the hypotheses into clusters that are mutually consistent within a loose global context. This secondary database maintains a probabilistic estimate of the likelihood of each cluster based on statistics about the occurrence of the keys in the primary database. The idea is similar to a multi-dimensional Hough transform without the space problems. In our case, since 3-D objects are represented by a set of views, the configurations represent two dimensional transforms of specific views. Efficient access to the associative memories is achieved using a hashing scheme on parameters of the keying features, followed by verification of the local context. As mentioned above, this local verification step gives the voting features sufficient power to substantially ameliorate well known problems with false positives in Hough-like voting schemes. Details on associative memory

A fundamental component of the approach is the use of distinctive local features we call keys. A key is any robustly extractable part or feature that has sufficient information content to specify a configuration of an associated object plus enough additional, pose-insensitive (sometimes called semi-invariant) parameters to provide efficient indexing. The local context amplifies the power of the feature by providing a means of verification. This local verification step is critical, because the invariant parameters of the key features are relatively weak evidence, leading to a proliferation of high-scoring false hypotheses if used alone. This is a well known problem with voting schemes, but can be alleviated if the voting features are sufficiently powerful. In the current implementation we have utilized keys based on extracted boundary fragments, both straight and curved, but the method is by no means limited to such keys, and we are looking at several complementary feature types. Details on keys used.

In order to use the system with an object, its appearances must be stored in the associative memory. Currently, this is done by obtaining a number of uncluttered images of the object from different directions. About 100 views are needed to cover the entire viewing sphere for the curve-based keys we have used. For each view, key features are extracted, and a number of the strongest are stored in the memory with associated information about the object and view that produced them, and their relationship to an arbitrarily specified 2-D configuration (position, orientation, scale) for that view.

To recognize an object, that is to answer the question "what object is in this image?", key features together with their local contexts are extracted from the image, and fed into the associative memory. All matches are retrieved, and for each match, the associated information is used to compute a hypothesis about the identity, view, and configuration of a possible object. This hypothesis is fed to a second, "working" associative memory, where current hypotheses are stored. If any matches are found, the evidence associated with them is updated to reflect the new information. Otherwise a new hypothesis is entered. The accumulation is not a flat voting process, but depends on the frequency of occurrence of the feature over the entire database, with uncommen features providing more evidence. The evidence combination scheme is Bayesian if the features are independent (they are not, but we don't have a better model, and the results are better than flat voting). The hypothesis memory is them examined, and the configuration with the most evidence selected as the most probable answer.

To find an object of known characteristics in a scene, that is to answer the question of the form "where is the dog in this image?", the same procedure is followed, except that key feature matches are filtered on the basis of whether the came from a view of a dog. This actually provides a rather powerful mechanisms for partially indexed retrieval, since the filtering can occur on any combination of attributes that we care to associate with the features, either in the database, or from the image, e.g. "animal", or "pink cup". Details of algorithm.

The approach has several advantages. First, because it is based on a merged percept of local features rather than global properties, the method is robust to occlusion and background clutter, and does not require prior segmentation. This is an advantage over systems based on principal components template analysis, which are sensitive to occlusion and clutter. Second, entry of objects into the memory is an active, automatic procedure. Essentially, the system explores the object visually from different viewpoints, accumulating 2-D views, until it has seen enough not to mix it up with any other object it knows about. Third, the method lends itself naturally to multi-modal recognition. Because there is no single, global structure for the model, evidence from different kinds of keys can be combined as easily as evidence from multiple keys of the same type. The only requirement is that the configuration descriptions evoked by the different keys have enough common structure to allow evidence combination procedures to be used. This is an advantage over conventional alignment techniques, which typically require a prior 3-D model of the object. Finally, the probabilistic nature of the evidence combination scheme, coupled with the formal definitions for semi-invariance and robustness allow quantitative predictions of the reliability of the system to be made.

We have run several large-scale performance tests, involving, altogether, over 2000 separate test images. In these experiments we investigate variation in performance with respect to increasing database size, clutter, and occlusion. In forced choice experiments using clean test images from a 24 object database, we obtain 97% classification accuracy. Performance with 75% clutter and 25% occlusion is in the 90%+ range. We have developed a statistical model for predicting the performance in a variety of situations from a few basic measurements of score distributions for clean test images and pure clutter. We also ran a generic recognition experiment, where the system was trained on several objects in each of several several classes, (e.g. planes, snakes, cars), and asked to classify example objects from the same generic classes, but not in the training set. Details of experiments.


Andrea Selinger and Randal C. Nelson, ``A Perceptual Grouping Hierarchy for Appearance-Based 3D Object Recognition'', Computer Vision and Image Understanding, vol. 76, no. 1, October 1999, pp.83-92. Abstract, gzipped postscript (preprint)

Randal C. Nelson and Andrea Selinger ``Large-Scale Tests of a Keyed, Appearance-Based 3-D Object Recognition System'', Vision Research, Special issue on computational vision, Vol. 38, No. 15-16, Aug. 1998. Abstract, gzipped postscript (preprint)

Randal C. Nelson and Andrea Selinger ``A Cubist Approach to Object Recognition'', International Conference on Computer Vision (ICCV98), Bombay, India, January 1998, 614-621. Abstract, gzipped postscript, also in an extended version with more complete description of the algorithms, and additional experiments.

Randal C. Nelson, Visual Learning and the Development of Intelligence, In Early Visual Learning, Shree K. Nayar and Tomaso Poggio, Editors, Oxford University Press, 1996, 215-236. Abstract,

Randal C. Nelson, ``From Visual Homing to Object Recognition'' , in Visual Navigation, Yiannis Aloimonos, Editor, Lawrence Earlbaum Inc, 1996, 218-250. Abstract,

Randal C. Nelson, ``Memory-Based Recognition for 3-D Objects'', Proc. ARPA Image Understanding Workshop, Palm Springs CA, February 1996, 1305-1310. Abstract, gzipped postscript

Randal C. Nelson, ``3-D Recognition Via 2-stage Associative Memory'', University of Rochester, Dept of Computer Science TR 565, January 1995. Abstract, gzipped postscript

Recap of Links in Text

Full Publication List

Back to research page

Back to Randal Nelson's home page