3D Model Similarity Search

This project is part of the strategic research initiative on Distributed Processing and Delivery of Digital Documents (V3D2)of the German Research Foundation.

Project Group

Project Leaders

Project Staff

Prof. Dr. Daniel A. Keim

Prof. Dr. Dietmar Saupe

Benjamin Bustos

Tobias Schreck

Dr. Dejan Vranic

Introduction

The amount of digital audio-visual information is huge and rapidly increasing. This data is available in digital libraries and information repositories in a number of different formats including pictures, video, audio and also three-dimensional models. 3D objects play an important role in application domains like manufacturing, design, science and entertainment. Efficient and effective methods to manage this data are crucial in making optimal use of it. This project aims at closing a gap which exists on the management of 3D models, considering effective content based model retrieval and efficient indexing and accessing methods.

Similarity Search System

Right now there is no fundamental theory on the optimal description of 3D models that could be used for an automatic retrieval system. Therefore we research a feature vector (FV) approach to capture important characteristics of 3D models and we use different FVs to determine the most similar models to a given query by performing a nearest neighbor (NN-) search. We consider certain properties to be important concerning our feature vector approach. The extraction of FVs should be invariant with respect to translation, rotation, scale, and be robust concerning a model's level-of-detail. This is a requirement in order to abstract from an author's more formal design decisions. Then, we want the FVs to support multiple levels of resolution to be able to dynamically use coarser or finer similarity measures. The system supports a wide range of fundamentally different feature vectors to capture as many model characteristics as possible. At query time, the search system should decide on which combinations of FVs to use, given the query object and available index data. Therefore, we need efficient indexing structures for the typically high-dimensional feature vector data.

For our project a test database of 1800 models was collected and manually classified. To query for similar objects, we first transform the data to be invariant with respect to scale, position and rotation by means of a modified Principal Component Analysis (PCA). Invariance to the level-of-detail is achieved by weighting the edges of the models in proportion to the adjacent areas and splitting larger triangles into smaller ones. After this normalization step, feature vectors are extracted to capture certain aspects of the models. We basically distinguish geometry and image based features. In the geometry class, we can scan the model by intersecting rays from its center of mass with the surface, and take the normalized lengths as FV dimensions. In addition, we can take into account the volume given by polyhedrons which are constituted by adding the center of mass to the models triangles. Furthermore, rasterization of the models into octree structures yields measures for similarity search.
The geometry based ray-scanning approach may be interpreted as sampling a real function defined on the unit sphere. It is possible to get multiresolution representations of these functions by spherical Fourier- or Wavelet transformation, and also use them for similarity search.
On the image based side, we render 2D shapes (parallel projections onto the planes orthogonal to the transformed coordinate system), and take Fourier coefficients from the resulting shilouettes. Those 2D shapes can also be enriched by depth information, resulting in gray-scale depth buffer maps.

Research Issues

Many interesting questions arise in this context, which we plan to study within this project. A deeper understanding of the characteristics of feature vector classes is needed to help determine the most relevant combinations of features for effective retrieval results. The feature vector resolution positively influences effectiveness, but increases retrieval complexity. A query processor should reflect this by dynamically generating execution plans based on available indexing and resolution information, as well as the query profile. In addition to global similarity, partial similarity may also be of concern in some application domains. This is another complex, yet challenging task, where further research is needed.
Concerning usability aspects, we are interested in providing interactive query and visualization techniques, making users aware of query consequences and allowing for input of relevance feedback to refine the search. More objective evaluation of retrieval effectiveness is needed. Therefore we are interested in suitable effectiveness measures based on adapted precision-recall metric.

Talks and Publications

Invited Talks

  • T. Schreck: "Search and Retrieval in 3D Model Databases", Workshop on Industry Challenges in Geometric Modeling and CAD, Darmstadt, Germany, March 10-11, 2005.
  • D. Saupe: "3D Model Retrieval", Technion Israel Institute of Technology, 3/2004 .
  • D. Saupe: "3D Model Retrieval", Tel-Aviv University, Israel, 3/2004.
  • D. Saupe: "Content-based Retrieval: 3D model retrieval", Dagstuhl-Seminar 1/2004.
  • D. Saupe: "Multimedia Retrieval: 3D model retrieval", Dagstuhl-Seminar Perspectives Workshop, 3/2003.

Workshop Talks

  • T. Schreck: "Ähnlichkeitssuche durch Gestaltcharakterisierung auf 3D Datenbanken", DFG Workshop Verallgemeinerte Dokumente und Digitale Bibliotheken, 29.-30. November 2004, HU/Berlin-Adlershof, 2004.
  • T. Schreck: "Methoden zur 3D Ähnlichkeitssuche - Kombination von Feature-Vektoren", DFG Workshop Verallgemeinerte Dokumente und Digitale Bibliotheken, 19.-20. März, Frankfurt/Main, 2003.
  • D. Vranic: "Methoden zur 3D Ähnlichkeitssuche", DFG Workshop Verallgemeinerte Dokumente und Digitale Bibliotheken, 19.-20. März, Frankfurt/Main, 2003.

Journals

  • B. Bustos, D. Keim, D. Saupe, T. Schreck, and A. Tatu: Methods and User Interfaces for Effective Retrieval in 3D Databases (in German). Datenbank-Spektrum - Zeitschrift fuer Datenbank Technologie und Information Retrieval, Dpunkt Verlag, 2006. To appear.
  • B. Bustos, D. Keim, D. Saupe, T. Schreck, D. Vranic: An Experimental Effectiveness Comparison of Methods for 3D Similarity Search, International Journal on Digital Libraries 6(1):39-54, Special Issue on Multimedia Contents and Management in Digital Libraries, Springer, 2006.
  • B. Bustos, D. Keim, D. Saupe, T. Schreck, D. Vranic: Feature-based Similarity Search in 3D Object Databases, ACM Computing Surveys (CSUR) 37(4):345-387, Association For Computing Machinery, 2005. [ ]
  • M. Heczko, D. Keim, D. Saupe, and D. V. Vranic. Methods for Similarity Search of 3D Objects (in German). In: Datenbank-Spektrum Zeitschrift für Datenbanktechnologie, 2(2):54-63, dpunkt.verlag, 2002. [ ] [ps.gz]

Conferences Publications

  • T. Schreck, D. Keim, C. Panse: Visual Feature Space Analysis for Unsupervised Effectiveness Estimation and Feature Engineering, IEEE International Conference on Multimedia and Expo (ICME'2006). Toronto, Canada, July 9-12, 2006. [ ]
  • B. Bustos, D. Keim, T. Schreck. A pivot-based index structure for combination of feature vectors. Proc. 20th Annual ACM Symposium on Applied Computing, Multimedia & Visualization Track (SAC-MMV'05) [ ]
  • B. Bustos, D. A. Keim, C. Panse, T. Schreck: 2D Maps for Visual Analysis and Retrieval in Large Multi-Feature 3D Model Databases, Poster Paper, IEEE Visualization Conference (VIS'2004). October 10-15, Austin, Texas, USA, 2004. [ ]
  • B. Bustos, D. A. Keim, D. Saupe, T. Schreck, D. Vranic: Automatic Selection and Combination of Descriptors for Effective 3D Similarity Search, IEEE International Workshop on Multimedia Content-based Analysis and Retrieval (MCBAR'2004). Miami, Florida, USA, December 15, 2004. [ ]
  • B. Bustos, D. Keim, D. Saupe, T. Schreck and D.Vranic. An Experimental Comparison of Feature-Based 3D Retrieval Methods, Second International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'04). Thessaloniki, Greece, September 6-9, 2004. [ ]
  • B. Bustos, D. Keim, D. Saupe, T. Schreck and D.Vranic. Using Entropy Impurity for Improved 3D Object Similarity Search. In: Proc. IEEE International Conference on Multimedia and Expo (ICME'04), June 27-30, Taipei/Taiwan. [ ]
  • D. V. Vranic. An Improvement of Rotation Invariant 3D Shape Descriptor Based on Functions on Concentric Spheres. In: Proceedings of the IEEE International Conference on Image Processing (ICIP 2003), Volume III, ISBN 0-7803-7751-6, Barcelona, Spain, pp. 757-760, September 2003. [ ]
  • D. V. Vranic and D. Saupe. Description of 3D-Shape Using a Complex Function on the Sphere. In: Proceedings of the IEEE International Conference on Multimedia and Expo (ICME 2002), Lausanne, Switzerland, pp. 177-180, August 2002. [ ] [ps.gz]
  • D. V. Vranic and D. Saupe. 3D Shape Descriptor Based on 3D Fourier Transform. In: Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services (ECMCS 2001) (editor K. Fazekas), Budapest, Hungary, pp. 271-274, September 2001. [ ] [ps.gz]
  • D. Saupe and D. V. Vranic. 3D Model Retrieval With Spherical Harmonics and Moments. In: Proceedings of the DAGM 2001 (editors B. Radig and S. Florczyk), Munich, Germany, pp. 392-397, September 2001. [ ] [ps.gz]
  • D. V. Vranic, D. Saupe, and J. Richter. Tools for 3D-object Retrieval: Karhunen-Loeve Transform and Spherical Harmonics. In: Proceedings of the IEEE 2001 Workshop Multimedia Signal Processing (editors J.-L. Dugelay and K. Rose), Cannes, France, pp. 293-298, October 2001. [ ] [ps.gz]
  • D. V. Vranic and D. Saupe. A Feature Vector Approach for Retrieval of 3D Objects in the Context of MPEG-7. In: Proceedings of the International Conference on Augmented, Virtual Environments and Three-Dimensional Imaging (ICAV3D 2001) (editors V. Giagourta and M.G. Strintzis), Mykonos, Greece, pp. 37-40, May 2001. [ ] [ps.gz]
  • M. Heczko, D. Keim, D. Saupe, and D. V. Vranic. A Method for Similarity Search of 3D Objects (in German). In: Proceedings of the BTW 2001 (editors A. Heuer, F. Leymann, D. Priebe), Oldenburg, Germany, Informatik Aktuell, Springer Verlag, ISBN=3-540-41707-9, pp. 384-401, March 2001. [ ] [ps.gz]
  • D. V. Vranic. An improvement of Ray-Based Shape Descriptor. In: Proceedings of the 8. Leipziger Informatik-Tage (LIT'2M) (editors W.S. Wittig and S. Paul), HTWK Leipzig, Germany, pp. 55-58, September 2000.
  • D. V. Vranic and D. Saupe. 3D Model Retrieval. In: Proceedings of the Spring Conference on Computer Graphics and its Applications (SCCG2000) (editor B. Falcidieno), Budmerice, Slovakia, pp. 89-93, May 2000. [ ] [ps.gz]

Master Theses

  • J. Richter. Image Based 3D Shape Recognition (in German). Master Thesis, University Leipzig, 2000.