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 three-dimensional (3
-D) polyhedral objects from 2-D images by indexing. Both the objects t
o be recognized and the images are represented by weighted graphs. The
indexing problem is therefore the problem of determining whether a gr
aph extracted from the image is present or absent in a database of mod
el graphs. We introduce a novel method for performing this graph index
ing process which is based both on polynomial characterization of bina
ry and weighted graphs and on hashing. We describe in detail this poly
nomial characterization and then we show how it can be used in the con
text of polyhedral object recognition. Next we describe a practical re
cognition-by-indexing system that includes the organization of the dat
abase, the representation of polyhedral objects in terms of 2-D charac
teristic 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.