1.引言

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

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

2.UMHexagons算法

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

(1)起始搜索點的預測：根據H.264采用多參考幀和7種分塊模式，運用空間域的上層預測、中值預測、和時間域的對應快的預測、鄰近參考幀來預測當前最優(yōu)預測的起始點。

(2)非對稱交叉十字型搜索：在搜索范圍內垂直方向的搜索點數為水平方向的一般，圖1為非對稱水平十字型搜索。

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

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

(5)小菱形模版反復搜索，得到最終的運動矢量。如圖3。

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

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

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

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

如果θ小于或等于π/4，則判定當前宏塊的運動為水平方向，選用水平十字型搜索模板；如果θ大于π/4，我則判定當前宏塊的運動方向為垂直方向，選用垂直十字型搜索模板。

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

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

圖1 非對稱十字型搜索

圖2 5χ5正方形搜索

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

圖4 垂直十字型搜索模板

圖5 改進5×5模板

圖6 改進后的超六邊形搜索流程

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

3.3 搜索步長的改進

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

表1 測試序列的實驗數據

在超六邊形搜索算法中，另設一個整形變量last_mincost用來儲存上一個像素點運動估計后的代價mcost，在下一個點的運動估計步驟第三步的超六邊形搜索及第四步中若滿足

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

對于第五步中的中六邊形搜索也做了類似改進，經過測試也取得一定效果。

4.實驗結果與分析

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

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

5.結論

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

[1]丁鑫,樊慧津.基于方向自適應的運動估計混合模板搜索算法[J].中國圖形圖像學報,2011,16(1):14-20.

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

[3]鄭振東,王沛,應駿.H.264 JM模型中運動估計算法及改進方案[J].中國圖象圖形學報,2007,12(10):1978-1982

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

[5]肖亮,梁亮理.基于H.264/AVC的快速運動估計改進算法[J].科學技術與工程,2009,9(15):4347-4350.

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