A tree-edit-distance algorithm for comparing simple, closed shapes

We discuss a graph-algorithmic approach to comparing shapes. We focus in this paper on comparing simple closed curves in the plane. Our approach is to (1) represent such a shape by its skeleton, which is a tree embedded in the plane, and (2) compare two shapes by comparing their skeletons via tree edit-distance. In this paper, we dene our version of tree edit-distance (it diers from that previously described in the literature), and give a polynomial-time algorithm to compute the distance between two trees. 1 Introduction This paper arose out of a collaboration between a computer-vision researcher and an algorithms researcher. Kimia et al. [4] had previously compared shapes by comparing their graphs using a heuristic for general graph-comparison. The heuristic, due to Gold and Rangarajan [3], is based on nding a local minimum to a quadratic program. This approach had several disadvantages, however, and Kimia was searching for another approach. Klein suggested that the notion of ed...