一種改進(jìn)的UMHexagonS運(yùn)動(dòng)估計(jì)算法

楊 齊，李子印

（中國(guó)計(jì)量學(xué)院光學(xué)與電子科技學(xué)院，浙江杭州 310018）

H.264是最新的國(guó)際通用的視頻編解碼標(biāo)準(zhǔn)，由動(dòng)態(tài)圖像專家組（MPEG）和視頻編碼專家組（VCEG）聯(lián)合開(kāi)發(fā)并于2003年正式發(fā)布。H.264因其高精度的運(yùn)動(dòng)估計(jì)、多參考幀預(yù)測(cè)、多宏塊劃分模式等特點(diǎn)而具有高效的編碼性能，得到了廣泛的應(yīng)用，并將在無(wú)線多媒體傳感器網(wǎng)絡(luò)、高清數(shù)字電視、遠(yuǎn)程視頻教學(xué)等諸多領(lǐng)域發(fā)揮很重要的作用［1］。運(yùn)動(dòng)估計(jì)是H.264視頻編碼器結(jié)構(gòu)中的核心部分，它和運(yùn)動(dòng)補(bǔ)償占據(jù)著整個(gè)編碼過(guò)程總運(yùn)算量的70%以上。目前UMHexagonS［2］算法已被H.264編碼標(biāo)準(zhǔn)正式采納為其整像素運(yùn)動(dòng)估計(jì)算法，其運(yùn)動(dòng)估計(jì)精度較高，但同三步法、新三步法、四步法等快速算法相比，該算法的搜索點(diǎn)數(shù)還較多，搜索速度還不夠快。

為了能在保持較好的率失真性能的同時(shí)，進(jìn)一步降低算法的復(fù)雜度，提高編碼效率。本文從起始搜索點(diǎn)預(yù)測(cè)、運(yùn)動(dòng)類型自適應(yīng)搜索選擇、搜索模板和提前終止判斷四個(gè)模塊對(duì)UMHexagonS算法進(jìn)行了改進(jìn)。

1 UMHexagonS算法介紹

UMHexagonS是一種混合的多層次運(yùn)動(dòng)估計(jì)算法，主要的搜尋步驟［3］可分為以下6步:

1）起始搜索點(diǎn)預(yù)測(cè)。分別采用4種不同的起始點(diǎn)預(yù)測(cè)方法（中值預(yù)測(cè)、對(duì)應(yīng)塊預(yù)測(cè)、上層預(yù)測(cè)和臨近參考幀預(yù)測(cè)）來(lái)搜索出一個(gè)使得對(duì)應(yīng)的代價(jià)函數(shù)J（m，λmotion）最小的候選運(yùn)動(dòng)矢量作為起始搜索點(diǎn)，并執(zhí)行提前終止判斷。

2）不對(duì)稱的十字交叉搜索。由于自然界中常見(jiàn)運(yùn)動(dòng)場(chǎng)景的水平方向的運(yùn)動(dòng)要比垂直方向的劇烈一些，故使用如圖1a所示的不對(duì)稱的十字交叉搜索方法，并執(zhí)行提前終止判斷。

3）正方形搜索。以當(dāng)前最佳點(diǎn)為中心，搜索如圖1b所示的25點(diǎn)方形區(qū)域。

4）多層次的六邊形搜索。以正方形搜索所獲得的最優(yōu)點(diǎn)為中心，在搜索窗中執(zhí)行直徑不斷擴(kuò)大一倍的16點(diǎn)六邊形模板（如圖1c所示）的搜索。

5）擴(kuò)展六邊形模板搜索。采用圖1d所示的搜索模板反復(fù)進(jìn)行搜索，直至最優(yōu)點(diǎn)位于六邊形的中心點(diǎn)時(shí)結(jié)束搜索。

6）小菱形搜索。以當(dāng)前最優(yōu)點(diǎn)作為中心，反復(fù)采用小菱形模板（如圖1e所示）進(jìn)行搜索，當(dāng)最優(yōu)點(diǎn)處在小菱形的中心點(diǎn)時(shí)結(jié)束搜索，并把此時(shí)對(duì)應(yīng)的運(yùn)動(dòng)矢量選定為最終的運(yùn)動(dòng)矢量。

圖1 UMHexagonS算法中使用的各種搜索模板

2 對(duì)UMHexagonS算法的改進(jìn)

2.1 起始搜索點(diǎn)預(yù)測(cè)的優(yōu)化

起始搜索點(diǎn)預(yù)測(cè)是依據(jù)運(yùn)動(dòng)物體的整體性和序列運(yùn)動(dòng)的連續(xù)性，利用待估計(jì)塊和其周邊塊的時(shí)空相關(guān)性，用周邊已編碼塊的運(yùn)動(dòng)矢量進(jìn)行當(dāng)前塊的運(yùn)動(dòng)矢量的起始點(diǎn)預(yù)測(cè)［4］。本文在此基礎(chǔ)上，進(jìn)一步考慮到中心偏移特性和固定背景上物體邊界的情況，在經(jīng)中值預(yù)測(cè)得到mvpred_MD、上層預(yù)測(cè)得到 mvpred_UP、對(duì)應(yīng)塊預(yù)測(cè)得到mvpred_CB、臨近參考幀預(yù)測(cè)得到mvpred_NRP的同時(shí)，也對(duì)原點(diǎn)（0，0）進(jìn)行搜索預(yù)測(cè)并計(jì)算出J0（m，λmotion），其對(duì)應(yīng)的預(yù)測(cè)矢量為mv=（0，0）。然后通過(guò)比較這5個(gè)運(yùn)動(dòng)矢量各自對(duì)應(yīng)的值，選取J（m，λmotion）最小的運(yùn)動(dòng)矢量作為起始搜索的最終預(yù)測(cè)運(yùn)動(dòng)矢量。

2.2 運(yùn)動(dòng)類型自適應(yīng)的搜索選擇

同一視頻幀中的不同區(qū)域塊有著不同的運(yùn)動(dòng)類型，可將物體運(yùn)動(dòng)類型區(qū)分為靜止或慢速運(yùn)動(dòng)、中速運(yùn)動(dòng)、快速運(yùn)動(dòng)三種。本文通過(guò)利用起始預(yù)測(cè)運(yùn)動(dòng)矢量的運(yùn)動(dòng)信息對(duì)當(dāng)前塊的運(yùn)動(dòng)類型進(jìn)行劃分，對(duì)靜止或慢速運(yùn)動(dòng)塊采用小模板進(jìn)行一步停止法搜索、對(duì)中速運(yùn)動(dòng)塊也適當(dāng)減少搜索步驟、對(duì)快速運(yùn)動(dòng)塊則仍采用多步的詳盡搜索［5］。

圖2 改進(jìn)算法的流程圖

2.3 搜索模板的改進(jìn)

UMHexaongS算法在不對(duì)稱十字交叉搜索之后，再搜索當(dāng)前最優(yōu)點(diǎn)周邊的25點(diǎn)正方形區(qū)域，并對(duì)一些較為劇烈的運(yùn)動(dòng)場(chǎng)景采用多層次的六邊形模板進(jìn)一步搜索，以獲取最佳的匹配點(diǎn)，這種方法可以比較準(zhǔn)確地找到當(dāng)前塊的匹配塊，但其搜索點(diǎn)數(shù)還比較多［7］。本文在保證重要區(qū)域的點(diǎn)得到精確搜索的同時(shí)，除去了對(duì)一些不重要區(qū)域的點(diǎn)的搜索，從而進(jìn)一步減少搜索點(diǎn)數(shù)、提高編碼效率。

2.3.1 正方形搜索模板的改進(jìn)

根據(jù)運(yùn)動(dòng)矢量中心偏移特性及大量的實(shí)驗(yàn)表明，最佳運(yùn)動(dòng)矢量落在以半徑為2的圓形區(qū)域內(nèi)的可能性高達(dá)80%以上［8］，UMHexagonS算法中采用的25點(diǎn)正方形搜索區(qū)域中有不少點(diǎn)是落在該圓形區(qū)域的外面。基于此，采用含有該圓形區(qū)域內(nèi)的所有整像素位置的13點(diǎn)菱形搜索模板代替正方形搜索模板，如圖3a所示。這種搜索模板能夠確保對(duì)重要搜索區(qū)域進(jìn)行搜索，并可為該搜索步驟節(jié)省12個(gè)搜索點(diǎn)。

2.3.2 多層次大六邊形模板的改進(jìn)

考慮到常見(jiàn)視頻序列的水平、垂直方向較其他方向運(yùn)動(dòng)更加劇烈，采用多層次大菱形搜索模板代替UMHexagonS算法中所采用的多層次大六邊形搜索模板，如圖3所示。這種改進(jìn)可使該步驟中的搜索點(diǎn)數(shù)變?yōu)樵瓉?lái)的一半。

圖3 改進(jìn)后的模板

2.4 提前終止判斷的優(yōu)化

本文沿用了UMHexagonS算法所采用的提前終止判斷方法［9］。具體如下

如果滿足條件（1），其SAD值判定為很小，執(zhí)行第6步;如果滿足條件（2），其SAD值判定為較小，跳至第5步;若滿足條件（3），其SAD值判定為很大，執(zhí)行下一步。

UMHexagonS源算法中，在正方形搜索和多層次大六邊形搜索后均未進(jìn)行提前終止的判斷。本文在改進(jìn)后的13點(diǎn)菱形搜索和8點(diǎn)多層次菱形搜索的步驟后均加入了提前終止判斷（閾值判斷）條件。

結(jié)合以上四個(gè)方面對(duì)改進(jìn)算法的描述，將整個(gè)改進(jìn)算法的實(shí)現(xiàn)流程［10-11］繪制如圖2所示。

3 實(shí)驗(yàn)仿真及分析

為了測(cè)試改進(jìn)算法的性能，采用H.264的參考軟件JM10.2在Visual C++6.0實(shí)驗(yàn)平臺(tái)上實(shí)現(xiàn)該算法。編碼幀數(shù)為80，參考幀數(shù)為5，搜索范圍為±16，量化參數(shù)為28，熵編碼為CABAC，編碼類型為IBPBP，幀率為30 Hz，其他參數(shù)為缺省默認(rèn)設(shè)置。

實(shí)驗(yàn)中選取了akiyo，foreman，coastguard三個(gè) QCIF格式的不同運(yùn)動(dòng)類型的序列進(jìn)行測(cè)試。其中akiyo代表慢速的運(yùn)動(dòng)序列，foreman代表中速運(yùn)動(dòng)序列，coastguard代表快速運(yùn)動(dòng)序列［12］。分別使用全搜索算法（FS）、UMHexagonS算法（UMH）和本文改進(jìn)的算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果及分析如表1～3所示。

表1 實(shí)驗(yàn)結(jié)果記錄

表2 改進(jìn)算法相對(duì)FS算法的變化

表3 改進(jìn)算法相對(duì)于UMHexagonS算法的變化

通過(guò)對(duì)表2、表3的觀察和分析可知，改進(jìn)算法相比于全搜索算法而言，信噪比平均降低0.015 dB，碼率變化率為-0.7% ～+0.8%，運(yùn)動(dòng)估計(jì)時(shí)間節(jié)省60% ～80%;改進(jìn)算法相比于UMHexagonS算法而言，信噪比平均增加0.008 dB，碼率變化率為-0.3% ～+1.1%，運(yùn)動(dòng)估計(jì)時(shí)間節(jié)省10%～25%。由此可知，改進(jìn)后的算法在保持信噪比和碼率基本不變的情況下，大大節(jié)省了運(yùn)動(dòng)估計(jì)的搜索時(shí)間，有效地提高了編碼器的實(shí)時(shí)性能。

4 小結(jié)

本文提出的改進(jìn)算法利用運(yùn)動(dòng)矢量的運(yùn)動(dòng)信息對(duì)視頻序列的運(yùn)動(dòng)類型進(jìn)行劃分，并結(jié)合原點(diǎn)預(yù)測(cè)、模板替換和提前終止，從四個(gè)方面對(duì)UMHexagonS算法進(jìn)行改進(jìn)和優(yōu)化。仿真結(jié)果表明，新改進(jìn)的算法在維持圖像質(zhì)量基本不變甚至略有改善的情形下，較大幅度地減少了搜索點(diǎn)數(shù)，使得運(yùn)動(dòng)估計(jì)的時(shí)間節(jié)省了10% ～23%，能夠更好地滿足許多實(shí)時(shí)場(chǎng)合（如實(shí)時(shí)視頻監(jiān)控、可視電話、物聯(lián)網(wǎng)）的應(yīng)用要求，具有較強(qiáng)的實(shí)用價(jià)值。

：

［1］畢厚杰，王健.新一代視頻壓縮編碼標(biāo)H.264/AVC［M］.北京:人民郵電出版社，2009.

［2］CHEN Zhibo，ZHOU Peng，HE Yun.Fast integer pel and fractional pel motion estimation for JVT［C］//Proc ISO/IEC MPEG&ITU-T VCEG 6th Meeting.［S.l.］:JVT，2002.

［3］羅哲.基于快速運(yùn)動(dòng)估計(jì)算法UMHexagonS的改進(jìn)和優(yōu)化［J］.研究與開(kāi)發(fā)，2011（3）:29-31.

［4］熊承義，白云.基于方向信息的快速整像素運(yùn)動(dòng)估計(jì)優(yōu)化［J］.中南民族大學(xué)學(xué)報(bào)，2010，29（1）:62-67.

［5］楊曉珍，吳延海，王鋒.基于塊運(yùn)動(dòng)類型的自適應(yīng)菱形運(yùn)動(dòng)估計(jì)搜索算法［J］. 計(jì)算機(jī)工程，2007，33（23）:220-222.

［6］丁鑫，樊慧津.基于方向自適應(yīng)的運(yùn)動(dòng)估計(jì)混合模板搜索算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2011，16（1）:14-20.

［7］申舟，李正明，潘天紅.H.264/AVC中基于搜索區(qū)域劃分及評(píng)估的運(yùn)動(dòng)估計(jì)［J］. 中國(guó)圖象圖形學(xué)報(bào)，2010，15（2）:242-246.

［8］LIN C C，LIN Y，HSIEH H J.Multi-direction search algorithm for block motion estimation in H.264/AVC［J］.IEEE Trans.Image Processing，2009，3（2）:88-99.

［9］楊曉琴，季曉勇.基于H.264的快速運(yùn)動(dòng)估計(jì)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（4）:174-175.

［10］盧政，盧俊.基于UMHexagonS的快速運(yùn)動(dòng)估計(jì)算法優(yōu)化［J］.電視技術(shù)，2011，7（35）:29-31.

［11］SHI Zhiru，F(xiàn)ERNANDO W A C，DE SILVA D V S X.A motion estimation algorithm based on predictive intensive direction search for H.264/AVC［C］//Proc.2010 ICME.［S.l.］:IEEE Press，2010:667-672.

［12］WU Xiaomin，XU Weizhang，ZHU Nanhao.A fast motion estimation algorithm for H.264［C］//Proc.2010 ICSAP.［S.l.］:IEEE Press，2010:112-116.