Fast eigenspace decomposition of correlated images

We present a computationally efficient algorithm for the eigenspace decompo sition of correlated images. Our approach is motivated by the fact that for a planar rotation of a two-dimensional (2-D) image, analytical expressions can be given for the eigendecomposition, based on the theory of circulant matrices. These analytical expressions turn out to be good first approximat ions of the eigendecomposition, even for three-dimensional (3-D) objects ro tated about a single axis. In addition, the theory of circulant matrices yi elds good approximations to the eigendecomposition for images that result w hen objects are translated and scaled. We use these observations to automat ically determine the dimension of the subspace required to represent an ima ge with a guaranteed user-specified accuracy, as well as to quickly compute a basis for the subspace, Examples show that the algorithm performs very w ell on a number of test cases ranging from images of 3-D objects rotated ab out a single axis to arbitrary video sequences.