Adjustable SAD matching algorithm using frequency domain

Fast Fourier transforms (FFTs) which are O(N logN) algorithms to compute a discrete Fourier transform (DFT) of size N have been called one of the ten most important algorithms of the twentieth century. However, even though many algorithms have been developed to speed up the computation the sum of absolute difference (SAD) matching, they are exclusively designed in the spatial domain. In this paper, we propose a fast frequency algorithm to speed up the process of (SAD) matching. We use a new approach to approximate the SAD metric by cosine series which can be expressed in correlation terms. These latter can be computed using FFT algorithms. Experimental results demonstrate the effectiveness of our method when using only the first correlation terms for block and template matching in terms of accuracy and speed. The proposed algorithm is suitable for software implementations and has a deterministic execution time unlike the existing fast algorithms for SAD matching.