Transcript Persistent Heat Signature for Pose-oblivious Matching of Incomplete

Persistent Heat Signature for
Pose-oblivious Matching of
Incomplete Models
Tamal K. Dey, Kuiyu Li, Chuanjiang Luo,
Pawas Ranjan, Issam Safa, Yusu Wang
[The Ohio State University]
(SGP 2010)
Problem
• Query and match partial, incomplete and
pose-altered models
Previous Work
• [CTS03]; [OBBG09]; [KFR04]; [BCG08];
[L06]; [RSWN09] …
• No unified approach for pose-invariant
matching of partial, incomplete models
Descriptor based Matching
• Represent shape with descriptor
‒
Compare descriptors
• Local vs Global descriptors
Need a multi-scale descriptor to capture
both local and global features
HKS [Sun-Ovsjanikov-Guibas 09]
 Signifies the amount of heat left at a point x ϵ M
at time t, if unit heat were placed at x when t=0
‒ Isometry invariant
‒ Stable against noise, small topological changes
‒ Local changes at small t for incomplete models
HKS as Shape Descriptor
Need to choose a concise subset of HKS values
• Possible solutions:
‒
Choose the maxima values for some t
•
•
Too many for small t
Sensitive to incompleteness of shape for
large t
Persistent HKS
Persistence
[Edelsbrunner et al 02]
• Tracks topological changes in sub-level sets
• Pairs point that created a component with one
that destroyed it
Persistent Maxima with Region
Merging
• Apply Persistence to HKS
‒ To obtain persistent maxima
• Region-merging algorithm
Persistent Maxima with Region
Merging
Persistent Maxima with Region
Merging
Persistent Maxima
Feature Vector
• Assign a multi-scale feature vector to each
persistent maximum
‒ HKS function values at multiple time scales
• A shape is represented by 15 feature
vectors in 15D space
The Algorithm
• Compute the HKS function on input mesh
for small t
• Find persistent maxima
• Compute HKS values for multiple t at the
persistent maxima
Scalability
• Expensive to compute the eigenvalues
and eigenvectors for large matrices
• Use an HKS-aware sub-sampling method
Scoring & Matching
• Pre-compute feature vectors for database
• Given a query
‒ Compute feature vectors of query
‒ Compare with feature vectors in database
• Score is based on L1-norm of feature vectors
Results
• 300 Database Models (22 Classes)
‒
198 Complete
‒
102 Incomplete
• 50 Query Models
‒
18 Complete
‒
32 Incomplete
Results
Comparison
• Eigen-Value Descriptor [JZ07]
• Light Field Distribution [CTSO03]
• Top-k Hit Rate
‒
Query hit if model of same class present in
top-k results returned
# queries
32 Incomplete
18 Complete
Total
ours
91
83
88
EVD
62
100
76
LFD
59
39
52
Comparison
Conclusion
• Combine techniques from spectral theory
and computational topology
‒ Fast database-style shape retrieval
‒ Unified method for pose-oblivious, incomplete
shape matching
• Handling non-manifold meshes
• Matching feature-less shapes