H.264中快速运动估计算法的一种改进方案

1、第27卷第4期计 算 机 应 用 研 究VoI27 No42010年 4月Application Research ofComputersApr2O10H264中快速运动估计算法的一种改进方案蔡自兴，蒋冬冬，谭 平，安基程(中南大学信息科学与工程学院，长沙 410083)摘 要：UMHexagonS是视频编码标准 H264的一种快速整像素运动估计算法 ，该算法较之全搜索算法在性能上有很大提高，但仍存在运算量大、复杂度高、耗时等问题。利用提前中止思想，在螺旋搜索和多层次大六边形搜索阶段增加提前中止条件，加速算法中止，然后用特殊的改进模板搜索法替换螺旋搜索策略，快速匹配最佳点。在 JM102测试模

2、型上进行 了算法验证，实验结果表明，改进算法在保证编码性能的同时，可以有效地减少5 15的运动估计时间。关键词：H264 ；运动估计；UMHexagonS算法；提前中止；螺旋搜索中图分类号：TN91981文献标志码：A文章编号：10013695(2010)04152402doi：103969jissn10013695201040 090Improvementon fastmotion estimation algorithm for H264CAIZixing，JIANG Dongdong，TAN Ping，AN Jicheng(ColegeofInformationScienceEngine

3、ering，CentralSouthUniversity，Changsha410083，China)Abstract：UMHexagonS is an rapid integerpixelmotion estimation algorithm for H264 video coding standard Itshowed much higherperformance compared to fullsearch，butthere were stilsome problems，such as heavy computing，high eom-plexityandtimeconsumingTore

4、solvetheseissues，thispaper，ontheonehand，addedearlyterminationjudgmenttobotlspiralsearch stage and multibighexagon search stage，on the other hand，replaced spiralsearching by a specialoneProposed the lgorithma notonly sped up term inate the lgorithma，butalso accelerated to match the bestpointsItimplem

5、entedand verified in JM102，which wasatestmode1The resultsshow thatthe improved UMHexagonS algorithm can reduce5 一15 time ofmotion estimation，butstilkeep the original oneSgood coding perform anceKey words： H264；motion estimation；UMHexagonS algorithm；early term ination；spiralsearch运动估计是视频压缩编码的关键部分，能有效

6、地去除序列图像的帧间冗余。在 H264的编码过程中，运动估计无疑是复杂度和运算量最高的部分 。目前 H_264参考软件JM102已正式采纳了采用由 Chen Zhibo等人 提出的“非对称十字形多层次六边形格点搜索”(unsymmetrical cross multihexagon一 d search，UMHexagonS )算法来进行运动估计，它的运算量相对于快速全搜索算法可节约9o以上，同时能保持较好的率失真性能 。在 JM 的测试模型中采用了该算法作为整像素运动估计算法，其性能非常接近全搜索算法。由于该算法对可变块大小和运动矢量等数据特征及其相关性等因素尚未充分挖掘并应用于搜索过程，搜索

7、的点数还相对较多，该算法仍有待改进。本文针对复杂度高、运算量大的问题，利用提前中止思想 3和优化局部搜索模板 的方法来改进算法，减少不必要的搜索点数。具体的改进有两处：a)在螺旋搜索和多层次六边形网格搜索之后加入一个搜索阈值判断，在运动估计性能达到满意的情况下提前结束该步搜索；b)根据场景中运动物体一 般的运动特性采用合适的模板代替螺旋搜索，从而减少搜索点数，降低运算量，减少计算时间。1 UMHexagonS算法介绍在已有的块匹配算法中，理论上全搜索算法具有最高的精度，但存在搜索时问长和运算量大等缺点，难以满足实时要求。为此学者们已提出多种快速运动估计算法，如六边形搜索(hexagonsear

8、ch，HEXS)、菱形搜索(diamondsearch，DS)等。这些算法简化了计算，却是以牺牲图像质量为代价，降低了图像精度。而 UMHexagonS算法的运算量相对于全搜索算法可节约 90以上，同时能保持较好的率失真性能。非对称十字形多层次六边形格点搜索(UMHexagonS)算法的基本步骤如下 ：a)起始搜索点的预测。利用五种预测模式求预测运动矢量 MV。d。b)非对称十字形模板搜索，如图 1(a)所示 。C)螺旋搜索。类似于全搜索策略，以目前最佳点为中心，搜索(一2，2)方形区域内的25个点，如图 1(b)所示。d)多层次大六边形模板如图 1(c)搜索。在 14searchrange的

9、范围内，用不断扩大倍直径的大六边形模板进行搜索。收稿日期：2009-0618；修回日期 ：20090813 基金项目：NSFC重大专项基金资助项目(90820302)；NSFC面上 (青年)基金资助项目(60805027)；国家博士点基金资助项目(200805330005)；米塔尔创新创业基金资助项目(08MYl1)作者简介：蔡自兴(1938)，男，联合国专家，纽约科学院院士，教授，博导，主要研究方向为人工智能、智能控制；蒋冬冬(1984一)，男，浙江湖州人，硕士研究生，主要研究方向为视频压缩编码、嵌入式 (do2jianggmailCOB)；谭平(1981一)，男，湖南涟源人，博士研究生，主

10、要研究方向为数字信号处理；安基程(1983一)，男，硕士，主要研究方向为图像视频编码、信号处理第 4期蔡自兴，等：H264中快速运动估计算法的一种改进方案1525e)多圈的中六边形模板(图 1(c)搜索。f)小菱形模板(图 1(e)反复搜索，得到最终的运动矢量。器 圈 豳(a)非对称十字形搜索(b)螺旋搜索(c)六边形搜索图1 UMHexagonS算 法中使用的各种搜索模板另外，在 a)b)中存在提前中止搜索的闽值判断。如果搜索到的点很满意 (绝对误差 和 SAD很小 )则转到 f)；如果比较满意(SAD较大)则转到 e)；如果不满意(SAD很大)则继续顺序搜索。UMHexagonS算法流程如

11、图 2所示。SAD 一，、卜藩i l辈囊妻藩不SAD很大董堡塞H 塞奎鎏鬓萎HH 墅薹图2 UMHexagonS算法 流程图2 基于 UMHexagonS的改进方法H264参考模型 JMIO2中 UMHexagonS算法，在螺旋搜索和多层次大六边形模板搜索阶段无阂值判断和提前中止处理，导致即使当前最佳点已经达到很满意状态，仍继续搜索剩余点，浪费运算量和计算时间 61。针对这一问题最简单有效的方法是加入 EARLYTERMINATION的阈值判断和提前中止处理，如图 3所示。实验证 明，这样处理可以有效地减少大约6的搜索点数。H264参考软件 JM102上实现了该算法，并对 CIF格式下不同运动

12、强度的三个视频序列 (akyiocifyuv，foremancifyuv， mobile cifyuv)和 QCIF格式 下的 foreman序列 (foremanqcifyuv)进行了实验 。实验条件：采用 IPPP格式进行编码；参考帧数为 5；帧率为 30 Hz；量化系数为 28；使用率失真优化；CIF格式：searchrange=32，QCIF格式：searchrange：32。测试序列如下：a)akyio_cifyuv，整个场景运动比较低的 CIF序列类型代表。b)foremaneifyuv，整个场景运动一般的 CIF序列类型代表 。c)mobilecifyuv，整个场景运动比较剧烈的

13、 CIF序列类型代表。e)remanqeifyuv，整个场景运动一般的 QCIF序列类型代表。实验平台：IntelCore2DuoCPU 183GHz；内存 lGB。SAD SAn壁匹二=；层次大 五l堕 堡室广SA图4 UMHexagonS算 法改进后流程图32 实验结果分析与对比本文主要采用 y、U、V各分量 的峰值信噪比(PSNR)和运动估计时间(MET)作为算法性能评判的标准。表 1、2是 对以上四个序列 40帧进 行测试的实验结果。表 1中数据 显示了MET以及改进后算法相对原算法 MET的改变率(一代表改善)；表 2中数据代表各分量 PSNR以及改进后算法各分量PSNR的改变率(+

14、代表改善)。表 1 UMHexagonS算 法改进前后平均 MET比较S口 嚣 口(a)菱形一六边形模板 (b)非对称十字形模板(c)六边形模板图3 三种改进搜索模板在 UMHexagonS算法的步骤 C)中使用的是螺旋搜索。螺旋搜索是一种类似全搜索的搜索策略，需要计算整个搜索范围内所有点的 SAD值。众所周知 ，全搜索是一个复杂度高、运算量大且费时的搜索算法，目前为止已经有很多搜索时间大大降低，同时率失真性能很好的搜索模板，如六边形模板、菱形模板等。针对局部范围内螺旋搜 索效率低下的问题，考虑到经典运动估计模板搜索的高效性，利用替换模板的办法可以很好地解决该问题，并在一定程度上可减少运算量，

15、降低计算时间，同时率失真性能几乎没有降低。在目前国内外学者的研究中，六边形模板和菱形模板效果最突出，如文献7。本文考虑到实际应用的图像中物体水平运动频率远大于垂直方向，经综合分析和反复实验得出结果，采用菱形一六边形模板(图 3(a)或非对称十字形模板(图 3(b)代替螺旋搜索的效果也比较突出，甚至优于六边形模板，改进后的算法流程如图 4所示。3 实验结果与分析31 实验环境为说明本文改进的 UMHexagonS算法的搜索效率，在测蓊序 原算法 六边形模板 菱模板-A进形改囊麦差从表 1看，改进算法的 MET时间减少明显，减少程度为515，两种模板的改进算法对运动剧烈的序列改进效果明显优于运动平

16、缓的序列，因为在运动幅度比较大的情况下，菱形一六边形模板和非对称十字形模板的运动搜索性能卓越。另外，针对三种不同的模板，表 1反映出：a)使用六边形搜索模板、菱形六边形搜索模板和非对称十字形搜索模板对算法性能改进的效果依次增强，这一点对场景运动比较剧烈的序列(如mobilecifyuv)效果尤其明显；b)使用两种改进模板的算法效果明显优于使用螺旋搜索策略的算法，略优于文献7使用六边形模板算法。从表2中可以看出，改进后算法各分量 PSNR相对于原算法有略微降低，但仍保持着与原算法相当接近的 PSNR，甚至局部的 PSNR分量略有上升。相对于文献7使用六边形模板算法，PSNR分量基本一致。综合来看

17、，基于菱形一六边形模板和非对称十字形模板的改进方法使各分量 PSNR保持在原算法水平的情况下，大幅(下转第 1529页)第4期李贤慧，等：基于概率距离及融合时空特征的镜头相似性度量1529 儿图3 本文方法检索结果表1 本方法四种类型视频镜头查全率和差准率霉一5霉为了更好地说明本方法的有效性，本文同时对比了只使用_i=时间特征、只使用空间特征、时空特征融合和欧氏距离等四种方法的查全鬻率 (recal1)和查准率 (precision)，对比结果如表 2所示。其中数据栏瞬的第一至四行对应体育、电影、动画、新闻视频。从表 中看出隧，使用时空特征融合的方法查全率和查准率明显地高于只使用时间特征、只使

18、用空间特征和欧氏距离。表2 四种方法的查全率和差准率对比4 结束语本文提出了一种新的镜头相似性度量方法。通过概率距离计算镜头空间相似性，利用直方图交求解镜头时间相似性，融合时空相似性最后得出镜头总相似性。实验部分对比了单文提出的方法更加有效。下一步工作主要是选取一种有效的方法提取镜头关键帧来代表镜头，减少检索过程中的计算量。参考文献：1 SHAO lie，HUANG Zi，SHEN Hengtao，eta1Batchnearestneighborsearch forvideo retrievalJIEEE Trans on Multimedia，2008，10(3)：4094202j GAO

19、Xinbo，LIXue-long，FENG JunShotbased videoretrieval withopticallowf tensorandHMMssourceJPatern RecognitionLeters，2009，30(2)：140147(3 彭宇新，NGO CW ，肖建国一种基于二分图最优匹配的镜头检索方法J电子学报，2004，32(7)：113511394 彭德华，申瑞民，江济基于内容检索中的镜头相似性度量J计算机仿真，2003，20(12)：981005 付畅俭，李国辉挖掘视频层次结构一改善视频管理 J】计 算机应用研究，2007，24(6)：1551606 GAO Y

20、ue，DAIQionghaiSbotbasedsimilaritymeasureforcontent-basedvideosummarizationCProcofthe15thInternational Conferenee on Image Processing San Diego：IEEE Press，2008：2512-25l57 ZHOUSK，CHELLAPPA RFrom samplesimilaritytoensemblesimilarity：probabilistie distance measure in reproducing kernel HilbespaceJIEEETr

21、ansonPaternAnalysisandMachine Inteligence，2006，28(6)：9179298 边肇祺，张学工模式识别M北京：清华大学出版社，20009 DEVIJVER PA，KITFLER JPaternrecognition：astatisticalapproachMLondon：PrenticeHal，198210GuidelinesorftheTRECVID 2007 evaluationDBOL (2007)独使用时间特征、空问特征以及融合时空特征的检索效果，并且与经典的欧氏距离镜头相似性度量方法相比较，可以看出，本(上接第1525页)降低算法的运动估计时

22、间和计算量，增强了算法实时性。表 2 UMHexagonS算法改进前后平 均 PSNR比较4 结束语本文结合 JM模型，首先介绍了 H264中的运动估计算法uMHexagons算法，然后针对 UMHexagonS算法的特点和不足，提出了两点改进：a)在螺旋搜索和多层次大六边形搜索阶段使用 EARLYTERMINATION进行提前中止；b)使用菱形一六边形搜索模板或者非对称十字形搜索模板代替螺旋搜索阶段的全搜索策略。改进算法在保证视频序列信噪比甚至有所提高的情况下，降低了5 一15的运动估计时间和较少20080117htp：wwwnlpirnistgovprojeetstv2007tv2007htm1运算量，增强了实时性。参考文献：1 WIEGAND T，SULLIVAN G JITUT ReeH264 ISOIEC14496一IOAVC draft ITUT recommendation and inalf draft international standardofjointvideospecifcationSJointVidEO Team(JVT)ofISOIEC JTC1SC29WGIIand ITUT SG16Q6 Doe20032 WIEGAND T，