一种改进遗传搜索块匹配运动估计算法

运动估计是帧间视频编码中的关键技术,但现有的快速搜索算法中大都是次优算法,且易陷于局部极小点。针对此问题,提出了一种改进型遗传算法应用于块运动估计中的遗传搜索块匹配运动估计算法(MGSAME)。该方法把块运动向量作为遗传染色体,经过杂交、变异等操作,以便得到全局意义上的最优解,并与经典的全局搜索法、三步搜索法和传统遗传算法(SGA)进行了比较。实验结果显示,该算法不仅有效地解决了局部极小问题,而且计算量也较少。

A Modified Genetic Search Algorithm for Motion Estimation

Motion estimation is essential for many inter frame video coding techniques, block- matching algorithms, such as FSA and TSS, have been widely used for motion estimation. The easiest implementation is the FSA, which evaluates all the blocks in the search window and has the highest computational cost. Therefore, many fast search algorithm including TSS, have been proposed to reduce the computational complexity, but most of them are based on the assumption that there should be only one optimal solution in the search window, however, in normal cases, there always exist multitudinous local optima, so they will miss the global optima, but get a suboptimal solution. In this paper, we propose a modified genetic search algorithm for motion estimation(MGSAME) which ap- plies genetic operation to motion estimation. We also introduce a scheme called competition evolution, which can bring the better so- lutions into the next evolution, and can accelerate the iteration process converging. In this method, the motion vector of block is de- fined as chromosome, after crossover, mutation and competition evolution, the global optimal solutions will be got. Lastly, we compare the MGASME to TSS,FSA and Simple Genetic Algorithm- SGA, and the result shows that the method not only solve the problem of being trapped to local optima, but also have speed close to that of TSS.