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. Gromov-Hausdorff distance ͉ isometric embedding ͉ iterative-closestpoint ͉ partial embedding T he problem of comparison between deformable surfaces has recently gained a lot of interest in pattern recognition, especially in the fields of three-dimensional (3D) data analysis and synthesis. It arises, for example, in medical imaging and 3D face recognition (1). The fundamental question is how to efficiently yet accurately quantify the similarity between a given reference surface ("model") and some other surface ("probe"), usually a bent version of the model. We would like to capture the distinction of the model and the probe intrinsic properties associated with the metric structure of the surface, while ignoring the extrinsic properties that describe the way the surface is immersed into the ambient space and that often change while the surface bends. A deformation that preserves the intrinsic structure of the surface is called an ''isometry.'' Our goal is thus to define a computable isometry-invariant measure of similarity between surfaces. Often, the problem is even more complicated, when having the probe only partially available (see Fig. 1 ). We refer to the latter setting as ''partial surface matching'' and to the case where the whole probe is available as ''full surface matching.'' One of the earliest attempts of isometry-invariant surface matching is the classical ''iterative closest point'' (ICP) algorithm (2). It addresses a particular case of the partial matching problem where only rigid (Euclidean) isometries are allowed. An efficient method for the construction of near-isometry-invariant representations of surfaces [called ''canonical forms'' (CFs)] based on Euclidean embeddings was presented in ref. 3, as a generalization of ref. 4. This approach used a multidimensional scaling (MDS) algorithm (5). MDS is closely related to dimensionality reduction (6, 7) and can be performed in a computationally efficient manner. Euclidean embeddings are used in theoretical computer science for representing metric spaces usually arising from geometry of graphs (8). Recently, Mémoli and Sapiro (9) used a discrete probabilistic approximation of the Gromov-Hausdorff (GH) distance (10) to compare surfaces up to isometries. Their method is based on evaluating all of the permutations between two sets of surface samples, which is computationally expensive. Moreover, the GH distance is inappropriate for partial matching. One of the main contributions of this work is the ''partial embedding (PE) distance,'' motivated by Gromov's theory. For its efficient computation, we introduce an extension of MDS, which we call generalized MDS (GMDS). The key idea is to measure the minimum possible distortion when trying to isometrically embed one surface into another. By using GMDS, we can handle full as well as partial surface matching; this ability is one advantage over a straightforward use of the GH distance. The paper includes six sections. Theoretical Foundations reviews the theoretical background of isometry-invariant surface matching. We define our PE distance and show its relation to the GH distance. The next section, GMDS, introduces the GMDS and addresses implementation and optimization considerations. The following section focuses on partial matching of surfaces. In Results, we show some experimental results. Finally, in Conclusions, we summarize the main results. Let S be a smooth connected and compact Riemannian surface (2-manifold) with minimal geodesics C* S (s, sЈ) between every two points s, sЈ on S. We define the geodesic distance function d S : S ϫ S 3 ‫ޒ‬ ϩ as d S (s, sЈ) ϭ length{C* S (s, sЈ)}. For simplicity, we say ''surface S,'' implying the underlying metric space (S, d S ) induced by the Riemannian geometry of S. In our context, surfaces are perceived from a point of view of metric rather than Riemannian geometry; in other words, we do not consider the Riemannian metric tensor, but the geodesic distances that it induces. In practice, we work with sampled surfaces represented by finite metric spaces. We use the following definitions: a subset S r ʚ S is called an ''r-covering'' (or ''r-net'') of S if S ϭ ഫ sʦSr B S (s, r), where B S (s 0 , r) ϭ {s ʦ S : d S (s, s 0 ) Ͻ r} is a ball of radius r around s 0 in S. A finite r-covering of S consisting of N points is denoted by S N r . The metric on S N r is assumed to be the restricted metric d S ͉ S N r (s, sЈ) ϭ d S (s, sЈ) for all s, sЈ in S N r . We refer to r as the ''sampling radius.'' An arbitrary finite sampling of S consisting of N points is denoted by S N , where S is called ''continuous'' surface and S N a ''discrete'' one.
Bronstein et al. embed the intrinsic geometry of S into the surface Q using generalized MDS REF .
Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching
Proceedings of the National Academy of Sciences
Proceedings of the National Academy of Sciences
Computer Science Medicine