WALRUS: a similarity retrieval algorithm for image databases

ABSTRACT

Traditional approaches for content-based image querying typically compute a single signature for each image based on color histograms, texture, wavelet tranforms etc., and return as the query result, images whose signatures are closest to the signature of the query image. Therefore, most traditional methods break down when images contain similar objects that are scaled differently or at different locations, or only certain regions of the image match. In this paper, we propose WALRUS (WAveLet-based Retrieval of User-specified Scenes), a novel similarity retrieval algorithm that is robust to scaling and translation of objects within an image. WALRUS employs a novel similarity model in which each image is first decomposed into its regions, and the similarity measure between a pair of images is then defined to be the fraction of the area of the two images covered by matching regions from the images. In order to extract regions for an image, WALRUS considers sliding windows of varying sizes and then clusters them based on the proximity of their signatures. An efficient dynamic programming algorithm is used to compute wavelet-based signatures for the sliding windows. Experimental results on real-life data sets corroborate the effectiveness of WALRUS's similarity model that performs similarity matching at a region rather than an image granularity.

REFERENCES

• BKSS90: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• DH73: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• FSN+95: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• GJ97: Amarnath Gupta , Ramesh Jain, Visual information retrieval, Communications of the ACM, v.40 n.5, p.70-79, May 1997 [doi>10.1145/253769.253798]
• GRT95: L.J. Guibas, B. Rogoff, and C. Tomasi. Fixedwindow image descriptors for image retrieval. In Storage and Retrieval for Image and Video Databases III, volume 2420 of SPIE Proceeding Series, pages 352-362, Feb. 1995. Available at http://vision, stanford.edu/public/publication/guibas/ guibas S rivd95, ps. gz.
• JFS95: Charles E. Jacobs , Adam Finkelstein , David H. Salesin, Fast multiresolution image querying, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.277-286, September 1995 [doi>10.1145/218380.218454]
• Nib93: W. Niblack et al. The qbic project: Query image by content using color, texture and shape. In Storage and Retrieval for Image and Video Databases, pa~;es 173-187, San Jose, 1993. SPIE.
• NRS98: P. Natsev, R. Rastogi, and K. Shim. WALRUS: A similarity matching algorithm for image databases. Technical report, Bell Laboratories, Murray Hill, 1998.
• PPS95: A. Pentland, R. W. Picard, and S. Sclaroff. Photobook: Content-based manipulation of image databases. In SPIE Storage and Retrieval Image and Video Databases H, San Jose, 1995.
• SDS96: Eric J. Stollnitz , Tony D. Derose , David H. Salesin, Wavelets for computer graphics: theory and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• Smi97: J.R. Smith. Integrated Spatial and Feature Image Systems: Retrieval Compression and Analysis. PhD thesis, Graduate School of Arts and Sciences, Columbia University, Feb. 1997. Available at http:flwww.ctr.columbia.edu/,-.,jrsmith/publications.html.
• WWFW98: James Ze Wang, Gio Wiederhold, Oscar Firschein, and Sha Xin Wei. Content-based image indexing and searching using daubechies' wavelets. Intl. Journal of Digital Libraries (IJODL), 1 (4):311-328, 1998. Available at http://wwwdb. stanford, edu/--.,zwang/proj ect/imsearch/IJODL97/.
• ZRL96: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Wavelets and fractals

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory