טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentMichael Bronstein
SubjectIsometry-Invariant Surface Matching:
Numerical Algorithms and Applications
DepartmentDepartment of Computer Science
Supervisor Full Professor Kimmel Ron
Full Thesis textFull thesis text - English Version


Abstract

Similarity is one of the most important abstract concepts in the perception of the world. With slight exaggeration, we can say that all pattern recognition problems boil down to giving a quantitative interpretation of similarity between objects. The definition of similarity is, to a large extent, a semantic question. For example, judging the similarity of faces, one may say that two faces are similar if they have a common skin tone, while someone else would require the identity of the geometric structure of facial features like the eyes, the nose, and the mouth. Since there is no unique definition of similarity, every class of objects and every problem require a specific, problem-dependent similarity criterion.


This thesis is dedicated to the question of similarity of non-rigid shapes. Such shapes appear at all scales in Nature - from our body organs to its microscopic components like protein molecules. In pattern recognition and computer vision, non-rigid shapes are often encountered in many important applications. The richness of the possible deformations and a large number of degrees of freedom of non-rigid shapes makes their analysis a great challenge.


Deformations of many natural objects (e.g., human and animal bodies, our face, body tissues and organs) can be modeled as isometries, preserving the intrinsic geometric properties of the shapes. Limiting our discussion to such deformations leads to a well-defined geometric criterion of intrinsic similarity, which is invariant to isometric deformations.


We present numerous facets of the non-rigid shape similarity problem: theoretical issues, numerical algorithms and practical applications. In the first part of the thesis, we discuss a method for representation of the intrinsic geometry of non-rigid shapes in a low-dimensional Euclidean space by means of a low-distortion embedding. The embedding is computed by the solution of the multidimensional scaling (MDS) problem. We show an efficient multigrid MDS algorithm for such a computation. In the second part, we extend the representations by embedding into non-Euclidean spaces, arguing that in such a way it is possible to make the representations more accurate, and, as the result, achieve better shape recognition. In the third part, we show the generalized MDS (GMDS) approach, allowing embedding one surface into another. We relate this method to the Gromov-Hausdorff distance in the fourth part. Finally, in the fifth part, we show how intrinsic similarity can be extended to shapes which have similar parts while being dissimilar when considered as a whole.