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

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

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

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

    本文在結(jié)合JM10.1模型的基礎(chǔ)上分析了H.264中運動估計算法(UMHexagonS算法),針對該算法的不足之處提出了兩處改進。首先，利用對稱十字模板9點搜索替換原來的5×5螺旋搜索，減少了64%的搜索點數(shù)；其次，利用對象內(nèi)部代價的相關(guān)性提出自適應(yīng)搜索長度方法。在保證視頻序列各分量的信噪比和比特率的情況下，使運動估計時間平均降低了15%,增強了編碼的實時性，有利于視頻圖像實時編碼傳輸?shù)膶崿F(xiàn)。
參考文獻
[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] 鄭振東,王沛,應(yīng)駿. H.264 JM模型中運動估計算法及其改進方案[J].中國圖像圖形學(xué)報，2007,10(12):1798-1780.