Technological improvements related to object acquisition, visualization and 
modeling, have caused a considerable growth of the number of 3D models in
digital form, which are now available in large databases of shapes, ranging from
unstructured repositories, like the web, to specialized catalogues used in
engineering and simulation. Whilst there are already techniques for rapidly 
extracting knowledge from massive volumes of texts (e.g., Google), it is harder 
to structure, filter, organize, retrieve and maintain archives of 3D digital
shapes. Efficient 3D search engines are therefore  necessary to avoid
re-inventing (or re-designing) the wheel every time, and to  support the re-use
of design models.

The majority of the methods developed so far for shape matching span from coarse
filters suited to browse large 3D repositories on the web, to domain-specific 
approaches to assess the similarity of models; they are related to four main 
scenarios:
1) recognition of objects whose overall shape is similar (global matching);
2) recognition of similar sub-parts in objects that are both structurally 
      and globally similar (sub-part correspondence);
3) recognition of similar sub-parts in objects having different overall 
      shape (partial matching);
4) recognition of a whole object as a sub-part of another (part-in-whole).

Note that the fourth case is a  particular case of the third one. The majority
of  the methods developed so far for shape matching fit into the first category.
Most of these methods are based on geometric shape descriptors (e.g., distances,
angles,  curvatures, area, or volumes) which characterize the shape distribution
of the object in the 3D space or visual shape characteristics. These methods are
suited to solve the global matching problem, and the matching is measured by
some  function that provides a global value of similarity. 

An important point is that the similarity between two shapes is assessed not
only in terms of identical global match but it is based on the contribution of
common  features compared to those distinguishing them. Therefore, a retrieval
system closer to the human perception of  similarity should be able to assess
similarity but also to identify the common parts. For example in the design
applications, partial matching is definitely desirable: if an existing object
differs only in a few details from a new model to be produced, then it is not
difficult to adapt the existing object to the new one.

In this sense, methods for global matching do not have the capability to
explicitly represent the relevant sub-parts of the object and how this sub-part
are spatially related among them. Methods for sub-part  correspondence and for
partial matching are more elaborate in the sense that they  provide not only a
global measure of similarity, but also the indication of where  the similarities
occur in the shapes.

We believe that by differentiating the geometric and structural level of
description of shapes, an automatic retrieval system will be able to provide 
results for sub-part correspondeence and partial matching. The use of structural
descriptors is an intermediate step between the geometry and the semantics of
the object, since it characterizes features of the object that are relevant with
respect to the application context. For example information about the shape
structure may make the difference when the sub-part analysis supports decisions
on how to reuse parts of a model for the design of a new one.

Since there is neither a single best shape characterization nor a single
best. similarity  measure, we propose a framework for working on shape
comparison where different characterization methods can be plugged-in and
tested, while keeping the same computational setting. When the structural
description can be encoded as a directed attributed graph, the sub-part
correspondence between two shapes is obtained by using graph matching
techniques. The proposed framework formalizes the enumeration of all common
subgraphs of two graphs in a way that makes it easy to plug in heuristics,
according to the specific case, thus achieving different approximations of the
optimal solution.