Hierarchical clustering of WWW image search results using visual, textual and link information

ABSTRACT

We consider the problem of clustering Web image search results. Generally, the image search results returned by an image search engine contain multiple topics. Organizing the results into different semantic clusters facilitates users' browsing. In this paper, we propose a hierarchical clustering method using visual, textual and link analysis. By using a vision-based page segmentation algorithm, a web page is partitioned into blocks, and the textual and link information of an image can be accurately extracted from the block containing that image. By using block-level link analysis techniques, an image graph can be constructed. We then apply spectral techniques to find a Euclidean embedding of the images which respects the graph structure. Thus for each image, we have three kinds of representations, i.e. visual feature based representation, textual feature based representation and graph based representation. Using spectral clustering techniques, we can cluster the search results into different semantic clusters. An image search example illustrates the potential of these techniques.

REFERENCES

• 1: AltaVista image search, http://www.altavista.com/image/
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: M. Belkin and P. Niyogi, "Laplacian eigenmaps and spectral techniques for embedding and clustering", Advances in Neural Information Processing Systems 14, Canada, 2001.
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: D. Cai, X. He, W.-Y. Ma, J.-R. Wen and H.-J. Zhang. "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.
• 6: Deng Cai , Xiaofei He , Ji-Rong Wen , Wei-Ying Ma, Block-level link analysis, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009068]
• 7: D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma, "VIPS: a vision-based page segmentation algorithm", Microsoft Technical Report, MSR-TR-2003-79, 2003.
• 8: Deng Cai , Shipeng Yu , Ji-Rong Wen , Wei-Ying Ma, Block-based web search, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009070]
• 9: Soumen Chakrabarti, Integrating the document object model with hyperlinks for enhanced topic distillation and information extraction, Proceedings of the 10th international conference on World Wide Web, p.211-220, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372054]
• 10: 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]
• 11: Charles Frankel , Michael J Swain , Vassilis Athitsos, WebSeer: An Image Search Engine for the World Wide Web, University of Chicago, Chicago, IL, 1996
• 12: Google image search engine, http://images.google.com/
• 13: Google Zeitgeist - Search patterns, trends, and surprises according to Google, (2004) http://www.google.com/press/zeitgeist.html
• 14: 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
• 15: X. He, D. Cai, J.-R. Wen, W.-Y. Ma and H.-J. Zhang, "ImageSeer: Clustering and Searching WWW Images Using Link and Page Layout Analysis", Microsoft Technical Report, MSR-TR-2004-38, 2004.
• 16: X. He, W.-Y. Ma, and H. J. Zhang, "ImageRank: spectral techniques for structural analysis of image database", IEEE International Conference on Multimedia and Expo, 2003.
• 17: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 18: Ronny Lempel , Aya Soffer, PicASHOW: pictorial authority search by hyperlinks on the Web, Proceedings of the 10th international conference on World Wide Web, p.438-448, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372098]
• 19: A. V. Leouski and B. Croft, An Evaluation of Techniques for Clustering Search Results. Technical Report IR-76, Computer Science Dept., University of Massachusetts, 1996.
• 20: B. S. Manjunath , W. Y. Ma, Texture Features for Browsing and Retrieval of Image Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.837-842, August 1996 [doi>10.1109/34.531803]
• 21: A. Y. Ng, M. Jordan, and Y. Weiss, "On spectral clustering: Analysis and an algorithm", Advances in Neural Information Processing Systems 14, Vancouver, Canada, 2001.
• 22: 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]
• 23: 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]
• 24: J. Smith and S.-F. Chang, "WebSEEK, a content-based image and video search and catalog tool for the web", IEEE Multimedia, 1997.
• 25: M. Stricker and M. Orengo, "Similarity of color images", Proc. Storage and Retrieval for Image and Video Databases,SPIE 2420, pp. 381--392, 1995.
• 26: Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]
• 27: H. Yu, M. Li, H.-J. Zhang, and J. Feng. Color texture moments for content-based image retrieval. In International Conference on Image Processing, pages 24--28. 2002.
• 28: Vivisimo clustering engine, (2004) http://vivisimo.com.
• 29: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Proceeding of the eighth international conference on World Wide Web, p.1361-1374, May 1999, Toronto, Canada

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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation; Retrieval models

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
        I.4.10 Image Representation
            Subjects: Statistical; Multidimensional

General Terms:
Algorithms, Design, Management, Theory

Keywords:
graph model, image clustering, link analysis, search result organization, spectral analysis, vision based page segmentation, web image search