טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAlexander Bronstein
SubjectNumerical Geometry of Non-Rigid Objects:
Embedding Problems
DepartmentDepartment of Computer Science
Supervisor Full Professor Kimmel Ron
Full Thesis textFull thesis text - English Version


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.