任克強 林芳明

(江西理工大學(xué)信息工程學(xué)院， 贛州， 341000)

H.264運動估計UMHexagonS算法的優(yōu)化與改進*

任克強 林芳明

(江西理工大學(xué)信息工程學(xué)院， 贛州， 341000)

針對H.264中UMHexagonS算法存在的不足，提出了一種改進的快速運動估計算法。改進算法根據(jù)起始預(yù)測運動矢量成為最佳點的可能性大小對起始預(yù)測運動矢量的檢測順序進行了優(yōu)化，提高了編碼效率；設(shè)計了一種改進的5×5螺旋全搜索模板，減少了5×5螺旋全搜索模板的搜索點數(shù)；增加了一種針對亞宏塊的提前終止策略，進一步減少了運動估計帶來的運算量。實驗結(jié)果表明，改進算法在基本保持UMHexagonS算法編碼性能的同時，有效減少了運動估計時間，提高了編碼效率，并且可適用于不同運動強度的視頻序列。

運動估計； 5×5螺旋全搜索； 起始預(yù)測； 提前終止策略

引 言

H.264是新一代視頻編碼標準，包括預(yù)測編碼、離散余弦變換(Discrete cosine transform，DCT)和量化、DCT反變換和反量化、熵編碼、環(huán)路濾波、運動估計以及運動補償?shù)饶K[1-2]，其中基于塊的運動估計是視頻編碼的關(guān)鍵內(nèi)容之一，運算量為整個編碼過程的50%～80%[3]。所以縮短運動估計時間是一種很有效的方法，可以明顯降低圖像序列的冗余度。全搜索(Full search，F(xiàn)S)算法[4]是基于塊運動估計的最簡單算法，通過檢測所有的可能點來得到最佳點，在獲取最佳運動矢量的同時也帶來龐大的運算量，有悖于視頻通信的實時性。

為了減少運動估計時間，研究人員提出了許多快速算法，非對稱十字多層六邊形搜索(Unsymmetrical-cross multi-hexagon-grid search，UMHexagonS)算法[5]就是其中的一種。盡管該算法有較優(yōu)秀的編碼性能，但依然存在搜索點數(shù)較多等不足。針對UMHexagonS存在的不足，研究人員對其進行了深入研究，先后提出了不同的改進方案。文獻[6]通過預(yù)測運動矢量(Motion vector,MV)來劃分需要搜索區(qū)域的重要等級，再根據(jù)等級為各區(qū)域分配不同的搜索策略，有效地提高了搜索速度。文獻[7]利用編碼塊預(yù)測運動矢量的準確度，自適應(yīng)地確定搜索區(qū)間大小，依據(jù)運動方向特性，確定有效的搜索方向，明顯減少了搜索量。文獻[8]設(shè)計了一種依據(jù)塊模式尺寸大小及運動類型來自適應(yīng)選擇搜索窗及搜索策略的算法；文獻[9]為不同運動程度和方向的宏塊分配不同的搜索方案，針對UMHexagonS的中值預(yù)測進行了改進，并設(shè)計了一種動態(tài)參考塊提前跳過方案；文獻[8，9]的改進方法對運動劇烈的視頻序列效果明顯，但對運動較為緩慢的視頻序列效果一般。文獻[10]充分考慮利用運動矢量時空相關(guān)性這一特點，使得起始預(yù)測更為精確；改固定閾值靜止塊判斷法為自適應(yīng)閾值判斷法，適合各種類型的序列；根據(jù)塊運動類型的不同相應(yīng)分配相應(yīng)搜索策略，有效保證圖像質(zhì)量及搜索速度，但此算法的起始搜索預(yù)測精度不夠高，可能導(dǎo)致局部最優(yōu)。文獻[11]針對UMHexagonS的固定搜索窗口、不對稱十字交叉、5×5螺旋模板、多層次大六邊形及中六邊形進行優(yōu)化，設(shè)計出一種自適應(yīng)模型方向搜索(Adaptive pattern direction search，APDS)算法，明顯提升了搜索速率。文獻[12]依據(jù)H.264中整數(shù)離散余弦變換和量化思想，設(shè)計出一種基于全零塊檢測的模式選擇快速算法。文獻[13]設(shè)計一種自適應(yīng)選擇編碼模式快速運動估計算法，結(jié)合視頻序列的空間相關(guān)性和運動特性選取更合適的尺寸模式，并通過不同搜索方式對分割塊進行搜索，有效降低了計算復(fù)雜度，然而此算法只對運動幅度大的視頻序列有明顯的優(yōu)勢。本文在UMHexagonS和相關(guān)文獻分析研究基礎(chǔ)上，從起始預(yù)測、搜索模板及亞宏塊模式檢測3個方面對其進行了優(yōu)化和改進，提出一種UMHexagonS的改進算法以提高編碼效率。

1 UMHexagonS算法分析

在JM測試模型現(xiàn)有的塊匹配算法中，F(xiàn)S最精確，但其搜索時間過長和計算量過于龐大，使得軟硬件上都難于實現(xiàn)，而UMHexagonS的運動估計時間不到FS的10%，且還具有較好的編碼性能。為了在編碼比特率與圖像失真之間選擇一個合適的折中，H.264對運動估計采用了率失真優(yōu)化準則，其定義的匹配誤差函數(shù)為

(1)

式中SAD為當前塊與參考塊之間的絕對差值和，即

(2)

圖1 UMHexagonS算法的主要搜索模板Fig.1 Main search patterns of UMHexagonS algorithm

式中：s為當前塊的數(shù)據(jù)；c為編碼重構(gòu)后的參考幀數(shù)據(jù)；MV為候選運動矢量；PMV為預(yù)測運動矢量；λ為拉格朗日因子；R(MV-PMV)為運動信息；A為像素區(qū)域。

UMHexagonS算法的基本步驟如下：(1) 用多種方式進行起始預(yù)測，包括中值、原點(0,0)、上層塊、前幀同位置塊及相鄰參考幀預(yù)測；(2) 非對稱十字交叉搜索，如圖1(a)；(3) 5×5螺旋全搜索，如圖1(b)；(4) 多層次非對稱大六邊形搜索，如圖1(c)；(5) 中六邊形搜索，如圖1(c)；(6) 小菱形反復(fù)搜索，如圖1(c)，當最佳點在小菱形中點時結(jié)束。

此外，在步驟(1～4)中都設(shè)置了提前終止的閾值判斷。把當前最小的塊匹配代價值(Sum of absolute differences,SAD)分別與兩個閾值T1和T2進行大小比較，若SADT2，則繼續(xù)順序搜索。

2 UMHexahonS算法優(yōu)化和改進

盡管UMHexagonS取得了較好的效率，但其還存在一些不足：(1) 起始預(yù)測部分沒有采用最合理的檢測順序；(2) 5×5螺旋搜索存在許多不必要的搜索點，運算量大，耗費過多時間；(3) 亞宏塊的模式選擇時，若開始的8×8模式就是最佳模式，則依然還要對剩余模式檢測，這大大增加了不必要的搜索。本文針對這3個方面的不足對該算法進行優(yōu)化與改進。

2.1 起始預(yù)測MV檢測順序的優(yōu)化

UMHexagonS在起始預(yù)測時，先后對中值、原點、上層塊、前幀同位置塊及相鄰參考幀預(yù)測進行檢測。非最優(yōu)的預(yù)測方式檢測順序會降低算法的編碼效率，增加不必要的搜索。理論上成為最佳點MV可能性最大的預(yù)測MV，應(yīng)該最先被檢測，可能性最小的預(yù)測MV，應(yīng)該最后被檢測。為獲得更好的編碼性能及減少不必要的搜索點，本文先通過實驗來確定這5種預(yù)測MV成為最佳點MV的可能性大小，再根據(jù)可能性由大到小依次進行這5種起始預(yù)測。

圖2 優(yōu)化的預(yù)測MV檢測順序 Fig.2 Checking order of optimized prediction MV

實驗中取運動劇烈程度不一的試序列，分別在不同參考幀下統(tǒng)計各預(yù)測MV成為最佳點MV的可能性，樣本總個數(shù)為對應(yīng)預(yù)測MV被檢測的總次數(shù)，可能性大小由對應(yīng)預(yù)測MV成為最佳點MV次數(shù)與被檢測總次數(shù)共同決定。為使所有預(yù)測MV均能被檢測，本實驗在上層塊預(yù)測后不進行提前終止檢測。由實驗統(tǒng)計，這5種預(yù)測MV成為最佳點MV的可能性大小可分成3個等級：首先為中值和上層塊預(yù)測，這兩種可能性最大；其次為前幀同位置塊和相鄰參考幀預(yù)測，可能性次之；最后為原點預(yù)測，可能性最小。因此本文先進行中值和上層塊預(yù)測，再進行前幀同位置塊和相鄰參考幀預(yù)測，最后進行原點預(yù)測，檢測流程如圖2所示。

2.2 5×5螺旋全搜索的改進

UMHexagonS中5×5螺旋全搜索總共要檢測25個點，復(fù)雜度過高、計算量過大，而且很費時間，因此有必要對原5×5螺旋全搜索進行優(yōu)化。經(jīng)研究統(tǒng)計，80%以上的運動矢量預(yù)測值落在中點5×5方形區(qū)域內(nèi)，但是分布很不均勻，接近72%預(yù)測值落在3×3的方形區(qū)域內(nèi)[14]，如圖3所示。由此可見，在5×5的方形區(qū)域中，最佳點落入3×3方形區(qū)域中的可能性很大，而落入其外圍邊界的可能性較小。文獻[15]對于16×16模式的塊，因運動分量近乎等于零，不執(zhí)行本步驟；對于4×4模式的塊，因運動細節(jié)過多，依舊使用原5×5模板；而對于其他模式的塊，使用3×3方形模板，以損失少量運動矢量換取減少較多的搜索點數(shù)。

本文采用一種較為折中的改進方案，先對3×3方形區(qū)域內(nèi)的點進行檢測，通過檢測可判斷其運動方向，然后沿著該方向向外圍進行搜索，能有效減少檢測點數(shù)。具體方法為：檢測居中的3×3方形區(qū)域中的8個點(除去中心點)，將互鄰的3個點劃為一組，共有8組，將各組中3個點對應(yīng)的塊匹配代價值相加，可得8個和值，對這8個和值進行大小比較，沿和值最小的一組相應(yīng)的外圍方向做進一步擴展搜索，如圖4所示。由圖4可以看出，本文改進的5×5螺旋全搜索只需檢測14個點，相比UMHexagonS減少了11個點。

圖3 5×5全搜索區(qū)域的運動矢量分布

Fig.4 Adaptive 5×5 spiral search

2.3 基于全零塊檢測的提前終止策略

對于一個運動補償后的殘差塊，如果在DCT變換及量化后系數(shù)都是零，就可以認為當前匹配塊為最佳匹配塊，通常稱其為全零塊。H.264中的亞宏塊可能采用8×8，8×4，4×8和4×4這4種模式，在運動估計的時候，每種模式都要被嘗試一次，按從大到小的順序依次檢測，一般選匹配代價值最小者作為最佳模式。如果第1個被檢測的8×8模式為最佳模式，仍然還會對剩余模式檢測，這無疑增加許多不必要的計算量。為了計算8×8模式下的匹配代價值，要對其包含的4×4子塊做變換及量化處理。在相同最優(yōu)運動矢量下，大尺寸模式對應(yīng)的匹配代價值更小，所以對8×8模式，若4個4×4子塊都是全零塊，則8×8模式下亞宏塊的匹配代價值最小，對后面3種更小塊模式進行檢測是多余的。針對上述情況，增加一種針對亞宏塊的提前終止策略，最先檢測完8×8模式后，若它所包括的4個4×4子塊都是全零塊，就不再去檢測剩下的模式，認為所有子塊都找到了對應(yīng)的最優(yōu)匹配塊，8×8尺寸下的子塊的最佳運動矢量可視為等同其他尺寸模式下各子分割塊的最優(yōu)運動矢量。此時該模式下亞宏塊對應(yīng)的代價值最小，所以不需要再對剩余3種模式進行檢測。

2.4 改進算法

綜上所述，本文改進算法描述如下。(1) 按圖2所示對起始預(yù)測MV進行檢測，確定起始點。(2) 選取目前SAD值最小的點，若SAD

3 實驗結(jié)果與分析

實驗環(huán)境為AMD Athlon(tm)Ⅱ X2 240 @ 2.81 GHz,2.0GB內(nèi)存；Windows XP SP2+JM10.2。實驗中主要編碼參數(shù)如下：NumberReferenceFrames=5，F(xiàn)rameRate=30.0，SearchRange=16，F(xiàn)ramesToBeEncoded=100，使用哈達瑪變換，開啟RDO優(yōu)化，采用IPPP碼流結(jié)構(gòu)，量化參數(shù)QP取值28，其他為默認配置。

測試序列使用分辨率和運動強度不一的YUV(4:2:0)序列，包括4個分辨率為176×144的QCIF序列：Coastguard，Mobile，F(xiàn)oreman和Akiyo，3個分辨率為352×288的CIF格式序列：Football,Bus和News。其中，Coastguard，Mobile和Football運動劇烈，F(xiàn)oreman，Bus運動中度劇烈，Akiyo，News運動緩慢。實驗結(jié)果用Y分量峰值信噪比PSNR(Y)值、輸出碼率Br值及運動估計時間MET值來表征算法性能。

(3)

(4)

(5)

式中：下標opt代表采用改進算法的實驗值；下標ref代表采用UMHexagonS算法的實驗值。

表1是上述序列前100幀編碼后的數(shù)據(jù)。由數(shù)據(jù)可知，對于不同的序列，本文改進算法的PSNR(Y)值及Br值與UMHexagonS相比差異很小，基本保持不變，PSNR(Y)平均減少0.021dB，Br平均增加0.52%。但本文算法的MET則比UMHexagonS大大減少；其中，對運動劇烈的視頻序列Coastguard(QCIF)，Mobile(QCIF)和Football(CIF)，MET分別減少30.22%,28.23%和32.34%；對運動中度劇烈的視頻序列Forman(QCIF)和Bus(CIF)，MET分別減少31.87%和27.63%；對運動緩慢的序列Akiyo(QCIF)和News(CIF)，MET分別減少21.63%和25.54%。由以上分析可得知，改進算法適合各種運動程度的序列。在運動劇烈的測試序列中，對應(yīng)的各預(yù)測MV值也差異很大，所以優(yōu)化起始預(yù)測MV檢測的效果更明顯；運動劇烈的序列有許多宏塊會進入全局搜索，所以改進5×5螺旋全搜索的效果也明顯；運動緩慢的序列包含大量的全零塊，因此基于全零塊檢測的提前終止策略效果更明顯。

表1 實驗結(jié)果比較

表2為本文改進方案、文獻[15，16]分別對UMHexagonS算法改進效果的比較。與UMHexagonS算法相比，文獻[15]的PSNR(Y)平均減少0.027 dB，Br平均增加1.07%，MET降低8.66%～30.88%，平均可減少21.93%；文獻[16]的PSNR(Y)平均減少0.002 dB，Br平均增加1.30%，MET降低7.58%～27.88%，平均可減少17.93%；本文算法的PSNR(Y)平均減少0.021 dB，Br平均增加0.52%，MET降低21.63%～32.34%，平均可減少28.21%?？梢钥闯?，本文算法的性能優(yōu)于文獻[15,16]，特別是對運動緩慢序列的編碼效果要明顯優(yōu)于文獻[15,16]。

圖5，6是在量化參數(shù)QP取不同值的情況下，本文算法與UMHexagonS算法分別對Foreman，Mobile序列編碼的率失真曲線圖。由圖可知，本文算法與UMHexagonS算法的率失真曲線圖基本一致，說明本文算法較好地保持了原算法的編碼性能。

圖5 Foreman序列的率失真曲線比較

Fig.6 Comparison of R-D curve for Mobile sequence

圖7，8以Foreman序列的前30幀為例，從PSNR(Y)和搜索點數(shù)兩方面對本文算法與原算法進行逐幀的編碼效果比較。由圖可知，本文算法在大體保持每幀峰值信噪比的條件下，比原算法節(jié)省了近50%的搜索點數(shù)。

圖7 Foreman序列的PSNR(Y)比較

Fig.8 Comparison of search points for Forman sequence

4 結(jié)束語

本文以JM模型中的UMHexagonS為基礎(chǔ)，提出一種UMHexagonS的改進方案，從起始預(yù)測順序、5×5螺旋搜索以及亞宏塊的提前終止策略3個方面對其進行優(yōu)化與改進，并對改進算法和UMHexagonS算法的峰值信噪比、輸出碼流碼率、運動估計時間、率失真曲線以及搜索點數(shù)進行了比較實驗。實驗結(jié)果表明，改進算法在保證輸出碼流碼率和峰值信噪比變化很小的前提下，可以有效地提高對不同運動復(fù)雜度視頻序列的編碼效率。

[1] 周欣,段哲民,周巍.一種適用于H.264/AVC的新型整數(shù)變換與量化算法[J].數(shù)據(jù)采集與處理,2011, 26(6):619-625.

Zhou Xin,Duan Zhemin,Zhou Wei. Novel integer transform and quantization algorithm for H.24/AVC[J]. Journal of Data Acquisition and Processing, 2011, 26(6):619-625.

[2] 陳曉,劉海英.基于綜合因子的H.264碼率控制算法[J].數(shù)據(jù)采集與處理,2013, 28(3):347-351.

Chen Xiao, Liu Haiying. Rate control algorithm for H.264 with comprehensive factor[J]. Journal of Data Acquisition and Processing, 2013, 28(3):347-351.

[3] Ismail Y, McNeely J B, Shaaban M, et al. Fast motion estimation system using dynamic models for H.264/AVC video coding[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(1): 28-42.

[4] Kim J, Park T. A novel VLSI architecture for full-search variable block-size motion estimation[J]. Consumer Electronics, IEEE Transactions on, 2009, 55(2): 728-733.

[5] 張新安,宮彥軍,李小武.一種AVS-M整數(shù)像素運動估計快速算法[J].小型微型計算機系統(tǒng),2011,32(4):793-796.

Zhang Xinan, Gong Yanjun, Li Xiaowu. Fast integer pixel motion estimation algorithm for AVS-M[J]. Journal of Chinese Computer Systems, 2011, 32(4):793-796.

[6] 申舟,李正明,潘天紅.H.264/AVC中基于搜索區(qū)域劃分及評估的運動估計[J].中國圖象圖形學(xué)報,2010,15(2):242-246.

Shen Zhou, Li Zhengming, Pan Tianhong. Motion estimation based on the partition and evaluation of the search area in H.264/AVC[J]. Journal of Image and Graphics, 2010, 15(2):242-246.

[7] 劉英哲,王進祥.H.264中一種基于搜索范圍自適應(yīng)調(diào)整的運動估計算法[J].電子與信息學(xué)報,2013,35(6):1382-1387.

Liu Yingzhe, Wang Jinxiang. Motion estimation algorithm based on adaptive search range adjustment for H.264[J]. Journal of Electronics and Information Technology, 2013, 35(6):1382-1387.

[8] 李子印,楊齊.基于運動信息自適應(yīng)的快速運動估計算法[J].中國圖象圖形學(xué)報,2012,17(9):1069-1074.

Li Ziyin, Yang Qi. Fast motion estimation algorithm based on motion information adaptation[J]. Journal of Image and Graphics,2012,17(9):1069-1074.

[9] 劉治,王玲,陶小娟.動態(tài)模式的快速運動估計算法[J].計算機工程與科學(xué),2014,36(9):1760-1764.

Liu Zhi, Wang Ling, Tao Xiaojuan. A fast motion estimation algorithm using dynamic models[J]. Computer Engineering and Science, 2014, 36(9): 1760-1764.

[10]丁鑫,樊慧津.基于方向自適應(yīng)的運動估計混合模板搜索算法[J].中國圖象圖形學(xué)報,2011,16(1):14-20.

Ding Xin, Fan Huijin. A mix-pattern motion estimation search algorithm based on direction adaptation[J].Journal of Image and Graphics, 2011, 16(1): 14-20.

[11]肖冰君,楊靜.H.264中UMHexagonS運動估計算法的改進[J].計算機應(yīng)用,2014,34(6):1699-1705.

Xiao Bingjun, Yang Jing. Improvement of UMHexagonS motion estimation algorithm in H.264 [J].Journal of Computer Applications, 2014, 34(6): 1699-1705.

[12]周韜,張茂軍,劉少華,等.H.264/AVC中基于全零塊的預(yù)測模式選擇[J].計算機工程,2009,35(24):232-235.

Zhou Tao, Zhang Maojun, Liu Shaohua, et al. Prediction mode selection based on all-zero block in H.264/AVC[J].Computer Engineering, 2009,35(24):232-235.

[13]葉仕通.自適應(yīng)選擇編碼模式的快速運動估計算法[J].計算機工程與科學(xué),2014,36(9):1780-1787.

Ye Shitong. A fast motion estimation algorithm with adaptive selecting encoding mode.[J]. Computer Engineering & Science, 2014, 36(9):1780-1787.

[14]Lam Chi-wai, Po Lai-man, Cheung Chun-ho. A novel kite-cross-diamond search algorithm for fast block matching motion estimation[C]// Proceedings of 2004 IEEE International Symposium on Circuits and Systems. Vancouver, Canada: IEEE Press, 2004: III729-III732.

[15]丁燕,宋雪樺,閆述,等.基于快速運動估計UMHexagonS算法的改進[J].數(shù)據(jù)采集與處理,2009,24(5):660-663.

Ding Yan, Song Xuehua, Yan Shu, et al. Improvements of UMHexagonS algorithm based on fast motion estimation[J]. Journal of Data Acquisition and Processing, 2009, 24(5):660-663.

[16]楊虎,潘紅兵,何書專,等.H.264視頻壓縮快速運動估計算法UMHexagons改進[J].計算機工程與設(shè)計,2013,34(2):550-555.

Yang Hu, Pan Hongbing, He Shuzhuan, et al. Improvements on fast motion estimation strategy based on UMHexagons for H.264[J]. Computer Engineering and Design, 2013,34(2):550-555.

Optimization and Improvement of Motion Estimation UMHexagonS Algorithm in H.264

Ren Keqiang , Lin Fangming

(School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, 341000, China)

Aiming at the existing problem of UMHexagonS algorithm in H.264, an improved fast motion estimation algorithm is proposed. The algorithm enhances the coding efficiency by optimizing the detection sequence of initial prediction motion vector(MV) according to the possibility of initial prediction MV becoming the best point, then an improved 5×5 spiral global search pattern is designed to reduce the search points of pattern, and an early termination technique for sub-macro block is proposed for further reducing the computation of motion estimation. The experimental results show that, with only negligible change of encoding performance, the improved algorithm can effectively reduce the motion estimation time and enhance the coding efficiency, and it can suit for video sequence of different motion intensities.

motion estimation; 5×5 spiral global search; initial prediction ; early termination technique

江西省教育廳青年科學(xué)基金(GJJ11132)資助項目；江西省研究生創(chuàng)新基金(YC2013-S199)資助項目。

2015-05-06；

2015-12-17

TN919.81

A

任克強(1959-)，男，教授，研究方向：信息隱藏、視頻信號處理，E-mail：renke qiang@21cn.com。

林芳明(1989-)，男，碩士研究生，研究方向：視頻壓縮編碼。