Retrieving 2D shapes using caterpillar decomposition
Machine Vision and Applications, cilt.24, sa.2, ss.435-445, 2013 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 24 Sayı: 2
- Basım Tarihi: 2013
- Doi Numarası: 10.1007/s00138-012-0406-8
- Dergi Adı: Machine Vision and Applications
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.435-445
- Anahtar Kelimeler: Caterpillar decomposition, Indexing, Shape retrieval
- Ankara Yıldırım Beyazıt Üniversitesi Adresli: Hayır
Özet
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. © 2012 Springer-Verlag.