Transcript Taxonomy of Shape Descriptors

Shape Descriptors I
Thomas Funkhouser
CS597D, Fall 2003
Princeton University
3D Representations
Analysis
Retrieval
Intuitive specification
Guaranteed continuity
Guaranteed validity
Efficient boolean operations
Efficient rendering
Accurate
Concise
Structure
Display
Property
Editing
What properties are required for analysis and retrieval?
Yes
Yes
Yes
Yes
Yes
Yes
?
Yes
No
No
No
No
Yes
Yes
?
Yes
No
No
No
No
No
?
?
Yes
No
No
No
No
No
?
Yes
Yes
Shape Analysis Problems
Examples:
• Feature detection
• Segmentation
• Labeling
• Registration
• Matching
 Retrieval
• Recognition
• Classification
• Clustering
1)
2)
3)
Query
4)
Ranked Matches
“How can we find 3D models best matching a query?”
Shape
Definition from Merriam-Webster’s Dictionary:
• a : the visible makeup characteristic of a
particular item or kind of item
b : spatial form or contour
Shape
Shape is independent of similarity transformation
(rotation, scale, translation, mirror)
=
Shape Similarity
Need a shape distance function d(A,B) that:
• matches our intuitive notion of shape similarity
• can be computed robustly and efficiently
Perhaps, shape distance function should be a metric:
•
•
•
•
Non-negative:
Identity:
Symmetry:
Triangle inequality:
d(A,B)
d(A,B)
d(A,B)
d(A,B)
 0 for all A and B
= 0 if and only if A=B
= d(B,A) for all A and B
+ d(B,C)  d(A,C)
Example Distance Functions
Lp norm:
d ( A, B) 
 a  b 
p
i
1
p
i
Hausdorff distance:
~
d ( A, B)  max min ai  bi
aA
bB
~
~

d ( A, B)  max d ( A, B), d ( B, A) 
Others (Fréchet, etc.)
Shape Matching
Compute shape distance function for pair of 3D models
• Can matching two objects
• Can find most similar object among a small set
Are these the same chair?
Shape Retrieval
Find 3D models with shape most similar to query
• Searching large database must take less than O(n)
Is this blue chair
in the database?
Shape Retrieval
Build searchable shape index
Geometric
Query
Shape
Analysis
Shape
Descriptor
Shape
Retrieval
Database
of
3D Models
Shape
Analysis
Shape
Index
Similar
Objects
Shape Retrieval
Find 3D models with shape similar to query
3D Query
Best Matches
3D Database
Challenge
Need shape descriptor that is:
•
•
•
•
Concise to store
Quick to compute
Efficient to match
Discriminating
3D Query
Shape
Descriptor
Best
Matches
3D Database
Challenge
Need shape descriptor that is:
 Concise to store
• Quick to compute
• Efficient to match
• Discriminating
3D Query
Shape
Descriptor
Best
Matches
3D Database
Challenge
Need shape descriptor that is:
• Concise to store
 Quick to compute
• Efficient to match
• Discriminating
3D Query
Shape
Descriptor
Best
Matches
3D Database
Challenge
Need shape descriptor that is:
• Concise to store
• Quick to compute
 Efficient to match
• Discriminating
3D Query
Shape
Descriptor
Best
Matches
3D Database
Challenge
Need shape descriptor that is:
• Concise to store
• Quick to compute
• Efficient to match
 Discriminating
3D Query
Shape
Descriptor
Best
Matches
3D Database
Challenge
Need shape descriptor that is:
• Concise to store
• Quick to compute
• Efficient to match
• Discriminating
 Invariant to transformations
• Insensitive to noise
• Insensitive to topology
• Robust to degeneracies
Different Transformations
(translation, scale, rotation, mirror)
Challenge
Image courtesy of
Ramamoorthi et al.
Need shape descriptor that is:
• Concise to store
• Quick to compute
• Efficient to match
• Discriminating
• Invariant to transformations
 Insensitive to noise
• Insensitive to topology
• Robust to degeneracies
Scanned Surface
Challenge
Images courtesy of
Viewpoint & Stanford
Need shape descriptor that is:
• Concise to store
• Quick to compute
• Efficient to match
• Discriminating
• Invariant to transformations
• Insensitive to noise
 Insensitive to topology
• Robust to degeneracies
Different Genus
Different Tessellations
Challenge
Images courtesy of
Utah & De Espona
Need shape descriptor that is:
• Concise to store
• Quick to compute
• Efficient to match
• Discriminating
• Invariant to transformations
• Insensitive to noise
• Insensitive to topology
 Robust to degeneracies
No Bottom!
&*Q?@#A%!
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
• Point descriptors
Images courtesy of
Amenta & Osada
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
• Point descriptors
Image courtesy of
De Espona
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
• Point descriptors
?
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
• Point descriptors
?
Statistical Shape Descriptors
Alignment-dependent
•
•
•
•
•
•
Voxels
Wavelets
Moments
Extended Gaussian Image
Spherical Extent Function
Spherical Attribute Image
Alignment-independent
• Shape histograms
• Harmonic descriptor
• Shape distributions
Image courtesy of
Mao Chen
Feature Vectors
Map shape onto point in multi-dimensional space
• Similarity measure is distance in feature space
Feature 1
Tables
Desks
File cabinets
Feature 2
Image courtesy of
Mao Chen
Feature Vectors
Cluster, classify, recognize, and retrieve similar
feature vectors using standard methods
What feature vectors?
Feature 1
Tables
Desks
File cabinets
Feature 2
Voxels
Use voxel values as feature vector (shape descriptor)
• Feature space has N3 dimensions
(one dimension for each voxel)
• d(A,B) = ||A-B||N
Example:
(
d
,
A
B
)
=
A-B
N
Image courtesy of
Misha Kazhdan
Voxels
Can store distance transform (DT) in voxels
• ||A-DT(B)||1 represents sum of distances from every
point on surface of A to closest point on surface of B
Surface
Distance Transform
Image courtesy of
Misha Kazhdan
Voxels
Can store distance transform (DT) in voxels
• ||A-DT(B)||1 represents sum of distances from every
point on surface of A to closest point on surface of B
Surface
Distance Transform
Voxels
Can build hierarchical search structure
• e.g., interior nodes store MIV and MSV
Image courtesy of
Daniel Keim, SIGMOD 1999
Voxel Retrieval Experiment
Test database is Viewpoint household collection
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
Evaluation Metric
Precision-recall curves
• Precision = retrieved_in_class / total_retrieved
• Recall = retrieved_in_class / total_in_class
1
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Evaluation Metric
Precision-recall curves
• Precision = 0 / 0
• Recall = 0 / 5
1
Query
1
2
3
4
5
6
7
8
9
Precision
0.8
0.6
0.4
Ranked Matches
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Evaluation Metric
Precision-recall curves
• Precision = 1 / 1
• Recall = 1 / 5
1
Query
1
2
3
4
5
6
7
8
9
Precision
0.8
0.6
0.4
Ranked Matches
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Evaluation Metric
Precision-recall curves
• Precision = 2 / 3
• Recall = 2 / 5
1
Query
1
2
3
4
5
6
7
8
9
Precision
0.8
0.6
0.4
Ranked Matches
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Evaluation Metric
Precision-recall curves
• Precision = 3 / 5
• Recall = 3 / 5
1
Query
1
2
3
4
5
6
7
8
9
Precision
0.8
0.6
0.4
Ranked Matches
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Evaluation Metric
Precision-recall curves
• Precision = 4 / 7
• Recall = 4 / 5
1
Query
1
2
3
4
5
6
7
8
9
Precision
0.8
0.6
0.4
Ranked Matches
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Evaluation Metric
Precision-recall curves
• Precision = 5 / 9
• Recall = 5 / 5
1
Query
1
2
3
4
5
6
7
8
9
Precision
0.8
0.6
0.4
Ranked Matches
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Voxel Retrieval Experiment
Test database is Viewpoint household collection
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
Voxel Retrieval Results
1
Voxels
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Voxels
Properties
 Discriminating
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Quick to compute
• Efficient to match?
X Concise to store
X Invariant to transforms
Image courtesy of
Jacobs, Finkelstein, & Salesin
Wavelets
Define shape with wavelet coefficients
16,000 coefficients
400 coefficients
100 coefficients
20 coefficients
Wavelets
Jacobs, Finkelstein, & Salesin
SIGGRAPH 95
Descriptor 1:
• Given an NxNxN grid, generate an NxNxN array of the
wavelet coefficients for the standard Haar basis functions
Wavelets
Jacobs, Finkelstein, & Salesin
SIGGRAPH 95
Descriptor 1:
• Given an NxNxN grid, generate an NxNxN array of the
wavelet coefficients for the standard Haar basis functions
Descriptor 2:
• Truncate: Find the m largest coefficients and set all
others equal to zero
• Quantize: Set the non-zero coefficients to +1 or –1
depending on their sign
Jackie Chan Example
Original Image (256x256)
Truncated And Quantized to 5000
Truncated And Quantized to 1000
Truncated And Quantized to 500
Truncated 100
Truncated 50
Truncated 10
Torus Example
Torus Truncated to 5000
Torus Truncated to 1000
Torus Truncated to 500
Torus Truncated to 100
Torus Truncated to 50
Jacobs, Finkelstein, & Salesin
SIGGRAPH 95
Wavelets
Distance Function 1:
• The query metric is defined by:
d ( A, B)   wi , j ,k Ai, j , k   Bi, j , k 
i , j ,k
where A[i,j,k] and B[i,j,k] are the truncated and
quantized coefficients and wi,j,k are weights,
fine tuned to the database.
Jacobs, Finkelstein, & Salesin
SIGGRAPH 95
Wavelets
Distance Function 2:
• The query metric can be approximated by:
d ( A, B) 
w
i , j ,k
i , j , k :A( i , j , k )  0
( Ai, j, k   Bi, j, k )
to enable efficient indexing and search.
Wavelets
Properties
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Quick to compute
 Efficient to match
 Concise to store
• Discriminating?
X Invariant to transforms
Jacobs, Finkelstein, & Salesin
SIGGRAPH 95
Moments
Define shape by moments of inertia:
m pqr 
x
surface
p
q r
y z dxdydz
Moments Retrieval Experiment
Test database is Viewpoint household collection
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
Moments Retrieval Results
1
Voxels
Moments [Elad et al.]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Moments Retrieval Results
1
Voxels
Moments [Elad et al.]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Moments
Properties
 Insensitive to topology
 Robust to degeneracies
 Quick to compute
 Efficient to match
 Concise to store
X Insensitive to noise
X Invariant to transforms
X Discriminating
Extended Gaussian Image
Define shape with histogram of normal directions
• Invertible for convex objects
• Spherical function
3D Model
EGI
EGI Retrieval Experiment
Test database is Viewpoint household collection
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
EGI Retrieval Results
1
Voxels
Moments [Elad et al.]
EGI [Horn 84]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Extended Gaussian Images
Properties
 Insensitive to topology
 Quick to compute
 Efficient to match
 Concise to store
X Insensitve to noise
X Robust to degeneracies
X Invariant to transforms
X Discriminating
Other Rotation-Dependent Descriptors
Spherical Extent Functions
(Vranic & Saupe, 2000)
Shape Histograms (sectors)
(Ankherst, 1999)
Shape Descriptors II
Thomas Funkhouser
CS597D, Fall 2003
Princeton University
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
• Point descriptors
Statistical Shape Descriptors
Alignment-dependent
•
•
•
•
•
•
Voxels
Wavelets
Moments
Extended Gaussian Image
Spherical Extent Function
Spherical Attribute Image
Alignment-independent
• Shape histograms
• Harmonic descriptor
• Shape distributions
Statistical Shape Descriptors
Alignment-dependent
•
•
•
•
•
•
Voxels
Wavelets
Moments
Extended Gaussian Image
Spherical Extent Function
Spherical Attribute Image
Alignment-independent
• Shape histograms
• Harmonic descriptor
• Shape distributions
Alignment
Translation (Center of Mass)
n
1
c   pi
n i 1
Scale (Radial Deviation)
n
1
s
pi

n i 1
2
Alignment
Rotation (PCA)
• Principal axes are eigenvectors associated with largest
eigenvalues of 2nd order moments covariance matrix
PCA
Computation
Principal Axis
Alignment
Alignment
Rotation (PCA)
• Principal axes are eigenvectors associated with largest
eigenvalues of 2nd order moments covariance matrix
Not very robust!
Alignment
Mirror
• PCA does not give directions for principal axes
Need heuristics to determine positive axes!
Alignment-Independent Descriptors
Observation: it is difficult to normalize for differences
in rotation and mirroring
Three mugs aligned automatically with PCA
Motivation: build a shape descriptor that is invariant to
rotations and mirrors and as discriminating
as possible
Image courtesy of
Ankerst et al, 1999
Shape Histograms
Shape descriptor stores histogram of how much surface
resides at different radii from center of mass
Radius
Shape Histograms (shells)
(Ankherst, 1999)
Image courtesy of
Misha Kazhdan
Shape Histograms
Shape descriptor stores histogram of how much surface
resides at different radii from center of mass
0.7
0.3
0.1
3D Model
Spherical
Decomposition
Shape
Descriptor
Shape Histogram Experiment
Test database is Viewpoint household collection
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
Shape Histogram Retrieval Results
Precision-recall curves (mean for all queries)
1
Shape Histogram [Ankerst et al.]
EGI [Horn]
Moments [Elad et al.]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Shape Histograms
Properties
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Quick to compute
 Efficient to match
 Concise to store
 Invariant to rotations
• Discriminating?
Harmonic Shape Descriptor
Key idea:
• Decompose each sphere into irreducible
set of rotation independent components
• Store “how much” of the model resides
in each component
3D Model
Harmonic
Decompositions
Shape
Descriptor
Step 1: Normalization
Normalize for translation and scale
3D Model
Step 2: Voxelization
Rasterize polygon surfaces into 3D voxel grid
3D Voxel Grid
Step 3: Spherical Decomposition
Intersect with concentric spheres
Spherical Functions
Step 4: Frequency Decomposition
Represent each spherical function as a sum
of harmonic frequencies (orders)
Spherical Functions
Step 4: Frequency Decomposition
Represent each spherical function as a sum
of harmonic frequencies (orders)
Spherical
Function
Spherical Functions
Step 4: Frequency Decomposition
Represent each spherical function as a sum
of harmonic frequencies (orders)
=
+
+
Spherical
Function
Harmonic Decomposition
+
…
Step 4: Frequency Decomposition
Represent each spherical function as a sum
of harmonic frequencies (orders)
=
+
+
+
…
=
+
+
+
…
Spherical
Function
Constant
1st Order
2nd Order
Step 4: Frequency Decomposition
Represent each spherical function as a sum
of harmonic frequencies (orders)
=
Amplitudes
are
+
+
invariant to rotation
+
…
+
…
Spherical
Function
=
+
+
Frequency Decomposition
Step 5: Amplitude Computation
Store “how much” (L2-norm) of the shape resides in
each harmonic frequency of each sphere
Harmonic Shape Descriptor
Matching Harmonic Descriptors
Define similarity as L2-distance between descriptors
• Enables nearest neighbor indexing and fast search
• Provides lower bound for L2-distance between models
Sim
,
=
-

-

Harmonic Shape Descriptor
Properties
 Concise to store?
• Quick to compute?
• Insensitive to noise?
• Insensitive to topology?
• Robust to degeneracies?
• Invariant to transforms?
• Efficient to match?
• Discriminating?
2048 bytes per model
(16 frequencies x 32 radii x 4 bytes)
Harmonic Shape Descriptor
Properties
1.6 seconds (on average)
 Concise to store
 Quick to compute?
• Insensitive to noise?
• Insensitive to topology?
• Robust to degeneracies?
• Invariant to transforms?
• Efficient to match?
• Discriminating?
Polygons
Voxels
Spherical
Decomposition
Frequency
Decomposition
Harmonic
Shape
Descriptor
Harmonic Shape Descriptor
Properties
1.6 seconds (on average)
 Concise to store
 Quick to compute?
• Insensitive to noise?
• Insensitive to topology?
• Robust to degeneracies?
• Invariant to transforms?
• Efficient to match?
• Discriminating?
Polygons
Voxels
Spherical
Decomposition
Frequency
Decomposition
Harmonic
Shape
Descriptor
Harmonic Shape Descriptor
Properties
 Concise to store
 Quick to compute
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
• Invariant to transforms?
• Efficient to match?
• Discriminating?
Rasterize polygon surfaces
(no solid reconstruction)
Harmonic Shape Descriptor
Properties
 Concise to store
 Quick to compute
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Invariant to transforms
• Efficient to match?
• Discriminating?
{
Rotation
Mirror
Translation (w/ normalization)
Scale (w/ normalization)
Harmonic Shape Descriptor
Properties
0.23 seconds
to search
17,500 models
Search time (secs)
 Concise to store
 Quick to compute
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Invariant to transforms
 Efficient to match?
• Discriminating?
2.0
1.5
1.0
Indexed
0.5
0.0
0
5000
10000
15000
Database size (models)
20000
Harmonic Shape Descriptor
Properties
 Concise to store
 Quick to compute
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Invariant to transforms
 Efficient to match?
 Discriminating?
Harmonic Matching Results
Test database is Viewpoint household collection
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
Harmonic Retrieval Results
Precision-recall curves (mean for all queries)
1
Harmonic Shape Descriptor
Shape Histogram [Ankerst et al.]
EGI [Horn]
Moments [Elad et al.]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Statistical Shape Descriptors
Alignment-dependent
•
•
•
•
•
•
Voxels
Wavelets
Moments
Extended Gaussian Image
Spherical Extent Function
Spherical Attribute Image
Alignment-independent
• Shape histograms
• Harmonic descriptor
 Shape distributions
Shape Distributions
Motivation: general approach to finding a
common parameterization for matching
Audio
3D Surface
2D Contour
3D Volume
Shape Distributions
Distance
Probability
Randomly
sample
shape
function
Probability
Key idea: map 3D surfaces to common parameterization
by randomly sampling shape function
Distance
3D Models
D2 Shape Distributions
Similarity
Measure
Which Shape Function?
Implementation: simple shape functions based on
angles, distances, areas, and volumes


A3
(angle)
D1
(distance)
[Ankerst 99]
D2
(distance)
D3
(area)
D4
(volume)
D2 Shape Distribution
Properties
•
•
•
•
•
•
•
•
Concise to store?
Quick to compute?
Invariant to transforms?
Efficient to match?
Insensitive to noise?
Insensitive to topology?
Robust to degeneracies?
Discriminating?
D2 Shape Distribution
 Concise to store?
 Quick to compute?
• Invariant to transforms?
• Efficient to match?
• Insensitive to noise?
• Insensitive to topology?
• Robust to degeneracies?
• Discriminating?
Probability
Properties
Skateboard
Distance
512 bytes (64 values)
0.5 seconds (106 samples)
D2 Shape Distribution
Properties
 Concise to store
 Quick to compute
 Invariant to transforms?
• Efficient to match?
• Insensitive to noise?
• Insensitive to topology?
• Robust to degeneracies?
• Discriminating?
{
Translation
Rotation
Mirror
Scale
(w/ normalization)
Skateboard
Porsche
Normalized Means
D2 Shape Distribution
Properties
Porsche
Probability
 Concise to store
 Quick to compute
 Invariant to transforms
 Efficient to match?
• Insensitive to noise?
• Insensitive to topology?
• Robust to degeneracies?
• Discriminating?
Skateboard
Distance
D2 Shape Distribution
Properties
 Concise to store
 Quick to compute
 Invariant to transforms
 Efficient to match
 Insensitive to noise?
 Insensitive to topology?
 Robust to degeneracies?
• Discriminating?
1% Noise
D2 Shape Distribution
Properties
 Concise to store
 Quick to compute
 Invariant to transforms
 Efficient to match
 Insensitive to noise
 Insensitive to topology
 Robust to degeneracies
 Discriminating?
D2 Shape Distribution Results
Question
• How discriminating are
D2 shape distributions?
Test database
• 133 polygonal models
• 25 classes
4 Mugs
6 Cars
3 Boats
D2 Shape Distribution Results
D2 distributions are different across classes
D2 shape distributions for 15 classes of objects
Probability
D2 Shape Distribution Results
Distance
D2 distributions for 5 tanks (gray) and 6 cars (black)
D2 Shape Distribution Results
Similarity Matrix
• Darkness
represents
similarity
Blocks
•
•
•
•
Tanks, cars
Airplanes
Humans
Helicopters
al
bl
bt bp bt cr
cr
cw hr
hn
lp lg me
mg
ok
pn
pe
pe
re
sd sa
sp
sb te
tk
tank
tank
table
table
sub
sub
spaceship
spaceship
sofa
sofa
skateboard
skateboard
rifle
rifle
plane
plane
phone
phone
pen
pen
openbook
openbook
mug
mug
missle
missle
lightning
lightning
lamp
lamp
human
human
helicopter
helicopter
claw
claw
chair
chair
car
car
boat
boat
blimp
belt
blimp
belt
ball
ball
animal
animal
al
bl
bt bp bt cr
cr
cw hr
hn
lp lg me
mg
ok
pn
pe
pe
re
sd sa
sp
sb te
tk
D2 Retrieval Experiment
Test database is Viewpoint household collection
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
D2 Retrieval Results
Precision-recall curves (mean for all queries)
1
Harmonic Shape Descriptor
D2 Shape Distribution [Osada et al.]
Shape Histogram [Ankerst et al.]
EGI [Horn]
Moments [Elad et al.]
Random
Precision
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
Recall
0.8
1
Shape Distributions
Next steps:
• Better shape functions
• Better comparsion methods
• Analysis apps
D2 Shape Distribution Results
Recognizing gross shapes with D2 distributions
Line Segment
D2 shape distributions for 15 classes of objects
D2 Shape Distribution Results
Recognizing gross shapes with D2 distributions
Circle
D2 shape distributions for 15 classes of objects
D2 Shape Distribution Results
Recognizing gross shapes with D2 distributions
Cylinder
D2 shape distributions for 15 classes of objects
D2 Shape Distribution Results
Recognizing gross shapes with D2 distributions
Sphere
D2 shape distributions for 15 classes of objects
D2 Shape Distribution Results
Recognizing gross shapes with D2 distributions
Two Spheres
D2 shape distributions for 15 classes of objects
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
• Point descriptors
Taxonomy of Shape Descriptors
Structural representations
• Skeletons
• Part-based methods
• Feature-based methods
Statistical representations
• Voxels, moments, wavelets, …
• Attributes, histograms, ...
 Point descriptors
Next Time!