Topology matching for fully automatic similarity estimation of 3D shapes

Masaki Hilaga, Yoshihisa Shinagawa, Taku Komura, Tosiyasu L. Kunii

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

There is a growing need to be able to accurately and efficiently search visual data sets, and in particular, 3D shape data sets. This paper proposes a novel technique, called Topology Matching, in which similarity between polyhedral models is quickly, accurately, and automatically calculated by comparing Multiresolutional Reeb Graphs (MRGs). The MRG thus operates well as a search key for 3D shape data sets. In particular, the MRG represents the skeletal and topological structure of a 3D shape at various levels of resolution. The MRG is constructed using a continuous function on the 3D shape, which may preferably be a function of geodesic distance because this function is invariant to translation and rotation and is also robust against changes in connectivities caused by a mesh simplification or subdivision. The similarity calculation between 3D shapes is processed using a coarse-to-fine strategy while preserving the consistency of the graph structures, which results in establishing a correspondence between the parts of objects. The similarity calculation is fast and efficient because it is not necessary to determine the particular pose of a 3D shape, such as a rotation, in advance. Topology Matching is particularly useful for interactively searching for a 3D object because the results of the search fit human intuition well.
Original languageEnglish
Title of host publicationProceedings of the 28th annual conference on Computer graphics and interactive techniques
Subtitle of host publicationSIGGRAPH 2001
Place of PublicationNew York, NY, USA
PublisherACM Association for Computing Machinery
Pages 203-212
Number of pages10
ISBN (Print)1-58113-374-X
Publication statusPublished - 1 Aug 2001
Event28th annual conference on Computer graphics and interactive techniques: SIGGRAPH 2001 - Los Angeles, United States
Duration: 12 Aug 200117 Aug 2001


Conference28th annual conference on Computer graphics and interactive techniques
Country/TerritoryUnited States
CityLos Angeles
Internet address

Keywords / Materials (for Non-textual outputs)

  • 3D search, computer vision, shape recognition


Dive into the research topics of 'Topology matching for fully automatic similarity estimation of 3D shapes'. Together they form a unique fingerprint.

Cite this