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