Recent technology has made it easy to construct complex 3D models of shapes.
As a result, a large number of digital 3D models are now available, and there
is a need to efficiently search through a large database of such shapes.
The authors wish to use a topological shape representation structure known as
a Reeb graph to represent shapes. They then wish to search a database
of 3D shapes by first comparing a query shape with each database shape using
the Reeb graphs of the shapes.
The authors introduce a technique called topology matching to measure
the similarity of two shapes for the purposes of searching. The basic idea
behind the technique is to compare two shapes by comparing their multiresolution Reeb graphs (MRGs), which is a set of Reeb graphs of a shape
at different levels of detail.
The similarity estimation algorithm of this paper seems to be fairly accurate
even if one of the shapes has been simplified (and the connectivity has hence
changed), if noise has been added, or if one of the shapes has been
transformed under a rigid motion. Searching based on this similarity
estimation seems to yield results that are fairly consistent with human
intuition. On average, the authors' search experiment took only 0.05 seconds
to calculate one similarity, where one query shape was compared against 230
other shapes.