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