Partial eigenvalue decomposition for large image sets using run-length encoding

摘要

Pattern recognition using eigenvectors is a recent active research area. Finding eigenvectors of a large image set, however, has been considered to require too much computation to be practical. We therefore propose a new method for reducing computation of the partial eigenvalue decomposition based on run-length encoding. In this method, called the constant regions method, spatial encoding is used to reduce storage and computation, then coeigenvectors are computed and later converted to eigenvectors. For simple images, and when the number of pixels in an image is much larger than the number of images, the resulting algorithm is shown to grow as the first power of the basic image dimension, rather than the fourth power as for conventional methods. For comparison, the power method, the conjugate gradient method, and a so-called direct method for computing the partial eigenvalue decomposition are also presented, and recommendations are given for when each method should be used. The advantage of the proposed method are verified by tests in which the first several eigenvectors are computed for sets of images having varying complexity. This algorithm is useful for a research area of pattern recognition using eigenvectors.