A unified framework for image database clustering and content-based retrieval

ABSTRACT

With the proliferation of image data, the need to search and retrieve images efficiently and accurately from a large image database or a collection of image databases has drastically increased. To address such a demand, a unified framework called <i>Markov Model Mediators</i> (MMMs) is proposed in this paper to facilitate conceptual database clustering and to improve the query processing performance by analyzing the summarized knowledge. The unique characteristics of MMMs are that it provides the capabilities of exploring the affinity relations among the images at the database level and among the databases at the cluster level respectively, using an effective data mining process. At the database level, each database is modeled by an intra-database MMM which enables accurate image retrieval within the database. Then the conceptual database clustering is performed and cluster-level knowledge summarization is conducted to reduce the cost of retrieving images across the databases. This framework has been tested using a set of image databases, which contain various numbers of images with different dimensions and concept categories. The experimental results demonstrate that our framework achieves better retrieval accuracy via inter-cluster retrieval than that of intra-cluster retrieval with minimal extra effort.

REFERENCES

• 1: Chad Carson , Serge Belongie , Hayit Greenspan , Jitendra Malik, Blobworld: Image Segmentation Using Expectation-Maximization and Its Application to Image Querying, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.8, p.1026-1038, August 2002 [doi>10.1109/TPAMI.2002.1023800]
• 2: Yixin Chen , James Z. Wang, A Region-Based Fuzzy Feature Matching Approach to Content-Based Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1252-1267, September 2002 [doi>10.1109/TPAMI.2002.1033216]
• 3: 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
• 4: Matthew Cooper , Jonathan Foote , Andreas Girgensohn , Lynn Wilcox, Temporal event clustering for digital photo collections, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957093]
• 5: Do, M. N. and Vetterli, M. Rotation Invariant Texture Characterization and Retrieval Using Steerable Wavelet-Domain Hidden Markov Models. IEEE Transactions on Multimedia, 4, 4 (Dec. 2002), 517--527.
• 6: 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]
• 7: 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]
• 8: Maria Halkidi , Yannis Batistakis , Michalis Vazirgiannis, On Clustering Validation Techniques, Journal of Intelligent Information Systems, v.17 n.2-3, p.107-145, December 2001 [doi>10.1023/A:1012801612483]
• 9: Feng Jing , Mingjing Li , Hong-Jiang Zhang , Bo Zhang, An effective region-based image retrieval framework, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641106]
• 10: Deok-Hwan Kim , Chin-Wan Chung, QCluster: relevance feedback using adaptive clustering for content-based image retrieval, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872829]
• 11: J. Banerjee , W. Kim , S.-J. Kim , J. F. Garza, Clustering a DAG for CAD Databases, IEEE Transactions on Software Engineering, v.14 n.11, p.1684-1699, November 1988 [doi>10.1109/32.9055]
• 12: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 13: Lu, G. Techniques and Data Structures for Efficient Multimedia Retrieval Based on Similarity. IEEE Transactions on Multimedia, 4, 3 (2002), 372-384.
• 14: Lu, Y. , Zhang, H. , Liu, W. , and Hu, C. Joint Semantics and Feature Based Image Retrieval Using Relevance Feedback. IEEE Transactions on Multimedia, 5, 3 (2003), 339--347.
• 15: Mao, J. and Jain, A. K. A Self-organizing Network for Hyperellipsoidal Clustering (hec). IEEE Transactions on Neural Networks, 7, 1 (1996), 16--29.
• 16: Apostol Natsev , Rajeev Rastogi , Kyuseok Shim, WALRUS: A Similarity Retrieval Algorithm for Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.16 n.3, p.301-316, March 2004 [doi>10.1109/TKDE.2003.1262183]
• 17: Rui, Y. , Huang, T. , Ortega, M. , and Mehrotra, S. Relevance Feedback: A Power Tool for Interactive Content-based Image Retrieval. IEEE Transactions on Circuit and Video Technology, 8, 5 (1998), 644--655.
• 18: Safar, M. , Shahabi, C. and Sun, X. Image Retrieval by Shape: A Comparative Study. In Proceedings of IEEE International Conference on Multimedia and Expo (ICME'00), 2000, 141--144.
• 19: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 20: Saux B. L. and Boujemaa N. Image Database Clustering with SVM-based Class Personalization. IS&T/SPIE Conference on Storage and Retrieval Methods and Applications for Multimedia, 2004.
• 21: Stan Sclaroff , Marco La Cascia , Saratendu Sethi, Unifying textual and visual cues for content-based image retrieval on the World Wide Web, Computer Vision and Image Understanding, v.75 n.1-2, p.86-98, July/Aug. 1999 [doi>10.1006/cviu.1999.0765]
• 22: Gholamhosein Sheikholeslami , Wendy Chang , Aidong Zhang, SemQuery: Semantic Clustering and Querying on Heterogeneous Features for Visual Data, IEEE Transactions on Knowledge and Data Engineering, v.14 n.5, p.988-1002, September 2002 [doi>10.1109/TKDE.2002.1033769]
• 23: Mei-Ling Shyu , Shu-Ching Chen , Min Chen , Chengcui Zhang, Affinity relation discovery in image database clustering and content-based retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027614]
• 24: Mei-Ling Shyu , Shu-Ching Chen , Min Chen , Chengcui Zhang , Kanoksri Sarinnapakorn, Image database retrieval utilizing affinity relationships, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA [doi>10.1145/951676.951691]
• 25: Shyu, M. -L. , Chen, S. -C. , and Haruechaiyasak, C. Mining User Access Behavior on the WWW. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, 2001, 1717--1722.
• 26: Shyu, M. -L. , Chen, S. -C. , Haruechaiyasak, C. , Shu, C. -M. , and Li, S. -T. Disjoint Web Document Clustering and Management in Electronic Commerce. In Proceedings of the Seventh International Conference on Distributed Multimedia Systems (DMS'2001), 2001, 494--497.
• 27: Shyu, M. -L. , Chen, S. -C. , and Kashyap, R. L. Organizing a Network of Databases Using Probabilistic Reasoning. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, 2000, 1990--1995.
• 28: Shyu, M. -L. , Chen, S. -C. , and Kashyap, R. L. A Probabilistic-Based Mechanism for Video Database Management Systems. In Proceedings of IEEE International Conference on Multimedia and Expo (ICME2000), 2000, 467--470.
• 29: Shyu, M. -L. , Chen, S. -C. , and Kashyap, R. L. Database Clustering and Data Warehousing. In Proceedings of the 1998 ICS Workshop on Software Engineering and Database Systems, 1998, 30-37.
• 30: Mei-Ling Shyu , Shu-Ching Chen , Chi-Min Shu, Affinity-Based Probabilistic Reasoning and Document Clustering on the WWW, 24th International Computer Software and Applications Conference, p.149-154, October 25-28, 2000
• 31: Shyu, M. -L. , Chen, S. -C. , and Rubin, S. H. Stochastic Clustering for Organizing Distributed Information Source. Accepted for publication, IEEE Transactions on Systems, Man and Cybernetics, Part B, 2004.
• 32: Renato O. Stehling , Mario A. Nascimento , Alexandre X. Falcão, On “shapes” of colors for content-based image retrieval, Proceedings of the 2000 ACM workshops on Multimedia, p.171-174, October 30-November 03, 2000, Los Angeles, California, United States [doi>10.1145/357744.361911]
• 33: Gerd Stumme , Rafik Taouil , Yves Bastide , Nicolas Pasquier , Lotfi Lakhal, Computing iceberg concept lattices with TITANIC, Data & Knowledge Engineering, v.42 n.2, p.189-222, August 2002 [doi>10.1016/S0169-023X(02)00057-5]
• 34: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 35: Hong Wu , Hanqing Lu , Songde Ma, A practical SVM-based algorithm for ordinal regression in image retrieval, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957144]
• 36: Keiji Yanai, Generic image classification using visual knowledge on the web, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957047]
• 37: Zhang, C. , Chen, S. -C. , and Shyu, M. -L. Multiple Object Retrieval for Image Databases Using Multiple Instance Learning and Relevance Feedback. In Proceedings of IEEE International Conference on Multimedia and Expo (ICME'04), 2004.
• 38: Zhang, D. S. and Lu, G. Generic Fourier Descriptors for Shape-based Image Retrieval. In Proceedings of IEEE International Conference on Multimedia and Expo (ICME'02), 1 (2002), 425--428.

INDEX TERMS

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

Additional Classification:
  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: Retrieval models

Keywords:
Markov model mediators (MMMs), content-based image retrieval (CBIR), image database clustering