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