Abstract

This paper presents algorithms for efficiently computing the covariance matrix for features that form sub-windows in a large multi- dimensional image. For example, several image processing applications, e.g. texture analysis/synthesis, image retrieval, and compression, operate upon patches within an image. These patches are usually pro jected onto a low-dimensional feature space using dimensionality reduction techniques such as Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA), which in-turn requires computation of the covariance matrix from a set of features. Covariance computation is usually the bot- tleneck during PCA or LDA (O(nd2 ) where n is the number of pixels in the image and d is the dimensionality of the vector). Our approach reduces the complexity of covariance computation by exploiting the re- dundancy between feature vectors corresponding to overlapping patches. Specifically, we show that the covariance between two feature compo- nents can be reduced to a function of the relative displacement between those components in patch space. One can then employ a lookup table to store covariance values by relative displacement. By operating in the frequency domain, this lookup table can be computed in O(n log n) time. We allow the patches to sub-sample the image, which is useful for hier- archical processing and also enables working with filtered responses over these patches, such as local gist features. We also propose a method for fast pro jection of sub-window patches onto the low-dimensional space.