基于H.264/AVC的运动估计算法研究

许晓中

(清华大学 电子工程系，北京 100084)

1 引言

由联合视频专家组JVT（Joint Video Team）提出的国际标准H.264/AVC[1]，是目前压缩效率最高的视频编码标准。在该标准提供的众多编码工具中，运动估计是其中的一项关键技术，它能够有效地降低帧间预测编码产生的误差。在提高编码效率的同时实现运动估计算法，也带来了很大的计算复杂度。以全搜索算法（遍历所有可能的匹配位置）为例，对一个宏块（16×16的亮度样本矩阵）进行整像素运动估计，如果采用5个参考帧和±32的搜索窗，需要进行（32×2+1）×（32×2+1）×（1+2+2+4+8+8+16）×5=866 125次块匹配操作。运动估计的计算量，构成了编码器的主要计算复杂度，也是实现实时编码器的主要瓶颈。

为了解决编码器计算复杂度过高的问题，许多快速运动估计算法被提出，在保持全搜索算法的高编码效率的同时，大大降低了原有算法所需的计算量。评价一个快速运动估计算法，需要同时考虑两方面的性能：一方面是相对于全搜索算法的搜索质量，一般由编码的PSNR值来衡量；另一方面是相对于全搜索算法的时间节省。H.264/AVC的参考软件JM中，采用了3种可选的的快速运动估计方法，分别是UMHS[2-3]，SUMHS（简化的UMHS）[4]以及EPZS算法[5]。在给定的测试条件下，它们相对于全搜索算法，能达到平均PSNR损失小于0.1 dB，同时节省了约90%的运动估计时间。

下面基于这3种算法对若干关键问题进行研究分析，指出这些算法各自的特点及不足，最后给出运动估计算法设计的几条基本原则。

2 快速运动估计算法简介

2.1 UMHS算法

UMHS主要分为3个部分：

1）起始搜索点预测：空域中值MV预测，上层块预测，临近参考图像预测，还有（0，0）位置，这些运动矢量预测点作为搜索起始点，被用来预测当前块的运动矢量。之后的搜索模式，将以最佳的起始预测点为中心展开。

2）全局搜索模式：以最佳起始预测点为中心，非对称十字型搜索，5×5矩形搜索和多重六边形网格搜索依次被采用。上一个搜索模式结束后得到的最佳匹配点，将作为下一个搜索模式的搜索中心。

3）局部优化搜索：基于小六边形的扩展搜索和基于小菱形的扩展搜索，依次在上一步骤中的最佳搜索点展开，作为最后的局部优化。

4）提前截止策略：进行运动估计后得到的大部分最佳运动矢量，它们的实际位置等同或者相当接近于起始预测点，这说明大部分的搜索工作实际上并不是必要的。所以，在运动估计过程中，引入一个合适的中途退出机制十分有意义。如图1所示，在算法的各个主要搜索部分后均有提前截止的阈值判断，如果当前最佳匹配结果满足设定阈值，则搜索提前结束。

图1 UMHS算法流程图

2.2 简化的UMHS算法

该算法仅采用中值MV预测，并省略了5×5的矩形搜索模式；提前截止算法也使用简单的常数阈值判断。因此，相对于原算法，简化算法在搜索速度上有明显提升。

2.3 EPZS算法

与UMHS相似，EPZS采用了多个MV预测点作为起始搜索点，但其固定搜索模式只有一个十字型搜索，接下来就进行局部迭代搜索，该搜索根据先前得到的信息，可以动态调整搜索模式。EPZS的提前截止阈值设计采用临近块匹配残差的预测值与常数阈值相结合的方式进行。

3 快速运动估计算法比较研究

3.1 性能表现

采用文献[6]中的测试序列和条件对3种方法进行比较测试，实验结果如表1所示。

从表1中列出的数据可以看出，3种方法相对于FFS运动搜索运算时间节省超过90%，大大降低了编码器的计算复杂度，其中简化的UMHS（SUMHS）算法在速度上优于另外2种算法；另一方面，在对FFS算法的性能保持上，SUMHS算法应用于不规则运动序列时，存在较大性能损失。

表1 3种快速算法相对于快速全搜索（FFS）算法的性能比较

3.2 搜索点数与搜索时间

构成运动估计时间开销的操作中，除了已经知道的海量块匹配操作外，对于不同算法而言，还存在例如内存读写、程序判断跳转等其他开销，把这部分开销统一称为额外运动估计时间开销，用以区分块匹配产生的开销。额外时间开销的比例越大，对整体运动估计时间的影响也就越大，因此，在给定平台上设计运动估计算法时，需要尽可能的降低额外开销与块匹配开销的比率。

表2 4种算法的搜索点数及搜索时间比较

3种快速算法比较来看，UMHS算法额外开销比率最小，而EPZS最大，其原因在下个小节中继续讨论。

3.3 搜索模式设计

在单个CPU的软件平台上，各个搜索点之间的关系时顺序进行的，即上一个搜索点操作结束后，进行下一个搜索点的块匹配运算。实际上，在一个给定的搜索模式中，各个搜索点的位置只由搜索模式的中心来决定，因此它们相互之间是独立的。在支持并行计算的平台上，这些相互独立的搜索点可以同时进行操作，从而进一步加快运动搜索速度。

基于这样的设计理念，UMHS算法给出了一系列可以并行计算的“固定”搜索模式，其特点是大量相对独立的搜索点覆盖搜索窗内。因此，就总的搜索点个数而言，该算法是最多的。与之相反，EPZS算法通过对上一个搜索点结束后所获得的信息（例如运动矢量大小和方向、块匹配残差大小等）进行判断，进而动态的调整后续的搜索模式，从而达到尽可能节省搜索点个数的目的。因此，EPZS算法产生了较高的额外时间开销率，其串行的结构也不利于进一步并行加速。

在实际设计中，需要考虑到时间算法平台对并行计算的支持程度，以在搜索模式的并行性以及搜索点数的最优性上寻找一个折中。

3.4 提前截止设计

总体来说，提前截止都是由阈值来决定的，比较当前搜索的结果和给定的阈值，如果满足则提前退出搜索过程。最简单的阈值设计为常数阈值，是基于经验设定一个常数阈值，该方法被SUMHS算法采用；第2种方法是通过相邻块最后得到的匹配残差值，对当前块进行预测，UMHS和EPZS算法都采用了这种方式；第3种方式是考虑到编码参数（例如图像尺寸等）对运动估计的影响，将这些参数引入阈值设计中来，从而达到在不同编码条件下均能高效提前截止的目的。在UMHS中，编码量化参数和图像尺寸被提前截止阈值设计所考虑。

[1]ITU-T and ISO/IEC JTC1.ITU-TRecommendation H.264-ISO/IEC 14496-10 AVC，Advanced video coding for generic audiovisual services[S].2003.

[2]CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integer-pel and fractional-pelmotion estimation for H.264/AVC[J].Journal of Visual Communication and Image Representation，2006，17（2）：264-290.

[3]XU Xiaozhong，HE Yun.Improvements on fast motion estimation strategy for H.264/AVC[J],IEEE Trans.Circuits and Systems for Video Technology，2008，18（3）：285-293.

[4]YI Xiaoquan，ZHANG Jun，LING N，et al.Improved and simplified fastmotion estimation for JM.JVT-P021[R].[S.l.]：JVT，2005.

[5]TOURAPISA M，CHEONG H Y，TOPIWALA P.FastME in the JM reference software.JVT-P026[R].[S.l.]：JVT，2005.

[6]SULLIVAN G，BJONTEGAARDG.Recommended simulation common conditions for H.26L coding efficiency experiments on low-resolution progressive-scan sourcematerial.VCEG-N81[R].[S.l.]：ITU-TQ6/16 VCEG，2001.