《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > H.264中快速運(yùn)動(dòng)估計(jì)UMHexagonS算法的改進(jìn)
H.264中快速運(yùn)動(dòng)估計(jì)UMHexagonS算法的改進(jìn)
來(lái)源：電子技術(shù)應(yīng)用2011年第8期
劉 易,， 李太君
(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?70228)
摘要： 在對(duì)H.264中非對(duì)稱十字型多層次六邊形格點(diǎn)搜索算法（UMHexagonS）研究的基礎(chǔ)上,，針對(duì)其存在運(yùn)算量大、耗時(shí)等問(wèn)題提出兩方面的改進(jìn),。首先,，利用對(duì)稱十字模板替換原來(lái)的5×5螺旋搜索，減少了64%的搜索點(diǎn)數(shù);其次,，利用對(duì)象內(nèi)部代價(jià)的相關(guān)性提出自適應(yīng)搜索長(zhǎng)度方法,以減少運(yùn)算量,。在JM10.1測(cè)試模型上進(jìn)行了驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法在保證圖像質(zhì)量的前提下,可以有效地減少平均15%的運(yùn)動(dòng)估計(jì)時(shí)間,，提高了總體的編碼性能,。
中圖分類號(hào)： TN919
文獻(xiàn)標(biāo)識(shí)碼： A
文章編號(hào)： 0258-7998(2011)08-128-03
Improvements on fast motion estimation UMHexagonS algorithm of H.264
Liu Yi, Li Taijun
College of Information Science & Technology, Hainan University,Haikou 570228,China
Abstract： Based on introducing an unsymmetrical cross grid search algorithm (UMHexagonS) of H.264, improvements the algorithm in two areas for the existence of large amount of computation, high complexity, time-consuming issues. Firstly, uses symmetric cross template replace the original 5×5 spiral search, decreases 64% of search points. Secondly, uses correlation of object inside cost, propose adaptive searching range method and reduce computation. In JM10.1, the experiment results show that the improved algorithm in the premise of image quality can effectively reduce average 15% of the motion estimation time, thus improving the overall coding performance.
Key words : H.264；adaptive searching range,；UMHexagonS algorithm,；symmetrical cross template


    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的編碼過(guò)程中,，由于H.264編碼器采用了高精度運(yùn)動(dòng)矢量,，計(jì)算量迅速增長(zhǎng)，運(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)專利庫(kù)中的一部分。
    UMHexagonS算法的基本步驟[5]如下：

 

    (1)起始搜索點(diǎn)預(yù)測(cè),。使用多幀參考,、中值預(yù)測(cè)、上層預(yù)測(cè),、相應(yīng)塊預(yù)測(cè)和鄰近參考幀預(yù)測(cè)五種方法來(lái)進(jìn)行預(yù)測(cè),。在起始搜索矢量的集合中,以擁有最小代價(jià)預(yù)測(cè)的運(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)矢量場(chǎng)通常是柔和平滑的，變化也比較緩慢,。參考文獻(xiàn)[6]中對(duì)典型的平緩和運(yùn)動(dòng)復(fù)雜的自然視頻序列的運(yùn)動(dòng)矢量的統(tǒng)計(jì)研究發(fā)現(xiàn),，超過(guò)80%的運(yùn)動(dòng)矢量預(yù)測(cè)值位于中心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)搜索來(lái)取代螺旋搜索5×5區(qū)域的25點(diǎn)搜索,。

2.2自適應(yīng)搜索長(zhǎng)度
     搜索長(zhǎng)度search_range在UMHexagonS算法中用來(lái)控制搜索候選搜索點(diǎn)的范圍。主要體現(xiàn)在以下幾個(gè)步驟：步驟(4)(多層次大六邊形格點(diǎn)搜索)中,，以1/4 search_range做為搜索長(zhǎng)度,。步驟(5)(小六邊形模板反復(fù)搜索)中，以search_range作為搜索長(zhǎng)度,；步驟(6)(菱形模板反復(fù)搜索)中,，以search_range作為搜索長(zhǎng)度?？梢?jiàn),，在UMHexagonS算法中搜索長(zhǎng)度是固定不變的，合理地設(shè)定搜索長(zhǎng)度能有效地減少UMHexagonS算法的復(fù)雜度,。
     場(chǎng)景中一般都是以某一對(duì)象為單位的運(yùn)動(dòng),，因此該對(duì)象內(nèi)部的代價(jià)（mcost）應(yīng)該具有很高的相關(guān)性[7]。據(jù)此,，本文利用前兩個(gè)搜索步驟的min_mcost之比,，提出自適應(yīng)搜索長(zhǎng)度的方法。
    設(shè)利用變量pre_min_mcost1,、pre_min_mcost2,、pre_min_mcost3、 pre_min_mcost4來(lái)分別保存步驟(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是搜索長(zhǎng)度,。根據(jù)ki來(lái)相應(yīng)地縮短改進(jìn)后的搜索長(zhǎng)度,，本文的改進(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測(cè)試序列進(jìn)行測(cè)試。
　    實(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)測(cè)試序列：akyio_qcif.yuv、foreman_qcif.yuv,、mobile_qcif.yuv,其場(chǎng)景運(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í)間的減少幅度不同,，主要由視頻場(chǎng)景運(yùn)動(dòng)的激烈程度不同所造成,。視頻序列akiyo運(yùn)動(dòng)場(chǎng)景相對(duì)平緩，起始點(diǎn)預(yù)測(cè)的精度較高,，在早期判斷EARLY_TERMINATION時(shí),因?yàn)镾AD很小,，直接跳到步驟(6),也就是說(shuō),沒(méi)有執(zhí)行對(duì)稱十字模板步驟(3)和通過(guò)自適應(yīng)搜索長(zhǎng)度來(lái)降低運(yùn)算量的步驟(4)和步驟(5)所以運(yùn)動(dòng)估計(jì)時(shí)間減少的效果不是很明顯。而對(duì)于場(chǎng)景運(yùn)動(dòng)一般和場(chǎng)景運(yùn)動(dòng)激烈的foreman和mobile序列,由于SAD指標(biāo)不符合早期判斷EARLY_TERMINATION條件, 執(zhí)行了對(duì)稱十字模板步驟(3)和自適應(yīng)搜索長(zhǎ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)搜索替換原來(lái)的5×5螺旋搜索,，減少了64%的搜索點(diǎn)數(shù),；其次，利用對(duì)象內(nèi)部代價(jià)的相關(guān)性提出自適應(yīng)搜索長(zhǎ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].中國(guó)圖像圖形學(xué)報(bào)，2007,10(12):1798-1780.

此內(nèi)容為AET網(wǎng)站原創(chuàng),，未經(jīng)授權(quán)禁止轉(zhuǎn)載,。