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