Scalable integrated region-based image retrieval using IRM and statistical clustering

ABSTRACT

Statistical clustering is critical in designing scalable image retriev al systems. In this paper, we present a scalable algorithm for indexing and retrieving images based on region segmentation. The method uses statistical clustering on region features and IRM (Integrated Region Matching), a measure developed to evaluate overall similarity between images that incorporates properties of all the regions in the images by a region-matching scheme. Compared with retrieval based on individual regions, our overall similarity approach (a) reduces the influence of inaccurate segmentation, (b) helps to clarify the semantics of a particular region, and (c) enables a simple querying interface for region-based image retrieval systems. The algorithm has been implemented as a part of our experimental SIMPLIcity image retrieval system and tested on large-scale image databases of both general-purpose images and pathology slides. Experiments have demonstrated that this technique maintains the accuracy and robustness of the original system while reducing the matching time significantly.

REFERENCES

• 1: 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
• 2: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 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: Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.1-12, May 11-15, 1997, Tucson, Arizona, United States
• 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: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 8: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 9: R. Finkel, J. Bentley, "Quad-trees: A data structure retrieval on composite keys," ACTA Informatica, vol. 4, no. 1, pp. 1-9, 1974.
• 10: 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]
• 11: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 12: J. A. Hartigan, M. A. Wong, "Algorithm AS136: a k-means clustering algorithm," Applied Statistics, vol. 28, pp. 100-108, 1979.
• 13: "Web surpasses one billion documents," Inktomi Corporation Press Release, January 18, 2000.
• 14: R. Jain, S. N. J. Murthy, P. L.-J. Chen, S. Chatterjee "Similarity measures for image databases", Proc. SPIE, vol. 2420, pp. 58-65, San Jose, CA, Feb. 9-10, 1995.
• 15: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 16: S. Lawrence, C.L. Giles, "Searching the World Wide Web," Science, vol. 280, pp. 98, 1998.
• 17: S. Lawrence, C.L. Giles, "Accessibility of information on the Web," Nature, vol. 400, pp. 107-109, 1999.
• 18: Jia Li , James Z. Wang , Gio Wiederhold, IRM: integrated region matching for image retrieval, Proceedings of the eighth ACM international conference on Multimedia, p.147-156, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.354452]
• 19: King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 20: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 21: W. Y. Ma , B. S. Manjunath, NeTra: a toolbox for navigating large image databases, Proceedings of the 1997 International Conference on Image Processing (ICIP '97) 3-Volume Set-Volume 1, p.568, October 26-29, 1997
• 22: Supporting Content-based Queries over Images in MARS, Proceedings of the 1997 International Conference on Multimedia Computing and Systems (ICMCS '97), p.632, June 03-06, 1997 [doi>10.1109/MMCS.1997.609791]
• 23: Sougata Mukherjea , Kyoji Hirata , Yoshinori Hara, AMORE: A World Wide Web image retrieval engine, World Wide Web, v.2 n.3, p.115-132, 1999 [doi>10.1023/A:1019248722478]
• 24: 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
• 25: W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, G. Taubin, "The QBIC project: querying images by content using color, texture, and shape," Proc. SPIE, vol. 1908, pp. 173-87, San Jose, February, 1993.
• 26: A. Pentland, R. W. Picard, S. Sclaroff, "Photobook: tools for content-based manipulation of image databases," Proc. SPIE, vol. 2185, pp. 34-47, San Jose, February 7-8, 1994.
• 27: R. W. Picard, T. Kabir, "Finding similar patterns in large image databases," Proc. IEEE ICASSP, Minneapolis, vol. V, pp. 161-64, 1993.
• 28: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 29: Y. Rubner, L. J. Guibas, C. Tomasi, "The earth mover's distance, Shimulti-dimensional scaling, and color-based image retrieval," Proc. ARPA Image Understanding Workshop, pp. 661-668, New Orleans, LA, May 1997.
• 30: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 31: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 32: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
• 33: J. R. Smith, S.-F. Chang, "An image and video search engine for the World-Wide Web," Proc. SPIE, vol. 3022, pp. 84-95, 1997.
• 34: John R. Smith , Chung-Sheng Li, Image classification and querying using composite region templates, Computer Vision and Image Understanding, v.75 n.1-2, p.165-174, July/Aug. 1999 [doi>10.1006/cviu.1999.0771]
• 35: Scott Stevens , Michael Christen , Howard Wactlar, Informedia: improving access to digital video, interactions, v.1 n.4, p.67-71, Oct. 1994 [doi>10.1145/194283.194311]
• 36: J. Z. Wang, G. Wiederhold, O. Firschein, X. W. Sha, "Content-based image indexing and searching using Daubechies' wavelets," International Journal of Digital Libraries, vol. 1, no. 4, pp. 311-328, 1998.
• 37: J. Z. Wang, J. Li, D. , G. Wiederhold, "Semantics-sensitive retrieval for digital picture libraries," D-LIB Magazine, vol. 5, no. 11, DOI:10.10 45/november99-wang, November, 1999. http://www.dlib.org
• 38: 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]
• 39: James Z. Wang , Jia Li , Robert M. Gray , Gio Wiederhold, Unsupervised Multiresolution Segmentation for Images with Low Depth of Field, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.1, p.85-90, January 2001 [doi>10.1109/34.899949]
• 40: James Z. Wang, Integrated Region-Based Image Retrieval, Kluwer Academic Publishers, Norwell, MA, 2001
• 41: 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

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering; Retrieval models

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Design, Documentation, Experimentation, Human Factors, Management, Measurement, Performance, Reliability, Theory

Keywords:
clustering, content-based image retrieval, integrated region matching, segmentaton, wavelets