H.264標(biāo)準(zhǔn)是由視頻聯(lián)合工作組JVT(Joint Video Team)組織提出的新一代數(shù)字視頻編碼標(biāo)準(zhǔn),與其他標(biāo)準(zhǔn)相比,，H.264具有更高的編碼效率[1],能夠節(jié)省大約50%的碼率,。但是對H.264性能的改進是以增加復(fù)雜性為代價的，其編碼的計算復(fù)雜度大約相當(dāng)于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標(biāo)準(zhǔn)專利庫中的一部分,。
    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作為搜索長度,?？梢姡赨MHexagonS算法中搜索長度是固定不變的,，合理地設(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個具有代表性的標(biāo)準(zhǔn)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è)置為默認(rèn)值。
3.2 實驗數(shù)據(jù)與分析
　　本文主要采用Y,、U,、V各分量的峰值信噪比( PSNR)、運動估計時間(MET)和比特率作為算法性能評判的標(biāo)準(zhǔn),。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指標(biāo)不符合早期判斷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] 畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)-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.