GPCA: an efficient dimension reduction scheme for image compression and retrieval

ABSTRACT

Recent years have witnessed a dramatic increase in the quantity of image data collected, due to advances in fields such as medical imaging, reconnaissance, surveillance, astronomy, multimedia etc. With this increase has come the need to be able to store, transmit, and query large volumes of image data efficiently. A common operation on image databases is the retrieval of all images that are similar to a query image. For this, the images in the database are often represented as vectors in a high-dimensional space and a query is answered by retrieving all image vectors that are proximal to the query image in this space, under a suitable similarity metric. To overcome problems associated with high dimensionality, such as high storage and retrieval times, a dimension reduction step is usually applied to the vectors to concentrate relevant information in a small number of dimensions. Principal Component Analysis (PCA) is a well-known dimension reduction scheme. However, since it works with vectorized representations of images, PCA does not take into account the spatial locality of pixels in images. In this paper, a new dimension reduction scheme, called Generalized Principal Component Analysis (GPCA), is presented. This scheme works directly with images in their native state, as two-dimensional matrices, by projecting the images to a vector space that is the tensor product of two lower-dimensional vector spaces. Experiments on databases of face images show that, for the same amount of storage, GPCA is superior to PCA in terms of quality of the compressed images, query precision, and computational cost.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Charu C. Aggarwal, On the effects of dimensionality reduction on high dimensional similarity search, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.256-266, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.383213]
• 3: Charu C. Aggarwal, Hierarchical subspace sampling: a unified framework for high dimensional data reduction, selectivity estimation and nearest neighbor search, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564743]
• 4: P. Aigrain, H.J. Zhang, and D. Petkovic. Content-based representation and retrieval of visual media: A state-of-the-art review. Multimedia Tools and Applications, 3(3):179--202, 1996.
• 5: Vittorio Castelli , Alexander Thomasian , Chung-Sheng Li, CSVD: Clustering and Singular Value Decomposition for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.671-685, March 2003 [doi>10.1109/TKDE.2003.1198398]
• 6: H. Cho, I.S. Dhillon, Y. Guan, and S. Sra. Minimum sum-squared residue co-clustering of gene expression data. In SIAM Data Mining Conference proceedings, pages 114--125, 2004.
• 7: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 8: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 9: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 10: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 11: H. Jin, B. C. Ooi, H. T. Shen, C. Yu, and A.Y. Zhou. An adaptive and efficient dimensionality reduction algorithm for high-dimensionality indexing. In ICDE Conference Proceedings, Bangalore, India, 2003.
• 12: I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, 1986.
• 13: R. Ng and A. Sedighian. Evaluating multi-dimensional indexing structures for images transformed by principal component analysis. In Proc. of the SPIE, number 2670, pages 50--61, 1994.
• 14: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States
• 15: L. Sirovich and M. Kirby. Low-dimensional procedure for the characterization of human faces. Journal of Optical Society of America, 4(3):519--524, 1987.
• 16: M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1):71--86, 1991.
• 17: Jieping Ye, Generalized low rank approximations of matrices, Proceedings of the twenty-first international conference on Machine learning, p.112, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015347]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
dimension reduction, image compression, principal component analysis, singular value decomposition, tensor product, vector space