An efficient fast full search block matching algorithm using FFT algorithms
Fedwa Essannouni, Rachid Oulad, Haj Thami, A. Salam, Driss Aboutajdine · 2006
Summary Motion estimation is the most computationally expensive operation in the coding and transmitting of video streams, and the search for efficient motion estimation (in terms of computational complexity and compression efficiency) algorithm has been a challenging problem for years. The challenge is to decrease the computational complexity of the full search as much as possible without losing too much performance and quality at the output. In this paper, we propose a fast algorithm which achieves exactly the same optimal result as the direct full search algorithm. The key idea is to express a robust matching criteria sum square difference (SSD) in terms of cross correlation operations. Speed is obtained from computing the cross correlations in the frequency domain via the Fast Fourier Transform (FFT).