Object Recognition Research
Randal C. NelsonDepartment 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
Full
Publication List
Back to
research page
Back to
Randal Nelson's home page