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

第20卷第1期廣西工學(xué)院學(xué)報Val.20 No.1 .2009年3月.JOURNAL OF GUANGXI UNIVERSIITY OF TECHNOLOGYMar.2009文章編號1004-6410 (20090) 01-0010-05UMHexagonS算法的優(yōu)化研究鄭藝玲(柳州職業(yè)技術(shù)學(xué)院信息工程系,廣西柳州545006)摘要:研究了 H.264視頻壓縮標準中的UMHexagonS算法,根據宏塊特征搜索范圍以及預測運動(dòng)矢量等的相關(guān)性,提出了簡(jiǎn)化搜索過(guò)程的改進(jìn)方法。仿真實(shí)驗表明，改進(jìn)后的算法有效降低了H.264運動(dòng)估計的運算量,使快速運動(dòng)估計比UMHexagonS算法平均提高50%以上的效率。關(guān)鍵詞:視頻編碼;運動(dòng)估計;算法優(yōu)化中圖分類(lèi)號:TP391文獻標識碼:A0引言H.264作為目前最新的國際視頻編碼標準,編碼效率相對于以前的視頻編碼標準有了較大的提高。但由于H.264采用了一系列新的編碼技術(shù),導致編碼復雜度大大提升。為提高視頻編碼的實(shí)時(shí)性,傳統的快速塊匹配運動(dòng)估計算法基本上是基于以下幾種方式:一是采用快速搜索的模型;二是利用時(shí)間和空間的相關(guān)性,采用運動(dòng)矢量的提前預測算法;三是利用統計規律,設定閾值來(lái)提前終止搜索過(guò)程;四是采用快速的匹配度計算方程。雖然以上提及的算法能減輕運動(dòng)估計的計算復雜度,但由于對H.264運動(dòng)估計中的可變塊、運動(dòng)矢量等方面的一些特性及其相關(guān)性認識還有待深人的研究,與實(shí)際的搜索范圍相比,仍然存在較大的差距,編碼效率還有提高的空間[(。本文在文獻[2]的研究基礎上做了進(jìn)一步的研究。從H.264運動(dòng)估計的特點(diǎn)出發(fā),分析了可變塊的劃分運動(dòng)矢量的分布特性和時(shí)域、空域相關(guān)性,對目前流行的UMHexagonS快速搜索算法做了系統的分析，提出了減少不必要的重復的塊匹配搜索步驟和搜索點(diǎn)數、提高運動(dòng)搜索效率的改進(jìn)算法,并用實(shí)驗結果驗證了該算法的可行性,對推動(dòng)現有視頻編碼標準應用具有積極的意義。1 UMHexagonS 算法簡(jiǎn)介由z. B.Chen等提出的UMHexagonS算法能降低90%的整像素運動(dòng)搜索復雜度,而平均峰值信噪比下降小于0.05 db,是目前效果最高的快速運動(dòng)估計算法,被H.264標準所采納。UMHexagonS算法包括以下幾個(gè)步驟:①初始搜索點(diǎn)預測;②混合搜索;③細化搜索。1.1 初始搜索點(diǎn)預測①中值運動(dòng)矢量預測:利用空間相關(guān)性,取已求出的當前塊的左、上、右上鄰塊的運動(dòng)矢量的中間值來(lái)預測當前塊的運動(dòng)矢量。②原點(diǎn)預測:考慮到在固定背景上的物體邊界的情況進(jìn)行預測。③上層塊運動(dòng)矢量預測:在H.264中,有7種不同的塊分割方式,用已求出的當前位置上- -級模式運動(dòng)向量,作為當前模式的運動(dòng)向量的預測值,這樣就可以用找出大塊的運動(dòng)矢量來(lái)預測其中小塊的運動(dòng)矢量。④前幀對應塊預測:對通常的視頻序列來(lái)說(shuō),物體的運動(dòng)總具連續的因此在時(shí)域中的運動(dòng)矢量存在著(zhù)很強的相關(guān)性,因此可以利用前- -幀對應塊 的運動(dòng)矢量來(lái)預中國煤化工Y片CNMHG收稿日期:2008-11-18作者簡(jiǎn)介:鄭藝玲(1968-),女,廣東恩平人,柳州職業(yè)技術(shù)學(xué)院信息工程系講師,碩士。第1期鄭藝玲等:MHexagonS算法的優(yōu)化研究11⑤相鄰參考幀預測:利用時(shí)間相關(guān)性,將前面參考幀的運動(dòng)向量按時(shí)間順序縮放進(jìn)行當前幀的運動(dòng)向量預測。.找出以上的運動(dòng)向量最小cost所對應的預測矢量,作為下一步搜索的最佳初始搜索點(diǎn)[3]。1.2混合搜索①非對稱(chēng)十字型搜索:對于- -般的自然視頻序列來(lái)說(shuō),水平方向的運動(dòng)要大于垂直方向的運動(dòng),因此能通過(guò)非對稱(chēng)的十字形搜索來(lái)近似找到最佳運動(dòng)矢量。②5X5全搜索:以起始位置為中心的5x5小范圍內的全搜索。③擴展六邊形搜索:采用六邊形的搜索模式進(jìn)行多級搜索,由內至外逐層展開(kāi),選出的最匹配塊位置作為下一步搜索的起始位置。與四邊形相比,六邊形搜索范圍近似圓形,能覆蓋更大的搜索區域。以上混合搜索步驟,在H.264的UMHexagonS算法中標記為first - step.1.3細化搜索①六邊形搜索:采用半徑為2的六邊形搜索。對于小的預測模式(如4X4模式) ,因為其預測矢量的精度較高,因此可以跳過(guò)十字形搜索和多級六邊形搜索,直接進(jìn)行細化的六邊形搜索。該步驟在H.264的UMHexagonS算法中標記為sec - step.②小菱形搜索:采用半徑為1的小六邊形一即通 常所說(shuō)的小菱形,搜索到最小匹配誤差點(diǎn)位于新形成的六邊形中心為止。該步驟在H.264的UMHexagonS算法中標記為third_ step.2 UMHexagonS 算法的優(yōu)化方案2.1 UMHexagonS 算法改進(jìn)思路分析2.1.1宏塊劃分H.264 中有16x 16、16X8、8X16、8X8、8x4、4x8、4X4等7種不同的塊分割方式,不同塊大小之間的運動(dòng)矢量存在很強的相關(guān)性。在運動(dòng)估計算法中,搜索范圍可設置為32x 32或16x 16,而劃分的最大的搜索塊為16X 16,最小的搜索塊為4x 4.清楚地認識搜索范圍與宏塊劃分之間的相關(guān)性,可為以下的分析奠定良好基礎。2.1.2搜索范圍分析由 于視頻圖像的運動(dòng)相關(guān)性,即在實(shí)際中的視頻圖像大部分塊是靜止或準靜止的,運動(dòng)矢量的分布以(0,0)為中心向外發(fā)散,越往外概率越小,即運動(dòng)矢量主要集中在搜索中心(0,0)附近很小范圍內。因此對于搜索起點(diǎn)的預測-般從中心位置開(kāi)始。以六邊形變量的定義為例:static int Hexagon_ x[6] = {2, 1, -1, -2, -1, 1};static int Hexagon_y[6] = {0, - 2, -2, 0, 2, 2};如圖1所示，六邊形搜索模板的搜索范圍覆蓋了5x5的區域,共25個(gè)點(diǎn)。而大六邊型搜索模板(初始狀態(tài))的搜索范圍為9X9的區域,共16個(gè)點(diǎn),擴展后的搜索范圍分別為15X 15、21 X21 27>27的區域。另外,非對稱(chēng)的十字型模板與搜索范圍和搜索步長(cháng)相關(guān)。當搜索范圍為32,搜索步長(cháng)為2時(shí),以預測的初始點(diǎn)為中心,非對稱(chēng)的十字型模板的水平搜索點(diǎn)為+1,士3, 5-.,....士31,垂直搜索點(diǎn)減半。而當搜索范圍為16,搜索步長(cháng)為2時(shí),對應的十字型模板的水平搜索點(diǎn)和圖1六邊形搜索模板垂直搜索點(diǎn)相應減半。由以上分析可知,非對稱(chēng)的十字型模板的搜索范圍的跨度為32x 16.設運動(dòng)矢量為(mv - x ,mv _ y) ,搜索范圍為search - range. 在UMHexagonS算法中,其搜索算法在頭文件fast_me.h中定義了執行SEARCH_ONE.PIXEL的條件,因而可將搜索范圍從全搜索的(2Xsearch_ range+ 1)2減少為(2x search_ range+ 1 - abs(mv _ x))X (2Xsearch ranre+ 1-ahs(mv - y)).如圖2所中國煤化工示。由以上分析可知,搜索范圍實(shí)際上呈動(dòng)態(tài)縮小,而在first..TYHC N M H G圍的搜索是不必要的(雖然早停止判斷減少了一些搜索運算)。2.1.3預測初始點(diǎn)分析UMHexagonS 算法的多種模式預測運動(dòng)矢量獲得初始搜索點(diǎn)。由于視頻序列的運動(dòng)12廣西工學(xué)院學(xué)報第20卷矢量大部分集中在(0,0)附近,而UMHexagonS算法采用的起點(diǎn)預測綜合利用了幀內幀間相鄰塊運動(dòng)矢量相關(guān)性,以及H.264采用宏塊劃分技術(shù)所帶來(lái)的不同尺寸塊的運動(dòng)矢量相關(guān)性,因而可以選出最能反映當前運動(dòng)塊趨勢的點(diǎn)作為初始搜索點(diǎn),準確率相當高。以初始搜索點(diǎn)為中心,再進(jìn)行下一步的搜索,使得搜索范圍呈現相對動(dòng)態(tài)的變化。2.1.4運動(dòng)矢分布特征宏塊的劃分存在相關(guān)性,如當前塊與幀內上方、左方和右上塊的相關(guān)性最強,與其他位置的相關(guān)性則較弱,因而中值預測采用以上相關(guān)塊得到較為精確的初始預測運動(dòng)矢量。在分析中,應將宏塊大小的劃分和運動(dòng)矢量大小的劃分區別開(kāi)來(lái)。小運動(dòng)矢量,指的是塊的運動(dòng)位移較小,而不是宏塊劃分為小的塊。實(shí)驗統計表明,大塊的運動(dòng)矢量相對較小，而小塊的運動(dòng)矢量相對較大,而且視頻序列的運動(dòng)矢量存在偏置性的特點(diǎn)。通過(guò)對大量視頻序列的研究表明,視頻序列的運動(dòng)矢量分布具有下列特征(圖3所示):①運動(dòng)矢量大部分集中在(0,0)附近;②運動(dòng)矢量差值的概率分布在(0,0)附近出現更為明顯預測初始點(diǎn)后的搜的峰值;索范圍③經(jīng)過(guò)中值預測后的運動(dòng)矢量差更是明顯的集中在(0,0)點(diǎn)周?chē)?4]。另外,基于對運動(dòng)矢量和宏塊劃分的特點(diǎn),在實(shí)驗分析中原來(lái)的搜索范圍也可得出以下結論,即較大的運動(dòng)矢量往往劃分出較小的塊,而較小的運動(dòng)矢量劃分較大的塊。這也符合實(shí)際視頻序列的特性,直觀(guān)效果是運動(dòng)劇烈的圖像相鄰幀之間細節變化較多,圈2搜索范圍對比示例劃分較小的塊可更好地提高準確度,視頻序列圖像效果清晰Y軸度較好,而運動(dòng)平緩圖像序列變化較小,以大的宏塊劃分已能保證較好的圖像質(zhì)量。參照圖3經(jīng)過(guò)初始運動(dòng)矢量預測以后,新的搜索起點(diǎn)如果不是落在坐標軸上,就應該落在任一象限之中。由此可見(jiàn),在first _ step中存在較多的大范圍搜索是不(1, 1)軸必要的。對于不必要的搜索,不但耗費了多余的運動(dòng)估計時(shí)間,也影響了搜索的效率。2.1.5運動(dòng)矢量偏置性分析 實(shí)驗統計表明, 在運動(dòng)估計中存在運動(dòng)矢量中心偏置性。為便于分析,以搜索范圍32像素為例子,假設極端的情況,初始搜索點(diǎn)落在I象限內的(2,2),根據運動(dòng)矢量偏置性圖3運動(dòng)矢分布特性示意的特點(diǎn),可以大致判定,要達到搜索范圍的邊界,至多搜索6X7=42個(gè)點(diǎn)(圖4所示),這不但比f(wàn)irst-step中理論上的搜索點(diǎn)數大大減少,而且在實(shí)際搜索中,由于初始搜索點(diǎn)的準確性較高,很好地避免了使搜索落人局部,因而搜索可以不必在相同的搜索區域內重復進(jìn)行。從另一個(gè)角度分析,如果六邊形搜索需要跨越I象限的大部分區域,可以倒推出,初始搜索1象限點(diǎn)的預測是失敗的。2.2 UMHexagonS算法改進(jìn)步驟在UMHexagonS算法高準確度的預測運動(dòng)矢量的前中國煤化工下,結合實(shí)驗對運動(dòng)矢量、搜索范圍以及宏塊劃分特性進(jìn)-:fYHCNMHG的研究和認識,提出以下改進(jìn)思路:圖4運動(dòng)矢量偏置性示意去除原算法中冗余的搜索步驟,即混合搜索:①非對稱(chēng)十鄭藝玲等:MHexagonS算法的優(yōu)化研究字型搜索;②5x5全搜索;③擴展六邊形搜索。也就是去除了在H.264的UMHexagonS算法中標記為first_ step的搜索步驟,使得運動(dòng)估計的搜索更加快捷。因此,改進(jìn)后的算法步驟如下:①沿用UMHexagonS算法高效的多模式預測運動(dòng)矢量以確定初始搜索點(diǎn);②以初始搜索點(diǎn)為中心,進(jìn)行六邊形搜索,找出最優(yōu)搜索點(diǎn),直至最優(yōu)搜索點(diǎn)落在六邊形的中心;③在最優(yōu)搜索點(diǎn)上做小菱形搜索,找出新的最優(yōu)搜索點(diǎn),直至最優(yōu)搜索點(diǎn)落在小菱形中心;④其余搜索策略和搜索步驟沿用UMHexagonS算法的內容,包括:沿用sec _ step和third_ step 搜索步驟進(jìn)行后續的搜索,沿用UMHexagonS算法中的早停止判斷和閡值判斷等。3改進(jìn)算法的實(shí)驗分析為驗證改進(jìn)算法的有效性,將該算法在H.264標準代碼JM86的baseline檔次下做了實(shí)現,對cif視頻格式下不同運動(dòng)強度的3個(gè)視頻序列進(jìn)行了測試,就編碼時(shí)間、比特率、PSNR指標,對UMHexagonS算法和在其基礎之上的改進(jìn)算法進(jìn)行了比較。實(shí)驗條件:按照PP...序列類(lèi)型編碼;5個(gè)參考幀;7種搜索模式;搜索范圍為16像素;量化系數為28、32、36 ,40;幀率為30 Hz;使用率失真優(yōu)化和ME哈達碼變換。執行平臺:CPU Intel (R) Celeron (R)2.00 GHz;內存(RAM)768 MB.兩算法實(shí)驗結果比較如下:表1 fotbll cif - ori90.yov 序列搜索算法性能參數QP=28QP=32QP=36QP=40SNR . Y(dB)6.6233.7931.1828.83UMHexgoS算法Bieae(hirs)1263.78911.52621.00437.40Total encoding time for the seq.7.9697.3596.9226.719Total ME time for scquance0.9261.0630.7180.919SNR_ Y(dB)36.6131.19改進(jìn)算法Birate(kbit/s)1263.60911 .34622.20438.60Total encoding time for the sq.7.4696.7506.0475.516Total ME time for sequence0.529 .0.5160.4950.263表2 stefan_ cif_ ori90.yuv序列搜術(shù)算法QP-3236.5433.4530.6128.15UMHexagonS算法Bitate(bi/s)1541.881119.06776.70541.86Total enoding tine for the seq.8.9847.9856.9371.0540.9991.2241.26536. sBitrate(kbit/s)1541.88 .119.06Total encoding time for the 9eq.8.0947.6417.1886.1400.5920.7360.423表3 news_ elif_ ori90. yuv序列QP=32 .37.6734.7132.0129.36UMHexagonS算法Birate(hbit/s)1279.92951.54691.26508.148.6577.8597.5466.7341.1571.3271.1340.95332.02951.54 .692.40508.98Total enooding time for the seq.7.4846.9546.5336.500Total ME time for sequence .0.5930.4070.4800.515基于以_上實(shí)驗數據,各項指標分析對比結果如下:①總運動(dòng)估計的時(shí)間對比分析:采用新算法比UM|中國煤化工十時(shí)間平均減少了51.32% ,有效地提高了編碼速度(實(shí)驗數據分析見(jiàn)表4-表:TYHCNMHG②總編碼時(shí)間的對比分析:采用新的改進(jìn)算法,比采用UMHexagonS算法平均減少了約10%左右(實(shí)驗數據分析略) ;14廣西工學(xué)院學(xué)報第20卷③亮度峰噪值對比分析:采用新的改進(jìn)算法,總體上保證了圖象質(zhì)量(實(shí)驗數據分析略);④比特率對比分析:采用新算法,比特率幾乎沒(méi)有變化(實(shí)驗數據分析略)。袈4 foball dif - ori90.yuv序列改進(jìn):搜術(shù)算法性能參數QP=28QP-32QP=36QP=40UMHexagonS 算法Total ME time for sequence0.9261.0630.7180.919改進(jìn)算法Total ME time for seruence0.5290.5160.4950.263改進(jìn)42.87%51.46%31.06%71.38%49. 19%表5 stefan_ cif _ ori90. yuv序列改進(jìn):搜索算法QP=32UMHexagonS算法Total ME time for squence1.0540.9991.2241.265Totel ME time for sequence0.5920.7360.42343.83%47.05%39.87%。66.56%49. 33%表6 news _ cif . ori90. yuv序列改進(jìn):平均改進(jìn)1.1571.3271.1340.9530.5930.4070.480.51548.75%69.33%57.67%45.96%55.43%表7各測試序列平 均改進(jìn)所占百分比(%)測試系列Fouballstefannews平均所占百分比各系列改進(jìn)所占百分比49.1949.3355.4351.324結語(yǔ)本文對H.264中采用的UMHexagonS算法進(jìn)行分析和研究,并在原算法基礎上進(jìn)行了改進(jìn),實(shí)驗結果顯示,改進(jìn)算法在基本保證圖像質(zhì)量和碼率幾乎沒(méi)有增加的情況下,大大減少了原算法中不必要的搜索范圍,減少了搜索點(diǎn)數,較大幅度地降低了運動(dòng)估計的耗時(shí),從而有效地提高了整體的編碼效率,也更加有利于實(shí)時(shí)應用。與文獻[2]的實(shí)驗結果比較,運動(dòng)估計時(shí)間減少了10%以上。參考文獻:[1]陳純,楊智,卜佳俊,等.一種基于H.264的可變塊快速運動(dòng)估計算法[].中國圖象圖形學(xué)報, 2007, 12(2):272 ~276.[2]鄭藝玲,謝翠蘭.H.264中FME算法的優(yōu)化[J].計算機工程, 2008,34(13):207~209.[3]楊育紅,徐煩,季曉勇.快速運動(dòng)估計UMHexagonS算法的探討與改進(jìn)[J].計算機工程與應用,2006.42(11):52~54.[4]段娟,張楠.快速可伸縮環(huán)形搜索算法[J].計算機工程與應用,2006,42(30):14~19.Research and Optimization of UMHexagonS algorithmZHENG Yi-ling(Department of Information Engineering, Liuzhou Vocational & Technical College, Liuzhou 545006, China)Abstract: This paper introduces the UMHexagonS algorithm and presents an optimal algorithm based on the cor-relation of the block feature, search range and forecast motion vector. The experimental results show that the ef-ficiency of this optimized algorithm reduces the amount of comp中國煤化工lexagonS algorithmfrom H.264 more than 50%.CYHCNMHGKey words: video coding; motion estimation; algorithm optimizanon