Our goal is to investigate issues in shape-based
retrieval and analysis of 3D models. As a first step, we have developed
a search engine for 3D polygonal models (check it out by clicking here).
The main research issues are to develop effective shape
representations and query
interfaces. The Princeton Shape Benchmark is a set of 3D
models that can be downloaded for further research.
This web page provides an overview of some projects on these topics.
Our publications provide more details.
Shape Representations
A key issue in developing a shape-based retrieval
and analysis system is to find a computational representation of shape
(a shape descriptor) for which an index can be built, similarity
queries can be answered efficiently. We are studying a spectrum of shape
descriptors, ranging from ones that are simple to compute (but perhaps
not very discriminating) to ones that require expensive computations (but
provide sophisticated shape analysis):
Shape Distributions:
On the low end of the spectrum, we have
been investigating shape distributions that represent the shape
of a 3D model as a probability distribution sampled from a shape function
measuring geometric properties of a 3D model. The motivation for this approach
is that samples can be computed quickly and easily, and the shape of the
resulting distributions are invariant to similarity transformations, noise,
tessellation, cracks, etc.(with a normalization step for scale invariance).
For example, one such shape distribution, which we call
D2, represents
the global shape of an object by the probability distribution of Euclidean
distances between pairs of randomly selected points on its surface.
The figure below shows the D2 distributions for 5 tanks (gray curves) and
6 cars (black curves). Note how the classes are distinguishable.
Reflective Symmetry Descriptors:
Computing reflective symmetries of 2D
and 3D shapes is a classical problem in computer vision and computational
geometry. Most prior work has focused on finding the main axes of symmetry,
or determining that none exists. We have studied a new shape descriptor
that represents a measure of reflective symmetry for an arbitrary 3D voxel
model for all planes through the model’s center of mass (even if they are
not planes of symmetry). For example, the figure to the right shows a car,
cube and chair (top) and their corresponding reflective symmetry descriptors
(bottom). The descriptors are drawn by scaling unit vectors on the sphere
in proportion to the measure of reflective symmetry about the plane through
the center of mass and normal to the vector.The main benefits of this new
shape descriptor are that it is defined over a canonical parameterization
(the sphere), which makes comparison simple, and it describes global symmetry
properties of a 3D shape, which capture significant semantic features of
many objects.
Spherical Harmonics:
One of the main challenges in matching
and indexing shapes is accounting for arbitrary rotations. Previous methods
that require alignment into a common coordinate system (e.g., with principal
axes) are not robust. Other methods that rely upon rotationally
invariant shape descriptors are usually not very discriminating.
We propose a novel rotation invariant shape-descriptor based on spherical
harmonics. The main idea is to decompose a 3D model into a collection
of functions defined on concentric spheres and to use spherical harmonics
to discard orientation information (phase) for each one. This yields a
shape descriptor that is both orientation invariant and descriptive.
Skeletal Graphs:
On the high end of the spectrum, we are
investigating skeletons as a descriptor of shape. The general idea is to
derive 1D skeletal curves from a 3D object such that each curve represents
a significant part of the object. These curves are then converted
to an attributed graph representation (a
skeletal graph), which
can be used for indexing, matching, segmentation, correspondence finding,
etc. As an example, the figure below shows a plane model, its medial axis
(as computed using the “Powercrust” algorithm [3]), our voxelized centerline
representation, and the resulting skeletal graph. Note that the medial
axis comprises a multitude of noisy curves and sheets, while our centerline
representation nicely segments the plane into its salient parts.
Query Interfaces
Another issue is how should people specify
shape-based queries? For instance, consider a person who wants to
build a 3D virtual world representing a city scene. She will need
cars, street lamps, stop signs, etc. What input should be given to
a search engine to retrieve objects of these types from the World Wide
Web? We have investigated several options:
Text:
The simplest query interface is to search
for 3D models based on textual keywords. To support this feature, we construct
for each 3D model a representative document containing the model filename,
the anchor and nearby text parsed from its referring Web page, and ASCII
labels parsed from inside the model file. For each document, stop words
are removed, verbs are stemmed to remove inflectional changes, and synonyms
are added using WordNet [Miller95]. We match documents to user-specified
keywords using the TF-IDF/Rocchio method [Rocchio71], a popular weighting
and classification scheme for text documents.
3D Model:
We also support shape-based queries.
For instance, the user can provide an existing 3D model and ask our search
engine to retrieve similar ones. Alternately, the user may search
for models with shapes like one returned in a previous search by clicking
on the ``Find Similar Shape'' link under its image on a results page (blue
text in the figure below).
3D Sketches:
Of course, shape similarity queries are
only possible when the user already has a representative 3D model.
In some cases, he will be able to find one by using a text search.
However, in other cases, he will have to create it from scratch (at least
to seed the search). To investigate this option, we have developed
a query interface in which the user creates a simple 3D model with Teddy
[Igarashi99], and then the system returns objects with similar shapes.
For example, the figure below shows a cup sketched in Teddy and its five
closest matches.
2D Sketches:
An alternative approach is to allow the
user to draw one or more 2D shapes with a pixel paint program and then
have the system match the resulting image(s) to 2D projections of 3D objects.
For example, in the figures below, the user has drawn outline contours
specifying a shape, and the system has returned a set of matching objects.
Princeton Shape
Benchmark
The Princeton Shape Benchmark provides a repository of 3D models and software tools
for evaluating shape-based retrieval and analysis algorithms. The motivation is to
promote the use of standardized data sets and evaluation methods for research in matching,
classification, clustering, and recognition of 3D models. Researchers are encouraged
to use these resources to produce comparisons of competing algorithms in future
publications.
The benchmark contains a database of 3D polygonal models collected from the World Wide
Web. For each 3D model, there is a Object File Format (.off) file
with the polygonal geometry of the model, an ASCII text file
with information about the model (e.g., the URL from whence it came), and a
JPEG image file
with a thumbnail view of the model. Version 1 of the
benchmark contains 1,814 models. Source code for parsing the
files, viewing the models, and creating overview web pages is provided.
Publications
Forrester Cole, Aleksey Golovinskiy, Alex Limpaecher, Heather Stoddart Barros,
Adam Finkelstein, Thomas Funkhouser, and Szymon Rusinkiewicz, Where Do People Draw Lines?, ACM Transactions on Graphics (SIGGRAPH 2008), August 2008.
Aleksey Golovinskiy, Joshua Podolak, and Thomas Funkhouser,
Symmetry-Aware Mesh Processing Princeton University Technical Report, TR-782-07 April 2007.
Joshua Podolak, Philip Shilane, Aleksey Golovinskiy, Szymon Rusinkiewicz, and Thomas Funkhouser,
"
A Planar-Reflective Symmetry Transform for 3D Shapes,"
ACM Transactions on Graphics (SIGGRAPH 2006), 25(3), July 2006.
Thomas Funkhouser, Michael Kazhdan, Philip Shilane, Patrick Min,
William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, and David Dobkin,
"
Modeling by Example,"
ACM Transactions on Graphics (SIGGRAPH 2004), Los Angeles, CA, August 2004
Michael Kazhdan, Thomas Funkhouser, and Szymon Rusinkiewicz,
"
Shape Matching and Anisotropy,"
ACM Transactions on Graphics (SIGGRAPH 2004), Los Angeles, CA, August 2004
Philip Shilane, Patrick Min, Michael Kazhdan, and Thomas Funkhouser,
"
The Princeton Shape Benchmark,"
Shape Modeling International, Genova, Italy, June 2004
Michael Kazhdan, Bernard Chazelle, David Dobkin, Thomas Funkhouser, and
Szymon Rusinkiewicz,
"
A Reflective Symmetry Descriptor for 3D Models,"
Algorithmica, 38(2), November 2003, pp. 201-225
Thomas Funkhouser, Patrick Min, Michael Kazhdan,
Joyce Chen, Alex Halderman, David Dobkin, and David Jacobs,
"
A Search Engine for 3D Models,"
ACM Transactions on Graphics, 22(1), pp. 83-105, January 2003
Robert Osada, Thomas Funkhouser,
Bernard Chazelle, and David Dobkin,
"
Shape Distributions,"
ACM Transactions on Graphics, 21(4), pp. 807-832, October 2002
Michael Kazhdan, Bernard Chazelle,
David Dobkin, Adam Finkelstein, and Thomas Funkhouser,
"
A Reflective Symmetry Descriptor,"
European Conference on Computer Vision (ECCV), May, 2002
Michael Kazhdan and Thomas Funkhouser,
"
Harmonic 3D Shape Matching"
SIGGRAPH 2002 Technical Sketches, p. 191, July, 2002.
Thomas Funkhouser, Michael Kazhdan, Philip Shilane, Patrick Min,
William Kiefer, Ayellet Tal, Szymon Rusinkiewicz, and David Dobkin,
"Modeling by Example,"
74MB AVI file, SIGGRAPH 2004.
Thomas Funkhouser, Patrick Min, Michael Kazhdan,
Joyce Chen, Alex Halderman, David Dobkin, and David Jacobs,
"A Search Engine for 3D Models,"
72MB AVI file, ACM TOG 2003.
