Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching

doi:10.1073/pnas.0508601103

Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching

Department of Computer Science, Technion Israel Institute of Technology, Haifa 32000, Israel

Edited by Alexandre J. Chorin, University of California, Berkeley, CA, and approved December 5, 2005 (received for review October 3, 2005)

Abstract

An efficient algorithm for isometry-invariant matching of surfaces is presented. The key idea is computing the minimum-distortion mapping between two surfaces. For this purpose, we introduce the generalized multidimensional scaling, a computationally efficient continuous optimization algorithm for finding the least distortion embedding of one surface into another. The generalized multidimensional scaling algorithm allows for both full and partial surface matching. As an example, it is applied to the problem of expression-invariant three-dimensional face recognition.

Footnotes

↵† To whom correspondence should be addressed. E-mail: ron{at}cs.technion.ac.il.
Author contributions: A.M.B., M.M.B., and R.K. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.
Conflict of interest statement: No conflicts declared.
This paper was submitted directly (Track II) to the PNAS office.
Abbreviations: CF, canonical form; FMM, fast marching method; GH, Gromov–Hausdorff; MDS, multidimensional scaling; GMDS, generalized MDS; PE, partial embedding.