Background and Previous Work

The problem of finding partial correspondences between shapes arises in many application areas, such as structural analysis of proteins, handwriting analysis, and recognition of partially-occluded objects in images.

Two partially-similar handwriting samples.

Richardson and Wang [RW] proposed an algorithm that achieved partial matching of shapes represented by sliding landmarks by allowing the beginning and ending landmarks to move, thereby matching a contiguous part of one shape to a contiguous part of the other. Chen et al. [CFK] adapted the Smith-Waterman algorithm to the task of comparing planar shapes represented by a novel descriptor based on the boundary curvature and distance across the shape. Bronstein et al. [BBBK] constructed a similarity criterion for 2-D non-rigid shapes, using generalized multidimensional scaling together with the idea of Pareto optimality.

Algorithm Description

Our work in this area has been focussed on finding partial correspondences between curves in Euclidean spaces of arbitrary dimension, within the context of the square root velocity (SRV) framework. In this framework, each parametric curve is represented by a point in an infinite-dimensional manifold. This space is equipped with a Riemannian metric, which makes it possible to consider geodesics between points. The geodesic distance between the representatives of a pair of curves is taken as a measure of their shape dissimilarity. Since the metric used in the SRV framework is an elastic metric, this geodesic distance is a measure of the amount of bending and stretching required to deform one curve into the other.

When computing the geodesic distance between two curves in the SRV framework, a key step is to find an elastic matching that minimizes the distance between the two curves. If the curves are parameterized on the interval [0,1], then the elastic matching problem is an optimization problem over the group of diffeomorphisms of this interval. The graph of such a diffeomorphism is an increasing, smooth curve through the unit square, beginning at (0,0) and ending at (1,1). If we place an NxN grid on the unit square, and discretize the problem by approximating diffeomorphisms with piecewise-linear paths from (0,0) to (1,1), then the optimization problem can be solved using a well-known algorithm based on dynamic programming. This algorithm finds the minimum-cost path from (0,0) to (1,1) in O(N^2) steps.

We extend the full elastic matching algorithm to a partial elastic matching algorithm by noting that a rectangle in the matching grid corresponds to a partial match between the two curves. A path through the rectangle corresponds to a particular registration between the relevant parts of the curves. If such a path has minimum cost, then that path corresponds to an optimal elastic matching between the two subcurves. Our algorithm finds the optimal path costs for every possible rectangle in the matching grid by applying the Floyd-Warshall all-pairs shortest-path algorithm.

Each rectangle in the grid corresponds to a partial match.

After this step completes, we know the parametrization-invariant shape distance for each possible partial match between the two curves. Depending on the application, it may be necessary to optimize over rotations as well. We currently do this by strategically selecting a small number of rotations so that, for each possible partial match, the optimal rotation for that partial match is well-approximated by one of our selected rotations. The Floyd-Warshall algorithm is run once for each one of these rotations.

References

  • [BBBK] 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.
  • [CFK] L. Chen, R. S. Feris, and M. Turk. "Efficient Partial Shape Matching Using SmithWaterman Algorithm." Workshop on Non-Rigid Shape Analysis and Deformable Image Alignment (NORDIA'08) 27-28 June 2008, Anchorage, Alaska, in conjunction with CVPR'08.
  • [RW] Richardson, Theodore and Song Wang. "Open-curve shape correspondence without endpoint correspondence." MICCAI 2006, pg. 17-24.