Clustered blockwise PCA for representing visual data.
Principal Component Analysis (PCA) is extensively used in computer vision and image processing. Since it provides the optimal linear subspace in a least-square sense, it has been used for dimensionality reduction and subspace analysis in various domains. However, its scalability is very limited because of its inherent computational complexity. We introduce a new framework for applying PCA to visual data which takes advantage of the spatio-temporal correlation and localized frequency variations that are typically found in such data. Instead of applying PCA to the whole volume of data (complete set of images), we partition the volume into a set of blocks and apply PCA to each block. Then, we group the subspaces corresponding to the blocks and merge them together. As a result, we not only achieve greater efficiency in the resulting representation of the visual data, but also successfully scale PCA to handle large data sets. We present a thorough analysis of the computational complexity and storage benefits of our approach. We apply our algorithm to several types of videos. We show that, in addition to its storage and speed benefits, the algorithm results in a useful representation of the visual data.
Nishino
Ko
K
Department of Computer Science, Columbia University, MC 0401, 1214 Amsterdam Avenue, New York, NY 10027, USA. kon@cs.columbia.edu
Nayar
Shree K
SK
Jebara
Tony
T
D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D015233:Models, Statistical; D010363:Pattern Recognition, Automated / Q000379:methods*; D025341:Principal Component Analysis