基于半八边形模板的运动估计算法

Half-octagon-based Search Pattern for Fast Block Motion Estimation Algorithm

H.264视频编码标准中,运动估计占用了编码器极大的运算量.针对H.264快速块匹配,本文提出了一种基于半八边形搜索模板的运动估计算法.该方法使用一个十字形模板来预测搜索方向,依据绝对差和(Sum of Absolute Differences,SAD)分布的方向性自适应地选取半八边形模板进行搜索,在搜索过程中,判断SAD值下降最快的方向精确定位匹配点,减少搜索点之间的冗余,提高搜索速度.理论分析表明该算法同经典六边形算法相比可以减少搜索点数.实验结果显示,在重建图像质量接近全搜索的同时,新算法减少了运动估计20%–30%的运算量.

Motion estimation is quite computationally intensive in H.264 video-coding standard. In this paper, a novel block-matching motion estimation algorithm applying half octagon based on search pattern （HOCTS） is presented. The initial small cross search pattern is designed to predict the search direction. Half octagon patterns are adaptively selected and determine the fastest drop direction to locate precisely the best matching point during the search according to the distribution direction character of Sum of Absolute （SAD）, and the search speed can be greatly improved with the decrease of redundancy of search points. Analysis shows that the HOCTS algorithm can seek the same motion vector with fewer search points than the hexagon Mgorithm. Numerical results show that the proposed algorithm provides similar prediction quality to the full search algorithm, and the motion estimation computation decreased by 20%-30% to hexagon algorithm.