Technical Report PHD-2007-04

Title: Isometry-invariant surface matching: numerical algorithms and applications
Authors: Michael Bronstein
Supervisors: Ron Kimmel
Abstract: Similarity is one of the most important abstract concepts in the human perception of the world. For example, we encounter it every day during our interaction with other people whose faces we recognize. In computer vision and pattern recognition, shape similarity is one of the most fundamental and largely open problem. 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 human 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 can be modeled as isometries, preserving the intrinsic geometric properties of the shapes. For example, deformations of human and animal bodies, our face, body tissues and organs can be approximated by isometries. Limiting our discussion to such deformations is not too restrictive in many cases, yet, 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 to embed 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. We devise a generic framework for partial similarity of objects, based on the notion of Pareto optimality.

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