Fast exhaustive block-based motion vector estimation algorithm using FFT

In video processing, block motion estimation represents a CPU-intensive task. For this reason, many fast algorithms have been developed to improve searching and matching phases. These methods however work generally in the spatial domain. In this paper we propose to benefit from speed of the available FFT algorithms. The proposed algorithm computes the motion vector for two blocks using simultaneous two-dimensional cross correlations and use again the FFT to compute the sum square blocks in the frequency domain. Simulation results show that the proposed algorithm gives an optimal SSD (sum square differences) full search results while having a computational cost inferior to the classical fast block matching algorithms.