Similarity and correspondence of nonrigid shapes
Nonrigid objects are ubiquitous in the world at all scales from macro to nano.
Nonrigid shapes are ubiquitous in Nature and are encountered at all levels of life, from macro to nano. The need to model such shapes and understand their behavior arises in many applications in imaging sciences, pattern recognition, computer vision, and computer graphics. Of particular importance is understanding which properties of the shape are attributed to deformations and which are invariant, i.e., remain unchanged.
We developed an approach to non rigid shapes from the point of view of metric geometry. Modeling shapes as metric spaces, one can pose the problem of shape similarity as the similarity of metric spaces and harness tools from theoretical metric geometry for the computation of such a similarity, in particular, the GromovHausdorff distance.
By choosing appropriately the metric, difference invariant properties are obtained. For example, Eucliden metric is invariant to rigid transformations (rotations and translations), geodesic metric is invariant to inelastic deformations (bending). Other metrics, such as diffusion and commute time, can be used to cope with changes in shape topology.
Shape matching is formulated as the best structurepreserving correspondence and computed by minimizing metric distortion using the Generalized multidimensional scaling (GMDS), a generalization of MDS algorithms as a numerical framework.
Papers
A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Analysis of twodimensional nonrigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 78/1, pp. 6788, June 2008.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Calculus of nonrigid surfaces for geometry and texture manipulation", IEEE Trans. Visualization and Computer Graphics, Vol 13/5, pp. 902913, SeptemberOctober 2007.
A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Matching twodimensional articulated shapes using generalized multidimensional scaling",
Proc. Conf. Articulated Motion and Deformable Objects (AMDO), pp. 4857, 2006.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Efficient computation of isometryinvariant distances between surfaces", SIAM J. Scientific Computing, Vol. 28/5, pp. 18121836, 2006.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Generalized multidimensional scaling: a framework for isometryinvariant partial surface matching", Proc. National Academy of Sciences (PNAS), Vol. 103/5, pp. 11681172, January 2006.
Patents
R. Kimmel, A. Bronstein, M. Bronstein,
"Method and apparatus for determining similarity between surfaces", European Patent No. EP1969523, September 2008; PCT No. WO2007069260, June 2007; US Patent application No. US2009028442, January 2009.
Software
GMDS tutorial
Data
TOSCA datasets
Media coverage
Abel Prize Science Lecture: Revolutionary work in geometry and shape analysis, SIAM News, July/August 2009.
See also
Symmetry of nonrigid shapes
Partial similarity and correspondence
