一种基于局部极值搜索的快速运动估计算法

摘要

A new method of motion estimation based on the search of the local extremum was proposed to reduce the time of motion estimation in the video encoding. Firstly, divided the search area into several parts according to the size of the search blocks; Secondly, started to find the local extremum of the search part in spiral way and compared it with the extremum ahead. In this step, early termination strategy and the algorithm of marking and skipping were proposed so as to further speed up the search. In the last, took the minimum value of the search parts as the global minimum and searched that part with the diamond pattern in the step of 1, which could get the perfect location. Test results show that compared with the UMH, the new method can improve the encoding speed but the PSNR increases less than 0.03 kb/s and the bitstream rate decreases less than 0.005 dB. What’s more, this method can reduce the encoding time by 10%compared with the UMH when encoding the video which has very high motion complexity.%为了减少运动估计在图像编码中所占用时间，提出了一种基于局部极值搜索的运动估计算法。首先根据搜索块的大小将搜索区域进行完全分割。然后从搜索原点进行螺旋扫描，确定扫描点所处分割区域的局部极小值位置，与前面极小值进行比较得到现阶段最小值。并根据一系列提前终止条件和标记跳过机制，在全局扫描的同时保持快速性。最后得到所有分割区域的最小值作为全局最小值，并进行步长为1的菱形细化搜索，确定最佳位置。实验表明，与UMH算法相比，该算法可在码率上升最大不超过0.03 kb/s、信噪比下降最大不超过0.005 dB的情况下提高编码速度，特别是对于中高运动复杂度图像的编码速度可比UMH算法提高10%左右，具有应用价值。