University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program


A topological framework for shape classification and matching


Dr. Michela Spagnuolo, IMATI-CNR, Genova, Italy
Genua, Italy

date & place

Wednesday, 30.05.2007, 16:15 h
Room C252


Assessing the similarity among 3D shapes is a very complex and challenging research topic. In this field, the methods developed so far span from coarse filters suited to browse very large 3D repositories on the web, to domain-specific approaches to assessing similarity of part models containing semantic as well as structural nformation.

The majority of the methods proposed in the literature mainly focus on the geometry of shapes, while there is a growing consensus that shapes are recognized and coded mentally in terms of relevant parts and their spatial configuration, or structure. Methods approaching the problem from a geometric point of view do not take into account the structure of the shape and generally the similarity distance between two objects depends on their spatial embedding. However all of them could be necessary and useful in a multi-step approach which considers a series of filters to progressively refine the set of geometrically similar candidates and/or a multimodal query mechanism that could provide a combination of various measures of shape similarities, corresponding to function, form and structure analysis of 3D shapes.

In this context, the talk will discuss a 3D shape comparison framework based on results of differential topology which deal with the description of shapes by means of the properties of one, or more, real-valued functions defined over the shape. Studying these properties, topological descriptions of the shape can be defined, namely the Reeb graphs, which can be embedded in the 3D space and augmented with different geometric and morphological attributes that globally and locally describe the shape. Based on these abstract descriptions, global as well as sub-part correspondence between two shapes is obtained by matching their corresponding Reeb graphs, using a specialization of error tolerant graph isomorphism. In the proposed graph matching framework makes it possible to plug in heuristics for tuning the algorithm to the specific application and for achieving different approximations to the optimal solution.