Shape matching using edit-distance: an implementation

Abstract

We report on our experience with the implementation of an algorithm for comparing shapes by computing the edit-distance 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-defined formulation and polynomial-time algorithms for solution.  Previous research has involved either ill-defined formulations or heuristic methods for solution.

Our starting-point for the implementation is the edit-distance algorithm of Klein et al.  We discuss how we altered that algorithm to handle rotation-invariance while keeping down the time and storage requirements.  Most important, we define 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.
 

Reference

@inproceedings{Klein:etal:SODA2001,
  author = {Philip Klein and Thomas Sebastian and Benjamin Kimia},
  title = {Shape matching using edit-distance: an implementation},
  booktitle = {Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  address = {Washington, D.C.},
  month = {January 7-9},
  pages = {781--790},
  year = {2001},
}

Lems Webpages on Shock Graph Matching

Back to LEMS Publications pages