H.264视频压缩快速运动估计算法UMHexagons改进

杨 虎，潘红兵，，何书专，李 丽

(1.南京大学电子学院微电子设计研究所，江苏南京210093;2.江苏省光电信息功能材料重点实验室，江苏南京210093)

0 引言

H.264/AVC［1］是MPEG和ITU-T联合制定的最新视频编码标准，其基本编码框架和先前类似标准并没有太大变化，但是编码模块的技术方案应用了目前编码的很多新技术，采用了非常高效和精确的运动估计预测方法，其编码效率比以往的编码标准H.261/H.263和MPEG-1/2/3均提高40%以上，获得了较高的编码质量，但却是以极大增加运算复杂度为代价的，一直成为实时应用的瓶颈。

视频编码领域中最关键的技术是运动估计算法，其作用是在编码过程中消除图像帧间冗余度，目前已经成为视频压缩研究领域的热点。当前，块匹配算法因其易于硬件实现已经广泛应用于各种视频编码标准，确定匹配块的准则是块失真度。研究表明，运动估计算法模块是整个编码过程中最耗时的部分，为了降低运动估计算法复杂度，减少耗时，提升编码效率，各国学者提出了很多运动估计快速算法［2］-［5］，包括新三步法 (NTSS)、钻石搜索法 (DS)、六边形模板搜索法 (HEXBS)以及十字-钻石-六边形搜索法 (CDHS)这些算法一定程度上能够降低运动估计算法复杂度，同时保证了原有的视频质量，对运动缓慢和图像尺寸较小的视频序列可以取得较好的效果，但是在编码运动剧烈和图像尺寸较大的序列时，效果不太满意，容易陷入局部最优点，从而影响编码质量。

非对称十字形多层次六边形搜索算法 (UMHexagonS)［6］是清华大学提出的快速运动估计算法，已经被H.264 JM参考模型所采纳，其运算量只有全搜索算法(FS)的10%，同时保持了较好的率失真性能，避免了运动搜索过早陷入局部最优点，而且能够应用于不同类型的视频序列，获得了与FS几乎相同的运动估计效果。UMHexagonS虽然有效加快了运动估计的速度，但是仔细分析仍然存在很大的优化空间，本文从早期结束阈值、混合搜索模板和宏块类型模板对UMHexagonS算法进行了改进。

1 UMHexagonS算法特征与存在问题

1.1 精确预测初始搜索起点

UMHexagonS算法开始是确定搜索的初始运动矢量，其矢量集包括中值预测矢量、上层预测矢量、原点预测矢量、相邻参考帧预测矢量和参考帧相同位置宏块预测矢量。上述运动矢量集中能使拉格朗日代价函数最小的矢量作为最小的运动矢量，若不满足搜索提前中止的条件，这个矢量即为下一步搜索的最佳搜索起点。UMHexagonS使用的起点预测有效利用了帧内、帧间相邻块的运动矢量相关性，因此其筛选出的搜索点最能够反映当前搜索块的运动趋势，很好的提升搜索精度。

1.2 早期提前终止搜索策略

为了使运动估计算法在搜索速度和搜索质量之间达到平衡，UMHexagonS算法中设计了一个适当的ET阈值，在每一次不同的搜索步骤之后使用ET阈值判断是否结束搜索:

(1) 初始搜索起点预测

(2) 非对称大十字搜索

(3) 5x5正方形搜索

(4) 非均匀多层次16点六边形搜索

每当满足ET结束条件时，搜索算法将会跳转到局部精细搜索部分。上述的ET值由式 (1)决定，其大小与当前块大小、量化步长、量化系数QP和相邻块MCOST有关

算法中不同搜索步骤之后使用ET阈值都是相同的，可能出现一个问题，就是得到的小于ET的最小点不是一个最佳点，然而利用ET在搜索后面阶段找到更好搜索点的可能性变得越来越小。以UMHexagons最后主要的搜索模板为例，从搜索中心到搜索窗口边界，其包含了4个16个点六边形搜索。如果一次六边形搜索不能找到更好的搜索点，当前的最优点仍然需要从前面的搜索步骤中获得，六边形搜索将会继续，这样的话后面六边形搜索中使用的ET将失效。文献［7］实验结果显示在不同图片尺寸和QP编码条件下，六边形搜索中ET的使用效率非常低 (ET效率的定义是搜索中途退出的次数/搜索总次数)，可见在这一搜索步骤中ET几乎没有用。因此为了提高算法的搜索效率，必须在不同的搜索步骤中使用不同的ET阈值。

1.3 混合多层次搜索

UMHexagons是混合多层次搜索算法，其搜索过程可分为大范围粗搜索、细搜索和精细搜索阶段，其中粗搜索阶段包含非对称大十字模板、5x5正方形模板和非均匀多层次六边形模板，细搜索阶段使用正六边形模板搜索，直到得到的最佳点位于正六边形中心时，进入精细搜索阶段，使用小钻石模板搜索，当搜索点位于小钻石中心时即可得到最佳运动向量，搜索结束。

从算法的3个搜索过程可以看到，最坏情况下，粗搜索阶段算法要搜索113个点 (非对称十字24+正方形25+非均匀多层次六边形64)，搜索点数过多，算法忽略了预测运动向量的方向性，过多的搜索了不必要的点;同时在细搜索阶段使用的是相同的正六边形模板，算法没有考虑到不同宏块使用不同的搜索模板以保证搜索速度和质量的折中，因此有必要对原算法进行改进。

2 对UMHexagonS算法的改进

由以上分析UMHexagonS算法中存在的问题，对算法的改进如下。

2.1 提出一种新的自适应ET阈值

根据文献［7］设计了自适应运动估计搜索早期结束策略，引入一种新的ET阈值，其ET阈值的大小由图像的大小和量化参数两个因素决定，以适应不同的编码条件。运动估计算法中需要的两个阈值由以下式子决定

式 (2)中 Threshold代表 Threshold1和 Threshold2，ThdBase代表ThdBase1和ThdBase2。由于大多数情况下物体的运动是规律且缓慢的，相邻块预测得到的中值预测矢量很有可能是最佳的搜索点，搜索中值预测点之后使用Threshold1，若满足条件，这时候可以认为运动估计算法就找到了最优点，可以结束整个搜索，极大节省搜索时间。每一步非均匀多层次六边形搜索之后可以使用Threshold2，因为这是算法最耗时的部分，一旦当前的MCOST小Threshold2，算法进入细搜索阶段。ThdBase由最小QP和最小图像尺寸设置，通常Thd1Base比Thd2Base小，因为假如满足了Threshold1，就没有必要再继续进行运动估计搜索，而且一个小的Threshold能确保对搜索质量影响最小。式 (3)M是阈值的调节因子，由两个变量QP和图像大小决定，目的是为了使阈值适应不同的QP和视频序列。M调节因子的原则是越大的阈值分配给尽量小的QP和大的图像尺寸。式(4)MAX_QP是H.264/AVC使用的最大QP值，式 (5)MIN_WIDTH是测试序列中最小的图像宽度，其中常数A和B由实验确定。根据实验测试的结果，各个参数的取值如下

Thd_Base中的7个值分别对应从16x16到4x4七种宏块大小，QP_factor的参数A在整像素搜索中设为0.9，分数像素搜索中设为0.3，Scale_factor的参数B设为0.3。

2.2 粗搜索阶段的模板改进

2.2.1 大十字模板和多层次六边形模板改进

根据文献［8］利用当前块的运动矢量和前一帧与当前块的相同位置块运动矢量可以减少运动估计搜索点数，用current_MV表示当前块运动矢量，previous_MV表示前一帧运动矢量，求出两个运动矢量的夹角，计算方法如下

若两个矢量都不为0，根据式 (8)计算出其夹角θ，否则仍然按照改进前算法计算，由式 (8)可知，current_MV是随着搜索中心的改变而变化，而previous_MV在每次块搜索中的大小是不变的。

根据参考文献［9］提出的对搜索模板的划分方式，对非对称大十字和多层次六边形进行划分，如图1所示，与水平方向成45度角互相垂直的两根直线把搜索区域分为4个部分，根据式 (8)计算出的θ决定将在哪个搜索区域继续寻找最佳运动向量，只要预测向量的精度足够高，就可在该区域找到最佳点，因此可以节省大量的搜索点，如图2可知，采用如此划分之后，非对称大十字搜索点数由之前的24点降为8点或4点，而多层次六边形由原来64点降为20点或12点，极大的减少了搜索点数，可以有效提升搜索速度。

由式 (8)的θ，确定相应的搜索区域，确定的方式如下:

当 θ∈ (0，45°］∪ (315°，360°］时:在 (a)(e)区域搜索;

当θ∈(45°，135°］时:在 (b)(f)区域搜索;

当θ∈(135°，225°］时:在 (c)(g)区域搜索;

当θ∈(225°，315°］时:在 (d)(h)区域搜索。

2.2.2 5x5方形搜索模板改进

根据文献［10］可知，搜索过程中正方形模板里每个点成为最佳点的概率是不一样的，因此没有必要对每个点进行搜索，只保留成为最佳点概率高的点，其它点可以弃掉，减少搜索点数。由于这一步是小范围搜索，因此可忽略其矢量的方向性，采用菱形—正方形模板替代之，由图3可知搜索的点数由25点减少到9点，同时还保持了搜索各个方向上点数的均匀。

图3 菱形—正方形搜索模板

2.3 细搜索阶段算法改进

由上面阶段得到的运动估计向量，进入细搜索阶段，对于16x16到4x4七种搜索模式，若都采用同一种搜索模板，则必会增加搜索时间。为了平衡搜索精度和搜索速度，针对不同的搜索模式采用不同的模板［11］，在保持搜索精度的前提下，提升搜索速度。

(1)若块类型为16x16、8x8时，搜索时仍用正六边形模板，如图4(a)所示。

(2)若块类型为16x8、8x4时，搜索时使用扁平六边形模板，如图4(b)所示。

(3)若块类型为8x16、4x8时，搜索时使用竖直六边形模板，如图4(c)所示。

(4)若块类型为4x4时，搜索时使用小钻石模板，如图5所示。

当得到的运动向量中心在模板中心时，上述每一种模式对应的模板搜索结束，进入精细搜索阶段。

2.4 精细搜索阶段改进

图4 六边形搜索模板

为了保证运动搜索的精度，精细搜索阶段仍然采用原算法图5的小钻石搜索，不过注意，若是模式4x4的搜索，则跳过精细搜索阶段，因为细搜索阶段得到的点已经是最佳运动向量点，其他模式的搜索直到最佳点在模板中心时结束。

图5 小钻石模板

3 实验结果与分析

首先，UMHexagons改进的算法在H.264标准测试平台JM10.1中实现。测试PC硬件为Intel(R)Pentium(R)D CPU 2.81GHz，2GB内存。操作系统为 Microsoft Windows XP Professional 2002，Service Pack3。编码器配置采用JM10.1的基本类，实验的主要编码参数见表1。

表1 主要的编码参数

为了测试改进算法的性能，采用不同运动类型的标准测试视频序列，见表2。

表2 待测试序列

表3 运动时间比较数据

由表3可知，对于运动缓慢的测试序列，改进算法运动估计时间减少不多，因为在这类序列中主要是静止块和运动缓慢的块，搜索过程大部分在新的ET Threshold1阈值判断阶段就结束了，所以在算法中使用的模板区域划分和改进模板没有起到作用。但是对于中等运动和运动剧烈测试序列，搜索的速度显著上升，尤其是运动剧烈序列，改进算法的速度提升在25%以上，主要是因为进入了混合搜索阶段后，改进的算法大大减少了搜索点数，发挥了极大的作用。通过实验表4可以看到，改进算法的PSNR平均只改变了0.02dB，最大只改变了0.03dB，压缩算法对图片质量的影响可忽略不计，同时，码率变化很小，平均值增加了1.30%，最大增加不超过2.07%。因此可以看到，对于不同类型的标准测试视频序列，改进的算法有效提升了运动估计的速度，同时保持了原算法的率失真性能，对图像质量的影响非常小。见表5。

表4 亮度信号峰值信噪比 (PSNR)比较数据

表5 码率比较数据

4 结束语

文章对H.264快速运动估计算法UMHexagonS的特点进行了分析，研究了算法中存在的问题并作了改进，引入了新的ET阈值，更好的发挥了算法中提前结束搜索的功能，同时应用了预测运动向量的方向偏置性，极大的减少了搜索点，加快了搜索速度，而且针对不同的宏块，应用不同的搜索模板，提高了搜索精度。实验的结果表明，对于不同类型的测试序列，在保证码率和图像质量的前提下，编码效率得到了有效的改进，提升了编码器的实时性。

［1］BI Houjie，WANGJian.H.264/AVCvideo compression video coding for next generation multimedia［M］.2et nd.Beijing:Posts＆Telecom Press，2009:51-76(in Chinese).［毕厚杰，王健.新一代视频压缩编码标准—H.264/AVC［M］.2版.北京:人民邮电出版社，2009:51-76.］

［2］Suh JW，Cho J，Jeong J.Model-based quarter-pixel motion estimation with low computational complexity ［J］.Electronics Letters，2009，45(12):618-620.

［3］Sarwer M G，WU Q M J.Adaptive variable block-size early motion estimation termination algorithm for H.264 /AVC video coding standard［J］.IEEE Trans on Circuits and Systems for Video Technology，2009，19(8):1196-1201.

［4］ISMAIL Y，McNEELY J，SHAABAN M，et al.A generalized fast motion estimation algorithm using external and internal stop search techniques for H.264 video coding standard［C］//Proc of IEEE International Symposium on Circuits and Systems.Seattle，WA，2008:3574-3577.

［5］WU Xiaomin，XU Weizhang，ZHU Nanhao，et al.A fast motion estimation algorithm for H.264［C］//Proceedings of International Conference on Signal Acquisition and Processing.Bangalore，India:IEEE Press，2010:112-116.

［6］CHEN Z，XU J，HE Y，et al.Fast integer-pel and fractional-pel motion estimation for H.264/AVC ［J］.Journal of Visual Communication and Image Representation，2006，17(2):264-290.

［7］XU Xiaozhong，HE Yun.Improvements on fast motion estimoton strategy for H.264/AVC ［J］.IEEE Transactions on Circuits and System for Video Technology，2008，18(3):285-293.

［8］Thambiduarai P，Ezhilarasan M，Ramachanfran D.Efficient motion estimation algorithm for advanced video coding［C］.Coference on Computational Intelligence and Multimedia Application.Sivakasi，Tamilnadu，India，2007:47-52.

［9］LI Guiju，LIU Gang，LIANG Jingqiu.Improvement of fast motion estimation algorithm used in H.264 ［J］.Optics and Precision Engineering，2010，18(11):2489-2496(in Chinese).［李桂菊，刘刚，梁静秋.H.264快速运动估计算法的改进 ［J］光学精密工程，2010，18(11):2489-2496.］

［10］DING Y，SONG X H，YAN S H，et al.Improvements of UMHexagonS algorithm based on fast motion estimation［J］.Data Acquisition ＆ Processing，2009，24(5):660-663.

［11］DUAN Qingqing，SONGXuerui.Fast Motion Estimation Algorithm in H.264/AVC ［J］.Computer Engineering，2008，34(16):244-246(in Chinese).［段青青，宋学瑞.一种H.264/AVC中的快速运动估计算法［J］.计算机工程，2008，34(16):244-246.］