Fast Matching of Planar Shapes in Sub-Cubic Runtime

Abstract

The matching of planar shapes can be cast as a problem of finding the shortest path through a graph spanned by the two shapes, where the nodes of the graph encode the local similarity of respective points on each contour. While this problem can be solved using dynamic time warping, the complete search over the initial correspondence leads to cubic runtime in the number of sample points. In this paper, we cast the shape matching problem as one of finding the shortest circular path on a torus. We propose an algorithm to determine this shortest cycle which has provably sub-cubic runtime. Numerical experiments demonstrate that the proposed algorithm provides faster shape matching than previous methods. As an application, we show that it allows to efficiently compute a clustering of a shape data base.