AVS的自适应提前终止运动估计算法

王园园，张 刚，李付江

(太原理工大学信息工程学院，山西 太原 030024)

责任编辑:哈宏疆

AVS(Advanced Video Standard)标准［1］，是我国自主研发的视频压缩标准。AVS视频编码主要包括运动估计、DCT变换、量化、扫描、熵编码等模块。由于运动估计采用了高精度的运动矢量，使得运算量大幅增加，因此，缩短运动估计时间是提高AVS视频编码实时性的重要内容。运动估计研究主要分两个方向:一是整像素运动估计［2-4］，参考文献［5］中根据中心偏移特性提出了在起始搜索点预测中加入原点预测;另一个是亚像素运动估计［1］。本文针对UMHexagonS搜索算法提出了搜索的提前终止判断以及SAD计算的提前结束条件判断，提高了最佳匹配块的搜索速度;在模式选择中提出了代价值的提前比较，有效减小了搜索量。

1 AVS运动估计过程

在视频编码中，帧间预测编码就是找出每个编码块在邻近帧中的位置，并得到两者空间位置的相对偏移量即运动矢量。运动估计就是得到运动矢量的过程［6］。在AVS标准中帧间预测模式有5种:skip模式、16×16模式、16×8模式、8×16模式和8×8模式。运动估计过程分为运动搜索和模式选择两个步骤。

AVS的运动搜索主要是基于块的搜索，在搜索算法中，经典的UMHexagonS搜索算法是通过多种搜索模型的混合使用［7］，得到比较准确的最佳匹配块，运算量也相对较小。每种搜索模型搜索得到的SAD的最小值记为min_sad，SAD阈值的上限和下限记为threshold1和threshold2。UMHexagonS搜索算法主要流程如图1所示。

除skip预测模式外，每种预测模式通过运动搜索得到最佳匹配块后，按16×16模式、8×8模式、16×8模式和8×16模式顺序分别得到各种模式的代价值，逐一进行比较，代价取值最小的预测模式即为当前块的最佳预测模式。

2 运动估计算法优化

2.1 运动估计分析

经过深入的研究发现，UMHexagonS搜索算法和模式选择仍存在以下4点不足:

1)SAD阈值是固定的，使得运动剧烈的视频序列过早终止搜索，运动缓慢的视频序列不能很好地提前结束搜索。

图1 UMHexagonS搜索算法流程图

2)经测试发现，视频序列中静止块的SAD值小于SAD阈值下限的约有98%。此值通常是参考帧的搜索区域中候选搜索起始点(0，0)所对应的块计算得到，候选搜索起始点之后的搜索有些多余。

3)据统计约有80%的搜索块，当计算了块中约50%像素点数时，累加值就已经大于已有最小SAD值，块中另外50%像素点的计算是多余的。

4)模式选择时，静止或者运动缓慢的块，通常选择16×16模式。算法中先是计算16×16预测模式的代价值me16x16.cost。然后，无条件的计算8×8模式4个块代价值的累加和i_cost8x8。实际1个8×8块的代价值已经大于me16x16.cost，所以，多余计算了其余3个8×8块的代价值。

2.2 运动估计优化

本文根据前文提到的几点不足，提出以下4个方面的优化:

1)自适应地选择SAD阈值。UMHexagonS搜索算法中SAD阈值是固定的，其中16×16预测模式的SAD阈值threshold1和threshold2分别为2000和500。以16×16模式为基准，得到16×8预测模式和8×16预测模式SAD的阈值threshold1＞＞1和threshold2＞＞1，8×8预测模式SAD的阈值为threshold1＞＞2和threshold2＞＞2。本文提出了以下改进方法:根据物体运动的空间和时间相关性，当前块的最佳匹配块的SAD值和候选搜索起始点对应块所得到的SAD值密切相关。所以，SAD阈值的设定可以根据候选搜索起始点得到的SAD值来确定。因此，SAD阈值的设定如下:

根据16×8模式、8×16模式和8×8模式的SAD阈值与16×16模式阈值的关系得到如下3个数组:

(1)data500［4］={500，250，250，125};

(2)data1000［4］={1000，500，500，250};

(3)data2000［4］={2000，1000，1000，500}。

其中，data500［4］表示4种预测模式阈值下限的最小取值;data1000［4］表示4种预测模式阈值下限的最大取值以及上限和下限的差值;data2000［4］表示4种预测模式阈值上限的最大取值。

通过候选搜索起始点得到的SAD的最小值记为min_sad。自适应选择SAD阈值的流程如图2所示。其中，4种预测模式 i_pixel取值分别为 0，1，2，3。该方法可使每种预测模式的阈值上限和下限都不再是固定值，而是存在一定的取值范围。采用上述自适应的SAD阈值，能有效地减少搜索点数，更快地搜索到最优点，使得计算量大大降低。

图2 自适应选择SAD阈值流程图

2)搜索提前终止判断。经候选起始点得到自适应SAD阈值上限threshold1和下限threshold2后加入条件判断语句“if(sad＜threshold2)”，满足条件则提前终止搜索。在不影响视频质量的前提下，可以平均减少24～36个搜索点的计算量。

3)SAD计算的优化。UMHexagonS搜索算法中每一种搜索模型都是通过一定的宏定义函数实现的。宏定义中用的SAD值计算函数的主要代码如下:

针对4 种预测模式(lx，ly)分别为(16，16)，(16，8)，(8，16)和(8，8)。将SAD值比较提前放入SAD计算函数中，每累加一个绝对差值进行一次“if(sum ＞=bcost)”比较，如果满足条件则跳出循环，提前结束计算，可以节省m－count次循环的计算量。

4)模式选择的提前结束判断。在帧间模式选择时，在函数xavs_mb_analyse_inter_p8x8()中每累加一个8×8块的代价执行一次条件判断“if(a-＞l0.i_cost8x8＞=a-＞l0.me16x16.cost)”，如果已有8×8代价值不小于16×16预测模式的代价值，则可以提前结束对代价值的计算，便可省去对其余8×8块的运动搜索和代价值计算。这种优化算法对静止或运动缓慢的视频序列改善较为明显。

3 实验结果与分析

实验分别从峰值信噪比(PSNR)、码率(BR)和帧率(FR)3个方面将优化后算法和优化前算法进行了比较。主要参数设置:参考帧为1帧，I帧的QP设为28，编码序列为IPPP格式，其中P帧预测模式不包括帧内预测模式。本实验测试了不同格式(QCIF，CIF，D1)和不同运动剧烈程度(如运动幅度较小的bridge序列，运动幅度中等的coastguard序列，运动幅度较大的football序列)的经典测试序列在不同QP(28，30)下的峰值信噪比、码率和帧率的变化。实验数据见表1～表6。

表1 QP=28时QCIF格式的实验结果

表2 QP=30时QCIF格式的实验结果

表3 QP=28时CIF格式的实验结果

表4 QP=30时CIF格式的实验结果

表5 QP=28时D1格式的实验结果

表6 QP=30时D1格式的实验结果

实验结果中前两项数据均为:变化率 =(优化后-优化前 )/优化前×100%，其中“-”号表示降低，“+”号表示增加，对于信噪比“+”号表示视频质量得到提高，而对于码率“-”号表示压缩率越大。由测试结果可以看出，所有测试序列信噪比降低不超出0.3%，码率增加不超出0.4%，帧率都有了明显提高，并且针对同一种格式的序列，QP越小时帧率提高越大。另外，部分测试序列的信噪比有所增加，也有部分测试序列码率有所减小。总体来看，在峰值信噪比和码率变化不明显的情况下，帧率平均提高1.4倍，更好地满足了视频压缩编码的实时性要求。

4 小结

本文通过对AVS编码器中整像素运动估计算法的深入研究和分析，分别针对运动搜索的UMHexagonS搜索算法和模式选择在SAD阈值选择、搜索的终止判断、SAD计算和代价值比较几方面进行了改进。实验表明，对于不同格式和量化参数的测试序列，在峰值信噪比和码率基本不变的情况下，编码速度大幅度提高，增强了编码器的实时性，更有利于视频的实时编码传输。

［1］周波，王力波，刘东华，等.用于AVS视频编码的快速子像素运动搜索算法［J］.计算机应用研究，2008，25(7):2238-2240.

［2］刘易，李太君.H.264中快速运动估计UMHexagonS算法的改进［J］.计算机技术与应用，2011，37(8):128-130.

［3］ZHU Shang，MA Kaikuang.A new diamond search algorithm for fast block-matching motion estimation［J］.IEEE Trans.Image Processing，2000，9(2):287-290.

［4］王超，于洪珍，厉丹，等.带有阀值的自适应混合搜索算法的设计与实现［J］.计算机工程与设计，2010，31(9):1968-1970.

［5］杨齐，李子印.一种改进的UMHexagonS运动估计算法［J］.电视技术，2012，36(5):15-17.

［6］毕厚杰.视频压缩编码标准——H.264/AVC［M］.北京:人民邮电出版社，2005.

［7］黄春庆，邱晓彬.基于x264的快速运动估计算法优化［J］.控制工程，2010，17(6):820-823.