Abstract
We describe a new indexing structure for general image retrieval that relies solely on a distance function giving the similarity between two images. For each image object in the database, its distance to a set of m predetermined vantage objects is calculated; the m-vector of these distances specifies a point in the m-dimensional vantage space. The database objects that are similar (in terms of the distance function) to a given query object can be determined by means of an efficient nearest-neighbor search on these points. We demonstrate the viability of our approach through experimental results obtained with a database of about 48,000 hieroglyphic polylines.
This research was supported by SION project No. 612-21-201: Advanced Multimedia Indexing and Searching (AMIS).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
The extended library. Centre for Computer-Aided Egyptological Research, Faculty of Theology, Utrecht University, Utrecht, the Netherlands. http://www.ccer.theo.uu.nl/ccer/extlib.html.
Edoardo Ardizzone, Marco La Cascia, Viti Di Gesú, and Cesare Valentie. Content based indexing of image and video databases by global and shape features. In Proc. Int. Conf. Pattern Recognition, 1996.
Esther M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and Joseph S. B. Mitchell. An efficiently computable metric for comparing polygonal shapes. IEEE Trans. Pattern Anal. Mach. Intell., 13(3):209–216, 1991.
S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms, pages 573–582, 1994. An implementation is available from http://www.cs.umd.edu/~mount/ANN.
J. L. Bentley. K-d trees for semidynamic point sets. In Proc. 6th Annu. ACM Sympos. Comput. Geom., pages 187–197, 1990.
S. Berchtold, D. A. Keim, and H.-P. Kriegel. The X-tree: An index structure for higher dimensional data. In Proc. 22th VLDB Conference, pages 28–39, 1996.
M. La Cascia and E. Ardizzone. JACOB: Just a content-based query system for video databases. In IEEE Int. Conf. Acoustics, Speech, and Signal Processing, 1996.
Bernard Chazelle and Emo Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom., 4:467–489, 1989.
K. L. Clarkson. Nearest neighbor queries in metric spaces. In Proc. 29th Annu. ACM Sympos. Theory Comput., pages 609–617, 1997.
S. D. Cohen and Leonidas J. Guibas. Partial matching of planar polylines under similarity transformations. In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pages 777–786, January 1997.
M. Hagedoorn and R. C. Veltkamp. Measuring resemblance of complex patterns. In Proc. Int. Conf. Discrete Geom. Comput. Imagery, 1999.
Norio Katayama and Shin’ichi Satoh. The SR-tree: An index structure for high-dimensional nearest neighbor queries. In SIGMOD’ 97, pages 369–380, 1997.
P. M. Kelly, T. M. Cannon, and D. R. Hush. Query by image example: the CANDID approach. In Proc. SPIE: Storage and Retrieval for Image and Video Databases III, volume 2420, pages 238–248, 1995.
J. Kleinberg. Two algorithms for nearest-neighbor search in high dimension. In Proc. 29th Annu. ACM Sympos. Theory Comput., pages 599–608, 1997.
K. I. Lin, H. V. Jagdish, and C. Faloutsos. The TV-tree: An index structure for higher dimensional data. VLDB Journal, 4:517–542, 1994.
J. Matoušek. Efficient partition trees. Discrete Comput. Geom., 8:315–334, 1992.
J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157–182, 1993.
Rajiv Mehrotra and James E. Gary. Similar-shape retrieval in shape data management. IEEE Computer, 28:57–62, 1995.
W. Niblack, R. Barber, W. Equitz, M. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, and G. Taubin. The QBIC project: Querying images by content using color, texture and shape. Storage Retrieval Image Video Databases, 1908:173–187, 1993.
Virginia E. Ogle and Michael Stonebraker. Chabot: Retrieval from a relational database of images. IEEE Computer, 28:40–48, 1995.
A. Pentland, R. W. Picard, and S. Sclaroff. Photobook: Tools for content-based manipulation of image databases. In Proc. SPIE: Storage and Retrieval for Image and Video Databases II, volume 2185, pages 34–47, 1994.
Otfried Schwarzkopf and Jules Vleugels. Range searching in low-density environments. Inform. Process. Lett., 60:121–127, 1996.
Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inform. Process. Lett., 40:175–179, 1991.
D. A. White and R. Jain. Similarity indexing with the SS-tree. In Proc. 12th IEEE Internat. Conf. Data Engineering, pages 516–523, 1996.
H. J. Wolfson. Model-based object recognition by geometric hashing. In Proc. 1st Europ. Conf. Comp. Vision, pages 526–536, 1990.
P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 311–321, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vleugels, J., Veltkamp, R. (1999). Efficient Image Retrieval through Vantage Objects. In: Huijsmans, D.P., Smeulders, A.W.M. (eds) Visual Information and Information Systems. VISUAL 1999. Lecture Notes in Computer Science, vol 1614. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48762-X_71
Download citation
DOI: https://doi.org/10.1007/3-540-48762-X_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66079-8
Online ISBN: 978-3-540-48762-3
eBook Packages: Springer Book Archive