Graph-based shape indexing

Graphs have become growingly important in representing shapes in computer vision. Given a query graph, it is essential to retrieve similar database graphs efficiently from a large database. In this paper, we present a graph-based indexing technique which overcomes significant drawbacks of the previo...

Full description

Saved in:
Bibliographic Details
Published in:Machine vision and applications 2012-05, Vol.23 (3), p.541-555
Main Author: Demirci, M. Fatih
Format: Article
Language:English
Subjects:
Algorithms
Communications Engineering
Computer Science
Computer vision
Empirical analysis
Graphical representations
Graphs
Image Processing and Computer Vision
Indexing
Matrix methods
Networks
Original Paper
Pattern Recognition
Similarity
Topology
Vector space
Vision systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graphs have become growingly important in representing shapes in computer vision. Given a query graph, it is essential to retrieve similar database graphs efficiently from a large database. In this paper, we present a graph-based indexing technique which overcomes significant drawbacks of the previous work (Demirci et al. in Comput Vis Image Underst 110(3):312–325, 2008) using a recently developed theorem from the domain of matrix analysis. Our technique starts by representing the topological structure of a graph in a vector space. As done in the previous work, the topological structure of a graph is constructed using its Laplacian spectra. However, unlike the previous approach, which represents all sugraphs of a database graph in the vector space to account for local similarity, a database graph in the proposed framework is represented as a single vector. By performing a range search around the query, the proposed indexing technique returns a set with both partial and global similarity. Empirical evaluation of the algorithm on an extensive set of retrieval trials including a comparison with the previous approach in both 2D and 3D demonstrates the effectiveness, efficiency, and robustness of the overall approach.
ISSN:0932-8092
1432-1769
DOI:10.1007/s00138-010-0290-z