1.引言

H.264/AVC視頻編碼標(biāo)準(zhǔn)是由ITU-T和ISO/IEC MPEG在2003年共同制定的，與以往視頻編碼標(biāo)準(zhǔn)相比，H.264在相同編碼質(zhì)量的前提下，可節(jié)約50%以上的碼率，但是其編碼效率的提高是以增加編碼的計(jì)算復(fù)雜度為代價(jià)的，運(yùn)動(dòng)估計(jì)作為視頻編碼的核心 技術(shù)，主要解決視頻 圖形中的時(shí)間冗余問題，通過運(yùn)動(dòng)估計(jì)技術(shù)可以使視頻傳輸?shù)谋忍財(cái)?shù)大大減少，在H.264中運(yùn)動(dòng)估計(jì)的計(jì)算復(fù)雜度占到了整個(gè)視頻編碼的60%-80%，因此對(duì)運(yùn)動(dòng)估計(jì)速度的優(yōu)化是關(guān)鍵，可以有效地提高編碼效率[1]。

運(yùn)動(dòng)估計(jì)算法性能最好的是全搜索算法（FS），但是其計(jì)算量太大，不適合于適時(shí)壓縮，目前，H.264的標(biāo)準(zhǔn)采用UMHexagons，與全搜索算法相比，該算法在保持較好的率失真性能的同時(shí)，可以節(jié)約80%以上的運(yùn)算量。UMH算法性能雖然比全搜索算法有很大提高，但是其運(yùn)算量還是偏高，在很多方面需進(jìn)一步優(yōu)化，本文通過對(duì)UMH算法的搜索模板和搜索步長進(jìn)行改進(jìn)，提高了搜索速度。

2.UMHexagons算法

UMH算法的搜索過程有以下幾步[2]：

(1)起始搜索點(diǎn)的預(yù)測(cè)：根據(jù)H.264采用多參考幀和7種分塊模式，運(yùn)用空間域的上層預(yù)測(cè)、中值預(yù)測(cè)、和時(shí)間域的對(duì)應(yīng)快的預(yù)測(cè)、鄰近參考幀來預(yù)測(cè)當(dāng)前最優(yōu)預(yù)測(cè)的起始點(diǎn)。

(2)非對(duì)稱交叉十字型搜索：在搜索范圍內(nèi)垂直方向的搜索點(diǎn)數(shù)為水平方向的一般，圖1為非對(duì)稱水平十字型搜索。

(3)非均勻多層次六邊形格點(diǎn)搜索：上一步產(chǎn)生的最優(yōu)匹配點(diǎn)作為本次搜索的中心，進(jìn)行包括5χ5區(qū)域的正方形搜索模板和16點(diǎn)的六邊形搜索模板，如圖2、3所示。

(4)在上一步產(chǎn)生的最優(yōu)匹配點(diǎn)上進(jìn)行擴(kuò)展的六邊形模版搜索：該過程包括多層次六邊形搜索。

(5)小菱形模版反復(fù)搜索，得到最終的運(yùn)動(dòng)矢量。如圖3。

3.UMHexagons算法的優(yōu)化

3.1 十字型搜索模板的優(yōu)化

上述的UMH算法在非對(duì)稱交叉十字型搜索算法是只采用水平十字型搜索，沒有采用垂直十字型搜索，統(tǒng)計(jì)表明，大多數(shù)視頻序列在水平方向和垂直方向運(yùn)動(dòng)的幾率較大，它們的運(yùn)動(dòng)矢量具有極強(qiáng)的水平和垂直偏移分布特性，因此將當(dāng)前宏快的運(yùn)動(dòng)分為水平方向和垂直方向的運(yùn)動(dòng)，根據(jù)對(duì)當(dāng)前宏塊預(yù)測(cè)的運(yùn)動(dòng)方向類型在搜索過程中使用帶方向的搜索策略，可以減少不必要的搜索，加快搜索速度。圖1是水平十字搜索模板，當(dāng)運(yùn)動(dòng)物體的運(yùn)動(dòng)估計(jì)具有水平運(yùn)動(dòng)特性時(shí)運(yùn)用該模板，該模板在水平方向上的搜索速度快于垂直方向，可以加快水平方向的搜索速度，提高運(yùn)動(dòng)估計(jì)效率。同理圖4是垂直十字型搜索模板，該算法在垂直運(yùn)動(dòng)特型的宏塊中具有較高的運(yùn)動(dòng)估計(jì)效率。

為了在第二步搜索中能快速正確的選擇水平搜索模板或垂直搜索模板，需要根據(jù)當(dāng)前宏塊的預(yù)測(cè)運(yùn)動(dòng)矢量獲得當(dāng)前宏塊的運(yùn)動(dòng)方向，預(yù)測(cè)運(yùn)動(dòng)矢量V與水平直線的夾角為：

如果θ小于或等于π/4，則判定當(dāng)前宏塊的運(yùn)動(dòng)為水平方向，選用水平十字型搜索模板；如果θ大于π/4，我則判定當(dāng)前宏塊的運(yùn)動(dòng)方向?yàn)榇怪狈较?，選用垂直十字型搜索模板。

3.2 5×5搜索模板的優(yōu)化

UMH算法中，在進(jìn)行非對(duì)稱十字型搜索完成之后進(jìn)行5×5正方形搜索模板的搜索是比較耗時(shí)的，統(tǒng)計(jì)實(shí)驗(yàn)表明[2]：運(yùn)動(dòng)矢量的概率分布是以(0，0)點(diǎn)位中心向四周遞減的，其中80%的運(yùn)動(dòng)矢量在搜索中心5×5窗口內(nèi)，約72%的運(yùn)動(dòng)矢量在搜索中心3×3窗口內(nèi)；運(yùn)動(dòng)矢量分布在垂直方向和水平方向的概率為61%左右，而分布在相同半徑的其他方向的概率為3%。

圖1 非對(duì)稱十字型搜索

圖2 5χ5正方形搜索

圖3 超六邊形模版搜素、中六邊形模版搜索、小菱形模版搜索

圖4 垂直十字型搜索模板

圖5 改進(jìn)5×5模板

圖6 改進(jìn)后的超六邊形搜索流程

由此可得，運(yùn)動(dòng)矢量的分布具有中心交叉偏置分布特性，依據(jù)運(yùn)動(dòng)矢量的中心交叉偏置特性，搜索模板的改進(jìn)如圖5所示，所有改進(jìn)的模板都覆蓋了搜索中心的3×3正方形區(qū)域；為了避免冗余搜索，小的塊尺寸保持大的搜索半徑，大的塊尺寸減小搜索半徑。如圖5所示，改進(jìn)后的模板比原模板最少可減少4個(gè)搜索點(diǎn)數(shù)，最多可減少16個(gè)搜索點(diǎn)，大大降低了運(yùn)算復(fù)雜度，提高了搜索效率。

3.3 搜索步長的改進(jìn)

在JM8.6的源代碼中，UMH算法中(3)(4)都是使用的是多圈的六邊形搜索，而在(5)小菱形搜索是以最佳點(diǎn)在模板中心為準(zhǔn)則搜索的，在搜索到最佳點(diǎn)時(shí)，仍需要把其余的像素點(diǎn)搜索完，才結(jié)束搜索繼續(xù)下一個(gè)模塊，這3處都是非常消耗搜索點(diǎn)數(shù)的步驟，本文改進(jìn)是基于提前結(jié)束搜索的思路。一般情況，視頻圖像序列都是以某一對(duì)象為單位的連續(xù)運(yùn)動(dòng)，那么對(duì)象內(nèi)部每一塊的像素點(diǎn)間的運(yùn)動(dòng)估計(jì)代價(jià)應(yīng)該具有高度的相關(guān)性。實(shí)驗(yàn)表明，對(duì)象內(nèi)部有非常相似的殘差性，因此在對(duì)象內(nèi)部各塊的代價(jià)也具有相似性。

表1 測(cè)試序列的實(shí)驗(yàn)數(shù)據(jù)

在超六邊形搜索算法中，另設(shè)一個(gè)整形變量last_mincost用來儲(chǔ)存上一個(gè)像素點(diǎn)運(yùn)動(dòng)估計(jì)后的代價(jià)mcost，在下一個(gè)點(diǎn)的運(yùn)動(dòng)估計(jì)步驟第三步的超六邊形搜索及第四步中若滿足

則直接結(jié)束搜索，其中k是一個(gè)小于1的數(shù)，具體改進(jìn)步驟如下：在改進(jìn)第三步的超六邊形搜索中，首先以search_range/4為半徑進(jìn)行預(yù)測(cè)點(diǎn)的搜索，然后使用(1)式的判決條件進(jìn)行判決，若滿足(1)式的條件，則結(jié)束搜索，若不滿足則使用search_range/2進(jìn)行預(yù)測(cè)點(diǎn)的搜索，再用(1)式判決，滿足則結(jié)束搜索，不滿足則用search_range，直至搜索結(jié)束，流程圖如圖6所示，在每次整個(gè)超六邊形搜索算法接受前將當(dāng)前塊的最小記錄下來，

對(duì)于第五步中的中六邊形搜索也做了類似改進(jìn)，經(jīng)過測(cè)試也取得一定效果。

4.實(shí)驗(yàn)結(jié)果與分析

本文在JM8.6源代碼上進(jìn)行改進(jìn)算法的驗(yàn)證，仿真以VC6.0作為開發(fā)平臺(tái)，測(cè)試選用了3類比較有代表的標(biāo)準(zhǔn)CIF序列akiyo，foreman，mobile，其中akiyo代表運(yùn)動(dòng)變化相對(duì)平緩的視頻序列，foreman代表空間細(xì)節(jié)中等序列，mobile是運(yùn)動(dòng)比較大，空間細(xì)節(jié)比較豐富的序列。所有測(cè)試序列Y、U、V4:2:0，CIF圖像搜索范圍search_range=16，實(shí)驗(yàn)對(duì)他們前50幀進(jìn)行了編碼，僅適用I幀和P幀，量化參數(shù)QP=28，評(píng)價(jià)標(biāo)準(zhǔn)主要選取了Y、U、V各分量的平均性噪比和運(yùn)動(dòng)估計(jì)時(shí)間MET，測(cè)試結(jié)果如表1所示。

從實(shí)驗(yàn)數(shù)據(jù)可知：改進(jìn)后的算法對(duì)于Y、U、V分量影響不大，對(duì)不同的視頻序列的運(yùn)動(dòng)估計(jì)時(shí)間的減少是不同的，視頻序列akiyo是運(yùn)動(dòng)場(chǎng)景相對(duì)平緩的視頻序列，在早期中止判斷時(shí)就通過SAD指標(biāo)跳過了一系列的搜索算法，所以許多可以通過搜索長度來降低運(yùn)算量的算法根本就沒有執(zhí)行，這就導(dǎo)致運(yùn)功估計(jì)改進(jìn)的時(shí)間效果不太明顯；而對(duì)場(chǎng)景運(yùn)動(dòng)一般的foreman和較劇烈的mobile序列，由于SAD的指標(biāo)一直不符合提前終止條件，因此執(zhí)行了大多數(shù)算法，改進(jìn)后的算法在平均信噪比變化不大的情況下，運(yùn)動(dòng)估計(jì)時(shí)間顯著減少，改進(jìn)效果良好，從而提高了編碼速度。

5.結(jié)論

本文通過對(duì)UMH算法進(jìn)行詳細(xì)分析，依據(jù)運(yùn)動(dòng)適量場(chǎng)的分布規(guī)律，從搜索模版和搜索步長兩方面對(duì)UMH算法進(jìn)行了改進(jìn)和優(yōu)化，實(shí)驗(yàn)結(jié)果表明：在保證視頻序列的性噪比變化不大的情況下，運(yùn)動(dòng)估計(jì)搜索時(shí)間減少，尤其對(duì)運(yùn)動(dòng)劇烈的視頻序列，有效地避免了冗余搜索，降低了搜索點(diǎn)數(shù)，效果良好。

[1]丁鑫,樊慧津.基于方向自適應(yīng)的運(yùn)動(dòng)估計(jì)混合模板搜索算法[J].中國圖形圖像學(xué)報(bào),2011,16(1):14-20.

[2]劉麗娟,王沛,應(yīng)駿.JM模型中UMHexagons算法及改進(jìn)方案[J].數(shù)字視頻,2011,35(03):18-20.

[3]鄭振東,王沛,應(yīng)駿.H.264 JM模型中運(yùn)動(dòng)估計(jì)算法及改進(jìn)方案[J].中國圖象圖形學(xué)報(bào),2007,12(10):1978-1982

[4]劉云,孟巖,孫芳.JM模型中UMHexagons改進(jìn)算法[J]系統(tǒng)仿真學(xué)報(bào),2009,21(1):149-151.

[5]肖亮,梁亮理.基于H.264/AVC的快速運(yùn)動(dòng)估計(jì)改進(jìn)算法[J].科學(xué)技術(shù)與工程,2009,9(15):4347-4350.

[6]畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)-H.264/AVC[M].北京:人民郵電出版社,2006.