20-07-2012, 10:51 AM
A Search Engine for 3D Models
A Search Engine.pdf (Size: 3.3 MB / Downloads: 32)
INTRODUCTION
Over the last few decades, computer science has made incredible progress in computeraided
retrieval and analysis of multimedia data. For example, suppose you want to obtain
an image of a horse for a Powerpoint presentation. A decade ago, you could: 1) draw a
picture, 2) go to a library and copy a picture, or 3) go to a farm and photograph a horse.
Today, you can simply pick a suitable image from the millions available on the web. Although
web search is commonplace for text, images, and audio, the information revolution
for 3D data is still in its infancy.
However, three recent trends are combining to accelerate the proliferation of 3D models,
leading to a time in the future when 3D models will be as ubiquitous as other multimedia
data are today: (1)
RELATED WORK
Data retrieval and analysis have recently been a very active area of research [Duda et al.
2001; Lesk 1997]. The most obvious examples are text search engines (e.g., Google [Brin
and Page 1998]), which have become part of our daily lives. However, content-based retrieval
and classification systems have also been developed for other multimedia data types,
including audio [Foote 1999], images [Castelli and Bergman 2001], and video [Veltkamp
et al. 2001].
Retrieval of data based on shape has been studied in several fields, including computer
vision, computational geometry, mechanical CAD, and molecular biology (see [Alt and
Guibas 1996; Arman and Aggarwal 1993; Besl and Jain 1985; Loncaric 1998; Pope 1994;
Veltkamp 2001] for surveys of recent methods). However, most prior work has focused
on 2D data [Flickner et al. 1995; Jacobs et al. 1995; Ogle and Stonebraker 1995]. For
instance, several content-based image retrieval systems allow a user to sketch a coarsely
detailed picture and retrieve similar images based on color, texture, and shape similarities
(e.g., [Jacobs et al. 1995]). Extending these systems to work for 3D surface models is
non-trivial, as it requires finding a good user interface for specifying 3D queries and an effective
algorithm for indexing 3D shapes. One problem for indexing 3D surfaces is boundary
parameterization. Although the 1D boundary contours of 2D shapes have a natural
arc length parameterization, 3D surfaces of arbitrary genus do not. As a result, common
shape descriptors for 2D contours (e.g., [Arbter et al. 1990; Arkin et al. 1991; Kashyap
and Chellappa 1981; Lin et al. 1992; Uras and Verri 1994; Young et al. 1974]) cannot
be extended to 3D surfaces, and computationally efficient matching algorithms based on
dynamic programming (e.g., [Tappert 1982; Tsai and Yu 1985]) cannot be applied to 3D
objects. Another problem is the higher dimensionality of 3D data, which makes registration,
finding feature correspondences, and fitting model parameters more expensive.
SKETCH QUERIES
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).
An interesting open question then is “what type of modeling tool should be used to
create shapes for 3D retrieval queries?”. This question is quite different than the one asked
in traditional geometric modeling research. Rather than providing a tool with which a
trained user can create models with exquisite detail and/or smoothness properties, our goal
is to allow novice users to specify coarse 3D shapes quickly. In particular, the interface
should be easy to learn for first time visitors to a website.
MULTIMODAL QUERIES
Since text and shape queries can provide orthogonal notions of similarity corresponding to
function and form, our search engine allows them to be combined.
We support this feature in two ways. First, text keywords and 2D/3D sketches may
be entered in a single multimodal query. Second, text and shape information entered in
successive queries can be combined so that a user can refine search terms adaptively. For
instance, if a user entered text keywords in a first query, and then clicked a “Find Similar
Shape” link, the text and 3D shape would combine to form a second query.
These types of multimodal queries are often helpful to focus a search on a specific subclass
of objects (Figure 10). For example, a query with only keywords can retrieve a class
of objects (e.g., tables), but it is often hard to home in on a specific subclass with text
alone (e.g., round tables with a single pedestal). Similarly, a query with only a sketch can
retrieve objects with a particular shape, but it may include objects with different functions
(e.g., both tables and chairs). Multimodal input can combine ways of describing objects to
form more specific queries (Figure 10©).
A Search Engine.pdf (Size: 3.3 MB / Downloads: 32)
INTRODUCTION
Over the last few decades, computer science has made incredible progress in computeraided
retrieval and analysis of multimedia data. For example, suppose you want to obtain
an image of a horse for a Powerpoint presentation. A decade ago, you could: 1) draw a
picture, 2) go to a library and copy a picture, or 3) go to a farm and photograph a horse.
Today, you can simply pick a suitable image from the millions available on the web. Although
web search is commonplace for text, images, and audio, the information revolution
for 3D data is still in its infancy.
However, three recent trends are combining to accelerate the proliferation of 3D models,
leading to a time in the future when 3D models will be as ubiquitous as other multimedia
data are today: (1)
RELATED WORK
Data retrieval and analysis have recently been a very active area of research [Duda et al.
2001; Lesk 1997]. The most obvious examples are text search engines (e.g., Google [Brin
and Page 1998]), which have become part of our daily lives. However, content-based retrieval
and classification systems have also been developed for other multimedia data types,
including audio [Foote 1999], images [Castelli and Bergman 2001], and video [Veltkamp
et al. 2001].
Retrieval of data based on shape has been studied in several fields, including computer
vision, computational geometry, mechanical CAD, and molecular biology (see [Alt and
Guibas 1996; Arman and Aggarwal 1993; Besl and Jain 1985; Loncaric 1998; Pope 1994;
Veltkamp 2001] for surveys of recent methods). However, most prior work has focused
on 2D data [Flickner et al. 1995; Jacobs et al. 1995; Ogle and Stonebraker 1995]. For
instance, several content-based image retrieval systems allow a user to sketch a coarsely
detailed picture and retrieve similar images based on color, texture, and shape similarities
(e.g., [Jacobs et al. 1995]). Extending these systems to work for 3D surface models is
non-trivial, as it requires finding a good user interface for specifying 3D queries and an effective
algorithm for indexing 3D shapes. One problem for indexing 3D surfaces is boundary
parameterization. Although the 1D boundary contours of 2D shapes have a natural
arc length parameterization, 3D surfaces of arbitrary genus do not. As a result, common
shape descriptors for 2D contours (e.g., [Arbter et al. 1990; Arkin et al. 1991; Kashyap
and Chellappa 1981; Lin et al. 1992; Uras and Verri 1994; Young et al. 1974]) cannot
be extended to 3D surfaces, and computationally efficient matching algorithms based on
dynamic programming (e.g., [Tappert 1982; Tsai and Yu 1985]) cannot be applied to 3D
objects. Another problem is the higher dimensionality of 3D data, which makes registration,
finding feature correspondences, and fitting model parameters more expensive.
SKETCH QUERIES
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).
An interesting open question then is “what type of modeling tool should be used to
create shapes for 3D retrieval queries?”. This question is quite different than the one asked
in traditional geometric modeling research. Rather than providing a tool with which a
trained user can create models with exquisite detail and/or smoothness properties, our goal
is to allow novice users to specify coarse 3D shapes quickly. In particular, the interface
should be easy to learn for first time visitors to a website.
MULTIMODAL QUERIES
Since text and shape queries can provide orthogonal notions of similarity corresponding to
function and form, our search engine allows them to be combined.
We support this feature in two ways. First, text keywords and 2D/3D sketches may
be entered in a single multimodal query. Second, text and shape information entered in
successive queries can be combined so that a user can refine search terms adaptively. For
instance, if a user entered text keywords in a first query, and then clicked a “Find Similar
Shape” link, the text and 3D shape would combine to form a second query.
These types of multimodal queries are often helpful to focus a search on a specific subclass
of objects (Figure 10). For example, a query with only keywords can retrieve a class
of objects (e.g., tables), but it is often hard to home in on a specific subclass with text
alone (e.g., round tables with a single pedestal). Similarly, a query with only a sketch can
retrieve objects with a particular shape, but it may include objects with different functions
(e.g., both tables and chairs). Multimodal input can combine ways of describing objects to
form more specific queries (Figure 10©).