Fast Image Alignment in the Fourier Domain

In this paper we propose a framework for gradient de-scent image alignment in the Fourier domain. Specifically, we propose an extension to the classical Lucas & Kanade (LK) algorithm where we represent the source and template image’s intensity pixels in the complex 2D Fourier domain rather than in the 2D spatial domain. We refer to this ap-proach as the Fourier LK (FLK) algorithm. The FLK for-mulation is especially advantageous, over traditional LK, when it comes to pre-processing the source and template im-ages with a bank of filters (e.g., Gabor filters) as: (i) it can handle substantial illumination variations, (ii) the ineffi-cient pre-processing filter bank step can be subsumed within the FLK algorithm as a sparse diagonal weighting matrix, (iii) unlike traditional LK the computational cost is invari-ant to the number of filters and as a result far more efficient, (iv) this approach can be extended to the inverse composi-tional form of the LK algorithm where nearly all steps (in-cluding Fourier transform and filter bank pre-processing) can be pre-computed leading to an extremely efficient and robust approach to gradient descent image matching. We demonstrate robust image matching performance on a va-riety of objects in the presence of substantial illumination differences with exactly the same computational overhead as that of traditional inverse compositional LK during fit-ting. 1