Back to Publications

Author(s) Vranic, D.
Title 3D model retrieval
Abstract The topic of the thesis is content-based retrieval of 3D-models by shape-similarity. In our 3D model retrieval system a model, a polygonal mesh, serves as a query and similar objects are retrieved from a collection of 3D-objects. Algorithms proceed rst by a normalization step in which models are transformed into a canonical coordinate frame. Second, feature vectors (descriptors) are extracted and compared with those derived from normalized models in the search space. Using a metric in the feature vector space nearest neighbors are computed and ranked. Objects thus retrieved are displayed for inspection, selection, and processing. Objects represented as polygonal meshes are given in arbitrary orientation, scale, and position in the 3D-space. If the invariance of descriptor with respect to similarity transforms is not provided by the representation of a feature, pose estimation (normalization) is necessary as a step preceding the feature extraction. The pose normalization procedure is a transformation of a 3D-mesh model into a canonical coordinate frame by translating, rotating, scaling, and re ecting ( ipping) the original set of vertices. We regard a triangle mesh model as a union of triangles, whence the point set of the model consists of in nitely many points. In contrast to pose normalization techniques based on sums over weighted vertices, we work with sums of integrals over triangles which makes our approach more complete taking into account all points of the model with equal weight. The main objective of this thesis is construction, analysis, and testing of new techniques for describing 3D-shape of polygonal mesh models. Since a solid formal framework that could be used for de ning optimal 3D-shape descriptors does not exist, we develop a variety of descriptors capturing di erent features of 3D-objects and using di erent representation methods. We consider a variety of features for characterizing 3D-shape such as extents of a model in certain directions, contours of 2D projections of a model, depth bu er images of a model, arti cially de ned volumes associated to triangles of a mesh, voxel grids attributed by fractions of the total surface area of a mesh, rendered perspective projections of a model on an enclosing sphere, and layered depth spheres. The used representation techniques include the 1D, 2D, and 3D discrete Fourier transforms, the Fourier transform on a sphere (spherical harmonics), and moments for representing the extent function. We also introduce two approaches for merging appropriate feature vectors, by de ning a complex function on a sphere, and by crossbreeding (hybrid descriptors). We present a variety of original feature extraction algorithms and give complete speci cations for forming feature vector components for each of presented approaches. A Webbased 3D model retrieval system is implemented and serves as a proof-of-concept. We compare two techniques for achieving invariance of descriptors with respect to rotation of the polygonal mesh, the Principal Component Analysis (PCA) vs. a property of spherical harmonics. Several tests show that the rst approach (PCA) is better method for attaining rotation invariance of descriptors. The retrieval performance of our feature vectors is carefully studied and compared to e ectiveness of techniques proposed by other authors. We compare 12 different types of 3D-descriptors de ned by ourselves to 7 types of descriptors de ned by other authors using six ground truth classi cations of 3D-models. The results unambiguously show that our best descriptor, a hybrid feature vector, outperforms the state-of-the-art.
Download Vranic04.pdf