Hexagon pattern particle swarm optimization based block matching algorithm for motion estimation / Siti Eshah Che Osman

Motion estimation in video compression process is computationally intensive for video encoder that involve a large percentage of processing time. Block Matching Algorithm (BMA) is a technique used to minimize the computational complexity of motion estimation in video coding application. Fixed search pattern technique is widely used in BMAs to provide less computations cost and improve prediction accuracy. Recently, intelligent searching methods were proposed to enhance the computational optimization issues in motion estimation but still lack in obtaining the best solution of block matching. Search pattern, search strategy and initial center are the main factors that contribute to the performance in the searching process. In this study, a pattern based using Particle Swarm Optimization (PSO) is proposed named as Hexagon PSO (HPSO). The proposed HPSO algorithm aims to obtain the least number of computations with low degradation value in estimation accuracy. This study is divided into several phases including preliminary study, experimental design, algorithm enhancement and result analysis. Initialization position of the particles is the first process in PSO and basically all particles are initialized at random position that may cause high computation risk. Due to the center biased nature of the videos, the HPSO algorithm uses an initial pattern (hexagon-shaped) to speed up the convergence of the algorithm. In this HPSO algorithm, totally seven particles positions are initialized. Zero Motion Prejudgment is implemented as an additional approach to speed up the searching process hence could reduce computation performance. The final results have proved that HPSO algorithm could achieve 5% - 34% of computation cost reduction with satisfying degradation value of image quality. In future, this work could be enhanced for better performances in both aspects using another variant of the PSO or other potential metaheuristic searching techniques such as Firefly Optimization, Bat Algorithm and etc.