1998
@inproceedings{TSK1998,
vgclass = {refpap},
vgproject = {cbir},
author = {Srikanta Tirthapura and Daniel Sharvit and Philip Klein
and Benjamin B. Kimia},
title = {Indexing based on edit-distance matching of shape graphs},
editor = {C.-C. Jay Kuo and Shih-Fu Chang and Sethuraman
Panchanathan},
booktitle = {Multimedia Storage and Archiving Systems III (VV02)},
address = {Boston, Massachusetts, USA},
volume = {3527},
series = {SPIE Proceedings},
pages = {25--36},
month = {November},
year = {1998},
note = {(SPIE Symposium on Voice, Video and Data Communications)},
abstract = {We are investigating a graph matching approach for
indexing into pictorial databases using \emph{shock graphs}, a
symmetry-based representation of shape. Each shape (or a collection of
edge elements) is represented by a shock graph. Indexing of a query
into a pictorial database is accomplished by comparing the
corresponding shock graph to the graphs representing database elements
and selecting the best match. This paper introduces a new metric for
comparing shock graphs.
The premise underlying the use of symmetry as a cue for indexing is
that the correlation of pairs of edge elements in the sketch query and
in the image is a more robust measure of indexing than simply
correlating edge elements. Each pair of edge elements is represented by
a symmetry curve, and can be extracted from real images and represented
as singularities resulting from the propagation of each such
orientation element. Previous work shows that these singularities, or
\emph{shocks}, can be detected, classified grouped, and organized into
a \emph{shock graph} embedded in the plane.
In previous work, we proposed the use of a graph comparison heuristic
called the \emph{graduated assignment algorithm} which casts the
problem as an integer quadratic program. This heuristic has two
drawbacks. First, the quadratic program does not fully capture the
topological constraints of graph matching, and so even an optimal
solution could be topologically incorrect. Second, since solving the
quadratic program is infeasible, the algorithm often finds only locally
optimal solutions.
We now present a matching approach based on the notion of \emph{edit
distance}. The edit distance between two graphs is defined as the cost
of the ``least action'' path of elementary edit transformations taking
one graph to the other. We have defined a set of elementary edit
transformations appropriate to shock graphs. These operations are
motivated by intuitive and natural deformations of shape and
mathematically correspond closely to the set of \emph{shock
transitions}. Moreover, we observe that shock graphs have special
structure: the are unrooted, planar-embedded trees. By exploiting this
structure, we have developed an algorithm to compute edit distance (and
corresponding edit transformations) between shock graphs precisely and
quickly (in polynomial time). We have implemented this algorithm for a
subset of these edit operations. In this paper, we illustrate these
results for a few shapes. We plan to report on a complete
implementation and results in a later paper.},
}