ISSN 1009-3044E- mail: edufccc.net.cnComputer Knowedge and Technology電腦知識技術(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算法作為整像素的快速運動估計算法。文章對UMHexagonS算法進(jìn)行了介紹,對其特點進(jìn)行詳盡分析后,提出了一種改進(jìn)方法,即在預(yù)測起點處增加一個內(nèi)容自適應(yīng)的中止搜索閾值判斯,以判斷是否可立即結(jié)束搜索。模擬實驗表明,相比原算法,在基本保持了原算法的的編碼效果,還明顯減少了搜索點減少了運動量,從而節(jié)省了編碼時間。關(guān)鍵詞:H.264;運動估計;UMHexagonS算法;提前終止中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A文章 編號: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)所采納的運動估計算法之一,全名為“非對稱十字型多層次六邊形格點搜索"。相比于全搜索算法,該算法在保持較好的率失真性能的同時,可以節(jié)約90%以上的運算鼂嗎。本文對UMHexagonS快速搜索算法做了系統(tǒng)的分析,提出了引進(jìn)調(diào)節(jié)因子Bsw,并在原算法的預(yù)測起點部分增加一個自適應(yīng)的終止搜索判斷,在保i證原算法良好的半失真特性前提下,降低了運箅量.從而提高了H.264 的編碼效率。1 UMHexagonS算法1.1 UMHexagonS算法簡介UMHexagonS算法包括4步不同種類的搜索過程.其基本步驟如下:第一步:多種預(yù)測模式進(jìn)行初始搜索點預(yù)測.包括:1)中值預(yù)測;2)原點預(yù)測;3)上層塊預(yù)測;4)前幀同位置塊預(yù)測;5)相鄰(多)參考幀預(yù)測。對以上運動矢量所指向的點進(jìn)行搜索.獲得當(dāng)前最優(yōu)預(yù)測起點。第二步:進(jìn)行混合搜索.包括:1)非對稱十字搜索;2) 5x5余搜索;3)擴(kuò)展的多層次六邊形格點搜索。第三步:滿意區(qū)的快搜索.以當(dāng)前最優(yōu)點為中心,用六邊型模板進(jìn)行搜索.直至最優(yōu)點在六邊型的中點為止。第四步:很滿意區(qū)的塊搜索.以當(dāng)前最優(yōu)點為中心.用小菱形模板進(jìn)行搜索.直至最優(yōu)點在:小菱形的中點為止。UMHexagonS算法依靠每個搜索步驟后的SAD(絕對誤差和)指標(biāo)或者mincost參數(shù)門限來判斷搜索精度.跳轉(zhuǎn)到相應(yīng)的搜索算法進(jìn)行循環(huán),或者提前終止。1.2 UMHexagonS算法特點1)多尺寸運動估計:H.264采用了7種塊尺寸的塊匹配".通過逐漸減小的過程來實現(xiàn)由粗到細(xì)的運動估計,從而獲得可靠性高.一致性好的運動矢量場。但是以相應(yīng)的提高了計算復(fù)雜度。2)基于內(nèi)容的自適應(yīng)搜索模板和搜索)i式:UMHexagonS算法每步的搜索都與圖像內(nèi)容有關(guān)。其搜索模板和搜索方式分為三類:大范圍的混合模板、細(xì)搜索的六角形模板精細(xì)搜索的十字模板,對于內(nèi)容程度不同的塊選拌不同的搜索模板。3)起點預(yù)測:由于綜合了H.264)的宏塊劃分技術(shù)所帶來的不同尺寸的運動矢鼠相關(guān)性,以及幀內(nèi)幀間的運動矢量相關(guān)性,故可以選出最能反映當(dāng)前運動趨勢的點作為搜索起點。4)匹配準(zhǔn)則:H.264采用率失真最優(yōu)化(Rate Distorion Opimization)準(zhǔn)則則，在保證目標(biāo)數(shù)據(jù)率的條件下傳輸?shù)囊曨l信號失真最小。率失真控制機(jī)制為:中國煤化工YHCNMHG收稿日期:2010-01-27作者簡介:宮婷婷(1984-),女,陜西西安人,西安建筑科技大學(xué)碩士研究生,研究方向為數(shù)字娛樂與多媒體通信;王民,副教授,研究.方向為控制理論與控制工程,信號與信息處理。2444..人工智能及識別技術(shù)....本欄目責(zé)任編輯:唐一東.第6卷第10期(2010 年4月)Computer Knowledge and Tchnoloy電腈知識與技術(shù)jewex(m,REF | )men )=SAD(s,c(REF.m)+ xa"(R(m-p)+R(REF),(1I式中: M=M,My)"為運動矢量,REF參考幀圖像,P=(PxPy)為預(yù)測的運動矢量,入mmn為拉格朗日乘數(shù)因子, R(m-p)為運動矢量差值比特數(shù),SAD為絕對誤差之和。2基于UMHexagonS的改進(jìn)方法UMHexagonS算法中SAD具有很強(qiáng)的相關(guān)性，因此將運動矢量MVpred,即p .MVpred. up .MVpred. _ref 所指向點的率失真值分別稱為Pred. space. mincost .Pred. uplayer. mincost .Pred. _ref mincost, 作為當(dāng)前mincost是否足夠準(zhǔn)確的標(biāo)尺,使用閾值判斷公式判斷此處屬于不甚滿意還是滿意或很滿意區(qū),并跳到相應(yīng)的二步或第三步或第四步。故在UMHexagonS算法中第步與第四步上,都是以“最佳點在模板中心”為準(zhǔn)則來判斷是否最優(yōu).是否可結(jié)束搜索。也就是說,即使所得點已經(jīng)是最佳點，卻仍要按模板搜索-到兩輪才能結(jié)束搜索,而這些點數(shù)都是浪費的。尤其對高準(zhǔn)確率的起點預(yù)測而盲,開始就找到最佳點的概率較大,則浪費在該結(jié)束而術(shù)結(jié)束搜索上的點數(shù)也就不可小視。例如:30幀的carphone 序列.根據(jù)統(tǒng)計其有76.1%的點在第一步預(yù)測后就直接進(jìn)人第三步或第四步,而這其中的96.1% .95.8%的點已經(jīng)找到最佳點，但仍需要在搜索4或10個點才能結(jié)束搜索。在第一步預(yù)測部分再增加一個與內(nèi)容相關(guān)的自適應(yīng)閾值,以判斷是否叮立即結(jié)束搜索。在UMHexagonS算法中,基本判斷方法為":設(shè)當(dāng)前最佳值為mincost(含義見式():.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ù)組,其值的選取諸見文獻(xiàn)[7]。判斷找到的點是否滿意的方法有兩種:這里稱作A類判斷與B類判斷。在A類判斷中，與mincost作比較的pred. minct=ped. uplayer_ mincost,僅用在第一步中的由MVpred. _up所指向的點求出比特率mincost后進(jìn)行;其余地方的判斷都使用B類判斷。B類判斷的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筆者將各類標(biāo)準(zhǔn)序列在第一步中進(jìn)行判斷 而進(jìn)入第二步、第三步,第V四步的點按blocktype的不同歸類.并進(jìn)行了大量的數(shù)據(jù)分析。提出改進(jìn)方法如下:在第一步的使用A類判斷的地方,冉增加一個類似B類判斷的.內(nèi)容自適應(yīng)的新閾值來判斷是否叮停止搜索(考慮到判斷本身的耗時，只在預(yù)測準(zhǔn)確率敢商處增加該停止判斷): mincost<(1 +Bs )xpred_ mincot, 則判為可停止搜索，其中pred_ mincost 取B類判斷中的pred. .mincostoPsm =Bse[bocktype]age[blocktype]pred min cost2根據(jù)實驗數(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)引入UMHexagonS算法之后結(jié)果表明.在對比特率、圖像質(zhì)放均影響不大的前提下,可比原UMHexagonS算法減少10%到30%的搜索點數(shù)。3實驗結(jié)果與分析表1兩種算法搜索點數(shù)的比較利試序列重算法改迎算去搜素鹵數(shù)為驗證改進(jìn)算法的有效性,將該算法在H.264標(biāo)準(zhǔn)代碼JM12.2Mobole sT220505657”” ””194 860435的測試模型下進(jìn)行。實驗參數(shù)匹:按照PPP序列類型編碼;5個參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í)行平臺:CPUAltyo. QCF2645647218668 167減少14.89。25799 6441"863 372減少11.63-。Intel (R) Celeron (R) 2.00 CHz ;內(nèi)存(RAM) 768 MB。由表1可見改進(jìn)算法較有效地降低了搜索點數(shù),特別對于大表2兩種算法平均比特率(kbits)的比較運動序列效果更為明顯,減少點數(shù)可達(dá)30%之多。利速字列改理后放變室為改善)由表2可看出改進(jìn)后的算法編碼產(chǎn)生的比特數(shù)變化較小,故Mobile. soF1602.40’”160191.00560%126.03126-4+0.5*19。對運動估計的準(zhǔn)確性影響較小。中國煤化工.0.0C10.0表3說明了改進(jìn)算法和UMHexagonS算法的率失真性能網(wǎng)幾乎-0.0-0.427%是一樣的,即改進(jìn)算法沒有減少準(zhǔn)確率對圖像質(zhì)量影響很小。。MYHCNMHG-4結(jié)束語本文對H.264所采用的UMHexagonS算法進(jìn)行了一定的分析.并在原算法基礎(chǔ)上,提出了改進(jìn)的優(yōu)化(下轉(zhuǎn)第2448頁)本欄目責(zé)任編輯;唐-東.....人工智能及識別技術(shù). 2445Computer Knowledge and Technoloy電騰知識與技術(shù)第6卷第10期(2010年4月)所示:表3備選方案量化指標(biāo)利用訓(xùn)練過程得到的SVM模型,將待評估的方案指標(biāo)作為輸人,輸出層得到的方高序號4| 44人輸出數(shù)據(jù)作為方案評估的結(jié)果。得出以下評估結(jié)果:0707口o表4作戰(zhàn)方案 評估結(jié)果腳05 0050.3將選方高4 4| 4|016707結(jié)果0.7089 I 0900 0.014 0.6909 」B安全性十T十070↑門結(jié)果表明在考慮裝備、人員等客觀條件的情況下，作戰(zhàn)方案A更符合實際情兄。因此在最后的決策中選擇方案A1。.B狐動性07 0705↑007004結(jié)論傳統(tǒng)的方案評估主要是由專家參與評定,其結(jié)果含有主觀因素?；赟VM的作理戰(zhàn)方案評估方法.彌補(bǔ)了專家評定法的不足,通過訓(xùn)練樣本的學(xué)習(xí)獲得專家的經(jīng)驗島的既重配力07 0507 0和知識.并利用所獲的經(jīng)驗和知識解決相應(yīng)問題.從而降低評估過程中人為因素,具I 107C7T 1有客觀性。品動雄o030707參考文獻(xiàn):雄HB可性個070507[1]王靜巖,鄭建軍,吳裕樹.一種基于神經(jīng)網(wǎng)絡(luò)的作戰(zhàn)方案評估方法[J].軍事運籌與系品安姓十703 07統(tǒng)T程學(xué)205,19():57-61.品吸性葉T7o[2]譚東風(fēng).指揮信息系統(tǒng)導(dǎo)論[M],湖南:國防科學(xué)技術(shù)大學(xué),2007:65 -70.[3]范昕煒.支持向最機(jī)算法的研究及其應(yīng)用[D1.杭州:浙江大學(xué),2004.馬業(yè)對口概駛5050s03[4]邊肇棋,張學(xué)工.模式識別[M].北京:清華大學(xué)出版社200:.2030- 210.[5]白鵬,張喜斌.支持向量機(jī)理論及工程應(yīng)用實例[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)方案評估專家系統(tǒng)的設(shè)計與研究J.沈陽航空工業(yè)學(xué)院學(xué)報,2004,21(3).B力調(diào)重理07070707(上接第2445頁)表3平均峰值信噪比運動估計算法。改進(jìn)算法在對運動估計準(zhǔn)確性和圖像質(zhì)量的影響測試中到PSIRdBT .三工本文夏去呂克革 ”為改善，-0 029*。不大的前提下,大大減少了原算法中不必要的搜索點數(shù),從而降低(SIF)了編碼器端的運動估計耗時,提高了編碼器的編碼效率。-0.0289.36.18Formo-0.02.4211019號[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運動估計算法研究[J].濟(jì)南大學(xué)學(xué)報:自然-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中國煤化工[8]馬蘭,沈笑云,萬棣.精逋Visual C++視頻/音頻編解碼技術(shù)[M]北京:人民MHCNMH G[9]佟雨兵,張其善,祁云平.基于PSNR與SSIM聯(lián)合的圖像質(zhì)量評價模型J中國圖家圖龍子報，2006,11(12):1758- 1759.2448 ..人工餐能及識別技術(shù)...本欄目責(zé)任編輯:唐一東