2008
@article{DLV2008,
vgclass = {refpap},
author = {M. Fatih Demirci and Reinier H. van Leuken and Remco C.
Veltkamp},
title = {Indexing through laplacian spectra},
journal = {Computer Vision and Image Understanding},
volume = {110},
number = {3},
pages = {312--325},
month = {June},
year = {2008},
note = {Special issue on Similarity Matching in Computer Vision
and Multimedia},
url = {http://dx.doi.org/10.1016/j.cviu.2007.09.012},
abstract = {With ever growing databases containing multimedia data,
indexing has become a necessity to avoid a linear search. We propose a
novel technique for indexing multimedia databases in which entries can
be represented as graph structures. In our method, the topological
structure of a graph as well as that of its subgraphs are represented
as vectors whose components correspond to the sorted laplacian
eigenvalues of the graph or subgraphs. Given the laplacian spectrum of
graph G, we draw from recently developed techniques in the field of
spectral integral variation to generate the laplacian spectrum of graph
G+e without computing its eigendecomposition, where G+e is a graph
obtained by adding edge e to graph G. This process improves the
performance of the system for generating the subgraph signatures for
1.8\% and 6.5\% in datasets of size 420 and 1400, respectively. By doing
a nearest neighbor search around the query spectra, similar but not
necessarily isomorphic graphs are retrieved. Given a query graph, a
voting schema ranks database graphs into an indexing hypothesis to
which a final matching process can be applied. The novelties of the
proposed method come from the powerful representation of the graph
topology and successfully adopting the concept of spectral integral
variation in an indexing algorithm. To examine the fitness of the new
indexing framework, we have performed a number of experiments using an
extensive set of recognition trials in the domain of 2D and 3D object
recognition. The experiments, including a comparison with a competing
indexing method using two different graph-based object representations,
demonstrate both the robustness and efficacy of the overall approach.},
}