A Multi-Resolution Approach For Calculating Primary Eigenvectors Of a Large Set of Images

Ren-Cang Li
Department of Mathematics
University of Kentucky
705 Patterson Office Hall
Lexington, KY 40506--0027, USA


Eigenvector analysis is used extensively in image processing, pattern matching, and machine vision. Often the involved matrices are huge and dense, and consequently computing those primary eigenvectors of interest can be too expensive to be practical. We propose here a multi-resolution algorithm for calculating primary eigenvectors of a large set of high resolution images. The algorithm systematically coarsens images to create a multi- resolution hierarchy of the image set. Then it computes directly co-eigenvectors for the coarsest images in the hierarchy and refines them to approximate those for the next coarsest images and works its way up, and finally it recovers primary eigenvectors for the original images from their approximate co- eigenvectors just computed. The algorithm gains substantial speedups over the often used SVD approach (3 to 10 speedups observed numerically) and is expected to run even faster as the underlying images' resolution gets higher.
Our approach can be combined with wavelet compression techniques to further speedup eigenvector computations considerably. This, together with other issues that need further investigations will be discussed.

Return to Numerical Analysis and Scientific Computing Seminar.