Fast block matching algorithms using frequency domain

Translational template matching addresses the registration problem and has long been a problem of interest in such areas as video compression, robot vision, and biomedical engineering. In this paper, we will present new fast algorithms developed in our group for template and block matching purposes using either second or higher order statistics. Fast Fourier transforms (FFTs) have been called one of the ten most important algorithms of the twentieth century. Using some substitutions and complex arithmetic, computation of the sum square differences sum absolute difference and sum fourth order moment are derived to be correlation functions of substituting functions. The former can be computed using the fast Fourier transform (FFT) approach, which is greatly less computationally expensive than the direct computation. The performance of the proposed methods, as well as some illustrative comparisons with other matching algorithms in the literature, are verified through simulations. The algorithm based on the higher order moment is seen to have better performance in terms of fastness and robustness even in low SNR meanwhile the extra computational cost is negligible.