| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
WALRUS: A Similarity Retrieval Algorithm for Image Databases
March 2004 (vol. 16 no. 3)
pp. 301-316
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.
[1] 301 TREC Video Retrieval Track. Available athttp://www-nlpir.nist. gov/projectstrecvid /.[2] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, The$R^{\ast}{\hbox{-}}{\rm{Tree}}$: An Efficient and Robust Access Method for Points and Rectangles Proc. ACM SIGMOD, pp. 322-331, May 1990.[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.[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.[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.[6] R.O. Duda and P.E. Hard, Pattern Classification and Scene Analysis. New York: Wiley-Interscience, 1973.[7] C. Faloutsos et al. Efficient and Effective Querying by Image Content J. Intelligent Information Systems, vol. 3, pp. 231-262, 1994.[8] 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, “Query by Image and Video Content: The QBIC System,” IEEE Computer, 1995.[9] A. Gupta and R. Jain, Visual Information Retrieval Comm. ACM, vol. 40, no. 5, pp. 69-79, 1997.[10] A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching Proc. ACM SIGMOD, pp. 47-57, June 1984.[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.[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, 1997.[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.[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.[18] H. Rowley, S. Baluja, and T. Kanade, "Neural Network-Based Face Detection," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 1, Jan. 1998, pp. 23-38.[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.[20] H. Samet, The Design and Analysis of Spatial Data Structures. New York: Addison-Wesley, 1990.[21] H. Schneiderman and T. Kanade, “Probabalistic Modeling of Local Appearance and Spatial Relationships for Object Recognition,” IEEE Conf. Computer Vision and Pattern Recognition, pp. 45-51, 1998.[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.[24] J.Z. Wang, J. Li, and G. Wiederhold, SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 9, pp. 947-963, Sept. 2001.[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.
Index Terms:
Wavelets, clustering, content-based retrieval, region matching, dynamic programming.
Citation:
Apostol Natsev, Rajeev Rastogi, Kyuseok Shim, "WALRUS: A Similarity Retrieval Algorithm for Image Databases," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 3, pp. 301-316, Mar. 2004, doi:10.1109/TKDE.2003.1262183
