Transcript Slides - Department of Computer Science

Harmonic
3D Shape Matching
Michael Kazhdan
Thomas Funkhouser
Princeton University
Motivation
Large databases of 3D models
Computer Graphics
(Princeton 3D Search Engine)
Mechanical CAD
(National Design Repository)
Molecular Biology
(Audrey Sanderson)
Goal
Find 3D models with similar shapes
3D Model
Shape
Descriptor
Nearest
Neighbor
Model Database
Research Challenge
Need shape descriptor that is:
• Discriminating
• Concise to store
• Quick to compute
• Efficient to match
3D Model
Nearest
Neighbor
Shape
Descriptor
Model Database
Research Challenge
Finding a 3D shape descriptor that is:
• Discriminating
• Concise to store
• Quick to compute
• Efficient to match
3D Model
Nearest
Neighbor
Shape
Descriptor
Model Database
Research Challenge
Finding a 3D shape descriptor that is:
• Discriminating
• Concise to store
• Quick to compute
• Efficient to match
3D Model
Nearest
Neighbor
Shape
Descriptor
Model Database
Research Challenge
Finding a 3D shape descriptor that is:
• Discriminating
• Concise to store
• Quick to compute
• Efficient to match
3D Model
Nearest
Neighbor
Shape
Descriptor
Model Database
Research Challenge
Finding a 3D shape descriptor that is:
• Discriminating
• Concise to store
• Quick to compute
Many possible alignments
• Efficient to match
3D Model
Nearest
Neighbor
Shape
Descriptor
Model Database
3D Model Matching Approaches
Search over all possible alignments
• Too slow for large database
-
-

min
-

3D Model Matching Approaches
Search over all possible alignments
• Too slow for large database
Normalize alignment (e.g., with moments)
• OK for translation and scale, not for rotation
PCA Aligned Models
3D Model Matching Approaches
Search over all possible alignments
• Too slow for large database
Normalize alignment (e.g., with moments)
• OK for translation and scale, not for rotation
Build alignment invariance into descriptor
• Previous methods not very discriminating
Shape Histograms
[Ankerst et al., 1999]
Outline
Introduction
Approach
Implementation
Experimental Results
Conclusion and Future Work
Our Approach
Harmonic 3D shape descriptor
• Decompose 3D shapes into irreducible set of
rotation independent components
• Store “how much” of the model resides
in each component
3D Model
Rotation Independent
Components
Shape
Descriptor
Our Approach
Harmonic 3D shape descriptor
• Decompose 3D shapes into irreducible set of
rotation independent components
• Store “how much” of the model resides
in each component
Concentric Spheres
3D Model
Rotation Independent
Components
Shape
Descriptor
Our Approach
Harmonic 3D shape descriptor
• Decompose 3D shapes into irreducible set of
rotation independent components
• Store “how much” of the model resides
in each component
Frequency Decomposition
3D Model
Rotation Independent
Components
Shape
Descriptor
Our Approach
Harmonic 3D shape descriptor
• Decompose 3D shapes into irreducible set of
rotation independent components
• Store “how much” of the model resides
in each component
Amplitudes
3D Model
Rotation Independent
Components
Shape
Descriptor
Outline
Introduction
Approach
Implementation
Experimental Results
Conclusion and Future Work
Voxelization
Convert polygonal model to 3D voxel grid
• Rasterize surfaces (no solid reconstruction)
• Normalize for translation and scale
3D Model
3D Voxel Grid
Spherical Decomposition
Intersect with concentric spheres
Frequency Decomposition
Represent each spherical function as a sum
of different frequencies
Spherical
Functions
Frequency
Components
Fourier Analysis
Circular
Function
Fourier Analysis
=
+
+
+
Circular
Function
Cosine/Sine Decomposition
+
…
Fourier Analysis
=
+
+
+
Circular
Function
=
Constant
Frequency Decomposition
+
…
Fourier Analysis
=
+
=
+
+
+
+
Circular
Function
Constant
1st Order
Frequency Decomposition
+
…
Fourier Analysis
=
+
+
=
+
+
+
+
Circular
Function
Constant
1st Order
2nd Order
Frequency Decomposition
+
…
Fourier Analysis
=
+
+
+
=
+
+
+
+
+
…
+
…
Circular
Function
Constant
1st Order
2nd Order
3rd Order
Frequency Decomposition
Fourier Analysis
=
Amplitudes
invariant
+
+
+
to rotation
+
+
…
+
…
Circular
Function
+
=
Constant
+
1st Order
+
2nd Order
3rd Order
Frequency Decomposition
Harmonic Analysis
Spherical
Function
Harmonic Analysis
=
+
+
+
Spherical
Function
Harmonic Decomposition
+
…
Harmonic Analysis
=
+
+
+
+
…
=
+
+
+
+
…
Spherical
Function
Constant
1st Order
2nd Order
3rd Order
Building Shape Descriptor
Store “how much” (L2-norm) of the shape
resides in each frequency of each sphere
Frequency Decomposition
Amplitudes
Harmonic
Shape
Descriptor
Matching
Model similarity defined as L2-distance
between their descriptors
-
• Bounds proximity of voxel grids
over all rotations
Sim
,
=
-

-

Outline
Introduction
Approach
Implementation
Experimental Results
Conclusion and Future Work
Princeton 3D Search Engine
Query
Retrieval Experiment
Viewpoint “household” database
1,890 models, 85 classes
153 dining chairs
25 livingroom chairs
16 beds
12 dining tables
8 chests
28 bottles
39 vases
36 end tables
Retrieval Results
Precision-recall curve (mean for all queries)
1
Precision
0.8
0.6
Query
0.4
0.2
Random
0
0
0.2
0.4
0.6
Recall
0.8
1
Retrieval Results
Precision versus recall (mean for all
1
queries)
3D Harmonics (Our Method)
D2 Shape Distributions [Osada et al., 2001]
Shape Histograms [Ankerst, 1999]
EGI [Horn, 1984]
Moments [Elad et al., 2001]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Retrieval Results
Precision versus recall (mean for all
1
queries)
3D Harmonics (Our Method)
D2 Shape Distributions [Osada et al., 2001]
Shape Histograms [Ankerst, 1999]
EGI [Horn, 1984]
Moments [Elad et al., 2001]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Retrieval Results
Precision versus recall (mean for all
1
queries)
3D Harmonics (Our Method)
D2 Shape Distributions [Osada et al., 2001]
Shape Histograms [Ankerst, 1999]
EGI [Horn, 1984]
Moments [Elad et al., 2001]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Retrieval Results
Precision versus recall (mean for all
1
queries)
3D Harmonics (Our Method)
D2 Shape Distributions [Osada et al., 2001]
Shape Histograms [Ankerst, 1999]
EGI [Horn, 1984]
Moments [Elad et al., 2001]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Summary and Conclusion
Harmonic shape descriptor is a rotation
invariant representation that is:
• Discriminating (46%-245% better than others tested)
• Concise to store (2048 bytes)
• Quick to compute (1-5 seconds)
• Efficient to match (0.45 seconds: 20,000 model DB)
Future Work
Extensions
• Partial object matching?
• Other 3D shape functions?
Other applications
• Molecular biology
• Medicine
Query
• Paleontology
• Forensics
http://shape.cs.princeton.edu/
Thank You
Funding
• National Science Foundation
• Sloan Foundation
People
• Bernard Chazelle, David Dobkin, David Jacobs,
David Kazhdan, Allison Klein, Patrick Min, Szymon
Rusinkiewicz, Peter Sarnak, Julianna Tymoczko
http://shape.cs.princeton.edu/
Analysis
The Harmonic Descriptor is not invertible
• Different spheres rotate independently
• Different orders rotate independently
• Rotations are not transitive within an order
Analysis
The Harmonic Descriptor is not invertible
• Different spheres rotate independently
• Different orders rotate independently
• Rotations are not transitive within an order
l=0
l=1
l=2
l=3
Inter-Radial Coherence
Force same orders on different spheres to
rotate together by setting up the rotation
invariant matrix Mk with:
M
k
i, j
 f k ,i , f k , j
where fk,j is the k-th order component of the
restriction of f to the j-th radius.
(The diagonal is precisely the collection of
L2-norms.)
Polygon Rasterization
Rasterize using the Euclidean Distance
Transform to measure how much models
miss by:
Polygonal
Model
Voxel
Model