Department of Computer & Information Science University of Konstanz
Working Group Databases, Data Mining and Visualization Research
Working Group Multimedia Signal Processing

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




3D Model Similarity Search


CCCC System

3D retrieval system (Web-based version).


3D retrieval system (BApplication version)

3D retrieval system (Application version).


SOM

Self-organizing map of our 3D database.

Project Group

Project Leaders

Prof. Dr. Daniel A. Keim
Prof. Dr. Dietmar Saupe

Project Staff

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.

Similarity Search System

Main idea behind the similarity search system.


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 metrics.

Below we illustrate some FVs which are used in our similarity search system. The first two origin from the geometry based side, the second two from the image based side.

Transformation

Ray-based scanning after principal axes transformation.


Harmonics

Multiresolution spherical harmonics representation.


Silhouettes

Flat 2D silhouettes with Fourier coefficients.


Depth buffers

Depth buffer maps from 6 directions.


Online Ressources

The CCCC web prototype.

Talks and Publications

Invited Talks Workshop Talks Journals Conferences Publications Master Theses

Last update: 05/03/2006, Tobias Schreck