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

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

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

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

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