EPZS算法的研究與優(yōu)化

通信技術(shù)Communications TEChNOlOGIESEPZS算法的研究與優(yōu)化田秀華'，劉慶利”('遼寧工程技術(shù)大學(xué)電信學(xué)院，遼寧葫蘆島125105; *阜新市人民防空辦公室,遼寧阜新12300 )[摘要] 深人分析了H.264視頻編碼標準推薦的運動(dòng)估計核心算法EPzS,針對該算法運動(dòng)估計實(shí)時(shí)性不足的缺點(diǎn)，對該算法進(jìn)行了兩方面的優(yōu)化，分別是參考搜索窗口起始位置的動(dòng)態(tài)確定和提前終止條件的優(yōu)化，并選擇含有不同特點(diǎn)的運動(dòng)類(lèi)型的序列進(jìn)行了實(shí)驗。實(shí)驗結果表明,優(yōu)化后的EPZS算法( AP123 )能夠高效快速地定位參考搜索窗口的位置,在整個(gè)搜索過(guò)程中改進(jìn)提前終止條件可以顯著(zhù)減少搜索點(diǎn)數量,并能達到較好的匹配效果。[關(guān)鍵詞]視頻壓縮;運動(dòng)估計;運動(dòng)矢量;改進(jìn)預測區域搜索;優(yōu)化[中圖分類(lèi)號] 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搜索算法中，一般中值預測最有可能是真實(shí)的塊MPEC-2等具有明顯的優(yōu)越性，特別是在編碼效率上的匹配位置， 作為搜索的起始點(diǎn)，以此點(diǎn)作為參考搜索窗口的中提高使它被應用于許多新的領(lǐng)域。但在算法的復雜度上,心點(diǎn)，在固定大小的窗口中搜索最佳匹配塊。對于不同序列都H.264的執行時(shí)間和所需的存儲量還較大。在H.264視頻把中值預測作為起始搜索窗口的中心點(diǎn)，而不是根據不同的序編碼標準中運算量最高，對編碼效率影響最明顯的是運動(dòng)列所特有的運動(dòng)特性動(dòng)態(tài)地確定搜索窗口位置，不利于快速匹估計技術(shù)。配和提高匹配精度，有待優(yōu)化和改進(jìn)，記為問(wèn)題1。文中對H.264推薦的運動(dòng)估計核心算法EPZS ( Enhanced在EPZS算法執行過(guò)程中，通過(guò)相鄰3個(gè)塊中最小的SadPreditive Zonal Search )進(jìn)行分析與研究,對EP2S算法在參值計算終止條件的標準(Stop Crieria)。設E表示當前塊的位考搜索窗口位置的確定和提前終止條件判斷標準兩方面進(jìn)行置，A、B和C分別表示當前塊左側、正上方和上方右側塊，優(yōu)化，以避免搜索過(guò)程過(guò)早陷人局部最優(yōu)和節省運動(dòng)估計時(shí)其Sad分別定義為SadA、SadB和SadC。為了減少提前終止間，降低算法的復雜度，提高編碼器的實(shí)時(shí)性。判斷標準計算錯誤的概率，把Stop Crieria限制在[minthres,maxthrea]間, minthres 和maxthres取值的大小取決于當前塊是7種中國煤化工x4，4x8和4x4)中收稿日期: 2010-02-03作者簡(jiǎn)介:田秀華，1961 年生，女,救授,研究方向:信的哪YHCNMHG_息處理與自動(dòng)控制;劉慶利，1981 年生,男,碩士,技術(shù)員，stopcrilericr -mn(Juun, sadB, SadC)(1)研究方向:通信與信號處理。stopcriteria max(stopcriteria, min thre[blockypeD (2)42 ww.clmg.com.cn通信技術(shù)Communications Technologies下兩種情況:stopcriteria=(9 x max(medthres[blocktype]), stopcriteria)+①col, mv和med. mv在同一個(gè)方向，起始搜索中心點(diǎn)預2 x medhres[blocktypeY8(4)測如圖1所示。blocktpe 的取值為0、1. 2、.. 7。其中，數組定義為:②相同的速度時(shí)，col mv滿(mǎn)足下面的條件: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算法充分利用當前塊和其周?chē)鷫KSad之間的關(guān)系m計算Stop Criteria 值，能滿(mǎn)足大多數情況并能保證計算出來(lái)的Stop Criteria 是可靠的。但當無(wú)運動(dòng)或者運動(dòng)特別小時(shí)，周?chē)鷫Kcol_ mvSad大小非常接近，而且當前塊的Sad值也可能非常的接近于周?chē)鷫K的Sad值。在這種情況下增加Stop Criterie 值不會(huì )影響Coloated rbioko壓縮質(zhì)量。由此可以看出上面計算Stop Criteria 的方法不是非\常的科學(xué)和全面，可以進(jìn)一步優(yōu)化， 記為問(wèn)題2。在首先計算Stop Criteria 時(shí)，EPZS 算法只利用了當前塊和周?chē)?個(gè)塊的Sad值，沒(méi)有考慮中心點(diǎn)(初始化起始搜索點(diǎn))_0. (Sad大小。相關(guān)資料表明，在上面的計算過(guò)程中，所有的SadcolLp1“ ! med_mv都位于同一幀中，中心點(diǎn)是最優(yōu)點(diǎn)的可能性非常大,這方面也Carreet Ybock可以進(jìn)一步優(yōu)化，記為問(wèn)題3。圉1起始搜索中心點(diǎn)預測(5)若當前塊與對應參考塊以相同方向不同速度運動(dòng)2 EPZS算法優(yōu)化.If滿(mǎn)足條件(4)中的①2.1起始搜索中心點(diǎn)預測優(yōu)化then mv(x, y)=(, col mv.+med_ mv,. col mv,+ med mv,、針對.上述第-一個(gè)問(wèn)題，采用動(dòng)態(tài)搜索窗口中心點(diǎn)"代替固(6)其他情況定搜索窗口中心，把這部分優(yōu)化稱(chēng)為AP1。假設幀內的物體比m(x, ))=(med mw,，med. m)一個(gè)分塊或子分塊大,則認為相鄰分塊或子分塊的運動(dòng)矢量是最后用mw代替med_ mv確定起始參考搜索窗口的中心位置。相關(guān)的。當相鄰宏塊不屬于同- -運動(dòng)對象時(shí)，這種估計就存在2.2 經(jīng)提前終止條件的優(yōu)化較大誤差，可以利用運動(dòng)矢量在時(shí)間上的相關(guān)性進(jìn)行改進(jìn)，由對于上述第2個(gè)問(wèn)題，利用相鄰區域的運動(dòng)特性計算Stop時(shí)間.上相鄰的運動(dòng)塊來(lái)進(jìn)行預測。在A(yíng)P1中,用運動(dòng)矢量的中Criteria 的大小。引入-一個(gè)自適應算子( motionF )來(lái)修改Stop值預測值(med. mv )和前一幀對應塊時(shí)間預測值(col. m)來(lái)Crieria大小田， 其主要目的是為了減少搜索預測過(guò)程而保證圖計算搜索窗口的位置，用mv表示期望預測的矢量(參考搜索像質(zhì)量， 此算子由3個(gè)相鄰塊的Sad之差確定。把這部分優(yōu)化窗口的中心位置由此值確定) .計算過(guò)程如下:稱(chēng)為AP2。為了使Stop Criteria更加有效,取消式(3)而增加(1)靜態(tài)塊( Stationary Block)式(7)，優(yōu)化后的算法為:If col_ mv :=0&col. mv,=0, then mvx，y)=0stopcriteria=min(SadA，SadB, SadC)(5)(2)垂直運動(dòng)( 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個(gè)相鄰塊中Sad的最大和(3)水平運動(dòng)( 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國像質(zhì)量的要求調整大如果當前塊與對應參考塊以相同的方向和速度運動(dòng),有如小， 其值可以取2、5. 8。實(shí)驗中取accuracy=8。由motionF信息安全與通信保密●2010.7 43通信技術(shù)Communicatlons Technologies的大小能測試出當前塊的Sad和給定周?chē)? -個(gè)塊Sad的接近程從統計結果可以發(fā)現，改進(jìn)后的算法比原算法的編碼時(shí)間度。實(shí)際上，周闈塊之間Sad差值越大, motionF 越接近于0,平均節省了25.218%，運動(dòng)估計時(shí)間平均節省了29.314%。由表Sad差值越小，motionF 越接近于accuracy。1可以清楚地看出，無(wú)論對于哪- -種序列，AP123 算法都表現出對于第3個(gè)問(wèn)題，利用起始搜索中心Sad和周?chē)?個(gè)Sad了較好的綜合性能，在搜索點(diǎn)數大幅度下降的同時(shí)，預測幀的信之間的關(guān)系計算Stop Criteria 的大小，把這部分優(yōu)化稱(chēng)為AP3。噪比相對于其他算法并沒(méi)有明顯下降，PSNR 提高了0.03 dB或者EPzS算法中，進(jìn)行提前終止判斷之前會(huì )進(jìn)行所有潛在最優(yōu)點(diǎn)降低了0.04 dB,基本保持了原有視頻質(zhì)量。的預測，其中包括中心預測點(diǎn)的Sad (Sadcenter)。最優(yōu)搜索4結語(yǔ)Sad和Sadcenter相關(guān)性越大，越有助于利用Stop Criteria值估計最優(yōu)Sad。用式(5')代替式(5)，即:文中對EPZS算法進(jìn)行了優(yōu)化，并通過(guò)實(shí)驗進(jìn)行了性能測stopcrieria=min(Sadcenter, SadA, SadB, SadC) (5')試。優(yōu)化后的搜索算法( AP123 )綜合運用了不同形狀搜索模板的優(yōu)點(diǎn)，無(wú)論對微小運動(dòng)還是較快運動(dòng)的圖像序列都有很好3實(shí)驗結果及分析的適應性。實(shí)驗測試分析表明，對于運動(dòng)位移較慢的圖像序列，在H.264參考軟件模型JM10.1下，選擇含有不同特點(diǎn)的運動(dòng)優(yōu)化后的算法平均搜索點(diǎn)數明顯比EPZS算法少，而得到的圖類(lèi)型的序列P進(jìn)行實(shí)驗。Foremen 為背景是靜止的中等運動(dòng)序列，像信噪比PSNR并沒(méi)有大幅下降，反而在處理大運動(dòng)序列時(shí)圖Mobile 和Highway為大運動(dòng)序列，編碼采用IPPP序列。測試結果像信噪比還有明顯提高。因此對于運動(dòng)位移更快一些的圖像序見(jiàn)表1。EPZS 為原EPZS算法, API為優(yōu)化問(wèn)題1的結果, AP23列來(lái)講，文中算法顯示出搜索點(diǎn)數少、圖像信噪比高的優(yōu)勢。為優(yōu)化問(wèn)題2和問(wèn)題3的結果，AP123 為優(yōu)化3個(gè)問(wèn)題的結果。參考文獻表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編碼擴頻技術(shù)及其應用[J].信息安全AP23 37.8212.70AP123 37.821.04與通信保密，200911); 243-312.第二十屆全國信息保密學(xué)術(shù)會(huì )議( IS2010)征文通知第二十屆全國信息保密學(xué)術(shù)會(huì )議定于2010年10月在廣東省深圳市召開(kāi)。此次學(xué)術(shù)年會(huì )由國家保密局指導，中國計算機學(xué)會(huì )信息保密專(zhuān)業(yè)委員會(huì )、國家保密科學(xué)技術(shù)研究所主辦，廣東省國家保密局承辦。歡迎同行專(zhuān)家、學(xué)者、科研工作者和信息.保密管理工作者積極投稿?，F將征文有關(guān)事宜通知如下:1.征文內容(1)信息安全保密的國際最新發(fā)展動(dòng)態(tài)(2)等級保護和分級保護技術(shù)與管理(3) 網(wǎng)絡(luò )與信息系統安全保密防護技術(shù)(4)網(wǎng)絡(luò )攻防技術(shù)(5) 信息安全保密檢查、監控與取證技術(shù)(6)信息系統測評技術(shù)(7)信息安全保密學(xué)科建設2.征文要求(1)論文應主題明確、論據充分、聯(lián)系實(shí)際、反映最新研究成果，字數- -般不超過(guò)5000字。已發(fā)表的論文請勿投稿。(2)文責自負，保密審查由作者所在單位負責。應征論文不論錄用與否，恕不退稿，請作者自留底稿。(3) 2010年8月1日前將論文全文按統-要求格式打印兩份、 光盤(pán)- -張 ( Word格式)及填寫(xiě)的投稿表以?huà)焯柗绞郊耐崭宓刂贰?4)論文錄取后將于2010年9月10日前通知作者參加會(huì )議的具體事項。3.收稿地址:北京市海淀區交大東路甲56號( 1004)姜放同志中國煤化工TYHC N M H G信息保密專(zhuān)業(yè)委員會(huì )2010年2月20日44 www.clsmag.com.cn