EPZS算法的研究与优化

通信技术Communications TEChNOlOGIESEPZS算法的研究与优化田秀华'，刘庆利”('辽宁工程技术大学电信学院，辽宁葫芦岛125105; *阜新市人民防空办公室,辽宁阜新12300 )[摘要] 深人分析了H.264视频编码标准推荐的运动估计核心算法EPzS,针对该算法运动估计实时性不足的缺点，对该算法进行了两方面的优化，分别是参考搜索窗口起始位置的动态确定和提前终止条件的优化，并选择含有不同特点的运动类型的序列进行了实验。实验结果表明,优化后的EPZS算法( AP123 )能够高效快速地定位参考搜索窗口的位置,在整个搜索过程中改进提前终止条件可以显著减少搜索点数量,并能达到较好的匹配效果。[关键词]视频压缩;运动估计;运动矢量;改进预测区域搜索;优化[中图分类号] TN919.81[文献标识码]A[文章编号] 1009- -8054 (2010) 07-0042-03Study and Optimization of EPZS AlgorithmTIAN Xiu-hua', LIU Qing-li'( College of Electronics and Information Engineering, Liaoning Technical University,Huludao Liaoning 125105, China; People's Air Defence Office of Fuxin City, Fuxin Liaoning 123000，China )[Abstract] The core of motion estimation algorithm EPZS recommended by the H.264 video coding standard is analyzed in-depth. For its deficient real-time performance in motion estimation, the algorithm is optimized in two aspecte, that is,optimization of the dynamic identifcation for the reference starting position of search window and optimization of the conditionsfor early termination, and the experiment on different types of sequences with different characteristics of movement is done.The experimental results show that the optimized EPZS algorithm ( AP123 ) could efficiently locate the position of referencesearch window, and the improvement of the conditions for early termination in the search process could significantly reduce thenumber of search points and achieves fairly good matching results.[Keywords] video compression; motion estimation; motion vector; EPZS; optimization0引言1EPZS算法分析.作为目前最新的视频编码标准，H.264比H.263、在EPzS搜索算法中，一般中值预测最有可能是真实的块MPEC-2等具有明显的优越性，特别是在编码效率上的匹配位置， 作为搜索的起始点，以此点作为参考搜索窗口的中提高使它被应用于许多新的领域。但在算法的复杂度上,心点，在固定大小的窗口中搜索最佳匹配块。对于不同序列都H.264的执行时间和所需的存储量还较大。在H.264视频把中值预测作为起始搜索窗口的中心点，而不是根据不同的序编码标准中运算量最高，对编码效率影响最明显的是运动列所特有的运动特性动态地确定搜索窗口位置，不利于快速匹估计技术。配和提高匹配精度，有待优化和改进，记为问题1。文中对H.264推荐的运动估计核心算法EPZS ( Enhanced在EPZS算法执行过程中，通过相邻3个块中最小的SadPreditive Zonal Search )进行分析与研究,对EP2S算法在参值计算终止条件的标准(Stop Crieria)。设E表示当前块的位考搜索窗口位置的确定和提前终止条件判断标准两方面进行置，A、B和C分别表示当前块左侧、正上方和上方右侧块，优化，以避免搜索过程过早陷人局部最优和节省运动估计时其Sad分别定义为SadA、SadB和SadC。为了减少提前终止间，降低算法的复杂度，提高编码器的实时性。判断标准计算错误的概率，把Stop Crieria限制在[minthres,maxthrea]间, minthres 和maxthres取值的大小取决于当前块是7种中国煤化工x4，4x8和4x4)中收稿日期: 2010-02-03作者简介:田秀华，1961 年生，女,救授,研究方向:信的哪YHCNMHG_息处理与自动控制;刘庆利，1981 年生,男,硕士,技术员，stopcrilericr -mn(Juun, sadB, SadC)(1)研究方向:通信与信号处理。stopcriteria max(stopcriteria, min thre[blockypeD (2)42 ww.clmg.com.cn通信技术Communications Technologies下两种情况:stopcriteria=(9 x max(medthres[blocktype]), stopcriteria)+①col, mv和med. mv在同一个方向，起始搜索中心点预2 x medhres[blocktypeY8(4)测如图1所示。blocktpe 的取值为0、1. 2、.. 7。其中，数组定义为:②相同的速度时，col mv满足下面的条件:minthres(8]=(0， 64, 32, 32, 16, 8, 8, 4}med. mv-2≤col mv,≤med_ mv.+2medthres[8)=(0，256， 128， 128, 64, 32, 32. 16}med. mv,-2≤col mv,≤med. mv,+2maxthres[8]={0, 768, 384, 384, 192, 96, 96, 48}then mv(x, y)=(col my, col mv)EPZS算法充分利用当前块和其周围块Sad之间的关系m计算Stop Criteria 值，能满足大多数情况并能保证计算出来的Stop Criteria 是可靠的。但当无运动或者运动特别小时，周围块col_ mvSad大小非常接近，而且当前块的Sad值也可能非常的接近于周围块的Sad值。在这种情况下增加Stop Criterie 值不会影响Coloated rbioko压缩质量。由此可以看出上面计算Stop Criteria 的方法不是非\常的科学和全面，可以进一步优化， 记为问题2。在首先计算Stop Criteria 时，EPZS 算法只利用了当前块和周围3个块的Sad值，没有考虑中心点(初始化起始搜索点)_0. (Sad大小。相关资料表明，在上面的计算过程中，所有的SadcolLp1“ ! med_mv都位于同一帧中，中心点是最优点的可能性非常大,这方面也Carreet Ybock可以进一步优化，记为问题3。圉1起始搜索中心点预测(5)若当前块与对应参考块以相同方向不同速度运动2 EPZS算法优化.If满足条件(4)中的①2.1起始搜索中心点预测优化then mv(x, y)=(, col mv.+med_ mv,. col mv,+ med mv,、针对.上述第-一个问题，采用动态搜索窗口中心点"代替固(6)其他情况定搜索窗口中心，把这部分优化称为AP1。假设帧内的物体比m(x, ))=(med mw,，med. m)一个分块或子分块大,则认为相邻分块或子分块的运动矢量是最后用mw代替med_ mv确定起始参考搜索窗口的中心位置。相关的。当相邻宏块不属于同- -运动对象时，这种估计就存在2.2 经提前终止条件的优化较大误差，可以利用运动矢量在时间上的相关性进行改进，由对于上述第2个问题，利用相邻区域的运动特性计算Stop时间.上相邻的运动块来进行预测。在AP1中,用运动矢量的中Criteria 的大小。引入-一个自适应算子( motionF )来修改Stop值预测值(med. mv )和前一帧对应块时间预测值(col. m)来Crieria大小田， 其主要目的是为了减少搜索预测过程而保证图计算搜索窗口的位置，用mv表示期望预测的矢量(参考搜索像质量， 此算子由3个相邻块的Sad之差确定。把这部分优化窗口的中心位置由此值确定) .计算过程如下:称为AP2。为了使Stop Criteria更加有效,取消式(3)而增加(1)静态块( Stationary Block)式(7)，优化后的算法为:If col_ mv :=0&col. mv,=0, then mvx，y)=0stopcriteria=min(SadA，SadB, SadC)(5)(2)垂直运动( Vertical Movement )stopcriteria=max(stopcriteria, min thres[blocktypeD (6)Ifs-=(mvMpLX, 4(myM4LX), (0, 0)，mvMpLX(, 0)，thenstopcriteria=min stopcriteria+motionF x (maxSad- -minSad) (7)IfcolL m,>2, then mv(x, y)=(0, max(col. my, med. mv)stopcriteria=(9 x stoperiteria+2 x maxthres[blocktypeV8 (8)else mv(x, )=(0, min(col my,，med my))其中，maxSad和minSad分别表示3个相邻块中Sad的最大和(3)水平运动( Horizontal Movenent)最小值，motionF 的计算为:If col_ mv -=0&&med_ mv=0, thenmotionF=((maxSad- minSad) x accuracy)/maxSad (9)Ifcol_ mv>2, then mv(x, y)=(max(co1 my，med_mv), 0)中国煤化工ionF( 10)else mv(x, )=(min(col_my, med_mv), 0)F0， 1]转换到区间[0,(4)当前块与对应参考块accuraMYHc N M H G国像质量的要求调整大如果当前块与对应参考块以相同的方向和速度运动,有如小， 其值可以取2、5. 8。实验中取accuracy=8。由motionF信息安全与通信保密●2010.7 43通信技术Communicatlons Technologies的大小能测试出当前块的Sad和给定周围- -个块Sad的接近程从统计结果可以发现，改进后的算法比原算法的编码时间度。实际上，周闱块之间Sad差值越大, motionF 越接近于0,平均节省了25.218%，运动估计时间平均节省了29.314%。由表Sad差值越小，motionF 越接近于accuracy。1可以清楚地看出，无论对于哪- -种序列，AP123 算法都表现出对于第3个问题，利用起始搜索中心Sad和周围3个Sad了较好的综合性能，在搜索点数大幅度下降的同时，预测帧的信之间的关系计算Stop Criteria 的大小，把这部分优化称为AP3。噪比相对于其他算法并没有明显下降，PSNR 提高了0.03 dB或者EPzS算法中，进行提前终止判断之前会进行所有潜在最优点降低了0.04 dB,基本保持了原有视频质量。的預测，其中包括中心预测点的Sad (Sadcenter)。最优搜索4结语Sad和Sadcenter相关性越大，越有助于利用Stop Criteria值估计最优Sad。用式(5')代替式(5)，即:文中对EPZS算法进行了优化，并通过实验进行了性能测stopcrieria=min(Sadcenter, SadA, SadB, SadC) (5')试。优化后的搜索算法( AP123 )综合运用了不同形状搜索模板的优点，无论对微小运动还是较快运动的图像序列都有很好3实验结果及分析的适应性。实验测试分析表明，对于运动位移较慢的图像序列，在H.264参考软件模型JM10.1下，选择含有不同特点的运动优化后的算法平均搜索点数明显比EPZS算法少，而得到的图类型的序列P进行实验。Foremen 为背景是静止的中等运动序列，像信噪比PSNR并没有大幅下降，反而在处理大运动序列时图Mobile 和Highway为大运动序列，编码采用IPPP序列。测试结果像信噪比还有明显提高。因此对于运动位移更快一些的图像序见表1。EPZS 为原EPZS算法, API为优化问题1的结果, AP23列来讲，文中算法显示出搜索点数少、图像信噪比高的优势。为优化问题2和问题3的结果，AP123 为优化3个问题的结果。参考文献表1测试结果_测试序列算法SNAdB 码率it.s”En:T节省事/ ME.T节省奉/(%)[1]Ce Zhu, Xiao Lin， Lap-Pui Chau. Hexagon-based Search-5Foreman EPZS 365913.0600.00Pattern for Fast Block Motion Estimation[J]. IEE Trans,133.0640.15AP23 36.6133.2650.1453.37Circuits and Systems, 2007. 12(05): 349 -55.Mobile185258.36[2]TsengCH. Wang H M, Wang J F. Enhanced Inta- 4x4 Mode413.193.5.22AP23 3.49415.3818.6524.78Decision for H.264/AVC Coders[J]. IEEE Trans. Cireuit Syet.AP123 33.49415.3019.1625.54Video Technol, 2006， 16(08): 1027-1032.Highwey EP2S 37.8666.990.000API 37.866.9-3..75[3]王立雅，周亮. CCSK编码扩频技术及其应用[J].信息安全AP23 37.8212.70AP123 37.821.04与通信保密，200911); 243-312.第二十届全国信息保密学术会议( IS2010)征文通知第二十届全国信息保密学术会议定于2010年10月在广东省深圳市召开。此次学术年会由国家保密局指导，中国计算机学会信息保密专业委员会、国家保密科学技术研究所主办，广东省国家保密局承办。欢迎同行专家、学者、科研工作者和信息.保密管理工作者积极投稿。现将征文有关事宜通知如下:1.征文内容(1)信息安全保密的国际最新发展动态(2)等级保护和分级保护技术与管理(3) 网络与信息系统安全保密防护技术(4)网络攻防技术(5) 信息安全保密检查、监控与取证技术(6)信息系统测评技术(7)信息安全保密学科建设2.征文要求(1)论文应主题明确、论据充分、联系实际、反映最新研究成果，字数- -般不超过5000字。已发表的论文请勿投稿。(2)文责自负，保密审查由作者所在单位负责。应征论文不论录用与否，恕不退稿，请作者自留底稿。(3) 2010年8月1日前将论文全文按统-要求格式打印两份、 光盘- -张 ( Word格式)及填写的投稿表以挂号方式寄往收稿地址。(4)论文录取后将于2010年9月10日前通知作者参加会议的具体事项。3.收稿地址:北京市海淀区交大东路甲56号( 1004)姜放同志中国煤化工TYHC N M H G信息保密专业委员会2010年2月20日44 www.clsmag.com.cn