Accelerating the Computation of Canonical Forms for 3D Nonrigid Objects using Multidimensional Scaling

Abstract

The analysis of 3D nonrigid objects usually involves the need to deal with a large number of degrees of freedom. When trying to match two such objects, one approach is to map the surfaces into a domain in which the matching process is simple to execute. Limiting the discussion to almost isometric mappings, which describe most natural deformations in nature, one could resort to Canonical forms. Such forms translate the surface's intrinsic geometry into an extrinsic one in a Euclidean space, thus eliminating the effect of deformations at the expense of (hopefully) minor embedding errors. Multidimensional Scaling (MDS) is a dimensionality reduction technique that can be used to compute canonical forms of 3D-objects, by first evaluating the pairwise geodesic distances between surface points, and then embedding the distances in a lower dimensional Euclidean space. The native computational and space complexities involved in describing such inter-geodesic distances is quadratic in the number of surface points, a property that could be prohibiting in various scenarios. We present an acceleration framework for multidimensional scaling, by accurately approximating the pairwise distance maps. We show how the proposed Nyström Multidimensional Scaling (NMDS) framework can be used to compute canonical forms in quasi-linear time and linear space complexities in the number of data points. It allows us to efficiently deal with high resolution structures without giving up the embedding accuracy.