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

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