«A 3D Model Search Engine Patrick Min A Dissertation Presented to the Faculty of Princeton University in Candidacy for the Degree of Doctor of ...»
A 3D Model Search Engine
Presented to the Faculty
of Princeton University
in Candidacy for the Degree
of Doctor of Philosophy
Recommended for Acceptance
By the Department of
c Copyright by Patrick Min, 2004.
All Rights Reserved
This thesis describes an online search engine for 3D models, focusing on query
interfaces and their corresponding model/query representations and matching methods.
A large number of 3D models has already been created, many of which are freely available on the web. Because of the time and eﬀort involved in creating a highquality 3D model, considerable resources could be saved if these models could be reused. However, ﬁnding the model you need is not easy, since most online models are scattered across the web, on repository sites, project sites, and personal homepages.
To make these models more accessible, we have developed a prototype 3D model search engine. This project serves as a test bed for new methods in web crawling, query interfaces, and matching of 3D models. This thesis focuses on query interfaces and their accompanying matching methods. We investigated query interfaces based on text keywords, 3D shape, 2D shape, and some combinations.
By testing matching methods that use text, 3D shape, and 2D shape, we found that the 3D shape matching method outperforms our text matching method for our application domain, due to the insuﬃcient text annotation of 3D models on the web.
Furthermore, classiﬁcation performance was improved by combining the 3D shapeand text-based matching methods. The results of a user study also suggest that text can combine with shape to make queries more eﬀective.
We compared shape matching methods based on matching multiple 2D projections of a 3D model and found that from a set of side, corner and edge projections, the combination of side and corner projections produced the best results. However, these results were still worse than those of the 3D shape matching method.
We present a 2D structural interface and accompanying matching method that iii produces better classiﬁcations than image matching for certain types of objects.
Our prototype search engine has been used extensively across the world (in 18 months, almost 300,000 queries have been processed from more than 100 countries) and has proven to be useful (models have been downloaded over 50,000 times, and almost 30% of all visitors per day are returning users).
iv Acknowledgments First and foremost I would like to thank my advisor, Tom Funkhouser, and my advisor in my ﬁrst two years, David Dobkin: Tom for his patience and his persistence in trying to turn me into a scientist, and David for his guidance and for always having time. Many thanks also to my other committee members, Szymon Rusinckiewicz, Andrea LaPaugh and David Jacobs, and former committee member Adam Finkelstein.
Many students played an important part in this project. I would like to thank Alex Halderman, who wrote the crawler, Joyce Chen, who ran two user studies, and David Bengali and Phil Shilane for their work in creating 3D model test databases.
And of course thanks to Misha Kazhdan, for his excellent work, and with whom it was great to collaborate.
I wish to acknowledge the help of the supporting technical and administrative staﬀ at the Princeton Computer Science department: Joe Crouthamel, Steve Elgersma, Ginny Hogan, Chris Kranz, Tina McCoy, Melissa Lawson, Jim Roberts, Chris Tengi, and Trish Zabielski.
Thanks to Viewpoint Corporation, Jose Maria De Espona, and Cacheforce for donating large collections of 3D models for use in our experiments. I would also like to acknowledge the National Science Foundation, who provided partial funding for this project under grants CCR-0093343, 11S-0121446, CCR-99-88173, and DGEand the Army Research Organization, who provided partial funding under grant DAAD19-99-1-0205. My advisor, Tom Funkhouser, is partially supported by an Alfred P. Sloan Fellowship.
A large number of friends made my time in Princeton special. In no particular order, and with some sadness because opportunities to see each other are fewer and further between: Rudro Samanta, Sanjeev Kumar and Sushma Bhope, Steve and Judy Kleinstein, Jason Lawrence, Iannis Tourlakis, Amal Ahmed, Tom Weaver, Susan Uhm, Mariesha Blazik, Patricia Sung, Chris Dunworth, Bob and Heather Thomas, Alejo Hausner, Wenjia Fang, Emil Praun, Allison Klein, Misha Kazhdan, Tony Wirth, Lena Petrovi´, Petra Sijpestein, Riky Schmidt, Wagner Corrˆa, and c e George Karakostas. To my friends in the Netherlands, who fortunately still kept in touch: Rob Klein, Nico van Paridon, Chris Nyqvist, Arjen van der Ziel, Dani¨lle e Hemels, Lizza Westerhof, Jacqueline Neumann, Reinoud van Leeuwen, Hanno Liem, Florine Asselbergs, and Karolien van der Ven.
Thanks to my parents, for always supporting me, no matter what I chose to do.
And ﬁnally, to my dear Katerina, for being part of my life.
4.1 Example objects created using (a) SKETCH , (b) a “suggestive interface” , (c) Teddy , (d) variational implicit surfaces ....... 30
4.2 Samples from ten representative classes from the Viewpoint “household” and “miscellaneous” database (images courtesy of Viewpoint)....... 32
4.3 A histogram of the class sizes of the 84 classes in the Viewpoint database 33
4.4 Precision/recall plots of our 3D shape matching method versus other methods 34
4.5 An example of each of eight categories for 1,000 submitted 3D sketches 34
6.17 Screenshots of all 75 models in the test set................. 72
6.18 Example models from two small test databases, their three plan views, and the selected “characteristic” view..................... 73
6.19 Example ellipses drawn for the selected views in Figure 6.18........ 74
6.20 Average precision for diﬀerent values of the weight of the (a) image overlap term, and (b) EDT alignment term, (c) ellipse overlap term, (d) deformation term. Note that in each graph the y-axis starts at 0.5 and ends at 0.65.. 75
6.21 The top ﬁve results for a set of ellipses representing a bird, with the image overlap weight set to (a) 0.25, (b) 1.0, (c) 3.0.......... 76
6.22 The top ﬁve results for a set of ellipses representing a ﬂoorlamp, with the EDT alignment weight set to (a) 0.25, (b) 1.0, (c) 3.0....... 76
6.23 The top ﬁve results for a set of ellipses representing a dinosaur, with the part overlap weight set to (a) 0.25, (b) 1.0, (c) 2.5......... 77
6.24 The top ﬁve results for a set of ellipses representing a table, with the deformation weight set to (a) 0.25, (b) 1.0, (c) 5.0........... 77
6.25 Average precision for diﬀerent values of (a) the number of orientations to try for the initial alignment, (b) the number of random image samples to use for the image overlap term (the horizontal line shows the optimal value, achieved when computing exact image overlap in pixels), (c) the number of boundary samples used to compute the approximate ellipse overlap term, (d) the number of samples along the ellipse’s major axis to compute the EDT alignment term............................ 79
6.26 Precision/recall for 2D structural matching, 2D outline image matching (of the ellipse outlines to the stored 2D view outlines), 2D image-to-image matching, and random retrieval, for a test database of 15 classes of 5 models each.................................... 80
6.27 Examples of structural matching across classes: (a) a man to a bird, (b) a ﬁghterjet to a passenger plane, (c) a dinosaur to a quadruped....... 80
6.28 Similarity matrix of (top) 2D structural matching and (bottom) 2D image matching. The brightness value of each pixel in each matrix has been normalized by the average similarity score of the whole matrix...... 81
6.29 Similarity matrix of (top) 2D structural matching and (bottom) 2D image matching. n : nearest match, : next four best matches (2-5), •: the next four (6-9).................................. 82
B.1 High-level schematic of the three main components of our search engine.. 107 B.2 Dataﬂow overview of the search engine................... 108 B.3 Query processing and matching stage. The path of a 3D sketch query has been highlighted.............................. 119
2.1 Some examples of search engines for combinations of the type of information indexed, and the type of query supported................. 10
2.2 Current 3D model search engines, their model database size, the number of freely downloadable models, and supported query interfaces........ 18
5.1 Seven “view sets” produced from diﬀerent subsets of the total set of 13 views 44
5.2 Comparison of retrieval results with queries comprising only text, only 2D sketches, and both combined........................ 51
7.1 The 81 classes in our test database of 1,000 3D web models, and the hierarchy in which they are organized. The actual classes are printed in boldface.
The right column shows the number of models in each class........ 87
Introduction Search Engines The world-wide web is changing the way we ﬁnd and use information. It provides access to a vast amount of text and image data on every conceivable topic. Unfortunately, the sheer quantity of information can make it diﬃcult to quickly ﬁnd what you are looking for. To aid in this search, many search engines exist that index large portions of the web. They typically provide a search interface based on text keywords: a user enters some descriptive keywords (e.g. “boeing 747”), after which web pages containing these keywords are returned. Examples of popular text-based search engines are Google  and AltaVista .
However, the web does not just contain text pages, but a lot of non-textual data as well, such as images, sound ﬁles, or CAD models. Many so-called specialized search engines targeting these speciﬁc kinds of data have been developed. Perhaps the biggest such search engine is Google Image Search , which indexes hundreds of millions of images. Other examples are FindSounds , a search engine for sound ﬁles, and MeshNose , a search engine for 3D models. Many of these specialized search engines take advantage of the fact that even though the indexed objects are of a non-textual type, often they are annotated with descriptive text. The search engine then simply tries to match the user-entered keywords to this descriptive text.
3D Models One such non-textual data type is the 3D model, the basic building block of many operations in 3D computer graphics applications. 3D models are used in, for example, Computer Aided Design (CAD): a designer uses a 3D modeling tool to create a 3D representation (i.e. a 3D model) of a new product. This model can then for example be visualized in diﬀerent colors and lighting conditions. It can also serve as a blueprint for guiding the subsequent manufacturing process. Because creating such a highquality 3D model takes a lot of time and eﬀort, it would be beneﬁcial to have the option of re-using and possibly adapting existing 3D models. Perhaps someone else created a similar product before, and the designer can start by adapting an existing model instead of having to create one from scratch. Existing 3D models could also be re-used, for example, in the creation of a virtual environment (e.g. for an architectural walkthrough), as characters in a game, or for movie special eﬀects.
The number of existing 3D models is already large, and we expect this number to increase at a growing rate for three reasons. First, high-performance PC graphics hardware has become very aﬀordable, creating an increased demand for 3D models to be used in applications such as games, online stores, scientiﬁc visualizations, and so on. Second, it is becoming easier to create 3D models, using new and improved methods to acquire models from the real world (e.g. using 3D scanners , computer vision ), and new modeling tools (e.g. Maya , which is now free for non-commercial use, Blender , a free modeling system, Teddy , a Java applet for 3D sketching). The improvement in PC hardware performance also enables many more people to use these 3D modeling tools to create 3D models themselves. Third, as is true for all digital data, a lot of these 3D models are available on the web for free download.
A 3D Model Search Engine To improve the accessibility of all these online 3D models, we have created a prototype specialized search engine for 3D models. It supports a text-based query interface and several diﬀerent types of shape-based query interfaces. Figure 1.1 shows a screenshot of the actual search engine web site, with its main components annotated. On the left side of the page the user can enter queries and specify which database is to be searched (both free and commercial databases have been indexed). On the right side search results are shown, as well as links that allow the selection of diﬀerent query interfaces and miscellaneous pages with a feedback form, information about our research, and links to similar projects elsewhere.