skip to main content
article

A search engine for 3D models

Published: 01 January 2003 Publication History

Abstract

As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).

References

[1]
Aherne, F., Thacker, N., and Rockett, P. 1997. Optimal pairwise geometric histograms. In Proceedings of BMVC (Essex, UK), 480--490.]]
[2]
Alt, H. and Guibas, L. J. 1996. Discrete geometric shapes: Matching, interpolation, and approximation: A survey. Tech. Rep. B 96-11, EVL-1996-142, Institute of Computer Science, Freie Universität Berlin.]]
[3]
Amit, Y., Grenander, U., and Piccioni, M. 1991. Structural image restoration through deformable templates. J. Am. Stat. Assn. 86, 440, 376--387.]]
[4]
Ankerst, M., Kastenmüller, G., Kriegel, H.-P., and Seidl, T. 1999a. 3D shape histograms for similarity search and classification in spatial databases. In Proceedings of SSD.]]
[5]
Ankerst, M., Kastenmüller, G., Kriegel, H.-P., and Seidl, T. 1999b. Nearest neighbor classification in 3D protein databases. In Proceedings of ISMB.]]
[6]
Arbter, K., Snyder, W. E., Burkhardt, H., and Hirzinger, G. 1990. Application of affine-invariant Fourier descriptors to recognition of 3-D objects. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7 (July), 640--647.]]
[7]
Arkin, E. M., Chew, L. P., Huttenlocher, D. P., Kedem, K., and Mitchell, J. S. 1991. An efficiently computable metric for comparing polygonal shapes. IEEE Trans. Pattern Anal. Mach. Intell. 13, 3 (March), 209--216.]]
[8]
Arman, F. and Aggarwal, J. 1993. Model-based object recognition in dense-range images---A review. ACM Comput. Surv. 25, 1, 5--43.]]
[9]
Ashbrook, A. P., Thacker, N. A., Rockett, P. I., and Brown, C. I. 1995. Robust recognition of scaled shapes using pairwise geometric histograms. In Proceedings of BMVC (Birmingham, UK), 503--512.]]
[10]
Bardinet, E., Vidal, S. F., Arroyo, S. D., Malandain, G., and de la Blanca Capilla, N. P. 2000. Structural object matching. Tech. Rep. DECSAI-000303, Dept. of Computer Science and AI, University of Granada, Spain, February.]]
[11]
Barequet, G. and Kumar, S. 1997. Repairing CAD models. In IEEE Visualization '97, 363--370.]]
[12]
Barrow, H., Tenenbaum, J., Bolles, R., and Wolf, H. 1977. Parametric correspondence and chamfer matching: Two new techniques for image matching. In Proceedings of the International Joint Conference on Artificial Intelligence, 659--663.]]
[13]
Belongie, S., Malik, J., and Puzicha, J. 2001. Matching shapes. ICCV.]]
[14]
Berchtold, S. and Kriegel, H.-P. 1997. S3: Similarity search in CAD database systems. In Proceedings of SIGMOD, J. Peckham, Ed. ACM, New York, 564--567.]]
[15]
Besl, P. 1995. Triangles as a primary representation. Object Recognition in Computer Vision. Lecture Notes in Computer Science, vol. 994, Springer-Verlag, New York, 191--206.]]
[16]
Besl, P. and McKay, N. 1992. A method for registration of 3D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14, 2, 239--256.]]
[17]
Besl, P. J. and Jain, R. C. 1985. Three-dimensional object recognition. ACM Comput. Surv. 17, 1 (March), 75--145.]]
[18]
Bhanu, B. 1987. CAD-based robot vision. Computer, 20.]]
[19]
Binford, T. 1971. Visual perception by computer. In IEEE Conference on Systems Science and Cybernetics.]]
[20]
Bloomenthal, J. and Lim, C. 1999. Skeletal methods of shape manipulation. In Proceedings of Shape Modeling and Applications. IEEE, 44--47.]]
[21]
Blum, H. 1967. A transformation for extracting new descriptors of shape. In Proceedings of Models for the Perception of Speech and Visual Form, W. Wathen-Dunn, Ed. MIT Press, Cambridge, Mass., 362--380.]]
[22]
Brin, S. and Page, L. 1998. The anatomy of a large-scale hypertextual Web search engine. Comput. Netw. ISDN Syst. 30, 1--7, 107--117.]]
[23]
Castelli, V. and Bergman, L. 2001. Image Databases: Search and Retrieval of Digital Imagery. Wiley, New York.]]
[24]
Chen, Y. and Medioni, G. 1992. Object modeling by registration of multiple range images. Image Vis. Comput. 10, 3, 145--155.]]
[25]
Curless, B. and Levoy, M. 1996. A volumetric method for building complex models from range images. In Proceedings of SIGGRAPH 96 (New Orleans), Computer Graphics Proceedings, Annual Conference Series, ACM, New York.]]
[26]
Debevec, P., Taylor, C. J., and Malik, J. 1996. Modeling and rendering architecture from photographs: A hybrid geometry- and image-based approach. In Proceedings of SIGGRAPH 1996. Computer Graphics Proceedings, Annual Conference Series. ACM, New York, 11--20.]]
[27]
De Espona Infographica. 2001. 3D model collection. Available at http://www.deespona.com.]]
[28]
Delingette, H., Hebert, M., and Ikeuchi, K. 1992. Shape representation and image segmentation using deformable surfaces. Image Vis. Comput. 10, 3 (April), 132--144.]]
[29]
Delingette, H., Hebert, M., and Ikeuchi, K. 1993. A spherical representation for the recognition of curved objects. In Proceedings of ICCV, 103--112.]]
[30]
Duda, R., Hart, P., and Stork, D. 2001. Pattern Classification, second ed. J. Wiley, New York.]]
[31]
Elad, M., Tal, A., and Ar, S. 2001. Content based retrieval of VRML objects---An iterative and interactive approach. In EG Multimedia, 97--108.]]
[32]
Evans, A., Thacker, N., and Mayhew, J. 1992. Pairwise representation of shape. In Proceedings of the Eleventh ICPR, vol. 1 (The Hague, the Netherlands), 133--136.]]
[33]
Flickner, M., Sawhney, H., Niblack, W., Ashley, J., and Huang, Q. 1995. Query by image and video content: The QBIC system. IEEE Computer 28, 9, 23--32.]]
[34]
Foote, J. 1999. An overview of audio information retrieval. ACM Multimedia Syst. 7, 2--10.]]
[35]
Gain, J. and Scott, J. 1999. Fast polygon mesh querying by example. SIGGRAPH Tech. Sketches, 241.]]
[36]
Grimson, W. 1990. Object Recognition by Computer: The Role of Geometric Constraints. MIT Press, Cambridge, Mass.]]
[37]
Gueziec, A., Taubin, G., Lazarus, F., and Horn, W. 1998. Converting sets of polygons to manifold surfaces by cutting and stitching. IEEE Visualization '98, 383--390.]]
[38]
Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, ACM, New York, 203--212.]]
[39]
Horn, B. 1984. Extended Gaussian images. Proc. IEEE 72, 12 (Dec.), 1671--1686.]]
[40]
Huttenlocher, D., Klanderman, D., and Rucklige, A. 1993. Comparing images using the Hausdorff distance. IEEE Trans. Pattern Anal. and Mach. Intell. 15, 9 (Sept.), 850--863.]]
[41]
Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: A sketching interface for 3D freeform design. In Proceedings of SIGGRAPH 1999, Computer Graphics Proceedings, Annual Conference Series, ACM, Los Angeles, 409--416.]]
[42]
Ikeuchi, K. and Flynn, P. 1995. Recent progress in CAD-based vision. Comput. Vis. Image Understand 61, 3.]]
[43]
Indyk, P. and Motwani, R. 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of 30th STOC.]]
[44]
Jacobs, C. E., Finkelstein, A., and Salesin, D. H. 1995. Fast multiresolution image querying. Proceedings of SIGGRAPH 95, 277--286.]]
[45]
Jain, A., Zhong, Y., and Lakshmanan, S. 1996. Object matching using deformable templates. IEEE Trans. Pattern Anal. Mach. Intell. 18, 3, 267--278.]]
[46]
Johnson, A. E. and Hebert, M. 1999. Using spin-images for efficient multiple model recognition in cluttered 3-D scenes. IEEE PAMI 21, 5, 433--449.]]
[47]
Kashyap, R. and Chellappa, R. 1981. Stochastic models for closed boundary analysis: Representation and reconstruction. IEEE Trans. Inf. Theor. 27, 627--637.]]
[48]
Kastenmüller, G., Kriegel, H.-P., and Seidl, T. 1998. Similarity search in 3D protein databases. In Proceedings of GCB.]]
[49]
Lamdam, Y. and Wolfson, H. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Proceedings of ICCV.]]
[50]
Lamdan, Y., Schwartz, J., and Wolfson, H. 1990. Affine invariant model-based object recognition. IEEE Trans. Robotics Autom. 6, 578--589.]]
[51]
Lesk, M. 1997. Practical Digital Libraries. Morgan Kaufmann, San Francisco.]]
[52]
Lin, Y., Dou, J., and Wang, H. 1992. Contour shape description based on an arch height function. Pattern Recogn. 25, 17--23.]]
[53]
Loncaric, S. 1998. A survey of shape analysis techniques. Pattern Recogn. 31, 8, 983--1001.]]
[54]
Lowe, D. 1985. Perceptual Organization and Visual Recognition. Kluwer Academic, Hingham, Mass.]]
[55]
McCallum, A. 1996. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. Available at http://www.cs.cmu.edu/∼mccallum/bow.]]
[56]
MeshNose. 2001. Available at http://www.deepfx.com/meshnose.]]
[57]
Miller, G. A. 1995. WordNet: A lexical database for English. Commun. ACM 38, 11, 39--41.]]
[58]
Mori, G., Belongie, S., and Malik, J. 2001. Shape contexts enable efficient retrieval of similar shapes. Proc. CVPR.]]
[59]
Murali, T. and Funkhouser, T. 1997. Consistent solid and boundary representations from arbitrary polygonal data. In SIGGRAPH Symposium on Interactive 3D Graphics (Providence), 155--162.]]
[60]
Murase, H. and Nayar, S. 1995. Visual learning and recognition of 3D objects from appearance. Int. J. Comput. Vis. 14, 5--24.]]
[61]
Ogle, V. and Stonebraker, M. 1995. Chabot: Retrieval from a relational database of images. IEEE Computer 28, 9, 40--48.]]
[62]
Okino. 2001. Polytrans. Available at http://www.okino.com/conv/conv.htm.]]
[63]
Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D. 2001. Matching 3D models with shape distributions. Shape Model. Int., 154--166.]]
[64]
Palmer, S., Rosch, E., and Chase, P. 1981. Canonical perspective and the perception of objects. Attention Perf. IX, 135--151.]]
[65]
Paquet, E. and Rioux, M. 2000. Nefertiti: A tool for 3-D shape databases management. SAE Trans. J. Aerospace 108, 387--393.]]
[66]
Pentland, A. and Sclaroff, S. 1991. Closed-form solutions for physically based shape modeling and recognition. IEEE Trans. Pattern Anal. and Mach. Intell. 13, 7, 715--729.]]
[67]
Pope, A. R. 1994. Model-based object recognition: A survey of recent research. Tech. Rep. TR-94-04, University of British Columbia. January.]]
[68]
Porter, M. 1980. An algorithm for suffix stripping. Program 14, 3, 130--137.]]
[69]
Prokop, R. J. and Reeves, A. P. 1992. A survey of moment-based techniques for unoccluded object representation and recognition. CVGIP: Graph. Models Image Processs. 54, 5, 438--460.]]
[70]
Regli, W. 2001. National design repository. Geometric and Intelligent Computing Laboratory, Drexel University, Available at http://repos.mcs.drexel.edu.]]
[71]
Reyna, R. D. 1996. How to Draw What You See. Watson-Guptil, New York.]]
[72]
Rocchio, J. 1971. The SMART Retrieval System: Experiments in Automatic Document Processing. Prentice-Hall, Englewood Cliffs, N.J., 313--323.]]
[73]
Rowe, J., Razdan, A., Collins, D., and Pachanathan, S. 2001. A 3D digital library system: Capture, analysis, query, and display. Proceedings of the Fourth International Conference on Digital Libraries (ICADL).]]
[74]
Rubner, Y., Tomasi, C., and Guibas, L. 1998. A metric for distributions with applications to image databases. In Proceedings of the Sixth ICCV (Bombay, India), 59--66.]]
[75]
Salton, G. 1971. The SMART Retrieval System. Prentice-Hall, Englewood Cliffs, N.J.]]
[76]
Saupe, D. and Vrani, D. V. 2001. 3D model retrieval with spherical harmonics and moments. DAGM 2001, 392--397.]]
[77]
Schurmans, U., Razdan, A., Simon, A., McCartney, P., Marzke, M., Alfen, D. V., Jones, G., Rowe, J., Farin, G., Collins, D., Zhu, M., Liu, D., and Bae, M. 2001. Advances in geometric modeling and feature extraction on pots, rocks and bones for representation and query via the Internet. Comput. Appl. Archaeology (CAA).]]
[78]
Sclaroff, S. and Pentland, A. P. 1995. Modal matching for correspondence and recognition. IEEE PAMI 17, 6 (June), 545--561.]]
[79]
Shokoufandeh, A., Dickinson, S. J., Siddiqi, K., and Zucker, S. W. 1999. Indexing using a spectral encoding of topological structure. In Proceedings of Computer Vision and Pattern Recognition. vol. 2, IEEE, Los Alamitos, Calif., 491--497.]]
[80]
Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., and Zucker, S. W. 1998. Shock graphs and shape matching. Comput. Vis., 222--229.]]
[81]
Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., and Zucker, S. W. 1999. Shock graphs and shape matching. Int. J. Comput. Vis. 35, 1, 13--31.]]
[82]
Solina, F. and Bajcsy, R. 1990. Recovery of parametric models from range images: The case for superquadrics with global deformations. IEEE Trans. Pattern Anal. Mach. Intell. 12, 2 (Feb.), 131-- 147.]]
[83]
SpharmonicKit 2.5. 1998. Fast spherical transforms: Spharmonickit. Available at http://www.cs.dartmouth.edu/∼geelong/sphere/.]]
[84]
Storti, D. W., Turkiyyah, G., Ganter, M. A., Lim, C. T., and Stal, D. M. 1997. Skeleton-based modeling operations on solids. In Proceedings of Solid Modeling. ACM, New York, 141--154.]]
[85]
Suzuki, M. T. 2001. A Web-based retrieval system for 3D polygonal models. Joint Ninth IFSA World Congress and Twentieth NAFIPS International Conference (IFSA/NAFIPS2001), 2271--2276.]]
[86]
Tappert, C. 1982. Cursive script recognition by elastic matching. IBM J. Res. Dev. 26, 6, 765--771.]]
[87]
Taubin, G. and Cooper, D. 1992. Geometric Invariance in Computer Vision. MIT Press, Cambridge, Mass.]]
[88]
Terzopoulos, D. and Metaxas, D. 1991. Dynamic 3D models with local and global deformations: Deformable superquadrics. IEEE Trans. Pattern Anal. Mach. Intell. 13, 7, 703--714.]]
[89]
Tsai, W. and Yu, S. 1985. Attributive string matching with merging for shape recognition. IEEE Trans. Pattern Anal. Mach. Intell. 7, 453--462.]]
[90]
Turk, G. and Levoy, M. 1994. Zippered polygon meshes from range images. In Proceedings of SIGGRAPH 94, Computer Graphics Proceedings, Annual Conference Series, ACM, New York, 311--318.]]
[91]
Uras, C. and Verri, A. 1994. On the recognition of the alphabet of the sign language through size functions. In Proceedings of IAPR (Jerusalem), 334--338.]]
[92]
Veltkamp, R. C. 2001. Shape matching: Similarity measures and algorithms. In Shape Modelling International (Genova), 188--197.]]
[93]
Veltkamp, R. C., Burkhardt, H., and Kriegel, H.-P. 2001. State-of-the-Art in Content-Based Image and Video Retrieval. Kluwer Academic, Hingham, Mass.]]
[94]
Viewpoint Corporation. 2001. Available at http://www.viewpoint.com.]]
[95]
Vranic, D. V., Saupe, D., and Richter, J. 2001. Tools for 3D-object retrieval: Karhunen--Loeve transform and spherical harmonics. In IEEE 2001 Workshop on Multimedia Signal Processing, 293--298.]]
[96]
Witkin, A., Fleischer, K., and Barr, A. 1987. Energy constraints on parameterized models. In Proceedings of SIGGRAPH 1987, Computer Graphics Proceedings, Annual Conference Series, ACM, New York, 225--232.]]
[97]
Wu, K. and Levine, M. 1994. Recovering parametric geons from multiview range data. In Proceeding of CVPR, 159--166.]]
[98]
Young, I., Walker, J., and Bowie, J. 1974. An analysis technique for biological shape. Comput. Graph. Image Process. 25, 357--370.]]
[99]
Zahn, C. and Roskies, R. 1972. Fourier descriptors for plane closed curves. IEEE Trans. Comput. 21, 269--281.]]
[100]
Zeleznik, R. C., Herndon, K. P., and Hughes, J. F. 1996. Sketch: An interface for sketching 3D scenes. In Proceedings of SIGGRAPH 96. Computer Graphics Proceedings, Annual Conference Series, ACM, New York, 163--170.]]
[101]
Zhang, D. and Hebert, M. 1999. Harmonic maps and their applications in surface matching. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR '99).]]

Cited By

View all
  • (2024)Application of computer vision techniques for 3D matching and retrieval of archaeological objectsF1000Research10.12688/f1000research.127095.212(182)Online publication date: 25-Mar-2024
  • (2024)Auto-summarization of Human Volumetric VideosProceedings of the 2024 ACM International Conference on Interactive Media Experiences Workshops10.1145/3672406.3672416(65-70)Online publication date: 12-Jun-2024
  • (2024)SketchDream: Sketch-based Text-To-3D Generation and EditingACM Transactions on Graphics10.1145/365812043:4(1-13)Online publication date: 19-Jul-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 22, Issue 1
January 2003
129 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/588272
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2003
Published in TOG Volume 22, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Search engine
  2. shape matching
  3. shape representation
  4. shape retrieval

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)151
  • Downloads (Last 6 weeks)25
Reflects downloads up to 15 Sep 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Application of computer vision techniques for 3D matching and retrieval of archaeological objectsF1000Research10.12688/f1000research.127095.212(182)Online publication date: 25-Mar-2024
  • (2024)Auto-summarization of Human Volumetric VideosProceedings of the 2024 ACM International Conference on Interactive Media Experiences Workshops10.1145/3672406.3672416(65-70)Online publication date: 12-Jun-2024
  • (2024)SketchDream: Sketch-based Text-To-3D Generation and EditingACM Transactions on Graphics10.1145/365812043:4(1-13)Online publication date: 19-Jul-2024
  • (2024)DualShape: Sketch-Based 3D Shape Design With Part Generation and RetrievalIEEE Access10.1109/ACCESS.2024.336165912(18888-18900)Online publication date: 2024
  • (2024)SketchCleanGAN: A generative network to enhance and correct query sketches for improving 3D CAD model retrieval systemsComputers & Graphics10.1016/j.cag.2024.104000123(104000)Online publication date: Oct-2024
  • (2023)A system for finding identical geometries when building 3-D modelsReporter of the Priazovskyi State Technical University. Section: Technical sciencesВестник Приазовского государственного технического университета. Серия: Технические наукиВісник Приазовського Державного Технічного Університету. Серія: Технічні науки10.31498/2225-6733.47.2023.299984(82-88)Online publication date: 28-Dec-2023
  • (2023)Application of computer vision techniques for 3D matching and retrieval of archaeological objectsF1000Research10.12688/f1000research.127095.112(182)Online publication date: 16-Feb-2023
  • (2023)Modeling by ExampleSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596735(203-214)Online publication date: 1-Aug-2023
  • (2023)Tesseract: Querying Spatial Design Recordings by Manipulating Worlds in MiniatureProceedings of the 2023 CHI Conference on Human Factors in Computing Systems10.1145/3544548.3580876(1-16)Online publication date: 19-Apr-2023
  • (2023)What’s in a Name? Evaluating Assembly-Part Semantic Knowledge in Language Models Through User-Provided Names in Computer Aided Design FilesJournal of Computing and Information Science in Engineering10.1115/1.406245424:1Online publication date: 23-Jun-2023
  • Show More Cited By

View Options

Get Access

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media