research-article

WALRUS: A Similarity Retrieval Algorithm for Image Databases

Authors:

Apostol Natsev,

Rajeev Rastogi,

Kyuseok ShimAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 16, Issue 3

Pages 301 - 316

https://doi.org/10.1109/TKDE.2003.1262183

Published: 01 March 2004 Publication History

Abstract

Abstract--Approaches for content-based image querying typically extract a single signature from each image based on color, texture, or shape features. The images returned as the query result are then the ones whose signatures are closest to the signature of the query image. While efficient for simple images, such methods do not work well for complex scenes since they fail to retrieve images that match the query only partially, that is, only certain regions of the image match. This inefficiency leads to the discarding of images that may be semantically very similar to the query image since they may contain the same objects. The problem becomes even more apparent when we consider scaled or translated versions of the similar objects. 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.

References

[1]

TREC Video Retrieval Track. Available at http://www-nlpir.nist. gov/projects/trecvid/.]]

[2]

N. Beckmann H.-P. Kriegel R. Schneider and B. Seeger, “The R<sup>*</sup>-Tree: An Efficient and Robust Access Method for Points and Rectangles,” Proc. ACM SIGMOD, pp. 322-331, May 1990.]]

Digital Library

[3]

C. Carson M. Thomas S. Belongie J.M. Hellerstein and J. Malik, “Blobworld: A System for Region-Based Image Indexing and Retrieval,” Proc. Third Int'l Conf. Visual Information Systems, June 1999.]]

Digital Library

[4]

M. Das R. Manmatha and E.M. Riseman, “Indexing Flowers by Color Names Using Domain Knowledge-Driven Segmentation,” IEEE Intelligent Systems, vol. 14, no. 5, pp. 24-33, 1999.]]

Digital Library

[5]

M. Das E.M. Riseman and B.A. Draper, “ FOCUS: Searching for Multi-Colored Objects in a Diverse Image Database,” Proc. IEEE Conf. Computer Vision and Pattern Recgonition (CVPR '97), pp. 756-761, June 1997.]]

Digital Library

[6]

R.O. Duda and P.E. Hard, Pattern Classification and Scene Analysis. New York: Wiley-Interscience, 1973.]]

Digital Library

[7]

C. Faloutsos, et al. “Efficient and Effective Querying by Image Content,” J. Intelligent Information Systems, vol. 3, pp. 231-262, 1994.]]

Digital Library

[8]

M. Flickner H. Sawhney W. Niblack J. Ashley B. Dom Q. Huang M. Gorkani J. Hafner D. Lee D. Petkovic D. Steele and P. Yanker, “Query by Image and Video Content: The Gbic System,” Computer, vol. 28, no. 9, pp. 23-32, Sept. 1995.]]

Digital Library

[9]

A. Gupta and R. Jain, “Visual Information Retrieval,” Comm. ACM, vol. 40, no. 5, pp. 69-79, 1997.]]

Digital Library

[10]

A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” Proc. ACM SIGMOD, pp. 47-57, June 1984.]]

Digital Library

[11]

C.E. Jacobs A. Finkelstein and D.H. Salesin, “Fast Multiresolution Image Querying,” Proc. SIGGRAPH '95, Ann. Conf. Series, pp. 277-286, Aug. 1995.]]

Digital Library

[12]

A. Lakshmi-Ratan O. Maron W.E.L. Grimson and T. Lozano-Perez, “A Framework for Learning Query Concepts in Image Classification,” Proc. IEEE Computer Vision and Pattern Recognition (CVPR '99), vol. I, pp. 423-429, 1999.]]

[13]

W.Y. Ma and B.S. Manjunath, “NETRA: A Toolbox for Navigating Large Image Databases,” Proc. IEEE Int'l Conf. Image Processing, vol. I, pp. 568-571, Oct. 1997.]]

Digital Library

[14]

A. Natsev R. Rastogi and K. Shim, “WALRUS: A Similarity Retrieval Algorithm for Image Databases,” Proc. ACM SIGMOD Int'l Conf. Management of Data, pp. 395-406, May 1999.]]

Digital Library

[15]

W. Niblack, et al. “The Gbic Project: Query Image by Content Using Color, Texture, and Shape,” Storage and Retrieval for Image and Video Databases, pp. 173-187, 1993.]]

[16]

A. Pentland R.W. Picard and S. Sclaroff, “Photobook: Content-Based Manipulation of Image Databases,” SPIE Storage and Retrieval Image and Video Databases II, 1995.]]

[17]

S. Ravela and R. Manmatha, “Retrieving Images by Similarity of Visual Appearance,” Proc. IEEE Workshop Content Based Access of Images and Videos (CAIVL '97), pp. 67-74, June 1997.]]

Digital Library

[18]

H.A. Rowley S. Baluja and T. Kanade, “Neural Network-Based Face Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 1, pp. 23-38, Jan. 1998.]]

Digital Library

[19]

Y. Rubner C. Thomasi and L. Guibas, “A Metric for Distributions with Applications to Image Databases,” Proc. IEEE Int'l Conf. Computer Vision (ICCV '98), pp. 59-66, Jan. 1998.]]

Digital Library

[20]

H. Samet, The Design and Analysis of Spatial Data Structures. New York: Addison-Wesley, 1990.]]

Digital Library

[21]

H. Schneiderman and T. Kanade, “Probabilistic Modeling of Local Appearance and Spatial Relationship for Object Recognition,” Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR '98), pp. 45-51, 1998.]]

Digital Library

[22]

J.R. Smith, “Integrated Spatial and Feature Image Systems: Retrieval, Compression and Analysis,” PhD thesis, Graduate School of Arts and Sciences, Columbia Univ., Feb. 1997.]]

[23]

E.J. Stollnitz T.D. DeRose and D.H. Salesin, Wavelets for Computer Graphics: Theory and Applications. Morgan Kaufmann, 1996.]]

Digital Library

[24]

J.Z. Wang J. Li and G. Wiederhold, “SIMPLIcity: Semantic-Sensitive Integrated Matching for Picture Libraries,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 9, Sept. 2001.]]

Digital Library

[25]

J.Z. Wang G. Wiederhold O. Firschein and S.X. Wei, “Content-Based Image Indexing and Searching Using Daubechies' Wavelets,” Int'l J. Digital Libraries (IJODL), vol. 1, no. 4, pp. 311-328, 1998.]]

[26]

T. Zhang R. Ramakrishnan and M. Livny, “Birch: An Efficient Data Clustering Method for Very Large Databases,” Proc. ACM SIGMOD Conf. Management of Data, pp. 103-114, June 1996.]]

Digital Library

Cited By

Gnanasivam PSudhakar M(2020)Extremely adaptive image retrieval scheme employing an optimized wavelet technique intended for characterization mapsMultimedia Tools and Applications10.1007/s11042-020-09515-z79:41-42(30419-30438)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11042-020-09515-z
Maheswari V UPrasad GRaju S(2018)A Survey on Local Textural Patterns for Facial Feature ExtractionInternational Journal of Computer Vision and Image Processing10.4018/IJCVIP.20180401018:2(1-26)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJCVIP.2018040101
Su CChen J(2015)Reconfigurable content-based image retrieval on peer-to-peer networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2015.06778518:1/2(23-36)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1504/IJAHUC.2015.067785
Show More Cited By

Index Terms

WALRUS: A Similarity Retrieval Algorithm for Image Databases
1. Information systems
  1. Information retrieval
  2. Information systems applications
    1. Data mining
      1. Clustering
    2. Multimedia information systems
      1. Multimedia databases
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

WALRUS: a similarity retrieval algorithm for image databases

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 ...
WALRUS: a similarity retrieval algorithm for image databases
SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data

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 ...
Learning-based linguistic indexing of pictures with 2--d MHMMs
MULTIMEDIA '02: Proceedings of the tenth ACM international conference on Multimedia

Automatic linguistic indexing of pictures is an important but highly challenging problem for researchers in computer vision and content-based image retrieval. In this paper, we introduce a statistical modeling approach to this problem. Categorized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 16, Issue 3

March 2004

95 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 2004 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 March 2004

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gnanasivam PSudhakar M(2020)Extremely adaptive image retrieval scheme employing an optimized wavelet technique intended for characterization mapsMultimedia Tools and Applications10.1007/s11042-020-09515-z79:41-42(30419-30438)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11042-020-09515-z
Maheswari V UPrasad GRaju S(2018)A Survey on Local Textural Patterns for Facial Feature ExtractionInternational Journal of Computer Vision and Image Processing10.4018/IJCVIP.20180401018:2(1-26)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.4018/IJCVIP.2018040101
Su CChen J(2015)Reconfigurable content-based image retrieval on peer-to-peer networksInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2015.06778518:1/2(23-36)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1504/IJAHUC.2015.067785
Zhang QIzquierdo E(2013)Multifeature analysis and semantic context learning for image classificationACM Transactions on Multimedia Computing, Communications, and Applications10.1145/2457450.24574549:2(1-20)Online publication date: 10-May-2013
https://dl.acm.org/doi/10.1145/2457450.2457454
Erdös DIshakian VLapets ATerzi EBestavros A(2012)The filter-placement problem and its application to minimizing information multiplicityProceedings of the VLDB Endowment10.14778/2140436.21404395:5(418-429)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.14778/2140436.2140439
Xie BMu YSong MTao D(2010)Random projection tree and multiview embedding for large-scale image retrievalProceedings of the 17th international conference on Neural information processing: models and applications - Volume Part II10.5555/1939751.1939837(641-649)Online publication date: 22-Nov-2010
https://dl.acm.org/doi/10.5555/1939751.1939837
Singh VBhattacharya ASingh A(2010)Querying spatial patternsProceedings of the 13th International Conference on Extending Database Technology10.1145/1739041.1739092(418-429)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1739041.1739092
Shen J(2009)Stochastic modeling western paintings for effective classificationPattern Recognition10.1016/j.patcog.2008.04.01642:2(293-301)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1016/j.patcog.2008.04.016
Chiang TTsai T(2008)Querying color images using user-specified wavelet featuresKnowledge and Information Systems10.5555/3225636.322578615:1(109-129)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.5555/3225636.3225786
Datta RJoshi DLi JWang J(2008)Image retrievalACM Computing Surveys10.1145/1348246.134824840:2(1-60)Online publication date: 8-May-2008
https://dl.acm.org/doi/10.1145/1348246.1348248
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents