Fast Construction of Covariance Matrices for Arbitrary Size Image Windows

We propose an integral image based algorithm to extract feature covariance matrices of all possible rectangular regions within a given image. Covariance is an essential indicator of how much the deviation of two or more variables match. In our case, these variables correspond to point-wise features, e.g. coordinates, color values, gradients, edge magnitude and orientation, local histograms, filter responses, etc. We significantly improve the speed of the covariance computation by taking advantage of the spatial arrangement of image points using integral images, which are intermediate representations used for calculation of region sums. Each point of the integral image corresponds to the summation of all point values inside the feature image rectangle bounded by the upper left corner and the point of interest. Using this representation, any rectangular region sum can be computed in constant time. We follow a similar idea for fast calculation of region covariance. We construct integral images for all separate features as well as integral images of the multiplication of any two feature combinations. Using these set of integral images and region corner point coordinates, we directly extract the covariance matrix coefficients. We show that the proposed method reduces the computational load to quadratic time.