基于x264的快速运动估计算法优化 7页

万方数据2010年11月第17卷96期控制工程ControlEngineeringofChinaNov．20lOV01．17，No．6文章编号：1671-7848(2010)06-0820-04基于x264的快速运动估计算法优化黄春庆，邱晓彬(厦门大学自动化系，福建厦门361005)摘要：运动估计是H．264视频编码标准中最重要且最耗时的一部分，大约占用这个视频编码的60％一80％的时间，针对x264中UMHexagonS快速运动估计算法编码速度的局限性，分别对算法中阈值的选择、提前终止条件判定、大六边形搜索模式三方面做了优化．同时改进COSTMV()函数，有效地缩短了计算SAD值的时间。通过仿真实验表明，优化后的UMHexagons算法在视频质量(PSNR)下降很小的情况，搜索点数减少了约30％，平均节省了20％一40％整体运动估计时间，提高了编码器的实时性。关键词：运动估计；UMHexagonS算法；编码速度；COST-MV()中图分类号：TP273文献标识码：AOptimizationonFastMotionEstimationAlgorithmBasedonx264HUANGChun．qing．olUXiao．bin(DepartmentofAutomation，XiamenUniversity，Xiamen361005，China)Abstrad：MotionestimationisthemostimportantandtimeconsumingpartofH．264videocoding．ittakesabout60％一80％ofen．codingtime．ToimprovetheencodingspeedoftheUMHexagonSalgorithminx264，alloptimizedalgorithmisproposedviathemodifiedschemeofthethresholdselection，earlyterminationofconditionandbighexagonsearchmode．ThemodifiedmethodoftheCOsT—MV()functionispresentedtoshortenthecomputingtimeofSADvalue．ThesimulationexperimentationshowsthattheproposedalgorithmsCallreducesearchpointsbyabout30％withsmallvideoqualitydecline．saves20％to40％oftheestimatedtimeandenhancethereal·timeperformanceoftheencoder．Keywords：motionestimation；UMHexagonSalgorithm；encodingspeed；COST_MV()1引言H．264是由11'U-T和ISO／IEC组成的联合视频专家组制定的视频编码标准，与以往的MPEG4和H．263标准相比，采用了更加高效和精确的运动估计预测算法，在同样的视频质量下其编码效率提高了50％(1】，然而，其运算复杂度还是相当的高，难于实现实时编码的要求。运动估计是H．264标准中最重要的环节。目前常用的估计方法是块匹配法(BMA)。最简单的快匹配算法是全搜索法(FS)心J，其精度最高，性能最好，但是计算量太大，不适用于实时压缩，但可以作为其他快速算法的编码性能的参考标准。现有中比较有代表性的快速算法有早期的三步搜索法(TSS)旧。和二维对数搜索法(LOGS)Ho等，该类算法特点是限制搜索点数而减少计算量，但是很容易陷入局部最优。改进的新三步法(NTSS)∞J，被MPEG-4采用的菱形算法(Ds)∞1和六边形算法(HEXS)一1以及被H264吸收的“非对称十字形多层次六边形格点”算法(UMHexagonS)旧1等利用中心偏置特性，提高了搜索精度。其中，又以UM．HexagonS算法最优秀，该算法使用混合扩展的运动搜索方法获得良好的编码效果，但是由于搜索模块过多以及模块的过于复杂，编码速度不能满足实时性场合的需求。本文对UMH算法进行深入研究，提出了自适应预测阈值、加入两处提前终止判断、对5×5模板和大六边形模板进行改进以及COST—MV函数等几个方面的优化。通过实验表明，改进的算法在视频质量下降很小的同时搜索点数减少了30％。整体的估计时间节约了20％～40％。2UMHexagonS算法1)UMHexagonS算法简介由z．B．Chen等提出的UMH算法针对H．264中的运动估计，采用多种运动矢量预测及六边形搜索模式，能降低90％收稿日期：2010-03-31；收修定稿日期：2010-05．17基金项目：国家自然科学基金资助项目(60704043)作者简介：黄春庆(1972·)，男，福建泉州人，教授，博士，主要从事机器人控制，控制系统分析与设计，以及机器人运动规划等方面的教学与科研工作。\n万方数据第6期黄春庆等：基于x264的快速运动估计算法优化·821·的整像素运动搜索复杂度，而PSNR的下降小于0．05db—o。x264中UMH算法代码位于voidx264一me—search—ref()中，采用2个提前终止门限(thresholdl，threshold2)，不同宏块分割采用不同的门限值，16×16模块设定thresholdl=2000，threshold2=500，UMH算法的基本步骤如下：Stepl搜索起点的预测(PMV)在函数void也64一mb—predict—mv一16×16()中利用空间相关性，计算出当前宏块的左、上、右上块运动矢量(mvl，mv2，mv3)的中间值mvO=(pmx。pmy)，加上参考帧原点(0，0)的运动矢量mv4。以上的(mvO，mvl，mv2，mv3．mv4)5个点作为候选点，计算出它们的SAD值，SAD值最小的点记为最小误差点(MBD)，该点的mv作为搜索起点PMV。Step2以Step1中的搜索起点为中心进行小菱形搜索，如果搜索起点不等于(0，0)，还要以(0，0)点为中心进行小菱形搜素，计算出MBD点以及对应的SAD值，如果SAD值小于thresholdl，转Step3，否则转Step5。Step3以Step2MBD点为中心，中菱形为模板进行搜索，得到新的MBD和SAD值，如果SAD小于threshold2，结束搜索，当前MBD点就是最优匹配点，否则转Step4。Step4以Step3的MBD点为中心，采用非对称十字模板il钊进行搜索，得到新的MBD点，再以该点为中心进行正八边形搜索，如果MBD点不改变，则结束搜索，否则转Step5。Step5以上面的MBD点为中心，进行非对称十字模板(搜索长度横轴是纵轴的2倍)搜索，计算出MBD点，以该点为中心进行5×5的逐步搜索，如果计算出的MBD值不变，转Step7，否则转Step6。Step6以Step5MBD点为中心，大六边形模板搜索，开始的搜索半径是4，以后逐步加4进行搜索，直到搜索边界为止，再转Step7。Step7以上面的MBD为中心，完成一次六边形搜索的全部过程。田口图1小菱型模板Fig．1SmallDApattern各个模板，如图1～图6所示。图2中菱形模板Fig．2MiddleDApattern图3非对称十字模板Fig．3Unsymmetrical-croSS圈口翻斟崩凿图4正八边形模板Fig．4Regularoctagon图55x5逐步模板Fig．55x5pattern2)UMHexagonS算法分析通过UMHexagonS算法简介可知，UMH算法采用复合式搜索，结合多种简单模型的优点，由中心点分级向外扩展搜索，最大限度地避免了搜索点的重复计算，加上高效的预测起点，使得UMH算法拥有优秀的编码性能。但是深入研究发现，UMH算法中还是存在许多不足，主要表现在以下几方面：①不足之一从Step1可以看出，UMH算法在检查完5个候选起点后，无条件地继续检查mvO和(0，0)点周围的8个点，对于静止视频或者是运动缓慢的视频序列，这些点的搜索显得有些多余。②不足之二UMH算法的阈值在同一宏块中是固定的，这样对一些运动缓慢的视频序列不能有效地提前终止，而对于运动剧烈的视频又过早终止。③不足之三Step5和Step6选择的模块搜索图6大六边形模板M辱6Ljl曜eHexagonpattern点数过多(Step5中共16+25=41点，Step6中共16×4=64点)，虽然提高了搜索的精度，然而浪费太大的计算量，难于满足剧烈运动视频序列的实时要求。④不足之四在x264中的COST—MV()函数中，计算SAD值时需要计算16×16次的减法，然而有些搜索点根本不需要计算这么多次就可以判定SAD值已经大于最优的SAD值。3优化后的UMHexagonS算法目前，提高运动估计算法的效率的主要技术包括初始搜索点的选择，匹配准则，和运动搜索策略。本文基于前文提出的不足，在初始搜索点的选择和运动搜索模块上提出以下3个方面的技术优化。1)基于自适应的阈值技术以及提前终止判定的加入统计发现约98％的静止宏块(16×16)在(0，0)\n万方数据·822·控制工程第17卷的SAD值小于512，因此本文在检查完5个候选点时加入if(SAD1ooo)threshold2=1ooo；／／限幅threshold2[500，1000]If(thresholdl>2000)thresholdl=2000；／／限幅thresholdl[1500，2000]2)5×5和大六边形搜索模块的优化根据中心偏置特性，运动矢量的概率分布是以(0，0)点为中心向四周递减的。通过对标准视频序列运动矢量的统计研究发现，80％的运动矢量集中在搜索中心5×5像素范围内，而中间3×3像素区域的运动矢量就高达70％“2l。虽然5×5模块运动矢量概率比3×3高10％，但是搜索点数却增加了64％。因此本文采用3×3模块代替5×5模块，同时把模块3的初始搜索半径改为3(x264中是5)，3×3模块，如图7所示。圈73×3模板Fig．73X3pattern对于Step6使用的多层次六边形十六格点搜索，如以原点(0，0)为中心，共需要搜索16×4=64个点。一般要执行到Step6的宏块都是运动剧烈的视频部分，SAD值大于threshold!或者运动矢量半径大于5。因此，针对不足之三，本文提出一种宏块剧烈程度的判定方法，根据剧烈程度不同采用不同的多层次六边形搜索半径，详见如下：L=max{Imv．菇I+Imp．yl}；my∈{mvOmvlmv2mv3}∥获取相邻块搜索半径最大值预设两个阈值L，，如，其中，L，=boost)gotoEND；／／添加2calnum++；／／添力口3{pixl+=i_stride_pixI：pix2+=i_stride_pix2；}END：returni_sum；／／添加4本文主要研究16×16模块，因此代码中ly=Ix=16。由代码可以看出每个搜索点需要计算pixl[x]一pix2[x]减法16×16次，本文在其后添加if(i_sum>=bcost)gotoEND条件，在i—sum的值大于最优的sad值就跳出循环，节省多余的计算量；同时增加一个32位的全局变量calnum用于记录pixl[X]一pix2[x]计算次数。4实验结果与分析本实验使用x264版本：x264—080605；仿真环境：VC6．0；主要设置参数：帧频30，参考帧1，搜索窗13大小33×33，编码序列为IPPP格式，量化系数为26，CABAC熵编码。选取x264里面的4种算法：FS，DIA，HEX，UMH，优化的算法记为EUMH。为了比较的公平性，实验选取3个不同运动特征的经典CIF格式视频序列：Foreman，Coastguard和Bridge。其中，Foreman运动较剧烈，Coastguard运动和纹理都一般，Bridge运动比较缓慢。实验数据，见表1，表2。\n万方数据第6期黄春庆等：基于x264的快速运动估计算法优化·823·表2运动估计时间比较Table2MEtimedata表1比较了5种算法的编码性能，包括视频质量(PSNR值)和编码速度(用平均搜索点数COST表示)；表2对COST_MV优化前后整体运动估计时间(ealnum值)进行对比。数据分析：从表1可看出5种算法中Fs的视频质量最优，但需要搜索整个搜索窗中的1089个点，计算量太大。DIA和HEX的编码速度快，但是视频质量下降也较多，UMH算法搜索点数明显高于DIA和HEX快速算法。EUMH算法相对UMH算法节省了约30％的搜索点数，非常接近HEX的编码速度，约为Fs的60倍，同时EUMH算法信噪比(PSNR)比UMH下降不超过0．1db，基本保持原有算法的视频质量，优化后的UMHS算法更适合于高清晰视频压缩要求场合的应用。从表2可以看出，COST—MV()优化后的Cal-Inlm值明显要小于优化前，这就大大提高了整体的运动估计时间，特别是对于运动较缓慢的视频序列，提升比率可以高达42％，在一些要求实时性的场合提供性能更好的x264算法。改进的EUMH算法与原UMH算法的搜索平均值COST和峰值信噪比PSNR的比较，测试序列是Foreman．cif，如图8，图9所示。图8UMH与EUMH的PSNR比较(foreman)Fig．8PSNRofUMHandEUMH图9UMH与EUMH的COST比较(foreman)Fig．9COSTofUMHandEUMH(下转第848页)\n万方数据·848·控制+工程第17卷从图8的波形可以看到，当输入电压加干扰而给定值突降时，输入电压振幅增大，积分斜率会变得更陡。但是不管积分斜率怎样变化，基于单周期控制的双管正激变换器在每一个周期中都将会进行快速响应，消除所产生的误差，使积分值始终跟随变化的给定值，并且达到新的稳定状态。由此可见，在简化单周期控制技术实现过程的同时，仍能够保持其快速消除误差，动态实时的获得稳定输出。5)纹波电压输入电压和负载保持不变时，电压纹波为0．1l％；输入电压加干扰时电压纹波为0．12％；负载突变时电压纹波为0．1l％；输入电压加干扰且给定突变时电压纹波为0．12％，均远远低于O．5％，完全符合开关电源的性能指标要求。从上述的仿真结果可以看到，单周期控制技术无论是在输入电压受干扰还是输入电压和给定值变化时均能很好的控制输出，使其能够快速地达到给定值。这充分说明基于单周期控制的双管正激变换器具有良好的抗干扰能力和快速的动态响应速度。5结语过对系统的电压、负载及给定等参数变化情况分别进行分析及研究，研究结果表明运用了单周期控制技术的双管正激变换器具有良好的动、静态特性及较强的抗干扰能力。将此新型电路运用到实际中，必将会使它在工业领域的应用范围更宽、效果更好。参考文献(References)：[1][2][3][4][5][6]本文研究了双管正激变换器，并将单周期控制[71技术应用于双管正激电路，取得了较好的效果。通顾亦磊，顾晓明，吕征宇，等．一种新颖的宽范围双管正激型DC／DC变换器[J]．中国电机工程学报．2005，25(2)：44-47．(GuYilei。GuXiaoming，LvZhengyu，eta1．AnovelwiderangedualswitchforwardDC／DCconverter【JI．ProceedingsoftheCSEE，2005。25(2)：44-47．)毕闯，王京梅．电压反馈型正激变换器中分岔与混沌现象的研究[J]．系统仿真学报，2009，21(20)：6585-6588．(BiChuang，WangJingmei．InvestigationofbifurcationandChaosinvoltage．fedforwardconverter[J]．JournalofSystemSimulation，2009，21(20)：6585-6588．)盛专成，李广勇，贺怀谦．一种双正激电路的软关断拓扑[J]．电力电子技术，2001，35(3)：43-46．(ShengZhuancheng，LiGuangyong．HeHuaiqian．AnewsoftswitchingtopologyfordoubleswitchingforwardconverterJ1．Powerelectronics．200l。35(3)：43-46．)GuYL．ZhengY．QianZM．DC／DCtopologyselectioneriterionfC1．Xi’an：IEEElPEMCProceedings。2004。YangGS，GengH，eta1．Anovelcontrolstrategyofinductionmo-totsfortheoptimiza—tionofbothefficiencyandtorqueresponse『C]．Busan，Korea：T}Ie30thAnnualConferenceoftheIEEEIn．dustriaJElectronicsSociety．2004．)XuM．LeeFC．Generalconceptsforhish-efficiencyhigh-frequency48VDC／DCconverterC】．Acapulco，USA：PowerElec．tronicsSpecialistConference．2003．XieXF，LiuJCP．PoonFNK．eta1．Twomethodstodrivesyn．chmnousreetifiemduringdeadtimeinforwardtopologiesIC]．NewOdeans。USA：IEEEAPEC．2000．—+·—■——+—+-+·+—+-+一_．——+—+-+-+*+—．．——+一—一+—+—+—+呻·+—+-+—+——一+—+—■——-卜-+—+-+-+·+—■——+—·+--—-—+·_．叶—+-+-+—·●-．(上接第823页)从图8和图9中可以看出，优化后的EUMH算法搜索点数明显会少于原UMH算法，峰值信噪比变化很小，基本保持了原算法的高视频质量。5结语本文通过深入研究x264中的UMHexagonS快速运动估计算法，提出了自适应阈值选择、提前终止判定增设、大六边形模块优化以及COST—MV()宏函数优化等几方面的改进，有效地降低了搜索点数，缩短了整个运动估计的时间，为视频压缩在高质量视频要求和实时性要求的场合提供更好的算法选择。参考文献(References)：[1][2][3][4]ChenJ．64videocoding＆transmissionsystemandratecontrolre-search[D]．Shanghai：ShaughaiJiaoTongUniversity，2007．DufauxF。MoscheniF．Morionestimationtechniquesfordigital"IV：Areviewandanewcontribution[J]．ProceedingsoftheIEEE，1995，839(3)：858-876．JainJ．JainA．Displacementmeasurementanditsapplicationininter-frameimagecoding[j]．IEEETransaetiomonCommuniea-tions，198l，29(5)：1799—1806．LiuLK．FeigE．Ablock-basedgradientdescentsearchalgorithmforblockmotionestimationinvideocedingfJ]．IEEETransac-tionsonCircuitsandSystemsforVideoTechnology。1996，6(4)：419-422．[5][6][7][8][9][10][11][12][13]LiR．ZengB，“uML．Anewthree—stepsearchalgorithmforblockmotionestimation[J]．IEEETransactionsonCircuitsandSystemsforVideoTechnology，1994，4(1)：438442．ZhuS，KKM．Anewdiamondsearchalgorithmforfastblockmatchingmotionestimation[J]．ProceedingsofICICS，1997，1(2)：292-296．ZhuC．LinX．LChau．Hexagon—BasedSearchPattenforFastBlockMotionestimation[J]．IEEETransonCSVT，2002，2(4)：349-355．“HY，“uMJ，ZhangZQ．Anewfastmotionestimationalgo-rithmbasedoilH．264『J1．2009InternationalConferenceonMul．timediaInformationNetworkingandSecurity，2009．1(1)：287·290．王伟，李伟．基于可变分块尺寸的多模板运动估计[J]．自动化学报，2009，35(1)：34-38．(WangWei，LiWei．Amultiplepat—ternalgorithmforblockestimationbasedonvariableblock．size[J]．2009，35(1)：34-38．)GhanbariM．Thecross-searchalgorithmformotionestimation[J]．IEEETransactiononCommunication．1990．38(6)：950-953．何宜宝，毕笃彦，许悦雷，等．基于时空相关性自适应运动估计快速算法[J]．计算机工程。2009，35(13)：228-231．(HeYiban，BiDuyan．XuYue．1ei．eta1．Fastadaptivemotionestima．donalgorithmbasedonspatiotemporalcorrelation[J]．ComputerEngineeing，2009，35(13)：228·231．)XuJ．ChenZ。HeY．EfficleatfastMEpredictionsandearlytermi．nationstrategybasedoilH．264statisticalcharacters『J】．InThe2003IEEEPacific-RimConferenceOnMultimedia。Dec．2003．1(6)：218-222．徐晗路．基于H264的运动估计算法研究[D]．成都：电子科技大学，2009．(XuHanlu．MotionestimationalgorithmstudybasedonH．264[D]．Chengdu：UniveraityofElectronicSeieneeandTechnologyofChina。2009．)\n基于x264的快速运动估计算法优化作者：黄春庆，邱晓彬，HUANGChun-qing，QIUXiao-bin作者单位：厦门大学,自动化系,福建,厦门,361005刊名：控制工程英文刊名：CONTROLENGINEERINGOFCHINA年，卷(期)：2010,17(6)参考文献(26条)1.徐晗路基于H.264的运动估计算法研究20092.ChenJ64videocoding&transmissionsystemandratecontrolresearch20073.XuJ;ChenZ;HeYEfficientfastMEpredictionsandearlyterminationstrategybasedonH.264statisticalcharacters20034.DufauxF.MoscheniFMotionestimationtechniquesfordigitalTV:Areviewandanewcontribution1995(3)5.何宜宝;毕笃彦;许悦雷基于时空相关性自适应运动估计快速算法[期刊论文]-计算机工程2009(13)6.lainJ.JainADisplacementmeasurementanditsapplicationininter-frameimagecoding1981(5)7.GhanbariMThecross-searchalgorithmformotionestimation1990(06)8.LiuLK.FeigEAblock-basedgradientdescentsearchalgorithmforblockmotionestimationinvideocoding1996(4)9.王伟;李伟基于可变分块尺寸的多模板运动估计[期刊论文]-自动化学报2009(01)10.LiR.ZengB.LiuMLAnewthree-stepsearchalgorithmforblockmotionestimation1994(1)11.LiHY;LiuMJ;ZhangZQAnewfastmotionestimationalgorithmbasedonH.264200912.ZhuS.KKMAnewdiamondsearchalgorithmforfastblockmatchingmotionestimation1997(2)13.ZhuC;LinX;LChaoHexagon-BasedSearchPattenforFastBlockMotionestimation2002(04)14.ZhuC.LinX.LChaoHexagon-BasedSearchPattenforFastBlockMotionestimation2002(4)15.ZhuS;KKMAnewdiamondsearchalgorithmforfastblockmatchingmotionestimation1997(02)16.LiHY.LiuMJ.ZhangZQAnewfastmotionestimationalgorithmbasedonH.264200917.LiR;ZengB;LiuMLAnewthree-stepsearchalgorithmforblockmotionestimation1994(01)18.王伟.李伟基于可变分块尺寸的多模板运动估计算法2009(1)19.LiuLK;FeigEAblock-basedgradientdescentsearchalgorithmforblockmotionestimationinvideocoding[外文期刊]1996(04)20.GhanbariMThecross-searchalgorithmformotionestimation1990(6)21.lainJ;JainADisplacementmeasurementanditsapplicationininter-frameimagecoding1981(05)22.何宜宝.毕笃彦.许悦雷.张明基于时空相关性的自适应运动估计快速算法2009(13)23.DufauxF;MoscheniFMotionestimationtechniquesfordigitalTV:Areviewandanewcontribution1995(03)24.XuJ.ChenZ.HeYEfficientfastMEpredictionsandearlyterminationstrategybasedonH.264statisticalcharacters200325.ChenJ64videocoding&transmissionsystemandratecontrolresearch200726.徐晗路基于H.264的运动估计算法研究2009\n本文链接：http://d.g.wanfangdata.com.cn/Periodical_jczdh201006027.aspx