Topology Matching For Fully Automatic Similarity Matching of 3d shapes Masaki Hilaga

Topology Matching For Fully Automatic Similarity Matching of 3D Shapes

• Masaki Hilaga

• Yoshihisa Shinagawa

• Taku Kohmura

• Tosiyasu L. Kunii

Shape Matching Problem

• Similarity between 3D objects

• Metric near-invariants

• Rigid transformations
• Surface simplification
• Noise

• Fast

Technique (1)

• Construct Multiresolution Reeb Graph (MRG)

• normalized geodesic distance

Technique (2)

• MRG matching algorithm for similarity queries

• Finds most similar regions

Reeb Graph

• Same as in Chand’s presentation

• Can use any function 

Geodesic distance function

• Integral of geodesic distances

• (v) = p g(v,p) dS

• Normalize

• n(v) = ((v) – min()) / min()

Geodesic Approximation

• Approximate integral

• Sample

• Simplify distance

• Use Dijkstra’s

Multiresolution Reeb Graph

• Binary discretization

• Preserve parent-child relationships

• Exploit them for matching

Matching process

• Calculate similarity

• Match nodes

• Find pairs with maximal similarity
• Preserve multires hierarchy topology

• Sum up similarity

Matching Process

Matching Process

Matching Process

Matching Process

Matching Process

Results

• Invariants satisfied fairly well

• Between pairs, similarity  0.94
• Across pairs, similarity  0.76

Results

• Database, 7 levels of MRG

• Similarity calculated in tens of milliseconds

• Database searched in average ~10 seconds

Critique

• Subjectively good matching

• Meet invariance criteria

• Approximation of geodesic distance

• Reeb graph discretization

• All models in DB must have same parameters

• Similarity metric