H.264標準是由視頻聯合工作組JVT(Joint Video Team)組織提出的新一代數字視頻編碼標準,與其他標準相比，H.264具有更高的編碼效率[1],能夠節省大約50%的碼率。但是對H.264性能的改進是以增加復雜性為代價的，其編碼的計算復雜度大約相當于H.263的3倍。運動估計是視頻壓縮編碼的關鍵部分,能有效地去除序列圖像的幀間冗余[2],在H.264的編碼過程中，由于H.264編碼器采用了高精度運動矢量，計算量迅速增長，運動估計消耗了整個編碼時間的80%左右,是復雜度和運算量最高的部分[3]。如何有效地減少運動估計的消耗,對提高編碼的效率和實時性編碼具有重大的意義。
1 UMHexagonS算法分析
    非對稱十字型多層次六邊形格點搜索算法(UMHexagonS算法)由Chen Zhibo等人[4]提出，由于該算法的運算量相對于快速全搜索算法可節約90%以上，同時能保持較好的率失真性能，因此，UMHexagonS算法已經被H.264的參考軟件JM正式采納,成為H.264標準專利庫中的一部分。
    UMHexagonS算法的基本步驟[5]如下：

    (1)起始搜索點預測。使用多幀參考、中值預測、上層預測、相應塊預測和鄰近參考幀預測五種方法來進行預測。在起始搜索矢量的集合中,以擁有最小代價預測的運動矢量作為起始搜索點,然后用EARLY_TERMINATION判斷是否提前截止，如果絕對誤差和SAD較大則跳到步驟5,SAD很小則跳到步驟6。
    (2)非對稱十字搜索，如圖1中步驟2。EARLY_TERMINATION判斷是否提前截止,SAD較大則跳到步驟5，SAD很小則跳到步驟6。
    (3)螺旋搜索5×5區域如圖1中步驟3-1。以目前最佳點為中心,搜索(-2, 2)方形區域內的25個點。
    (4)多層次大六邊形格點搜索如圖1中步驟3-2。在1/4 search_range的范圍內,用不斷擴大一倍直徑的大六邊形模板進行搜索。

    (5)小六邊形模板反復搜索如圖1中步驟4-1。以小六邊形為模板，在search_range范圍內搜索，直到最優點出現在模板中心才停止搜索。
    (6)菱形模板反復搜索如圖1中步驟4-2。以菱形為模板，在search_range范圍內搜索，直到最優點出現在模板中心才停止搜索，得到最終的運動矢量。
2 UMHexagonS算法的改進
2.1 對稱十字搜索模板
    在UMHexagonS算法的步驟3中使用的是螺旋搜索5×5區域。螺旋搜索是一種全搜索的搜索策略,需要計算整個搜索范圍內所有點的SAD值,也就是要搜索25點。這樣不僅復雜度高、運算量大而且費時。
    自然的視頻序列的運動矢量場通常是柔和平滑的，變化也比較緩慢。參考文獻[6]中對典型的平緩和運動復雜的自然視頻序列的運動矢量的統計研究發現，超過80%的運動矢量預測值位于中心5×5的網格區域內，但不是均勻分布。從圖2中可以看出,總的5×5網格區域內的運動矢量是81.79%，而以原點為中心的半徑為2的對稱十字型區域（也就是A+B+C區域）運動矢量為74.74%。對稱十字模板和螺旋搜索模板如圖3所示。從5×5網格區域到半徑為2的對稱十字型區域，雖然運動矢量減少了7.05%，但是搜索點數減少達到64%，如圖3(b)所示搜索點數從25點減少到9點。所以本文用對稱十字型模板的9點搜索來取代螺旋搜索5×5區域的25點搜索。

2.2自適應搜索長度
     搜索長度search_range在UMHexagonS算法中用來控制搜索候選搜索點的范圍。主要體現在以下幾個步驟：步驟(4)(多層次大六邊形格點搜索)中，以1/4 search_range做為搜索長度。步驟(5)(小六邊形模板反復搜索)中，以search_range作為搜索長度；步驟(6)(菱形模板反復搜索)中，以search_range作為搜索長度。可見，在UMHexagonS算法中搜索長度是固定不變的，合理地設定搜索長度能有效地減少UMHexagonS算法的復雜度。
     場景中一般都是以某一對象為單位的運動，因此該對象內部的代價（mcost）應該具有很高的相關性[7]。據此，本文利用前兩個搜索步驟的min_mcost之比，提出自適應搜索長度的方法。
    設利用變量pre_min_mcost1、pre_min_mcost2、pre_min_mcost3、 pre_min_mcost4來分別保存步驟(2)、(3)、(4)、(5)的min_mcost，其定義公式如下：
     ki=pre_min_mcosti/pre_min_mcost(i+1)  (1)
     search_range=search_range/ki               (2)
     式(1)中，ki表示前兩個搜索步驟的min_mcost之比，式(2)中search_range是搜索長度。根據ki來相應地縮短改進后的搜索長度，本文的改進方法分別用在步驟(4)、(5)、(6)。
3實驗結果與分析
3.1 實驗環境
    本文在H.264的參考軟件JM10.1上實現改進后的UMHexagonS算法，選取3個具有代表性的標準QCIF測試序列進行測試。
　    實驗平臺：Windows XP SP3系統，Intel Core 2 Duo CPU（T6400）2.00 GHz,內存2 GB。
　　實驗測試序列：akyio_qcif.yuv、foreman_qcif.yuv、mobile_qcif.yuv,其場景運動快慢鮮明，運動劇烈程度由左到右依次加強。
　　實驗參數設置：FramesToBeEncoded=20,FrameRate=30.0,SearchRange=16,NumberReferenceFrames=5,其他參數設置為默認值。
3.2 實驗數據與分析
　　本文主要采用Y、U、V各分量的峰值信噪比( PSNR)、運動估計時間(MET)和比特率作為算法性能評判的標準。Y、U、V 各分量的PSNR表明壓縮后圖像的質量，“+”為改善；MET表明運動搜索的時間，“-”為改善；比特率表明壓縮率，“-”為改善。改進率=（改進后算法-原算法）/原算法×100%。實驗結果比較如表1所示。
    從表1中可以看出，改進后算法對Y、U、V各分量的峰值信噪比和比特率影響不大，但運動估計時間減少很顯著(從7.4%~20.5%)，平均減少了15%。實驗中,改進算法對于不同視頻序列的運動估計時間的減少幅度不同，主要由視頻場景運動的激烈程度不同所造成。視頻序列akiyo運動場景相對平緩，起始點預測的精度較高，在早期判斷EARLY_TERMINATION時,因為SAD很小，直接跳到步驟(6),也就是說,沒有執行對稱十字模板步驟(3)和通過自適應搜索長度來降低運算量的步驟(4)和步驟(5)所以運動估計時間減少的效果不是很明顯。而對于場景運動一般和場景運動激烈的foreman和mobile序列,由于SAD指標不符合早期判斷EARLY_TERMINATION條件, 執行了對稱十字模板步驟(3)和自適應搜索長度搜索步驟(4)、(5)、(6)，因此運動估計時間減少顯著。

    本文在結合JM10.1模型的基礎上分析了H.264中運動估計算法(UMHexagonS算法),針對該算法的不足之處提出了兩處改進。首先，利用對稱十字模板9點搜索替換原來的5×5螺旋搜索，減少了64%的搜索點數；其次，利用對象內部代價的相關性提出自適應搜索長度方法。在保證視頻序列各分量的信噪比和比特率的情況下，使運動估計時間平均降低了15%,增強了編碼的實時性，有利于視頻圖像實時編碼傳輸的實現。
參考文獻
[1] Yang Enhui, Xu Xiang. Rate distortion optimization for H.264 interframe coding: a general framework and algorithms[J]. IEEE Transactions on Image Processing,2007,16(7):1774-1784.
[2] 畢厚杰.新一代視頻壓縮編碼標準-H.264/AVC[M].北京：人民郵電出版社，2005:33-45.
[3] WIEGAND T, SULLIVAN G J.Overview of the H. 264/AVC video coding standard[J].IEEE Transactions on Ciruits and Systems for Video Technology,2003,13(7):560-576.
[4] CHEN Z, ZHOU P, HE Y. Fast motion estimation for JVT [S]. JVT-G016,7th Meeting[C]. Thailand, Pattaya II: JVT  of ISO/IEC MPEG & ITU-T VCEG, 7-14 March, 2003.
[5] CHEN Z, ZHOU P, HE Y. Fast integer pixel and fractional pixel motion estimation for JVT[S].JVT-F017,2002,6th Meeting[C].Awajilsland,Japan:JVT of ISO/IEC MPEG & ITU-T VCEG,2002,5-13.
[6] LAM C H, PO L M, CHEUNG C H. A novel kite-cross-diamond search algorithm for fast block motion estimation[C]. Proceedings of 2004 IEEE International Symposium on  Circuits and Systems. Canada:IEEE, 2004:729-732.
[7] 鄭振東,王沛,應駿. H.264 JM模型中運動估計算法及其改進方案[J].中國圖像圖形學報，2007,10(12):1798-1780.