Web image clustering by consistent utilization of visual features and surrounding texts

ABSTRACT

Image clustering, an important technology for image processing, has been actively researched for a long period of time. Especially in recent years, with the explosive growth of the Web, image clustering has even been a critical technology to help users digest the large amount of online visual information. However, as far as we know, many previous works on image clustering only used either low-level visual features or surrounding texts, but rarely exploited these two kinds of information in the same framework. To tackle this problem, we proposed a novel method named consistent bipartite graph co-partitioning in this paper, which can cluster Web images based on the consistent fusion of the information contained in both low-level features and surrounding texts. In particular, we formulated it as a constrained multi-objective optimization problem, which can be efficiently solved by semi-definite programming (SDP). Experiments on a real-world Web image collection showed that our proposed method outperformed the methods only based on low-level features or surround texts.

REFERENCES

• 1: Bach, F.R., and Jordan, M.I. Learning spectral clustering. Neural Info. Processing Systems 16 (NIPS 2003), 2003.
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: H. P. Benson, Global optimization algorithm for the nonlinearsum of ratios problem, Journal of Optimization Theory and Applications, v.112 n.1, p.1-29, January 2002 [doi>10.1023/A:1013072027218]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Deng Cai , Xiaofei He , Zhiwei Li , Wei-Ying Ma , Ji-Rong Wen, Hierarchical clustering of WWW image search results using visual, textual and link information, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027747]
• 6: Cai, D., He, X., Ma, W., Wen, J., and Zhang, H. Organizing WWW Images Based on The Analysis of Page Layout and Web Link Structure. In the 2004 IEEE International Conference on Multimedia and EXPO, 2004.
• 7: Chang, T., and Kuo, C. -CJ. Texture analysis and classification with tree-structured wavelet transform. IEEE Transactions on Image Processing, 2, 4(Oct. 1993), 429--441.
• 8: Yixin Chen , James Z. Wang , Robert Krovetz, Content-based image retrieval by clustering, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California [doi>10.1145/973264.973295]
• 9: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 10: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 11: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 12: Dumais, S.T. Latent semantic analysis. Annual Review of Information Science and Technology (ARIST), Volume 38, Chapter 4, 189--230, 2004.
• 13: Frenk, J.B.G., and Schaible, S. Fractional Programming. ERIM Report Series Reference No. ERS-2004-074-LIS. http://ssrn.com/abstract=595012.
• 14: Bin Gao , Tie-Yan Liu , Guang Feng , Tao Qin , Qian-Sheng Cheng , Wei-Ying Ma, Hierarchical Taxonomy Preparation for Text Categorization Using Consistent Bipartite Spectral Graph Copartitioning, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1263-1273, September 2005 [doi>10.1109/TKDE.2005.147]
• 15: Bin Gao , Tie-Yan Liu , Xin Zheng , Qian-Sheng Cheng , Wei-Ying Ma, Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081879]
• 16: Golub, G.H., and Loan, C.F.V. Matrix computations. Johns Hopkins University Press, 3rd edition, 1996.
• 17: Alex A. Freitas, A critical review of multi-objective optimization in data mining: a position paper, ACM SIGKDD Explorations Newsletter, v.6 n.2, December 2004 [doi>10.1145/1046456.1046467]
• 18: Shiri Gordon , Hayit Greenspan , Jacob Goldberger, Applying the Information Bottleneck Principle to Unsupervised Clustering of Discrete and Continuous Image Representations, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.370, October 13-16, 2003
• 19: Hagen, L., and Kahng, A.B. New spectral methods for ratio cut partitioning and clustering. IEEE. Trans. on Computed Aided Desgin, 11:1074--1085, 1992.
• 20: M. La Cascia , S. Sethi , S. Sclaroff, Combining Textual and Visual Cues for Content-Based Image Retrieval on the World Wide Web, Proceedings of the IEEE Workshop on Content - Based Access of Image and Video Libraries, p.24, June 21-21, 1998
• 21: Zhiwei Li , Gu Xu , Mingjing Li , Wei-Ying Ma , Hong-Jiang Zhang, Grouping WWW Image Search Results by Novel Inhomogeneous Clustering Method, Proceedings of the 11th International Multimedia Modelling Conference (MMM'05), p.255-261, January 12-14, 2005 [doi>10.1109/MMMC.2005.47]
• 22: Jianchang Mao , Anil K. Jain, Texture classification and segmentation using multiresolution simultaneous autoregressive models, Pattern Recognition, v.25 n.2, p.173-188, Feb. 1992 [doi>10.1016/0031-3203(92)90099-5]
• 23: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 24: Guoping Qiu, Image and Feature Co-Clustering, Proceedings of the Pattern Recognition, 17th International Conference on (ICPR'04) Volume 4, p.991-994, August 23-26, 2004 [doi>10.1109/ICPR.2004.468]
• 25: Kerry Rodden , Wojciech Basalaj , David Sinclair , Kenneth Wood, Does organisation by similarity assist image browsing?, Proceedings of the SIGCHI conference on Human factors in computing systems, p.190-197, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365097]
• 26: Semidefinite Programming. http://www-user.tu-chemnitz.de/~helmberg/semidef.html.
• 27: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 28: Hongyuan Zha , Xiaofeng He , Chris Ding , Horst Simon , Ming Gu, Bipartite graph partitioning and data clustering, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502591]
• 29: Zhao, R. and Grosky, W.I. Narrowing the Semantic Gap - Improved Text-Based Web Document Retrieval Using Visual Features. IEEE Transactions on Multimedia, Vol. 4, No. 2, June 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

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

Keywords:
co-clustering, consistency, image processing, spectral graph