Fast Covariance Computation and Dimensionality Reduction for Sub-Window Features in Images
Venue
European Conference on Computer Vision (ECCV 2010)
Publication Year
2010
Authors
BibTeX
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 projected 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 bottleneck
during PCA or LDA (O(nd^2) 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 redundancy between feature vectors
corresponding to overlapping patches. Specifically, we show that the covariance
between two feature components 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 hierarchical processing
and also enables working with filtered responses over these patches, such as local
gist features. We also propose a method for fast projection of sub-window patches
onto the low-dimensional space.
