Efficient region-based image retrieval

ABSTRACT

Region-based image retrieval(RBIR) was recently proposed as an extension of content-based image retrieval(CBIR). An RBIR system automatically segments images into a variable number of regions, and extracts for each region a set of features. Then, a dissimilarity function determines the distance between a database image and a set of reference regions. Unfortunately, the large evaluation costs of the dissimilarity function are restricting RBIR to relatively small databases. In this paper, we apply a multi-step approach to enable region-based techniques for large image collections. We provide cheap lower and upper bounding distance functions for a recently proposed dissimilarity measure. As our experiments show, these bounding functions are so tight, that we have to evaluate the expensive distance function for less than 0.5\%of the images. For a typical image database with more than 370,000images, our multi-step approach improved retrieval performance by a factor of more than5 compared to the currently fastest methods.

REFERENCES

• 1: Mihael Ankerst , Bernhard Braunmüller , Hans-Peter Kriegel , Thomas Seidl, Improving Adaptable Similarity Query Processing by Using Approximations, Proceedings of the 24rd International Conference on Very Large Data Bases, p.206-217, August 24-27, 1998
• 2: I. Bartolini , P. Ciaccia , M. Patella, A Sound Algorithm for Region-Based Image Retrieval Using an Index, Proceedings of the 11th International Workshop on Database and Expert Systems Applications, p.930, September 06-08, 2000
• 3: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 4: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 5: Chad Carson , Megan Thomas , Serge Belongie , Joseph M. Hellerstein , Jitendra Malik, Blobworld: A System for Region-Based Image Indexing and Retrieval, Proceedings of the Third International Conference on Visual Information and Information Systems, p.509-516, June 02-04, 1999
• 6: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 7: Yining Deng , b. s. Manjunath, Unsupervised Segmentation of Color-Texture Regions in Images and Video, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.8, p.800-810, August 2001 [doi>10.1109/34.946985]
• 8: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 9: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: V. Gouet , N. Boujemaa, Object-based queries using color points of interest, Proceedings of the IEEE Workshop on Content-based Access of Image and Video Libraries (CBAIVL'01), p.30, December 14-14, 2001
• 11: J. Hebborn. Decision Maths 2, chapter 2. Allocation (assignment) problems, p. 29--45. Heinemann Modular Maths for Edexcel AS and A-level. Heinemann, 2001.
• 12: Lothar Hermes , Thomas Zöller , Joachim M. Buhmann, Parametric Distributional Clustering for Image Segmentation, Proceedings of the 7th European Conference on Computer Vision-Part III, p.577-591, May 28-31, 2002
• 13: D. E. Knuth. The Stanford Graph Base, p. 77--89. 1993.
• 14: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 15: Apostol Natsev , Rajeev Rastogi , Kyuseok Shim, WALRUS: a similarity retrieval algorithm for image databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.395-406, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 16: Y. Rui, T. S. Huang, and S.-F. Chang. Image Retrieval: Current Techniques, Promising Directions and Open Issues. Journal of Visual Communication and Image Representation, 10(4):39--62, 1999.
• 17: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 18: M. A. Stricker and M. Orengo. Similarity of Color Images. In Storage and Retrieval for Image and Video Databases, volume 2420 of SPIE Proceedings, p. 381--392, San Diego/La Jolla, CA, USA, 1995.
• 19: James Z. Wang , Jia Li , Gio Wiederhold, SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.947-963, September 2001 [doi>10.1109/34.955109]
• 20: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Performance

Keywords:
CBIR, RBIR, region-based image retrieval