No Title

Project: Edit-Distance Based Algorithms for Shape-Based Retrieval of Images

Philip Klein (Computer Science), Benjamin Kimia and Thomas Sebastian (Engineering)

Papers

``A Tree-edit-distance algorithm for comparing simple, closed shapes,'' Philip Klein, Srikanta Tirthapura, Daniel Sharvit, and Ben Kimia, Proceedings, ACM-SIAM Symposium on Discrete Algorithms (1999), pp. 696-704.
``Indexing based on edit-distance matching of shape graphs,'' Philip Klein, Srikanta Tirtapura, Daniel Sharvit, and Benjamin Kimia, Proceedings, SPIE International Symposium on Voice, Video, and Data Communications (1998), pp. 25-36.
``Computing the edit distance between unrooted ordered trees'', Philip Klein Proceedings, 6th European Symposium on Algorithms (1998), pp. 91-102.
"Constructing 2D Curve Atlases," Thomas Sebastian, Joseph J. Crisco, Philip N. Klein, Benjamin B. Kimia, submitted.

Goal: Enable shape-based retrieval from an image database

input: shape sketch
output: images in database that most closely match input shape

Question: How to measure similarity of shapes?
Answer: Compare their skeletons (labeled graphs)
$\psfig{figure=figs/orig1.ps, height=3in}$ $\psfig{figure=figs/orig2.ps, height=3in}$

What metric to use? Earlier work by Kimia:
distance between labeled graphs = value of a quadratic integer program.
Disadvantages:

NP-hard, so heuristic used to solve (Graduated Assignment)
Formulation does not respect the planar embedding of the graph.
Formulation does not completely capture topology.

Our Approach - Edit Distance

Define a set of elementary transformations (edit operations and costs for these transformations.
Define distance between labeled graphs = minimum cost of a sequence of edit operations that morph one graph into the other

$\psfig{figure=figs/bonefish_original_boundary.ps,height=6.2cm}$ $\psfig{figure=figs/bonefish_to_herring_editop1.ps,height=6.2cm}$ $\psfig{figure=figs/attempt.ps,height=6.2cm}$ $\psfig{figure=figs/herring_to_bonefish_editop3.ps,height=6.2cm}$ $\psfig{figure=figs/herring_to_bonefish_editop2.ps,height=6.2cm}$ $\psfig{figure=figs/herring_to_bonefish_editop1.ps,height=6.2cm}$ $\psfig{figure=figs/herring_original_boundary.ps,height=6.2cm}$

Ongoing research

How to define cost of edit operations?
Faster edit-distance algorithms?
Computing prototypes and clusters for shapes represented by graphs.
Fast processing of closest-shape queries.

Philip Klein
2000-03-02