H.264运动估计UMHexagonS算法的优化与改进*

任克强 林芳明

(江西理工大学信息工程学院， 赣州， 341000)

H.264运动估计UMHexagonS算法的优化与改进*

任克强 林芳明

(江西理工大学信息工程学院， 赣州， 341000)

针对H.264中UMHexagonS算法存在的不足，提出了一种改进的快速运动估计算法。改进算法根据起始预测运动矢量成为最佳点的可能性大小对起始预测运动矢量的检测顺序进行了优化，提高了编码效率；设计了一种改进的5×5螺旋全搜索模板，减少了5×5螺旋全搜索模板的搜索点数；增加了一种针对亚宏块的提前终止策略，进一步减少了运动估计带来的运算量。实验结果表明，改进算法在基本保持UMHexagonS算法编码性能的同时，有效减少了运动估计时间，提高了编码效率，并且可适用于不同运动强度的视频序列。

运动估计； 5×5螺旋全搜索； 起始预测； 提前终止策略

引 言

H.264是新一代视频编码标准，包括预测编码、离散余弦变换(Discrete cosine transform，DCT)和量化、DCT反变换和反量化、熵编码、环路滤波、运动估计以及运动补偿等模块[1-2]，其中基于块的运动估计是视频编码的关键内容之一，运算量为整个编码过程的50%～80%[3]。所以缩短运动估计时间是一种很有效的方法，可以明显降低图像序列的冗余度。全搜索(Full search，FS)算法[4]是基于块运动估计的最简单算法，通过检测所有的可能点来得到最佳点，在获取最佳运动矢量的同时也带来庞大的运算量，有悖于视频通信的实时性。

为了减少运动估计时间，研究人员提出了许多快速算法，非对称十字多层六边形搜索(Unsymmetrical-cross multi-hexagon-grid search，UMHexagonS)算法[5]就是其中的一种。尽管该算法有较优秀的编码性能，但依然存在搜索点数较多等不足。针对UMHexagonS存在的不足，研究人员对其进行了深入研究，先后提出了不同的改进方案。文献[6]通过预测运动矢量(Motion vector,MV)来划分需要搜索区域的重要等级，再根据等级为各区域分配不同的搜索策略，有效地提高了搜索速度。文献[7]利用编码块预测运动矢量的准确度，自适应地确定搜索区间大小，依据运动方向特性，确定有效的搜索方向，明显减少了搜索量。文献[8]设计了一种依据块模式尺寸大小及运动类型来自适应选择搜索窗及搜索策略的算法；文献[9]为不同运动程度和方向的宏块分配不同的搜索方案，针对UMHexagonS的中值预测进行了改进，并设计了一种动态参考块提前跳过方案；文献[8，9]的改进方法对运动剧烈的视频序列效果明显，但对运动较为缓慢的视频序列效果一般。文献[10]充分考虑利用运动矢量时空相关性这一特点，使得起始预测更为精确；改固定阈值静止块判断法为自适应阈值判断法，适合各种类型的序列；根据块运动类型的不同相应分配相应搜索策略，有效保证图像质量及搜索速度，但此算法的起始搜索预测精度不够高，可能导致局部最优。文献[11]针对UMHexagonS的固定搜索窗口、不对称十字交叉、5×5螺旋模板、多层次大六边形及中六边形进行优化，设计出一种自适应模型方向搜索(Adaptive pattern direction search，APDS)算法，明显提升了搜索速率。文献[12]依据H.264中整数离散余弦变换和量化思想，设计出一种基于全零块检测的模式选择快速算法。文献[13]设计一种自适应选择编码模式快速运动估计算法，结合视频序列的空间相关性和运动特性选取更合适的尺寸模式，并通过不同搜索方式对分割块进行搜索，有效降低了计算复杂度，然而此算法只对运动幅度大的视频序列有明显的优势。本文在UMHexagonS和相关文献分析研究基础上，从起始预测、搜索模板及亚宏块模式检测3个方面对其进行了优化和改进，提出一种UMHexagonS的改进算法以提高编码效率。

1 UMHexagonS算法分析

在JM测试模型现有的块匹配算法中，FS最精确，但其搜索时间过长和计算量过于庞大，使得软硬件上都难于实现，而UMHexagonS的运动估计时间不到FS的10%，且还具有较好的编码性能。为了在编码比特率与图像失真之间选择一个合适的折中，H.264对运动估计采用了率失真优化准则，其定义的匹配误差函数为

(1)

式中SAD为当前块与参考块之间的绝对差值和，即

(2)

图1 UMHexagonS算法的主要搜索模板Fig.1 Main search patterns of UMHexagonS algorithm

式中：s为当前块的数据；c为编码重构后的参考帧数据；MV为候选运动矢量；PMV为预测运动矢量；λ为拉格朗日因子；R(MV-PMV)为运动信息；A为像素区域。

UMHexagonS算法的基本步骤如下：(1) 用多种方式进行起始预测，包括中值、原点(0,0)、上层块、前帧同位置块及相邻参考帧预测；(2) 非对称十字交叉搜索，如图1(a)；(3) 5×5螺旋全搜索，如图1(b)；(4) 多层次非对称大六边形搜索，如图1(c)；(5) 中六边形搜索，如图1(c)；(6) 小菱形反复搜索，如图1(c)，当最佳点在小菱形中点时结束。

此外，在步骤(1～4)中都设置了提前终止的阈值判断。把当前最小的块匹配代价值(Sum of absolute differences,SAD)分别与两个阈值T1和T2进行大小比较，若SADT2，则继续顺序搜索。

2 UMHexahonS算法优化和改进

尽管UMHexagonS取得了较好的效率，但其还存在一些不足：(1) 起始预测部分没有采用最合理的检测顺序；(2) 5×5螺旋搜索存在许多不必要的搜索点，运算量大，耗费过多时间；(3) 亚宏块的模式选择时，若开始的8×8模式就是最佳模式，则依然还要对剩余模式检测，这大大增加了不必要的搜索。本文针对这3个方面的不足对该算法进行优化与改进。

2.1 起始预测MV检测顺序的优化

UMHexagonS在起始预测时，先后对中值、原点、上层块、前帧同位置块及相邻参考帧预测进行检测。非最优的预测方式检测顺序会降低算法的编码效率，增加不必要的搜索。理论上成为最佳点MV可能性最大的预测MV，应该最先被检测，可能性最小的预测MV，应该最后被检测。为获得更好的编码性能及减少不必要的搜索点，本文先通过实验来确定这5种预测MV成为最佳点MV的可能性大小，再根据可能性由大到小依次进行这5种起始预测。

图2 优化的预测MV检测顺序 Fig.2 Checking order of optimized prediction MV

实验中取运动剧烈程度不一的试序列，分别在不同参考帧下统计各预测MV成为最佳点MV的可能性，样本总个数为对应预测MV被检测的总次数，可能性大小由对应预测MV成为最佳点MV次数与被检测总次数共同决定。为使所有预测MV均能被检测，本实验在上层块预测后不进行提前终止检测。由实验统计，这5种预测MV成为最佳点MV的可能性大小可分成3个等级：首先为中值和上层块预测，这两种可能性最大；其次为前帧同位置块和相邻参考帧预测，可能性次之；最后为原点预测，可能性最小。因此本文先进行中值和上层块预测，再进行前帧同位置块和相邻参考帧预测，最后进行原点预测，检测流程如图2所示。

2.2 5×5螺旋全搜索的改进

UMHexagonS中5×5螺旋全搜索总共要检测25个点，复杂度过高、计算量过大，而且很费时间，因此有必要对原5×5螺旋全搜索进行优化。经研究统计，80%以上的运动矢量预测值落在中点5×5方形区域内，但是分布很不均匀，接近72%预测值落在3×3的方形区域内[14]，如图3所示。由此可见，在5×5的方形区域中，最佳点落入3×3方形区域中的可能性很大，而落入其外围边界的可能性较小。文献[15]对于16×16模式的块，因运动分量近乎等于零，不执行本步骤；对于4×4模式的块，因运动细节过多，依旧使用原5×5模板；而对于其他模式的块，使用3×3方形模板，以损失少量运动矢量换取减少较多的搜索点数。

本文采用一种较为折中的改进方案，先对3×3方形区域内的点进行检测，通过检测可判断其运动方向，然后沿着该方向向外围进行搜索，能有效减少检测点数。具体方法为：检测居中的3×3方形区域中的8个点(除去中心点)，将互邻的3个点划为一组，共有8组，将各组中3个点对应的块匹配代价值相加，可得8个和值，对这8个和值进行大小比较，沿和值最小的一组相应的外围方向做进一步扩展搜索，如图4所示。由图4可以看出，本文改进的5×5螺旋全搜索只需检测14个点，相比UMHexagonS减少了11个点。

图3 5×5全搜索区域的运动矢量分布

Fig.4 Adaptive 5×5 spiral search

2.3 基于全零块检测的提前终止策略

对于一个运动补偿后的残差块，如果在DCT变换及量化后系数都是零，就可以认为当前匹配块为最佳匹配块，通常称其为全零块。H.264中的亚宏块可能采用8×8，8×4，4×8和4×4这4种模式，在运动估计的时候，每种模式都要被尝试一次，按从大到小的顺序依次检测，一般选匹配代价值最小者作为最佳模式。如果第1个被检测的8×8模式为最佳模式，仍然还会对剩余模式检测，这无疑增加许多不必要的计算量。为了计算8×8模式下的匹配代价值，要对其包含的4×4子块做变换及量化处理。在相同最优运动矢量下，大尺寸模式对应的匹配代价值更小，所以对8×8模式，若4个4×4子块都是全零块，则8×8模式下亚宏块的匹配代价值最小，对后面3种更小块模式进行检测是多余的。针对上述情况，增加一种针对亚宏块的提前终止策略，最先检测完8×8模式后，若它所包括的4个4×4子块都是全零块，就不再去检测剩下的模式，认为所有子块都找到了对应的最优匹配块，8×8尺寸下的子块的最佳运动矢量可视为等同其他尺寸模式下各子分割块的最优运动矢量。此时该模式下亚宏块对应的代价值最小，所以不需要再对剩余3种模式进行检测。

2.4 改进算法

综上所述，本文改进算法描述如下。(1) 按图2所示对起始预测MV进行检测，确定起始点。(2) 选取目前SAD值最小的点，若SAD

3 实验结果与分析

实验环境为AMD Athlon(tm)Ⅱ X2 240 @ 2.81 GHz,2.0GB内存；Windows XP SP2+JM10.2。实验中主要编码参数如下：NumberReferenceFrames=5，FrameRate=30.0，SearchRange=16，FramesToBeEncoded=100，使用哈达玛变换，开启RDO优化，采用IPPP码流结构，量化参数QP取值28，其他为默认配置。

测试序列使用分辨率和运动强度不一的YUV(4:2:0)序列，包括4个分辨率为176×144的QCIF序列：Coastguard，Mobile，Foreman和Akiyo，3个分辨率为352×288的CIF格式序列：Football,Bus和News。其中，Coastguard，Mobile和Football运动剧烈，Foreman，Bus运动中度剧烈，Akiyo，News运动缓慢。实验结果用Y分量峰值信噪比PSNR(Y)值、输出码率Br值及运动估计时间MET值来表征算法性能。

(3)

(4)

(5)

式中：下标opt代表采用改进算法的实验值；下标ref代表采用UMHexagonS算法的实验值。

表1是上述序列前100帧编码后的数据。由数据可知，对于不同的序列，本文改进算法的PSNR(Y)值及Br值与UMHexagonS相比差异很小，基本保持不变，PSNR(Y)平均减少0.021dB，Br平均增加0.52%。但本文算法的MET则比UMHexagonS大大减少；其中，对运动剧烈的视频序列Coastguard(QCIF)，Mobile(QCIF)和Football(CIF)，MET分别减少30.22%,28.23%和32.34%；对运动中度剧烈的视频序列Forman(QCIF)和Bus(CIF)，MET分别减少31.87%和27.63%；对运动缓慢的序列Akiyo(QCIF)和News(CIF)，MET分别减少21.63%和25.54%。由以上分析可得知，改进算法适合各种运动程度的序列。在运动剧烈的测试序列中，对应的各预测MV值也差异很大，所以优化起始预测MV检测的效果更明显；运动剧烈的序列有许多宏块会进入全局搜索，所以改进5×5螺旋全搜索的效果也明显；运动缓慢的序列包含大量的全零块，因此基于全零块检测的提前终止策略效果更明显。

表1 实验结果比较

表2为本文改进方案、文献[15，16]分别对UMHexagonS算法改进效果的比较。与UMHexagonS算法相比，文献[15]的PSNR(Y)平均减少0.027 dB，Br平均增加1.07%，MET降低8.66%～30.88%，平均可减少21.93%；文献[16]的PSNR(Y)平均减少0.002 dB，Br平均增加1.30%，MET降低7.58%～27.88%，平均可减少17.93%；本文算法的PSNR(Y)平均减少0.021 dB，Br平均增加0.52%，MET降低21.63%～32.34%，平均可减少28.21%。可以看出，本文算法的性能优于文献[15,16]，特别是对运动缓慢序列的编码效果要明显优于文献[15,16]。

图5，6是在量化参数QP取不同值的情况下，本文算法与UMHexagonS算法分别对Foreman，Mobile序列编码的率失真曲线图。由图可知，本文算法与UMHexagonS算法的率失真曲线图基本一致，说明本文算法较好地保持了原算法的编码性能。

图5 Foreman序列的率失真曲线比较

Fig.6 Comparison of R-D curve for Mobile sequence

图7，8以Foreman序列的前30帧为例，从PSNR(Y)和搜索点数两方面对本文算法与原算法进行逐帧的编码效果比较。由图可知，本文算法在大体保持每帧峰值信噪比的条件下，比原算法节省了近50%的搜索点数。

图7 Foreman序列的PSNR(Y)比较

Fig.8 Comparison of search points for Forman sequence

4 结束语

本文以JM模型中的UMHexagonS为基础，提出一种UMHexagonS的改进方案，从起始预测顺序、5×5螺旋搜索以及亚宏块的提前终止策略3个方面对其进行优化与改进，并对改进算法和UMHexagonS算法的峰值信噪比、输出码流码率、运动估计时间、率失真曲线以及搜索点数进行了比较实验。实验结果表明，改进算法在保证输出码流码率和峰值信噪比变化很小的前提下，可以有效地提高对不同运动复杂度视频序列的编码效率。

[1] 周欣,段哲民,周巍.一种适用于H.264/AVC的新型整数变换与量化算法[J].数据采集与处理,2011, 26(6):619-625.

Zhou Xin,Duan Zhemin,Zhou Wei. Novel integer transform and quantization algorithm for H.24/AVC[J]. Journal of Data Acquisition and Processing, 2011, 26(6):619-625.

[2] 陈晓,刘海英.基于综合因子的H.264码率控制算法[J].数据采集与处理,2013, 28(3):347-351.

Chen Xiao, Liu Haiying. Rate control algorithm for H.264 with comprehensive factor[J]. Journal of Data Acquisition and Processing, 2013, 28(3):347-351.

[3] Ismail Y, McNeely J B, Shaaban M, et al. Fast motion estimation system using dynamic models for H.264/AVC video coding[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(1): 28-42.

[4] Kim J, Park T. A novel VLSI architecture for full-search variable block-size motion estimation[J]. Consumer Electronics, IEEE Transactions on, 2009, 55(2): 728-733.

[5] 张新安,宫彦军,李小武.一种AVS-M整数像素运动估计快速算法[J].小型微型计算机系统,2011,32(4):793-796.

Zhang Xinan, Gong Yanjun, Li Xiaowu. Fast integer pixel motion estimation algorithm for AVS-M[J]. Journal of Chinese Computer Systems, 2011, 32(4):793-796.

[6] 申舟,李正明,潘天红.H.264/AVC中基于搜索区域划分及评估的运动估计[J].中国图象图形学报,2010,15(2):242-246.

Shen Zhou, Li Zhengming, Pan Tianhong. Motion estimation based on the partition and evaluation of the search area in H.264/AVC[J]. Journal of Image and Graphics, 2010, 15(2):242-246.

[7] 刘英哲,王进祥.H.264中一种基于搜索范围自适应调整的运动估计算法[J].电子与信息学报,2013,35(6):1382-1387.

Liu Yingzhe, Wang Jinxiang. Motion estimation algorithm based on adaptive search range adjustment for H.264[J]. Journal of Electronics and Information Technology, 2013, 35(6):1382-1387.

[8] 李子印,杨齐.基于运动信息自适应的快速运动估计算法[J].中国图象图形学报,2012,17(9):1069-1074.

Li Ziyin, Yang Qi. Fast motion estimation algorithm based on motion information adaptation[J]. Journal of Image and Graphics,2012,17(9):1069-1074.

[9] 刘治,王玲,陶小娟.动态模式的快速运动估计算法[J].计算机工程与科学,2014,36(9):1760-1764.

Liu Zhi, Wang Ling, Tao Xiaojuan. A fast motion estimation algorithm using dynamic models[J]. Computer Engineering and Science, 2014, 36(9): 1760-1764.

[10]丁鑫,樊慧津.基于方向自适应的运动估计混合模板搜索算法[J].中国图象图形学报,2011,16(1):14-20.

Ding Xin, Fan Huijin. A mix-pattern motion estimation search algorithm based on direction adaptation[J].Journal of Image and Graphics, 2011, 16(1): 14-20.

[11]肖冰君,杨静.H.264中UMHexagonS运动估计算法的改进[J].计算机应用,2014,34(6):1699-1705.

Xiao Bingjun, Yang Jing. Improvement of UMHexagonS motion estimation algorithm in H.264 [J].Journal of Computer Applications, 2014, 34(6): 1699-1705.

[12]周韬,张茂军,刘少华,等.H.264/AVC中基于全零块的预测模式选择[J].计算机工程,2009,35(24):232-235.

Zhou Tao, Zhang Maojun, Liu Shaohua, et al. Prediction mode selection based on all-zero block in H.264/AVC[J].Computer Engineering, 2009,35(24):232-235.

[13]叶仕通.自适应选择编码模式的快速运动估计算法[J].计算机工程与科学,2014,36(9):1780-1787.

Ye Shitong. A fast motion estimation algorithm with adaptive selecting encoding mode.[J]. Computer Engineering & Science, 2014, 36(9):1780-1787.

[14]Lam Chi-wai, Po Lai-man, Cheung Chun-ho. A novel kite-cross-diamond search algorithm for fast block matching motion estimation[C]// Proceedings of 2004 IEEE International Symposium on Circuits and Systems. Vancouver, Canada: IEEE Press, 2004: III729-III732.

[15]丁燕,宋雪桦,闫述,等.基于快速运动估计UMHexagonS算法的改进[J].数据采集与处理,2009,24(5):660-663.

Ding Yan, Song Xuehua, Yan Shu, et al. Improvements of UMHexagonS algorithm based on fast motion estimation[J]. Journal of Data Acquisition and Processing, 2009, 24(5):660-663.

[16]杨虎,潘红兵,何书专,等.H.264视频压缩快速运动估计算法UMHexagons改进[J].计算机工程与设计,2013,34(2):550-555.

Yang Hu, Pan Hongbing, He Shuzhuan, et al. Improvements on fast motion estimation strategy based on UMHexagons for H.264[J]. Computer Engineering and Design, 2013,34(2):550-555.

Optimization and Improvement of Motion Estimation UMHexagonS Algorithm in H.264

Ren Keqiang , Lin Fangming

(School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, 341000, China)

Aiming at the existing problem of UMHexagonS algorithm in H.264, an improved fast motion estimation algorithm is proposed. The algorithm enhances the coding efficiency by optimizing the detection sequence of initial prediction motion vector(MV) according to the possibility of initial prediction MV becoming the best point, then an improved 5×5 spiral global search pattern is designed to reduce the search points of pattern, and an early termination technique for sub-macro block is proposed for further reducing the computation of motion estimation. The experimental results show that, with only negligible change of encoding performance, the improved algorithm can effectively reduce the motion estimation time and enhance the coding efficiency, and it can suit for video sequence of different motion intensities.

motion estimation; 5×5 spiral global search; initial prediction ; early termination technique

江西省教育厅青年科学基金(GJJ11132)资助项目；江西省研究生创新基金(YC2013-S199)资助项目。

2015-05-06；

2015-12-17

TN919.81

A

任克强(1959-)，男，教授，研究方向：信息隐藏、视频信号处理，E-mail：renke qiang@21cn.com。

林芳明(1989-)，男，硕士研究生，研究方向：视频压缩编码。