UMHexagonS算法的优化研究

第20卷第1期广西工学院学报Val.20 No.1 .2009年3月.JOURNAL OF GUANGXI UNIVERSIITY OF TECHNOLOGYMar.2009文章编号1004-6410 (20090) 01-0010-05UMHexagonS算法的优化研究郑艺玲(柳州职业技术学院信息工程系,广西柳州545006)摘要:研究了 H.264视频压缩标准中的UMHexagonS算法,根据宏块特征搜索范围以及预测运动矢量等的相关性,提出了简化搜索过程的改进方法。仿真实验表明，改进后的算法有效降低了H.264运动估计的运算量,使快速运动估计比UMHexagonS算法平均提高50%以上的效率。关键词:视频编码;运动估计;算法优化中图分类号:TP391文献标识码:A0引言H.264作为目前最新的国际视频编码标准,编码效率相对于以前的视频编码标准有了较大的提高。但由于H.264采用了一系列新的编码技术,导致编码复杂度大大提升。为提高视频编码的实时性,传统的快速块匹配运动估计算法基本上是基于以下几种方式:一是采用快速搜索的模型;二是利用时间和空间的相关性,采用运动矢量的提前预测算法;三是利用统计规律,设定阈值来提前终止搜索过程;四是采用快速的匹配度计算方程。虽然以上提及的算法能减轻运动估计的计算复杂度,但由于对H.264运动估计中的可变块、运动矢量等方面的一些特性及其相关性认识还有待深人的研究,与实际的搜索范围相比,仍然存在较大的差距,编码效率还有提高的空间[(。本文在文献[2]的研究基础上做了进一步的研究。从H.264运动估计的特点出发,分析了可变块的划分运动矢量的分布特性和时域、空域相关性,对目前流行的UMHexagonS快速搜索算法做了系统的分析，提出了减少不必要的重复的块匹配搜索步骤和搜索点数、提高运动搜索效率的改进算法,并用实验结果验证了该算法的可行性,对推动现有视频编码标准应用具有积极的意义。1 UMHexagonS 算法简介由z. B.Chen等提出的UMHexagonS算法能降低90%的整像素运动搜索复杂度,而平均峰值信噪比下降小于0.05 db,是目前效果最高的快速运动估计算法,被H.264标准所采纳。UMHexagonS算法包括以下几个步骤:①初始搜索点预测;②混合搜索;③细化搜索。1.1 初始搜索点预测①中值运动矢量预测:利用空间相关性,取已求出的当前块的左、上、右上邻块的运动矢量的中间值来预测当前块的运动矢量。②原点预测:考虑到在固定背景上的物体边界的情况进行预测。③上层块运动矢量预测:在H.264中,有7种不同的块分割方式,用已求出的当前位置上- -级模式运动向量,作为当前模式的运动向量的预测值,这样就可以用找出大块的运动矢量来预测其中小块的运动矢量。④前帧对应块预测:对通常的视频序列来说,物体的运动总具连续的因此在时域中的运动矢量存在着很强的相关性,因此可以利用前- -帧对应块 的运动矢量来预中国煤化工Y片CNMHG收稿日期:2008-11-18作者简介:郑艺玲(1968-),女,广东恩平人,柳州职业技术学院信息工程系讲师,硕士。第1期郑艺玲等:MHexagonS算法的优化研究11⑤相邻参考帧预测:利用时间相关性,将前面参考帧的运动向量按时间顺序缩放进行当前帧的运动向量预测。.找出以上的运动向量最小cost所对应的预测矢量,作为下一步搜索的最佳初始搜索点[3]。1.2混合搜索①非对称十字型搜索:对于- -般的自然视频序列来说,水平方向的运动要大于垂直方向的运动,因此能通过非对称的十字形搜索来近似找到最佳运动矢量。②5X5全搜索:以起始位置为中心的5x5小范围内的全搜索。③扩展六边形搜索:采用六边形的搜索模式进行多级搜索,由内至外逐层展开,选出的最匹配块位置作为下一步搜索的起始位置。与四边形相比,六边形搜索范围近似圆形,能覆盖更大的搜索区域。以上混合搜索步骤,在H.264的UMHexagonS算法中标记为first - step.1.3细化搜索①六边形搜索:采用半径为2的六边形搜索。对于小的预测模式(如4X4模式) ,因为其预测矢量的精度较高,因此可以跳过十字形搜索和多级六边形搜索,直接进行细化的六边形搜索。该步骤在H.264的UMHexagonS算法中标记为sec - step.②小菱形搜索:采用半径为1的小六边形一即通 常所说的小菱形,搜索到最小匹配误差点位于新形成的六边形中心为止。该步骤在H.264的UMHexagonS算法中标记为third_ step.2 UMHexagonS 算法的优化方案2.1 UMHexagonS 算法改进思路分析2.1.1宏块划分H.264 中有16x 16、16X8、8X16、8X8、8x4、4x8、4X4等7种不同的块分割方式,不同块大小之间的运动矢量存在很强的相关性。在运动估计算法中,搜索范围可设置为32x 32或16x 16,而划分的最大的搜索块为16X 16,最小的搜索块为4x 4.清楚地认识搜索范围与宏块划分之间的相关性,可为以下的分析奠定良好基础。2.1.2搜索范围分析由 于视频图像的运动相关性,即在实际中的视频图像大部分块是静止或准静止的,运动矢量的分布以(0,0)为中心向外发散,越往外概率越小,即运动矢量主要集中在搜索中心(0,0)附近很小范围内。因此对于搜索起点的预测-般从中心位置开始。以六边形变量的定义为例:static int Hexagon_ x[6] = {2, 1, -1, -2, -1, 1};static int Hexagon_y[6] = {0, - 2, -2, 0, 2, 2};如图1所示，六边形搜索模板的搜索范围覆盖了5x5的区域,共25个点。而大六边型搜索模板(初始状态)的搜索范围为9X9的区域,共16个点,扩展后的搜索范围分别为15X 15、21 X21 27>27的区域。另外,非对称的十字型模板与搜索范围和搜索步长相关。当搜索范围为32,搜索步长为2时,以预测的初始点为中心,非对称的十字型模板的水平搜索点为+1,士3, 5-.,....士31,垂直搜索点减半。而当搜索范围为16,搜索步长为2时,对应的十字型模板的水平搜索点和图1六边形搜索模板垂直搜索点相应减半。由以上分析可知,非对称的十字型模板的搜索范围的跨度为32x 16.设运动矢量为(mv - x ,mv _ y) ,搜索范围为search - range. 在UMHexagonS算法中,其搜索算法在头文件fast_me.h中定义了执行SEARCH_ONE.PIXEL的条件,因而可将搜索范围从全搜索的(2Xsearch_ range+ 1)2减少为(2x search_ range+ 1 - abs(mv _ x))X (2Xsearch ranre+ 1-ahs(mv - y)).如图2所中国煤化工示。由以上分析可知,搜索范围实际上呈动态缩小,而在first..TYHC N M H G围的搜索是不必要的(虽然早停止判断减少了一些搜索运算)。2.1.3预测初始点分析UMHexagonS 算法的多种模式预测运动矢量获得初始搜索点。由于视频序列的运动12广西工学院学报第20卷矢量大部分集中在(0,0)附近,而UMHexagonS算法采用的起点预测综合利用了帧内帧间相邻块运动矢量相关性,以及H.264采用宏块划分技术所带来的不同尺寸块的运动矢量相关性,因而可以选出最能反映当前运动块趋势的点作为初始搜索点,准确率相当高。以初始搜索点为中心,再进行下一步的搜索,使得搜索范围呈现相对动态的变化。2.1.4运动矢分布特征宏块的划分存在相关性,如当前块与帧内上方、左方和右上块的相关性最强,与其他位置的相关性则较弱,因而中值预测采用以上相关块得到较为精确的初始预测运动矢量。在分析中,应将宏块大小的划分和运动矢量大小的划分区别开来。小运动矢量,指的是块的运动位移较小,而不是宏块划分为小的块。实验统计表明,大块的运动矢量相对较小，而小块的运动矢量相对较大,而且视频序列的运动矢量存在偏置性的特点。通过对大量视频序列的研究表明,视频序列的运动矢量分布具有下列特征(图3所示):①运动矢量大部分集中在(0,0)附近;②运动矢量差值的概率分布在(0,0)附近出现更为明显预测初始点后的搜的峰值;索范围③经过中值预测后的运动矢量差更是明显的集中在(0,0)点周围(4]。另外,基于对运动矢量和宏块划分的特点,在实验分析中原来的搜索范围也可得出以下结论,即较大的运动矢量往往划分出较小的块,而较小的运动矢量划分较大的块。这也符合实际视频序列的特性,直观效果是运动剧烈的图像相邻帧之间细节变化较多,圈2搜索范围对比示例划分较小的块可更好地提高准确度,视频序列图像效果清晰Y轴度较好,而运动平缓图像序列变化较小,以大的宏块划分已能保证较好的图像质量。参照图3经过初始运动矢量预测以后,新的搜索起点如果不是落在坐标轴上,就应该落在任一象限之中。由此可见,在first _ step中存在较多的大范围搜索是不(1, 1)轴必要的。对于不必要的搜索,不但耗费了多余的运动估计时间,也影响了搜索的效率。2.1.5运动矢量偏置性分析 实验统计表明, 在运动估计中存在运动矢量中心偏置性。为便于分析,以搜索范围32像素为例子,假设极端的情况,初始搜索点落在I象限内的(2,2),根据运动矢量偏置性图3运动矢分布特性示意的特点,可以大致判定,要达到搜索范围的边界,至多搜索6X7=42个点(图4所示),这不但比first-step中理论上的搜索点数大大减少,而且在实际搜索中,由于初始搜索点的准确性较高,很好地避免了使搜索落人局部,因而搜索可以不必在相同的搜索区域内重复进行。从另一个角度分析,如果六边形搜索需要跨越I象限的大部分区域,可以倒推出,初始搜索1象限点的预测是失败的。2.2 UMHexagonS算法改进步骤在UMHexagonS算法高准确度的预测运动矢量的前中国煤化工下,结合实验对运动矢量、搜索范围以及宏块划分特性进-:fYHCNMHG的研究和认识,提出以下改进思路:图4运动矢量偏置性示意去除原算法中冗余的搜索步骤,即混合搜索:①非对称十郑艺玲等:MHexagonS算法的优化研究字型搜索;②5x5全搜索;③扩展六边形搜索。也就是去除了在H.264的UMHexagonS算法中标记为first_ step的搜索步骤,使得运动估计的搜索更加快捷。因此,改进后的算法步骤如下:①沿用UMHexagonS算法高效的多模式预测运动矢量以确定初始搜索点;②以初始搜索点为中心,进行六边形搜索,找出最优搜索点,直至最优搜索点落在六边形的中心;③在最优搜索点上做小菱形搜索,找出新的最优搜索点,直至最优搜索点落在小菱形中心;④其余搜索策略和搜索步骤沿用UMHexagonS算法的内容,包括:沿用sec _ step和third_ step 搜索步骤进行后续的搜索,沿用UMHexagonS算法中的早停止判断和阂值判断等。3改进算法的实验分析为验证改进算法的有效性,将该算法在H.264标准代码JM86的baseline档次下做了实现,对cif视频格式下不同运动强度的3个视频序列进行了测试,就编码时间、比特率、PSNR指标,对UMHexagonS算法和在其基础之上的改进算法进行了比较。实验条件:按照PP...序列类型编码;5个参考帧;7种搜索模式;搜索范围为16像素;量化系数为28、32、36 ,40;帧率为30 Hz;使用率失真优化和ME哈达码变换。执行平台:CPU Intel (R) Celeron (R)2.00 GHz;内存(RAM)768 MB.两算法实验结果比较如下:表1 fotbll cif - ori90.yov 序列搜索算法性能参数QP=28QP=32QP=36QP=40SNR . Y(dB)6.6233.7931.1828.83UMHexgoS算法Bieae(hirs)1263.78911.52621.00437.40Total encoding time for the seq.7.9697.3596.9226.719Total ME time for scquance0.9261.0630.7180.919SNR_ Y(dB)36.6131.19改进算法Birate(kbit/s)1263.60911 .34622.20438.60Total encoding time for the sq.7.4696.7506.0475.516Total ME time for sequence0.529 .0.5160.4950.263表2 stefan_ cif_ ori90.yuv序列搜术算法QP-3236.5433.4530.6128.15UMHexagonS算法Bitate(bi/s)1541.881119.06776.70541.86Total enoding tine for the seq.8.9847.9856.9371.0540.9991.2241.26536. sBitrate(kbit/s)1541.88 .119.06Total encoding time for the 9eq.8.0947.6417.1886.1400.5920.7360.423表3 news_ elif_ ori90. yuv序列QP=32 .37.6734.7132.0129.36UMHexagonS算法Birate(hbit/s)1279.92951.54691.26508.148.6577.8597.5466.7341.1571.3271.1340.95332.02951.54 .692.40508.98Total enooding time for the seq.7.4846.9546.5336.500Total ME time for sequence .0.5930.4070.4800.515基于以_上实验数据,各项指标分析对比结果如下:①总运动估计的时间对比分析:采用新算法比UM|中国煤化工十时间平均减少了51.32% ,有效地提高了编码速度(实验数据分析见表4-表:TYHCNMHG②总编码时间的对比分析:采用新的改进算法,比采用UMHexagonS算法平均减少了约10%左右(实验数据分析略) ;14广西工学院学报第20卷③亮度峰噪值对比分析:采用新的改进算法,总体上保证了图象质量(实验数据分析略);④比特率对比分析:采用新算法,比特率几乎没有变化(实验数据分析略)。袈4 foball dif - ori90.yuv序列改进:搜术算法性能参数QP=28QP-32QP=36QP=40UMHexagonS 算法Total ME time for sequence0.9261.0630.7180.919改进算法Total ME time for seruence0.5290.5160.4950.263改进42.87%51.46%31.06%71.38%49. 19%表5 stefan_ cif _ ori90. yuv序列改进:搜索算法QP=32UMHexagonS算法Total ME time for squence1.0540.9991.2241.265Totel ME time for sequence0.5920.7360.42343.83%47.05%39.87%。66.56%49. 33%表6 news _ cif . ori90. yuv序列改进:平均改进1.1571.3271.1340.9530.5930.4070.480.51548.75%69.33%57.67%45.96%55.43%表7各测试序列平 均改进所占百分比(%)测试系列Fouballstefannews平均所占百分比各系列改进所占百分比49.1949.3355.4351.324结语本文对H.264中采用的UMHexagonS算法进行分析和研究,并在原算法基础上进行了改进,实验结果显示,改进算法在基本保证图像质量和码率几乎没有增加的情况下,大大减少了原算法中不必要的搜索范围,减少了搜索点数,较大幅度地降低了运动估计的耗时,从而有效地提高了整体的编码效率,也更加有利于实时应用。与文献[2]的实验结果比较,运动估计时间减少了10%以上。参考文献:[1]陈纯,杨智,卜佳俊,等.一种基于H.264的可变块快速运动估计算法[].中国图象图形学报, 2007, 12(2):272 ~276.[2]郑艺玲,谢翠兰.H.264中FME算法的优化[J].计算机工程, 2008,34(13):207~209.[3]杨育红,徐煩,季晓勇.快速运动估计UMHexagonS算法的探讨与改进[J].计算机工程与应用,2006.42(11):52~54.[4]段娟,张楠.快速可伸缩环形搜索算法[J].计算机工程与应用,2006,42(30):14~19.Research and Optimization of UMHexagonS algorithmZHENG Yi-ling(Department of Information Engineering, Liuzhou Vocational & Technical College, Liuzhou 545006, China)Abstract: This paper introduces the UMHexagonS algorithm and presents an optimal algorithm based on the cor-relation of the block feature, search range and forecast motion vector. The experimental results show that the ef-ficiency of this optimized algorithm reduces the amount of comp中国煤化工lexagonS algorithmfrom H.264 more than 50%.CYHCNMHGKey words: video coding; motion estimation; algorithm optimizanon