H.264視頻壓縮快速運動估計算法UMHexagons改進

楊 虎，潘紅兵，，何書專，李 麗

(1.南京大學電子學院微電子設計研究所，江蘇南京210093;2.江蘇省光電信息功能材料重點實驗室，江蘇南京210093)

0 引言

H.264/AVC［1］是MPEG和ITU-T聯合制定的最新視頻編碼標準，其基本編碼框架和先前類似標準并沒有太大變化，但是編碼模塊的技術方案應用了目前編碼的很多新技術，采用了非常高效和精確的運動估計預測方法，其編碼效率比以往的編碼標準H.261/H.263和MPEG-1/2/3均提高40%以上，獲得了較高的編碼質量，但卻是以極大增加運算復雜度為代價的，一直成為實時應用的瓶頸。

視頻編碼領域中最關鍵的技術是運動估計算法，其作用是在編碼過程中消除圖像幀間冗余度，目前已經成為視頻壓縮研究領域的熱點。當前，塊匹配算法因其易于硬件實現已經廣泛應用于各種視頻編碼標準，確定匹配塊的準則是塊失真度。研究表明，運動估計算法模塊是整個編碼過程中最耗時的部分，為了降低運動估計算法復雜度，減少耗時，提升編碼效率，各國學者提出了很多運動估計快速算法［2］-［5］，包括新三步法 (NTSS)、鉆石搜索法 (DS)、六邊形模板搜索法 (HEXBS)以及十字-鉆石-六邊形搜索法 (CDHS)這些算法一定程度上能夠降低運動估計算法復雜度，同時保證了原有的視頻質量，對運動緩慢和圖像尺寸較小的視頻序列可以取得較好的效果，但是在編碼運動劇烈和圖像尺寸較大的序列時，效果不太滿意，容易陷入局部最優點，從而影響編碼質量。

非對稱十字形多層次六邊形搜索算法 (UMHexagonS)［6］是清華大學提出的快速運動估計算法，已經被H.264 JM參考模型所采納，其運算量只有全搜索算法(FS)的10%，同時保持了較好的率失真性能，避免了運動搜索過早陷入局部最優點，而且能夠應用于不同類型的視頻序列，獲得了與FS幾乎相同的運動估計效果。UMHexagonS雖然有效加快了運動估計的速度，但是仔細分析仍然存在很大的優化空間，本文從早期結束閾值、混合搜索模板和宏塊類型模板對UMHexagonS算法進行了改進。

1 UMHexagonS算法特征與存在問題

1.1 精確預測初始搜索起點

UMHexagonS算法開始是確定搜索的初始運動矢量，其矢量集包括中值預測矢量、上層預測矢量、原點預測矢量、相鄰參考幀預測矢量和參考幀相同位置宏塊預測矢量。上述運動矢量集中能使拉格朗日代價函數最小的矢量作為最小的運動矢量，若不滿足搜索提前中止的條件，這個矢量即為下一步搜索的最佳搜索起點。UMHexagonS使用的起點預測有效利用了幀內、幀間相鄰塊的運動矢量相關性，因此其篩選出的搜索點最能夠反映當前搜索塊的運動趨勢，很好的提升搜索精度。

1.2 早期提前終止搜索策略

為了使運動估計算法在搜索速度和搜索質量之間達到平衡，UMHexagonS算法中設計了一個適當的ET閾值，在每一次不同的搜索步驟之后使用ET閾值判斷是否結束搜索:

(1) 初始搜索起點預測

(2) 非對稱大十字搜索

(3) 5x5正方形搜索

(4) 非均勻多層次16點六邊形搜索

每當滿足ET結束條件時，搜索算法將會跳轉到局部精細搜索部分。上述的ET值由式 (1)決定，其大小與當前塊大小、量化步長、量化系數QP和相鄰塊MCOST有關

算法中不同搜索步驟之后使用ET閾值都是相同的，可能出現一個問題，就是得到的小于ET的最小點不是一個最佳點，然而利用ET在搜索后面階段找到更好搜索點的可能性變得越來越小。以UMHexagons最后主要的搜索模板為例，從搜索中心到搜索窗口邊界，其包含了4個16個點六邊形搜索。如果一次六邊形搜索不能找到更好的搜索點，當前的最優點仍然需要從前面的搜索步驟中獲得，六邊形搜索將會繼續，這樣的話后面六邊形搜索中使用的ET將失效。文獻［7］實驗結果顯示在不同圖片尺寸和QP編碼條件下，六邊形搜索中ET的使用效率非常低 (ET效率的定義是搜索中途退出的次數/搜索總次數)，可見在這一搜索步驟中ET幾乎沒有用。因此為了提高算法的搜索效率，必須在不同的搜索步驟中使用不同的ET閾值。

1.3 混合多層次搜索

UMHexagons是混合多層次搜索算法，其搜索過程可分為大范圍粗搜索、細搜索和精細搜索階段，其中粗搜索階段包含非對稱大十字模板、5x5正方形模板和非均勻多層次六邊形模板，細搜索階段使用正六邊形模板搜索，直到得到的最佳點位于正六邊形中心時，進入精細搜索階段，使用小鉆石模板搜索，當搜索點位于小鉆石中心時即可得到最佳運動向量，搜索結束。

從算法的3個搜索過程可以看到，最壞情況下，粗搜索階段算法要搜索113個點 (非對稱十字24+正方形25+非均勻多層次六邊形64)，搜索點數過多，算法忽略了預測運動向量的方向性，過多的搜索了不必要的點;同時在細搜索階段使用的是相同的正六邊形模板，算法沒有考慮到不同宏塊使用不同的搜索模板以保證搜索速度和質量的折中，因此有必要對原算法進行改進。

2 對UMHexagonS算法的改進

由以上分析UMHexagonS算法中存在的問題，對算法的改進如下。

2.1 提出一種新的自適應ET閾值

根據文獻［7］設計了自適應運動估計搜索早期結束策略，引入一種新的ET閾值，其ET閾值的大小由圖像的大小和量化參數兩個因素決定，以適應不同的編碼條件。運動估計算法中需要的兩個閾值由以下式子決定

式 (2)中 Threshold代表 Threshold1和 Threshold2，ThdBase代表ThdBase1和ThdBase2。由于大多數情況下物體的運動是規律且緩慢的，相鄰塊預測得到的中值預測矢量很有可能是最佳的搜索點，搜索中值預測點之后使用Threshold1，若滿足條件，這時候可以認為運動估計算法就找到了最優點，可以結束整個搜索，極大節省搜索時間。每一步非均勻多層次六邊形搜索之后可以使用Threshold2，因為這是算法最耗時的部分，一旦當前的MCOST小Threshold2，算法進入細搜索階段。ThdBase由最小QP和最小圖像尺寸設置，通常Thd1Base比Thd2Base小，因為假如滿足了Threshold1，就沒有必要再繼續進行運動估計搜索，而且一個小的Threshold能確保對搜索質量影響最小。式 (3)M是閾值的調節因子，由兩個變量QP和圖像大小決定，目的是為了使閾值適應不同的QP和視頻序列。M調節因子的原則是越大的閾值分配給盡量小的QP和大的圖像尺寸。式(4)MAX_QP是H.264/AVC使用的最大QP值，式 (5)MIN_WIDTH是測試序列中最小的圖像寬度，其中常數A和B由實驗確定。根據實驗測試的結果，各個參數的取值如下

Thd_Base中的7個值分別對應從16x16到4x4七種宏塊大小，QP_factor的參數A在整像素搜索中設為0.9，分數像素搜索中設為0.3，Scale_factor的參數B設為0.3。

2.2 粗搜索階段的模板改進

2.2.1 大十字模板和多層次六邊形模板改進

根據文獻［8］利用當前塊的運動矢量和前一幀與當前塊的相同位置塊運動矢量可以減少運動估計搜索點數，用current_MV表示當前塊運動矢量，previous_MV表示前一幀運動矢量，求出兩個運動矢量的夾角，計算方法如下

若兩個矢量都不為0，根據式 (8)計算出其夾角θ，否則仍然按照改進前算法計算，由式 (8)可知，current_MV是隨著搜索中心的改變而變化，而previous_MV在每次塊搜索中的大小是不變的。

根據參考文獻［9］提出的對搜索模板的劃分方式，對非對稱大十字和多層次六邊形進行劃分，如圖1所示，與水平方向成45度角互相垂直的兩根直線把搜索區域分為4個部分，根據式 (8)計算出的θ決定將在哪個搜索區域繼續尋找最佳運動向量，只要預測向量的精度足夠高，就可在該區域找到最佳點，因此可以節省大量的搜索點，如圖2可知，采用如此劃分之后，非對稱大十字搜索點數由之前的24點降為8點或4點，而多層次六邊形由原來64點降為20點或12點，極大的減少了搜索點數，可以有效提升搜索速度。

由式 (8)的θ，確定相應的搜索區域，確定的方式如下:

當 θ∈ (0，45°］∪ (315°，360°］時:在 (a)(e)區域搜索;

當θ∈(45°，135°］時:在 (b)(f)區域搜索;

當θ∈(135°，225°］時:在 (c)(g)區域搜索;

當θ∈(225°，315°］時:在 (d)(h)區域搜索。

2.2.2 5x5方形搜索模板改進

根據文獻［10］可知，搜索過程中正方形模板里每個點成為最佳點的概率是不一樣的，因此沒有必要對每個點進行搜索，只保留成為最佳點概率高的點，其它點可以棄掉，減少搜索點數。由于這一步是小范圍搜索，因此可忽略其矢量的方向性，采用菱形—正方形模板替代之，由圖3可知搜索的點數由25點減少到9點，同時還保持了搜索各個方向上點數的均勻。

圖3 菱形—正方形搜索模板

2.3 細搜索階段算法改進

由上面階段得到的運動估計向量，進入細搜索階段，對于16x16到4x4七種搜索模式，若都采用同一種搜索模板，則必會增加搜索時間。為了平衡搜索精度和搜索速度，針對不同的搜索模式采用不同的模板［11］，在保持搜索精度的前提下，提升搜索速度。

(1)若塊類型為16x16、8x8時，搜索時仍用正六邊形模板，如圖4(a)所示。

(2)若塊類型為16x8、8x4時，搜索時使用扁平六邊形模板，如圖4(b)所示。

(3)若塊類型為8x16、4x8時，搜索時使用豎直六邊形模板，如圖4(c)所示。

(4)若塊類型為4x4時，搜索時使用小鉆石模板，如圖5所示。

當得到的運動向量中心在模板中心時，上述每一種模式對應的模板搜索結束，進入精細搜索階段。

2.4 精細搜索階段改進

圖4 六邊形搜索模板

為了保證運動搜索的精度，精細搜索階段仍然采用原算法圖5的小鉆石搜索，不過注意，若是模式4x4的搜索，則跳過精細搜索階段，因為細搜索階段得到的點已經是最佳運動向量點，其他模式的搜索直到最佳點在模板中心時結束。

圖5 小鉆石模板

3 實驗結果與分析

首先，UMHexagons改進的算法在H.264標準測試平臺JM10.1中實現。測試PC硬件為Intel(R)Pentium(R)D CPU 2.81GHz，2GB內存。操作系統為 Microsoft Windows XP Professional 2002，Service Pack3。編碼器配置采用JM10.1的基本類，實驗的主要編碼參數見表1。

表1 主要的編碼參數

為了測試改進算法的性能，采用不同運動類型的標準測試視頻序列，見表2。

表2 待測試序列

表3 運動時間比較數據

由表3可知，對于運動緩慢的測試序列，改進算法運動估計時間減少不多，因為在這類序列中主要是靜止塊和運動緩慢的塊，搜索過程大部分在新的ET Threshold1閾值判斷階段就結束了，所以在算法中使用的模板區域劃分和改進模板沒有起到作用。但是對于中等運動和運動劇烈測試序列，搜索的速度顯著上升，尤其是運動劇烈序列，改進算法的速度提升在25%以上，主要是因為進入了混合搜索階段后，改進的算法大大減少了搜索點數，發揮了極大的作用。通過實驗表4可以看到，改進算法的PSNR平均只改變了0.02dB，最大只改變了0.03dB，壓縮算法對圖片質量的影響可忽略不計，同時，碼率變化很小，平均值增加了1.30%，最大增加不超過2.07%。因此可以看到，對于不同類型的標準測試視頻序列，改進的算法有效提升了運動估計的速度，同時保持了原算法的率失真性能，對圖像質量的影響非常小。見表5。

表4 亮度信號峰值信噪比 (PSNR)比較數據

表5 碼率比較數據

4 結束語

文章對H.264快速運動估計算法UMHexagonS的特點進行了分析，研究了算法中存在的問題并作了改進，引入了新的ET閾值，更好的發揮了算法中提前結束搜索的功能，同時應用了預測運動向量的方向偏置性，極大的減少了搜索點，加快了搜索速度，而且針對不同的宏塊，應用不同的搜索模板，提高了搜索精度。實驗的結果表明，對于不同類型的測試序列，在保證碼率和圖像質量的前提下，編碼效率得到了有效的改進，提升了編碼器的實時性。

［1］BI Houjie，WANGJian.H.264/AVCvideo compression video coding for next generation multimedia［M］.2et nd.Beijing:Posts＆Telecom Press，2009:51-76(in Chinese).［畢厚杰，王健.新一代視頻壓縮編碼標準—H.264/AVC［M］.2版.北京:人民郵電出版社，2009:51-76.］

［2］Suh JW，Cho J，Jeong J.Model-based quarter-pixel motion estimation with low computational complexity ［J］.Electronics Letters，2009，45(12):618-620.

［3］Sarwer M G，WU Q M J.Adaptive variable block-size early motion estimation termination algorithm for H.264 /AVC video coding standard［J］.IEEE Trans on Circuits and Systems for Video Technology，2009，19(8):1196-1201.

［4］ISMAIL Y，McNEELY J，SHAABAN M，et al.A generalized fast motion estimation algorithm using external and internal stop search techniques for H.264 video coding standard［C］//Proc of IEEE International Symposium on Circuits and Systems.Seattle，WA，2008:3574-3577.

［5］WU Xiaomin，XU Weizhang，ZHU Nanhao，et al.A fast motion estimation algorithm for H.264［C］//Proceedings of International Conference on Signal Acquisition and Processing.Bangalore，India:IEEE Press，2010:112-116.

［6］CHEN Z，XU J，HE Y，et al.Fast integer-pel and fractional-pel motion estimation for H.264/AVC ［J］.Journal of Visual Communication and Image Representation，2006，17(2):264-290.

［7］XU Xiaozhong，HE Yun.Improvements on fast motion estimoton strategy for H.264/AVC ［J］.IEEE Transactions on Circuits and System for Video Technology，2008，18(3):285-293.

［8］Thambiduarai P，Ezhilarasan M，Ramachanfran D.Efficient motion estimation algorithm for advanced video coding［C］.Coference on Computational Intelligence and Multimedia Application.Sivakasi，Tamilnadu，India，2007:47-52.

［9］LI Guiju，LIU Gang，LIANG Jingqiu.Improvement of fast motion estimation algorithm used in H.264 ［J］.Optics and Precision Engineering，2010，18(11):2489-2496(in Chinese).［李桂菊，劉剛，梁靜秋.H.264快速運動估計算法的改進 ［J］光學精密工程，2010，18(11):2489-2496.］

［10］DING Y，SONG X H，YAN S H，et al.Improvements of UMHexagonS algorithm based on fast motion estimation［J］.Data Acquisition ＆ Processing，2009，24(5):660-663.

［11］DUAN Qingqing，SONGXuerui.Fast Motion Estimation Algorithm in H.264/AVC ［J］.Computer Engineering，2008，34(16):244-246(in Chinese).［段青青，宋學瑞.一種H.264/AVC中的快速運動估計算法［J］.計算機工程，2008，34(16):244-246.］