Matching non-rigidly deformable shapes across images: A globally optimal solution

While global methods for matching shapes to images have recently been proposed, so far research has focused on small deformations of a fixed template. In this paper we present the first global method able to pixel-accurately match non-rigidly deformable shapes across images at amenable run-times. By finding cycles of optimal ratio in a four-dimensional graph - spanned by the image, the prior shape and a set of rotation angles - we simultaneously compute a segmentation of the image plane, a matching of points on the template to points on the segmenting boundary, and a decomposition of the template into a set of deformable parts. In particular, the interpretation of the shape template as a collection of an a priori unknown number of deformable parts - an important aspect of higher-level shape representations - emerges as a byproduct of our matching algorithm. On real-world data of running people and walking animals, we demonstrate that the proposed method can match strongly deformed shapes, even in cases where simple shape measures and optic flow methods fail.