Retrieving 2D shapes using caterpillar decomposition

Graphs provide effective data structures modeling complex relations and schemaless data such as images, XML documents, circuits, compounds, and proteins. Given a query graph, finding sufficiently similar database graphs without performing a sequential search is an important problem arising in differ...

Full description

Saved in:
Bibliographic Details
Published in:Machine vision and applications 2013-02, Vol.24 (2), p.435-445
Main Author: Demirci, M. Fatih
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Caterpillars
Communications Engineering
Computer Science
Computer science
control theory
systems
Data structures
Decomposition
Domains
Exact sciences and technology
Graph theory
Graphical representations
Graphs
Image Processing and Computer Vision
Information retrieval. Graph
Information systems. Data bases
Memory organisation. Data processing
Networks
Pattern Recognition
Perturbation
Query processing
Searching
Shape recognition
Short Paper
Software
Theoretical computing
Trees
Two dimensional models
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 provide effective data structures modeling complex relations and schemaless data such as images, XML documents, circuits, compounds, and proteins. Given a query graph, finding sufficiently similar database graphs without performing a sequential search is an important problem arising in different domains. In this paper, we propose a new method for indexing tree structures based on a graph-theoretic concept called caterpillar decomposition. Our algorithm starts by representing each tree along with its subtrees in the geometric space using its caterpillar decomposition. After representing the query in the same fashion, similar database trees are retrieved efficiently by means of nearest neighbor searches. We have successfully evaluated the proposed algorithm on two shape databases and include a set of perturbation experiments that establish the algorithm’s robustness to noise. We have also shown that the approach compares favorably to previous approaches for shape retrieval on these datasets.
ISSN:0932-8092
1432-1769
DOI:10.1007/s00138-012-0406-8