Image clustering with tensor representation

ABSTRACT

We consider the problem of image representation and clustering. Traditionally, an n1 x n2 image is represented by a vector in the Euclidean space ℝ ^{n1 x n2}. Some learning algorithms are then applied to these vectors in such a high dimensional space for dimensionality reduction, classification, and clustering. However, an image is intrinsically a matrix, or the second order tensor. The vector representation of the images ignores the spatial relationships between the pixels in an image. In this paper, we introduce a tensor framework for image analysis. We represent the images as points in the tensor space Rⁿ¹ mathcal Rⁿ² which is a tensor product of two vector spaces. Based on the tensor representation, we propose a novel image representation and clustering algorithm which explicitly considers the manifold structure of the tensor space. By preserving the local structure of the data manifold, we can obtain a tensor subspace which is optimal for data representation in the sense of local isometry. We call it TensorImage approach. Traditional clustering algorithm such as k-means is then applied in the tensor subspace. Our algorithm shares many of the data representation and clustering properties of other techniques such as Locality Preserving Projections, Laplacian Eigenmaps, and spectral clustering, yet our algorithm is much more computationally efficient. Experimental results show the efficiency and effectiveness of our algorithm.

REFERENCES

• 1: M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14, 2001.
• 2: 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]
• 3: F. R. K. Chung. Spectral Graph Theory, volume 92 of Regional Conference Series in Mathematics. 1997.
• 4: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 5: 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
• 6: Stephen Guattery , Gary L. Miller, Graph Embeddings and Laplacian Eigenvalues, SIAM Journal on Matrix Analysis and Applications, v.21 n.3, p.703-723, Feb.-March 2000 [doi>10.1137/S0895479897329825]
• 7: X. He and P. Niyogi. Locality preserving projections. Advances in Neural Information Processing Systems 16, 2003.
• 8: J. M. Lee. Introduction to Smooth Manifolds. Springer-Verlag New York, 2002.
• 9: J. Lim, J. Ho, M.-H. Yang, K.-C. Lee, and D. Kriegman. Image clustering with metric, local linear structure and affinity symmetry. In Proceedings of the European Conference on Computer Vision, 2004.
• 10: Xinguo Liu , Yizhou Yu , Heung-Yeung Shum, Synthesizing bidirectional texture functions for real-world surfaces, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.97-106, August 2001 [doi>10.1145/383259.383269]
• 11: L. Lovasz and M. Plummer. Matching Theory. Akadémiai Kiadó, North Holland, Budapest, 1986.
• 12: B. Mohar. Some applications of laplace eigenvalues of graphs. In In G. Hahn and G. Sabidussi, editors, Graph Symmetry: Algebraic Methods and Applications, 1997.
• 13: A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14, 2001.
• 14: J.-M. Odobez, D. Gatica-Perez, and M. Guillemot. Spectral structuring of home videos. In Proceedings of the 2nd International Conference on Image and Video Retrieval, July 2003.
• 15: J. C. Platt, M. Czerwinski, and B. A. Field. Phototoc: Automatic clustering for browsing personal photographs. In Fourth IEEE Pacific Rim Conference on Multimedia, Singapore, 2003.
• 16: S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, 2000.
• 17: 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]
• 18: J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.
• 19: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860485]
• 20: Xin Zheng , Deng Cai , Xiaofei He , Wei-Ying Ma , Xueyin Lin, Locality preserving clustering for image database, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027731]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.m Miscellaneous

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

Keywords:
dimensionality reduction, graph, image clustering, image representation, locality preserving projection, manifold, subspace learning, tensor