Image clustering based on a shared nearest neighbors approach for tagged collections

ABSTRACT

Browsing and finding pictures in large-scale and heterogeneous collections is an important issue, most particularly for online photo sharing applications. Since such services are experiencing rapid growth of their databases, the tag-based indexing strategy and the results displayed in a traditional matrix representation may not be optimal for browsing and querying image collections. Naturally, unsupervised data clustering appeared as a good solution by presenting a summarized view of an image set instead of an exhaustive but useless list of its element. We present a new method for extracting meaningful and representative clusters based on a shared nearest neighbors (SNN) approach that treats both content-based features and textual descriptions (tags). We describe, discuss and evaluate the SNN method for image clustering and present some experimental results using the Flickr collections showing that our approach extracts representative information of an image set.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: Csurka, G., Dance C.R., Fan, L., Willamowski, J., Bray C., Visual categorization with bags of keypoints. In Proc. of ECCV Workshop on Statistical Learning in Computer Vision, pages 1--22, 2004
• 5: Ertoz, L., Steinback, M., Kumar, V. Finding clusters of different size, shapes and densities in noisy, high dimensional data, SIAM International Conference on Data Mining (SDM '03). 2003
• 6: Ertoz, L., Steinback, M., Kumar, V. Finding topics in documents, a shared nearest neighbors approach. Clustering and Information Retrieval, Kluwer Academic Publishers. 2002
• 7: Goldberger, J., Gordon, S., Greenspan, H. Unsupervised image-set clustering using an information theoretic framework. IEEE Trans. on Image Processing, 15(2):449--458, 2006
• 8: Hegland, M. Data mining, challenges, models, methods and algorithms, 2003
• 9: Irving Hofman , Ray Jarvis, Robust and Efficient Cluster Analysis Using a Shared Near Neighbours Approach, Proceedings of the 14th International Conference on Pattern Recognition-Volume 1, p.243, August 16-20, 1998
• 10: Eva Hörster , Rainer Lienhart , Malcolm Slaney, Image retrieval on large-scale image databases, Proceedings of the 6th ACM international conference on Image and video retrieval, p.17-24, July 09-11, 2007, Amsterdam, The Netherlands [doi>10.1145/1282280.1282283]
• 11: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 12: R. A. Jarvis , E. A. Patrick, Clustering Using a Similarity Measure Based on Shared Near Neighbors, IEEE Transactions on Computers, v.22 n.11, p.1025-1034, November 1973 [doi>10.1109/T-C.1973.223640]
• 13: Lyndon S. Kennedy , Mor Naaman, Generating diverse and representative image search results for landmarks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367539]
• 14: Svetlana Lazebnik , Cordelia Schmid , Jean Ponce, Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2169-2178, June 17-22, 2006 [doi>10.1109/CVPR.2006.68]
• 15: Liao, W.K., A parallel K-Means data clustering: www.ece.northwestern.edu/~wkliao/Kmeans/index.html
• 16: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 17: Mathieu, B., Besancon, R., Fluhr, C. Multilingual document clusters discovery, Recherche d'Information Assistée par Ordinateur, RIAO'2004, 1--10. Avignon, France, 2004
• 18: Simon, I., Snavely, N., Seitz, S.M. Scene Summarization for Online Image Collections, ICCV 2007, Rio de Janeiro, Brazil, Ocotber 14-20, 2007
• 19: Sivic, J. Efficient visual search of images and videos, PhD thesis (2006), University of Oxford
• 20: Sergios Theodoridis , Konstantinos Koutroumbas, Pattern Recognition, Third Edition, Academic Press, Inc., Orlando, FL, 2006
• 21: Wang, H.B., Yu, Y.Q., Zhou, D.R., Meng B. Fuzzy nearest neighbor clustering of high-dimensional data, International Conference on Machine Learning and Cybernetics, 2003 , Vol.4, 2569--2572. Nov. 2003
• 22: 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]
• 23: Shuo Wang , Feng Jing , Jibo He , Qixing Du , Lei Zhang, IGroup: presenting web image search results in semantic clusters, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240718]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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

General Terms:
Algorithms, Experimentation

Keywords:
information retrieval and browsing, multimedia indexing, unsupervised data categorization