ISSN 1009-3044E- mail: edufccc.net.cnComputer Knowedge and Technology電腦知識(shí)技術(shù)htp://ww .dnzs.net.cnVal.6,No.10,April 2010, p.24444 2445.2448Tel:+86- -551- -5690963 5690964UMHexagonS算法的優(yōu)化研究宮婷婷,王民(西安建筑科技大學(xué)信控學(xué)院,陜西西安710055) :摘要:視頻編碼標(biāo)準(zhǔn)H.264已經(jīng)正式采納了UMHexagonS算法作為整像素的快速運(yùn)動(dòng)估計(jì)算法。文章對(duì)UMHexagonS算法進(jìn)行了介紹,對(duì)其特點(diǎn)進(jìn)行詳盡分析后,提出了一種改進(jìn)方法,即在預(yù)測(cè)起點(diǎn)處增加一個(gè)內(nèi)容自適應(yīng)的中止搜索閾值判斯,以判斷是否可立即結(jié)束搜索。模擬實(shí)驗(yàn)表明,相比原算法,在基本保持了原算法的的編碼效果,還明顯減少了搜索點(diǎn)減少了運(yùn)動(dòng)量,從而節(jié)省了編碼時(shí)間。關(guān)鍵詞:H.264;運(yùn)動(dòng)估計(jì);UMHexagonS算法;提前終止中圖分類(lèi)號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章 編號(hào):1009- 3044(2010)10 2444224Research and Optimization of UMHexagonS AlgorithmGONG Ting- ting,WANG Min(Architecture and Technology University, Xi'an 710055,China)Abstract: The video coding standards H.264 have adopted Unsymmetrial cross Muli Hexagon grid Search (UMHexagonS) algorithm forinteger pels motion estimation. However, further investigation on fast motion esimation method is still necessary. In this paper, based on thestudy of the principles of the UMHexagonS algorithm, an improved method is proposed, in which the idea of a new adapive facor is intro-duced in initial search point prediction step for early termination. Simulation Results show that the improved UMHexagonS algorithm canreduce search points with minimal loss in bit -tate and reconsructed quality compared with those of the original UMHexagonS algnthm.Key words: H.264; motion estimation; UMHexagonS algorithm; ealy terminaionUMHexagonS算法-2是H.264標(biāo)準(zhǔn)所采納的運(yùn)動(dòng)估計(jì)算法之一,全名為“非對(duì)稱(chēng)十字型多層次六邊形格點(diǎn)搜索"。相比于全搜索算法,該算法在保持較好的率失真性能的同時(shí),可以節(jié)約90%以上的運(yùn)算鼂嗎。本文對(duì)UMHexagonS快速搜索算法做了系統(tǒng)的分析,提出了引進(jìn)調(diào)節(jié)因子Bsw,并在原算法的預(yù)測(cè)起點(diǎn)部分增加一個(gè)自適應(yīng)的終止搜索判斷,在保i證原算法良好的半失真特性前提下,降低了運(yùn)箅量.從而提高了H.264 的編碼效率。1 UMHexagonS算法1.1 UMHexagonS算法簡(jiǎn)介UMHexagonS算法包括4步不同種類(lèi)的搜索過(guò)程.其基本步驟如下:第一步:多種預(yù)測(cè)模式進(jìn)行初始搜索點(diǎn)預(yù)測(cè).包括:1)中值預(yù)測(cè);2)原點(diǎn)預(yù)測(cè);3)上層塊預(yù)測(cè);4)前幀同位置塊預(yù)測(cè);5)相鄰(多)參考幀預(yù)測(cè)。對(duì)以上運(yùn)動(dòng)矢量所指向的點(diǎn)進(jìn)行搜索.獲得當(dāng)前最優(yōu)預(yù)測(cè)起點(diǎn)。第二步:進(jìn)行混合搜索.包括:1)非對(duì)稱(chēng)十字搜索;2) 5x5余搜索;3)擴(kuò)展的多層次六邊形格點(diǎn)搜索。第三步:滿意區(qū)的快搜索.以當(dāng)前最優(yōu)點(diǎn)為中心,用六邊型模板進(jìn)行搜索.直至最優(yōu)點(diǎn)在六邊型的中點(diǎn)為止。第四步:很滿意區(qū)的塊搜索.以當(dāng)前最優(yōu)點(diǎn)為中心.用小菱形模板進(jìn)行搜索.直至最優(yōu)點(diǎn)在:小菱形的中點(diǎn)為止。UMHexagonS算法依靠每個(gè)搜索步驟后的SAD(絕對(duì)誤差和)指標(biāo)或者mincost參數(shù)門(mén)限來(lái)判斷搜索精度.跳轉(zhuǎn)到相應(yīng)的搜索算法進(jìn)行循環(huán),或者提前終止。1.2 UMHexagonS算法特點(diǎn)1)多尺寸運(yùn)動(dòng)估計(jì):H.264采用了7種塊尺寸的塊匹配".通過(guò)逐漸減小的過(guò)程來(lái)實(shí)現(xiàn)由粗到細(xì)的運(yùn)動(dòng)估計(jì),從而獲得可靠性高.一致性好的運(yùn)動(dòng)矢量場(chǎng)。但是以相應(yīng)的提高了計(jì)算復(fù)雜度。2)基于內(nèi)容的自適應(yīng)搜索模板和搜索)i式:UMHexagonS算法每步的搜索都與圖像內(nèi)容有關(guān)。其搜索模板和搜索方式分為三類(lèi):大范圍的混合模板、細(xì)搜索的六角形模板精細(xì)搜索的十字模板,對(duì)于內(nèi)容程度不同的塊選拌不同的搜索模板。3)起點(diǎn)預(yù)測(cè):由于綜合了H.264)的宏塊劃分技術(shù)所帶來(lái)的不同尺寸的運(yùn)動(dòng)矢鼠相關(guān)性,以及幀內(nèi)幀間的運(yùn)動(dòng)矢量相關(guān)性,故可以選出最能反映當(dāng)前運(yùn)動(dòng)趨勢(shì)的點(diǎn)作為搜索起點(diǎn)。4)匹配準(zhǔn)則:H.264采用率失真最優(yōu)化(Rate Distorion Opimization)準(zhǔn)則則，在保證目標(biāo)數(shù)據(jù)率的條件下傳輸?shù)囊曨l信號(hào)失真最小。率失真控制機(jī)制為:中國(guó)煤化工YHCNMHG收稿日期:2010-01-27作者簡(jiǎn)介:宮婷婷(1984-),女,陜西西安人,西安建筑科技大學(xué)碩士研究生,研究方向?yàn)閿?shù)字娛樂(lè)與多媒體通信;王民,副教授,研究.方向?yàn)榭刂评碚撆c控制工程,信號(hào)與信息處理。2444..人工智能及識(shí)別技術(shù)....本欄目責(zé)任編輯:唐一東.第6卷第10期(2010 年4月)Computer Knowledge and Tchnoloy電腈知識(shí)與技術(shù)jewex(m,REF | )men )=SAD(s,c(REF.m)+ xa"(R(m-p)+R(REF),(1I式中: M=M,My)"為運(yùn)動(dòng)矢量,REF參考幀圖像,P=(PxPy)為預(yù)測(cè)的運(yùn)動(dòng)矢量,入mmn為拉格朗日乘數(shù)因子, R(m-p)為運(yùn)動(dòng)矢量差值比特?cái)?shù),SAD為絕對(duì)誤差之和。2基于UMHexagonS的改進(jìn)方法UMHexagonS算法中SAD具有很強(qiáng)的相關(guān)性，因此將運(yùn)動(dòng)矢量MVpred,即p .MVpred. up .MVpred. _ref 所指向點(diǎn)的率失真值分別稱(chēng)為Pred. space. mincost .Pred. uplayer. mincost .Pred. _ref mincost, 作為當(dāng)前mincost是否足夠準(zhǔn)確的標(biāo)尺,使用閾值判斷公式判斷此處屬于不甚滿意還是滿意或很滿意區(qū),并跳到相應(yīng)的二步或第三步或第四步。故在UMHexagonS算法中第步與第四步上,都是以“最佳點(diǎn)在模板中心”為準(zhǔn)則來(lái)判斷是否最優(yōu).是否可結(jié)束搜索。也就是說(shuō),即使所得點(diǎn)已經(jīng)是最佳點(diǎn)，卻仍要按模板搜索-到兩輪才能結(jié)束搜索,而這些點(diǎn)數(shù)都是浪費(fèi)的。尤其對(duì)高準(zhǔn)確率的起點(diǎn)預(yù)測(cè)而盲,開(kāi)始就找到最佳點(diǎn)的概率較大,則浪費(fèi)在該結(jié)束而術(shù)結(jié)束搜索上的點(diǎn)數(shù)也就不可小視。例如:30幀的carphone 序列.根據(jù)統(tǒng)計(jì)其有76.1%的點(diǎn)在第一步預(yù)測(cè)后就直接進(jìn)人第三步或第四步,而這其中的96.1% .95.8%的點(diǎn)已經(jīng)找到最佳點(diǎn)，但仍需要在搜索4或10個(gè)點(diǎn)才能結(jié)束搜索。在第一步預(yù)測(cè)部分再增加一個(gè)與內(nèi)容相關(guān)的自適應(yīng)閾值,以判斷是否叮立即結(jié)束搜索。在UMHexagonS算法中,基本判斷方法為":設(shè)當(dāng)前最佳值為mincost(含義見(jiàn)式():.min cost>(1+Px)' pred - mincost判為不滿意(1+ rmra) pred - mincost < mincostr(l+ Psm). pred - min cost判為較滿意mincost<(1+βn _)xpred_ mincost判為滿意其中調(diào)節(jié)因子為:Bsitel[locknpe]-ase [blocknpx]Bnms=Bsrblockpepred_ mmcosrpred_ mmcost'數(shù)組Bsize為當(dāng)前塊尺寸; "Sec ."Third為常數(shù)組,其值的選取諸見(jiàn)文獻(xiàn)[7]。判斷找到的點(diǎn)是否滿意的方法有兩種:這里稱(chēng)作A類(lèi)判斷與B類(lèi)判斷。在A類(lèi)判斷中，與mincost作比較的pred. minct=ped. uplayer_ mincost,僅用在第一步中的由MVpred. _up所指向的點(diǎn)求出比特率mincost后進(jìn)行;其余地方的判斷都使用B類(lèi)判斷。B類(lèi)判斷的pred. _mincost 則視情況而定:1) 若參考幀的ref不為O,pred. _incst=pred. -ref mincost2)若ref為0:(目) blocktype為16x16,則pred. _mincost =pred-space- -mincost(b) blocktype不為16x16, 則pred_ umincost =pred-uplayer-mincost筆者將各類(lèi)標(biāo)準(zhǔn)序列在第一步中進(jìn)行判斷 而進(jìn)入第二步、第三步,第V四步的點(diǎn)按blocktype的不同歸類(lèi).并進(jìn)行了大量的數(shù)據(jù)分析。提出改進(jìn)方法如下:在第一步的使用A類(lèi)判斷的地方,冉增加一個(gè)類(lèi)似B類(lèi)判斷的.內(nèi)容自適應(yīng)的新閾值來(lái)判斷是否叮停止搜索(考慮到判斷本身的耗時(shí)，只在預(yù)測(cè)準(zhǔn)確率敢商處增加該停止判斷): mincost<(1 +Bs )xpred_ mincot, 則判為可停止搜索，其中pred_ mincost 取B類(lèi)判斷中的pred. .mincostoPsm =Bse[bocktype]age[blocktype]pred min cost2根據(jù)實(shí)驗(yàn)數(shù)據(jù),按其概率分布規(guī)律,本文將"Stoplblocktype]取值選為:(sJ)-=.303;s[)-0-33:;5@q313033a:3,4)a0.27;,[5]=.1;as,[6J=0.13 ;a1[7]--0.44將上述改進(jìn)引入U(xiǎn)MHexagonS算法之后結(jié)果表明.在對(duì)比特率、圖像質(zhì)放均影響不大的前提下,可比原UMHexagonS算法減少10%到30%的搜索點(diǎn)數(shù)。3實(shí)驗(yàn)結(jié)果與分析表1兩種算法搜索點(diǎn)數(shù)的比較利試序列重算法改迎算去搜素鹵數(shù)為驗(yàn)證改進(jìn)算法的有效性,將該算法在H.264標(biāo)準(zhǔn)代碼JM12.2Mobole sT220505657”” ””194 860435的測(cè)試模型下進(jìn)行。實(shí)驗(yàn)參數(shù)匹:按照PPP序列類(lèi)型編碼;5個(gè)參n OCF”灌少29.44.04851061.10 28111考幀;7種搜索模式:搜索范圍為16像素;量化系數(shù)為28.32.36 ,40 ;Trevos. QCF40662 731減少16.28。16456472幀率為30Hz;使用率失真優(yōu)化和ME哈達(dá)碼變換。執(zhí)行平臺(tái):CPUAltyo. QCF2645647218668 167減少14.89。25799 6441"863 372減少11.63-。Intel (R) Celeron (R) 2.00 CHz ;內(nèi)存(RAM) 768 MB。由表1可見(jiàn)改進(jìn)算法較有效地降低了搜索點(diǎn)數(shù),特別對(duì)于大表2兩種算法平均比特率(kbits)的比較運(yùn)動(dòng)序列效果更為明顯,減少點(diǎn)數(shù)可達(dá)30%之多。利速字列改理后放變室為改善)由表2可看出改進(jìn)后的算法編碼產(chǎn)生的比特?cái)?shù)變化較小,故Mobile. soF1602.40’”160191.00560%126.03126-4+0.5*19。對(duì)運(yùn)動(dòng)估計(jì)的準(zhǔn)確性影響較小。中國(guó)煤化工.0.0C10.0表3說(shuō)明了改進(jìn)算法和UMHexagonS算法的率失真性能網(wǎng)幾乎-0.0-0.427%是一樣的,即改進(jìn)算法沒(méi)有減少準(zhǔn)確率對(duì)圖像質(zhì)量影響很小。。MYHCNMHG-4結(jié)束語(yǔ)本文對(duì)H.264所采用的UMHexagonS算法進(jìn)行了一定的分析.并在原算法基礎(chǔ)上,提出了改進(jìn)的優(yōu)化(下轉(zhuǎn)第2448頁(yè))本欄目責(zé)任編輯;唐-東.....人工智能及識(shí)別技術(shù). 2445Computer Knowledge and Technoloy電騰知識(shí)與技術(shù)第6卷第10期(2010年4月)所示:表3備選方案量化指標(biāo)利用訓(xùn)練過(guò)程得到的SVM模型,將待評(píng)估的方案指標(biāo)作為輸人,輸出層得到的方高序號(hào)4| 44人輸出數(shù)據(jù)作為方案評(píng)估的結(jié)果。得出以下評(píng)估結(jié)果:0707口o表4作戰(zhàn)方案 評(píng)估結(jié)果腳05 0050.3將選方高4 4| 4|016707結(jié)果0.7089 I 0900 0.014 0.6909 」B安全性十T十070↑門(mén)結(jié)果表明在考慮裝備、人員等客觀條件的情況下，作戰(zhàn)方案A更符合實(shí)際情兄。因此在最后的決策中選擇方案A1。.B狐動(dòng)性07 0705↑007004結(jié)論傳統(tǒng)的方案評(píng)估主要是由專(zhuān)家參與評(píng)定,其結(jié)果含有主觀因素?；赟VM的作理戰(zhàn)方案評(píng)估方法.彌補(bǔ)了專(zhuān)家評(píng)定法的不足,通過(guò)訓(xùn)練樣本的學(xué)習(xí)獲得專(zhuān)家的經(jīng)驗(yàn)島的既重配力07 0507 0和知識(shí).并利用所獲的經(jīng)驗(yàn)和知識(shí)解決相應(yīng)問(wèn)題.從而降低評(píng)估過(guò)程中人為因素,具I 107C7T 1有客觀性。品動(dòng)雄o030707參考文獻(xiàn):雄HB可性個(gè)070507[1]王靜巖,鄭建軍,吳裕樹(shù).一種基于神經(jīng)網(wǎng)絡(luò)的作戰(zhàn)方案評(píng)估方法[J].軍事運(yùn)籌與系品安姓十703 07統(tǒng)T程學(xué)205,19():57-61.品吸性葉T7o[2]譚東風(fēng).指揮信息系統(tǒng)導(dǎo)論[M],湖南:國(guó)防科學(xué)技術(shù)大學(xué),2007:65 -70.[3]范昕煒.支持向最機(jī)算法的研究及其應(yīng)用[D1.杭州:浙江大學(xué),2004.馬業(yè)對(duì)口概駛5050s03[4]邊肇棋,張學(xué)工.模式識(shí)別[M].北京:清華大學(xué)出版社200:.2030- 210.[5]白鵬,張喜斌.支持向量機(jī)理論及工程應(yīng)用實(shí)例[M].西安:西安電子科技大學(xué)出版潔B人員制情備的慢控能力T 070707 0↑杜,2008:13-20.0T070[6] Tax D,Duin R. Support vector domain decripionpJ].Pat tem Recogniton Ltters1999(20):1191-1199.T050305 05[7] Tax D,Duin R. Support veetors data deseription[J.Machine Leanmin.20045):45-66.07070 0[8]王文勝,劉奎,王治德.作戰(zhàn)方案評(píng)估專(zhuān)家系統(tǒng)的設(shè)計(jì)與研究J.沈陽(yáng)航空工業(yè)學(xué)院學(xué)報(bào),2004,21(3).B力調(diào)重理07070707(上接第2445頁(yè))表3平均峰值信噪比運(yùn)動(dòng)估計(jì)算法。改進(jìn)算法在對(duì)運(yùn)動(dòng)估計(jì)準(zhǔn)確性和圖像質(zhì)量的影響測(cè)試中到PSIRdBT .三工本文夏去呂克革 ”為改善，-0 029*。不大的前提下,大大減少了原算法中不必要的搜索點(diǎn)數(shù),從而降低(SIF)了編碼器端的運(yùn)動(dòng)估計(jì)耗時(shí),提高了編碼器的編碼效率。-0.0289.36.18Formo-0.02.4211019號(hào)[1] JVT2F017, Fast Integer Pel and Fractional PelMotion Estimation520-0.069Thevo3896forJVT[S].(QCIF)[2] JVT2P021, Imp roved and Simp lified FastMotion Estimation forMotber-0219.JM [S].(QCF)-013*.[3]李紅葉劉明軍.H.264運(yùn)動(dòng)估計(jì)算法研究[J].濟(jì)南大學(xué)學(xué)報(bào):自然-0.029.科學(xué)版,2009,23(1):72- -76.Aliyo3985-0028[4]畢厚杰新- .代視頻編碼壓縮標(biāo)準(zhǔn)- H.264/AVCM]北京:人民郵-0029元電出版社2005.[5] Cote G, Eml B, GallantM, et al. H. 263 + : video coding at low bit rate [JIEEE Trans on Cireuit and Syslems for Video Technology,1998,8(7):849 -866.[6] Hye- Yeon Cheong Tourapis, Alexis Michael Tourapis, Pankaj Topiwala. Fast Motion Estimation wihin the JVT codec [C]In: JVT-E023, 5th Meeting: Geneva, Switzerland, 2002- 10[7] Zhibo Chen, Peng Zhou, Yun He.Fast Motion Estimation for JVTC].In:JVT中國(guó)煤化工[8]馬蘭,沈笑云,萬(wàn)棣.精逋Visual C++視頻/音頻編解碼技術(shù)[M]北京:人民MHCNMH G[9]佟雨兵,張其善,祁云平.基于PSNR與SSIM聯(lián)合的圖像質(zhì)量評(píng)價(jià)模型J中國(guó)圖家圖龍子報(bào)，2006,11(12):1758- 1759.2448 ..人工餐能及識(shí)別技術(shù)...本欄目責(zé)任編輯:唐一東