Technical Report PHD-2007-07

Title: Numerical geometry of non-rigid objects: embedding problems
Authors: Alexander Bronstein
Supervisors: Prof. Ron Kimmel
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.

CopyrightThe 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 (, 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

Computer science department, Technion