Topology matching for fully automatic similarity estimation of 3D shapes

TLDR

The growing need for accurate, efficient search of visual and 3D shape datasets motivates this work. The paper proposes Topology Matching, a technique that quickly, accurately, and automatically computes similarity between polyhedral models using Multiresolutional Reeb Graphs. MRGs, built from a geodesic‑distance function invariant to translation and rotation, encode a shape’s skeletal and topological structure at multiple resolutions, and similarity is computed with a coarse‑to‑fine strategy that preserves graph consistency to establish part correspondences. The method is fast and efficient without requiring pose alignment, and it yields intuitive results that make it well suited for interactive 3D object search.

Abstract

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.