FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |   ...   | 17 |

«A 3D Model Search Engine Patrick Min A Dissertation Presented to the Faculty of Princeton University in Candidacy for the Degree of Doctor of ...»

-- [ Page 1 ] --

A 3D Model Search Engine

Patrick Min

A Dissertation

Presented to the Faculty

of Princeton University

in Candidacy for the Degree

of Doctor of Philosophy

Recommended for Acceptance

By the Department of

Computer Science

January 2004

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 effort involved in creating a highquality 3D model, considerable resources could be saved if these models could be reused. However, finding 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 insufficient text annotation of 3D models on the web.

Furthermore, classification 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 effective.

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 classifications 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 first 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 staff 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 finally, to my dear Katerina, for being part of my life.

–  –  –

4.1 Example objects created using (a) SKETCH [113], (b) a “suggestive interface” [45], (c) Teddy [46], (d) variational implicit surfaces [52]....... 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 different 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 five 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 five results for a set of ellipses representing a floorlamp, with the EDT alignment weight set to (a) 0.25, (b) 1.0, (c) 3.0....... 76

6.23 The top five 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 five 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 different 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 fighterjet 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 Dataflow 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 different 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 find 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 difficult to quickly find 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 [17] and AltaVista [3].

However, the web does not just contain text pages, but a lot of non-textual data as well, such as images, sound files, or CAD models. Many so-called specialized search engines targeting these specific kinds of data have been developed. Perhaps the biggest such search engine is Google Image Search [37], which indexes hundreds of millions of images. Other examples are FindSounds [34], a search engine for sound files, and MeshNose [67], 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 different 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 effort, it would be beneficial 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 effects.

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 affordable, creating an increased demand for 3D models to be used in applications such as games, online stores, scientific 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 [24], computer vision [35]), and new modeling tools (e.g. Maya [2], which is now free for non-commercial use, Blender [13], a free modeling system, Teddy [45], 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 different 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 different query interfaces and miscellaneous pages with a feedback form, information about our research, and links to similar projects elsewhere.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 17 |

Similar works:

«USABLE AUTHENTICATION AND CLICK-BASED GRAPHICAL PASSWORDS by Sonia Chiasson A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY School of Computer Science at CARLETON UNIVERSITY Ottawa, Ontario December 2008 c Copyright by Sonia Chiasson, 2008 Table of Contents List of Tables vii List of Figures ix Abstract xi Acknowledgements xii Chapter 1 Introduction 1 1.1 Context...................»

«Loughborough University Institutional Repository Richard Hamilton a multi-elusive artist of the modern world? This item was submitted to Loughborough University's Institutional Repository by the/an author.Additional Information: • A Master's Thesis. Submitted in partial fullment of the requirements for the award of Master of Philosophy of Loughborough University. Volume 1 is available on open access and Volume 2 is closed access for copyright reasons. https://dspace.lboro.ac.uk/2134/8542...»

«Fugitive Pleasure and the Meaningful Life: Nietzsche on Nihilism and Higher Values Paul Katsafanas Forthcoming in Journal of the American Philosophical Association Penultimate draft In an early text, Nietzsche tells us that philosophers have a distinctive and undeniably exalted role: their “proper task” is “to be lawgivers as to the measure, stamp and weight of things” (UM III.3).1 Not particular things, though: Nietzsche does not imagine philosophers assessing the value of apples and...»

«UNIVERSITY OF CALIFORNIA, SAN DIEGO Gravity changes associated with underground injection of CO2 at the Sleipner storage reservoir in the North Sea, and other marine geodetic studies. A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy in Earth Sciences By Scott L. Nooner Committee in charge: Mark A. Zumberge, Chair Donna K. Blackman Ahmed-Waeil Elgamal Robert L. Parker Glenn S. Sasagawa Fred N. Spiess 2005 Copyright Scott L. Nooner, 2005 All...»

«The Dynamics of the Acetylcholine Receptor and the Receptor-Associated Rapsyn Scaffolding Protein Studied In Vitro and In Vivo by Emile G. Bruneau A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Neuroscience) in The University of Michigan 2008 Doctoral Committee: Professor Mohammed Akaaboune, Chair Professor Daniel J. Goldman Professor Richard I. Hume Professor John Y. Kuwada Assistant Professor Jose A. Esteban © Emile G. Bruneau 2008...»

«Where Physics and Metaphysics Meld. By Sarukkai R. Narayanan Ph.D. (Nanu) July 30, 2013 © Nanu Narayanan, 2011 Introduction. sits Hinduism; (continuation of the title). For most, the foregoing title will be baffling. This is because Hinduism is viewed in the context in which other religions are defined. It is religion, philosophy and spirituality all rolled into one and its underpinnings reflect modern scientific thought. There is none other like it! As one reads on, one will have a better...»

«APRES MOI LE DELUGE: INDIVIDUALS, INCENTIVES, AND CONFLICT TERMINATION A Dissertation submitted to the Faculty of the Graduate School of Arts and Sciences of Georgetown University in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Government By John Furman Daniel, III, B.A. Washington, D.C. August 31, 2010 Copyright 2010 by John Furman Daniel, III All Rights Reserved ii APRES MOI LE DELUGE: INDIVIDUALS, INCENTIVES, AND CONFLICT TERMINATION John Furman Daniel,...»

«Partial melting and melt segregation within the contact aureole of the Sudbury Igneous Complex (Ontario, Canada) and their significance in hydrothermal Cu-Ni-PGE mineralization of the footwall ATTILA PÉNTEK M.Sc. Geology Dissertation submitted to the Ph.D. program for Geology and Geophysics at the Ph.D. school of Earth Sciences, Eötvös Loránd University, Budapest in partial fulfilment of the requirements for the degree of DOCTOR OF PHILOSOPHY Supervisors: FERENC MOLNÁR, Ph.D. associate...»


«THESES SIS/LIBRARY TELEPHONE: +61 2 6125 4631 R.G. MENZIES LIBRARY BUILDING NO:2 FACSIMILE: +61 2 6125 4063 THE AUSTRALIAN NATIONAL UNIVERSITY EMAIL: library.theses@anu.edu.au CANBERRA ACT 0200 AUSTRALIA USE OF THESES This copy is supplied for purposes of private study and research only. Passages from the thesis may not be copied or closely paraphrased without the written consent of the author. Early Daoist Biography: A Study of Shenxian zhuan Benjamin David Cooper Penny Volume One A thesis...»


«Magid, Michael (2011) A validation and application of the L2 motivational self system among Chinese learners of English. PhD thesis, University of Nottingham.Access from the University of Nottingham repository: http://eprints.nottingham.ac.uk/11971/1/Magid_Thesis.pdf Copyright and reuse: The Nottingham ePrints service makes this work by researchers of the University of Nottingham available open access under the following conditions. This article is made available under the University of...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.