  In computer vision, the indexing problem is the problem of recognizing a few
objects in a large database of objects while avoiding the help of the classical
image-feature-to-object-feature matching paradigm. In this paper we address the
problem of recognizing 3-D polyhedral objects from 2-D images by indexing. Both
the objects to be recognized and the images are represented by weighted graphs.
The indexing problem is therefore the problem of determining whether a graph
extracted from the image is present or absent in a database of model graphs. We
introduce a novel method for performing this graph indexing process which is
based both on polynomial characterization of binary and weighted graphs and on
hashing. We describe in detail this polynomial characterization and then we
show how it can be used in the context of polyhedral object recognition. Next
we describe a practical recognition-by-indexing system that includes the
organization of the database, the representation of polyhedral objects in terms
of 2-D characteristic views, the representation of this views in terms of
weighted graphs, and the associated image processing. Finally, some
experimental results allow the evaluation of the system performance.
