Shock-based Indexing into Large Shape Databases
Abstract
This paper examines issues arising in applying a previously
developed
edit-distance shock graph matching technique to indexing
into
large shape databases. This approach compares
the shock
graph topology and attributes to produce a similarity
metric,
and results in 100% recognition rate in querying
a database of
approximately 200 shapes. However, indexing into a significantly
larger database is faced with both the lack of a suitable
database,
and more significantly with the expense related to computing
the
metric. We have thus (i) gathered shapes
from a variety of sources to create
a database of over 1000 shapes from forty categories
as a stage towards
developing an approach for indexing into a much larger
database; (ii) developed
a coarse-scale approximate similarly measure
which relies
on the shock graph topology and a very coarse sampling
of link
attributes. We show that this is a good first-order
approximation of
the similarly metric and is two orders of magnitude more
efficient to
compute. An interesting outcome of using this efficient
but approximate
similarity measure is that the approximation naturally
demands a
notion of categories to give high precision; (iii)
developed
an
exemplar-based indexing scheme which discards a large
number of
non-matching shapes solely based on distance to exemplars,
coarse
scale representatives of each category. The use
of a coarse-scale
matching measure in conjunction with a coarse-scale sampling
of the
database leads to a significant reduction in the computational
effort
without discarding correct matches, thus paving the way
for indexing
into databases of tens of thousands of shapes.
Reference
@inproceedings{Sebastian:ECCV2002,
author = {Thomas B. Sebastian and Philip N. Klein and Benjamin B. Kimia},
title = {Shock-based Indexing into Large Shape Databases},
pages = {Part III:731-746},
year = {2002},
}
Gzipped postscript file (Copyright
Springer
Verlag)
PDF file
Lems
Webpages on Shock Graph Matching
Back
to LEMS Publications pages