Recognition of Shapes by Editing Shock Graphs

Abstract

This paper presents a novel recognition framework which is based
on matching shock graphs of 2D shape outlines, where the distance
between two shapes is defined to be the cost of the least action path
deforming one shape to the other. Two key issues are addressed
which render the implementation of this framework practical: First, the
shape space is partitioned by defining an equivalence class on shapes
where two shapes  with the same shock graph topology are
equivalent. The space of deformations is discretized  by formally
enumerating all possible transitions when the shock graph topology
changes and defining all deformations with the same sequence of shock
graph transitions as equivalent. Second,  we employ a graph edit
distance algorithm that searches in the space of all possible
transition sequences and finds  the globally optimal sequence in
polynomial time.  The effectiveness of the proposed technique in the
presence of a variety of visual transformations including occlusion,
articulation and deformation of parts, shadow and highlights,
viewpoint variation, scale, and boundary perturbations is
demonstrated. Indexing into  two separate databases of roughly 100
shapes reveals that 100% accuracy for top three matches and 99.5% for
the next three matches.

Reference

@inproceedings{Sebastian:ICCV2001,
  author = {Thomas B. Sebastian and Philip N. Klein and Benjamin B. Kimia},
  title = {Recognition of Shapes by Editing Shock Graphs},
  booktitle = {ICCV},
  pages = {755-762},
  year = {2001},
}

PDF file

Lems Webpages on Shock Graph Matching

Back to LEMS Publications pages