| TR#: | PHD-2007-07 |
| Class: | PHD |
| Title: | Numerical geometry of non-rigid objects: embedding problems |
| Authors: | Alexander Bronstein |
| Supervisors: | Prof. Ron Kimmel |
| PHD-2007-07.pdf | |
| Abstract: | Non-rigid shapes appear at all scales in nature -- from our body,
its organs and tissues, to tiny bacteria and microscopic protein
molecules. Being so ubiquitous, such shapes are often encountered in
pattern recognition and computer vision applications. The main
challenge appears to be the richness and the amount of degrees of
freedom of the class of possible non-rigid deformations.
Among the variety of non-rigid deformations, of particular interest
are near-isometric ones, which approximately preserve intrinsic
metric properties of the shape. Near isometries accurately model
many deformations appearing in nature, such as expressions of the
human face or postures of our body.
The purpose of this thesis is to provide both theoretical and
practical tools for dealing with non-rigid near-isometric objects.
This thesis comprises four parts. The focus of the first two parts
can be roughly associated with two principal problems in non-rigid
geometry: analysis, consisting of finding an isometry-invariant
measure of similarity between two objects, and synthesis consisting
of finding a correspondence between two shapes and creating new
shapes from the existing ones. We show that a common framework based
on minimum distortion embedding serves both problems. We introduce
generalized multidimensional scaling (GMDS), a numerical tool which
extends the family of multidimensional scaling (MDS) algorithms and
allows embedding metric structures into arbitrary two-dimensional
surfaces.
As the GMDS algorithm assumes the knowledge of pair-wise geodesic distances on the surfaces, an efficient numerical procedure for geodesic distance approximation is one of the key components of the method. The third part of this thesis is therefore devoted to computation of distance maps on parametric surfaces. We present a parallel modification of the fast marching algorithm, outperforming state-of-the-art techniques by up to two orders of magnitude on standard hardware. In the fourth part, we extend the fast marching method to three-dimensional non-Euclidean volumes. The main obstacle in such an extension is the problem of obtuse tessellations. We propose to split the obtuse simplices by adding virtual connections to neighbor grid points, which is formulated as a set of small integer linear programs. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2007/PHD/PHD-2007-07), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the PHD technical reports of 2007
To the main CS technical reports page