A Novel Coarse-to-Fine Search Algorithm for Motion Estimation

This paper presents a new algorithm which outperforms full search block matching algorithm (FSBMA) and other fast search block-matching motion estimation (FBMME) algorithms in terms of improved subjective and objective quality, reduction in computational complexity, increase in speed up factor and low bit rate. Here, unlike FSBMA, a coarse-to-fine search approach is chosen to find the motion vector whereby complexity of motion estimation is greatly reduced. The coarse search sees to that the search will never be caught at a local minimum, as that was the case in many FBMME. The fine search assures the exact location of the global minimum. Pixel sub-sampling is performed in the selected candidate blocks which significantly reduces computational cost with low quality degradation. A new evaluation function is introduced which further reduces the computational complexity. Simulation results have proved the effectiveness of the proposed algorithm for low, medium and high motion sequences.