A novel Cooperative Motion Estimation Algorithm based on Particle Swarm Optimization and its multicore implementation

• Collaboration between neighboring MBs is allowed during motion estimation.
• Cooperation between neighboring MBs allows refining motion vectors found so far.
• Temporal correlation used in PSO initialization removes dependency between MBs.
• The maximum allowed velocity of the PSO particles is adaptively varied.
• An efficient multi-core implementation using Matlab is presented.

A cooperative motion estimation (ME) scheme using a modified Particle Swarm Optimization (PSO) algorithm is presented. The proposed algorithm is based on a multi-swarm PSO model where a swarm of PSO particles is defined for each macroblock (MB) in the frame. Motion estimation is then performed in a cooperative manner concurrently for all the MBs in the frame. Cooperation between neighboring MBs during the motion estimation process is allowed through a communication step to exchange information about the motion vectors found so far in the estimation process. This synergic relationship between the swarms of adjacent MBs allows refining the motion search and leads to both a faster convergence of the PSO process and an improvement in the resulting motion vectors. Several techniques are also proposed to improve the search capacity and computational complexity of the PSO iterations. A novel PSO initialization scheme that exploits the existing temporal correlation is proposed to remove dependency between adjacent MBs. A fitness function history preservation mechanism is also presented to prevent redundant repeated calculations of the fitness function of a given search point by the PSO particles which dramatically decreases the computational complexity. Moreover, the maximum allowed velocity of the particles is adaptively varied during the PSO iterative process which provides a balance between search exploration and exploitation. The proposed scheme exhibits a high level of data parallelism since it is capable of performing motion estimation for all the MBs of the frame in parallel rather than serially. As a result, the presented algorithm is amenable to parallel processing techniques. In this paper, a multicore implementation of our proposed algorithm is performed using the MATLAB® Parallel Computing Toolbox™ (PCT). Extensive simulations are performed to analyze the performance of the presented algorithm. It is found that the presented scheme provides improvements in terms of accuracy and computational complexity as compared to conventional fast motion estimation techniques and two state-of-the-art PSO-based ME schemes. An analysis of the parallel performance shows that the presented scheme is highly scalable and that the parallel efficiency increases with the increase in video resolution. The multicore implementation of the proposed algorithm using MATLAB could achieve a speedup of 6.21 on eight CPU cores for high-definition (HD) video sequences. The multicore performance of the proposed scheme is also compared with existing parallel algorithms in the literature and is shown to give superior results.