A novel parallel motion estimation algorithm based on Particle Swarm Optimization

Motion estimation is a common tool used in all video coding standards. Fast and accurate algorithms are needed to target the real-time processing requirements of emerging applications. Many fast-search block motion estimation algorithms have been developed to reduce the computational cost required by the full-search algorithm. These techniques however often converge to a local minimum, which makes them subject to noise and matching errors. In the literature, several schemes were proposed to employ strategies of Particle Swarm Optimization (PSO) in the problem of motion estimation since PSO promises to alleviate the problem of being trapped in local minima. The existing schemes, however, still don´t achieve the necessary improvement in terms of accuracy or speedup as compared to the existing fast searching methods. In this paper, we propose a novel fast and accurate block motion estimation scheme based on an improved parallel Particle Swarm Optimization algorithm. Unlike existing motion estimation algorithms which operate on blocks of the frame serially following the raster order, the proposed algorithm achieves parallelism since it performs motion estimation for all blocks of the frame in parallel. Simulation results showed that the proposed scheme could provide a higher accuracy and a remarkable speedup as compared to the well-known fast searching techniques and to a recent PSO-based motion estimation algorithm.