Abstract
We consider the problem of finding the best match for a given query shape among candidate shapes stored in a shape base. This is central to a wide range of applications, such as, digital libraries, digital film databases, environmental sciences, and satellite image repositories. We present an efficient matching algorithm built around a novel similarity criterion and based on shape normalization about the shape’s diameter, which reduces the effects of noise or limited accuracy during the shape extraction procedure. Our matching algorithm works by gradually “fattening” the query shape untilthe best match is discovered. The algorithm exhibits poly-logarithmic time behavior assuming uniform distribution of the shape vertices in the locus of their normalized positions.
This work was supported in part by a GSRT (GeneralS ecretariat of Research and Technology) Bilateral Research Cooperation Grant between Greece and the Czech Republic
Chapter PDF
Similar content being viewed by others
References
M. Ankerst, H. P. Kriegel, and T. Seidl. Multistep approach for shape similarity search in image databases. IEEE Transactions on Knowledge and Data Engineering, 10(6):996–1004, 1998. 506
E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell. An efficiently computable metric for comparing polygonal shapes. IEEE Transactions on Knowledge and Data Engineering, 13(3):209–216, 1997. 507
H. G. Barrow, J. M. Tenenbaum, R. C. Bolles, and H. C. Wolf. Parametric correspondence and chamfer matching: Two new techniques for image matching. In Proc. of the 5th IJCAI, pages 659–663, Cambridge, MA, 1977. 506
A. Del Bimbo and P. Pala. Visualim age retrievalb y elastic matching of user sketches. IEEE Transactions on Knowledge and Data Engineering, 19(2):121–132, 1997. 506
G. Borgefors. An improved version of the chamfer matching algorithm. In ICPR1984, pages 1175–1177, 1984. 506
G. Borgefors. Hierarchicalc hamfer matching: A parametric edge matching algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(6):849–865, 1988. 506
C. Carson and V. E. Ogle. Storage and retrieval of feature data for a very large online image collection. IEEE Bulletin of the Tech. Comm. on Data Engineering, 19(4):19–27, 1996. 505
B. Chazelle and L. J. Guibas. Fractional cascading: I. a data structuring technique; II. applications. Algorithmica, 1:133–191, 1986. 513
Ronald Fagin and Larry Stockmeyer. Relaxing the triangle inequality in pattern matching. International Journal of Computer Vision, to appear, 1999. 506, 507
M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. QBIC: Query by image and video content. IEEE Computer, 28(9):23–32, 1995. 505
J. E. Gary and R. Mehrotra. Similar shape retrieval using a structural feature index. Information Systems, 18(7):527–537, 1993. 506
J. E. Gary and R. Mehrotra. Feature-index-based similar shape retrieval. In S. Spaccapietra and R. Jain, editors, Visual Database Systems, volume 3, pages 46–65, 1995. 506, 507
J. E. Goodman and J. O’Rourke. Handbook of Discrete and Computational Geometry. CRC Press LLC, 1997. 513
D. P. Huttenlocher and W. J. Rucklidge. A multi-resolution technique for comparing images using the hausdorff distance. Technical Report TR92-1321, CS Department, Cornell University, 1992. 507
R. Mehrotra and J. E. Gary. Similar-shape retrieval in shape data management. IEEE Computer, 28(9):57–62, 1995. 506
W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glassman, D. Petkovic, and P. Yanker. The QBIC project: querying images by content using color, texture and shape. In Proc. SPIE Conference on Storage Retrieval for Image and Video Databases, volume 1908, pages 173–181. SPIE, 1993. 506
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fudos, I., Palios, L. (2000). An Efficient Shape-Based Approach to Image Retrieval. In: Borgefors, G., Nyström, I., di Baja, G.S. (eds) Discrete Geometry for Computer Imagery. DGCI 2000. Lecture Notes in Computer Science, vol 1953. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44438-6_41
Download citation
DOI: https://doi.org/10.1007/3-540-44438-6_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41396-7
Online ISBN: 978-3-540-44438-1
eBook Packages: Springer Book Archive