|
Similarity and correspondence of non-rigid shapes
Non-rigid objects are ubiquitous in the world at all scales from macro to nano.
Non-rigid 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 Gromov-Hausdorff 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 structure-preserving correspondence and computed by minimizing metric distortion using the Generalized multidimensional scaling (GMDS), a generalization of MDS algorithms as a numerical framework.
Papers
C. Wang, M. M. Bronstein, N. Paragios, A. M. Bronstein,
"Discrete minimum distortion correspondence problems for non-rigid shape matching",
Proc. Conf. on Scale Space and Variational Methods in Computer Vision (SSVM), 2011.
A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Analysis of two-dimensional non-rigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 78/1, pp. 67-88, June 2008.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Calculus of non-rigid surfaces for geometry and texture manipulation", IEEE Trans. Visualization and Computer Graphics, Vol 13/5, pp. 902-913, September-October 2007.
A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Matching two-dimensional articulated shapes using generalized multidimensional scaling",
Proc. Conf. Articulated Motion and Deformable Objects (AMDO), pp. 48-57, 2006.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Efficient computation of isometry-invariant distances between surfaces", SIAM J. Scientific Computing, Vol. 28/5, pp. 1812-1836, 2006.
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching", Proc. National Academy of Sciences (PNAS), Vol. 103/5, pp. 1168-1172, 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 non-rigid shapes
Partial similarity and correspondence
|