Shape matching using edit-distance: an implementation

This work defines costs for the edit-operations and gives an algorithm for computing them, and shows that this approach performs intuitively in categorization and indexing tasks, and its results are better than previous approaches.

Abstract

We report on our experience with the implementation of an algorithm for comparing shapes by computing the editdistance between their medial axes. A shape-comparison method that is robust to various visual transformations has several applications in computer vision, including organizing and querying an image database, and object recognition. There are two components to research on this problem, mathematical formulation of the shape-comparison problem and the computational solution method. We have a clear, well-dened formulation and polynomial-time algorithms for solution. Previous research has involved either ill-dened formulations or heuristic methods for solution. Our starting-point for the implementation is the editdistance algorithm of Klein et al. [6]. We discuss how we altered that algorithm to handle rotation-invariance while keeping down the time and storage requirements. Most important, we dene costs for the edit-operations and give an algorithm for computing them. We use a database of shapes to illustrate that our approach performs intuitively in categorization and indexing tasks, and our results are better than previous approaches.