基于方向信息的快速整像素運動估計優(yōu)化

熊承義,白 云

(中南民族大學(xué)電子信息工程學(xué)院,武漢430074)

在視頻編碼應(yīng)用,如H.264等視頻編碼標(biāo)準(zhǔn)中,基于塊匹配的運動估計和運動補(bǔ)償能有效去除序列圖像的幀間冗余,使得視頻傳輸?shù)谋忍財?shù)大為減少[1],因而成為視頻壓縮編碼標(biāo)準(zhǔn)的關(guān)鍵部分.全搜索 (FS)算法通過對搜索區(qū)域內(nèi)的所有點進(jìn)行匹配運算,從而達(dá)到全局最佳估計,但是其搜索點數(shù)過多,運算量非常大,成為視頻編碼實時實現(xiàn)的主要瓶頸.多年來,運動估計的快速實現(xiàn)一直成為許多研究者關(guān)注和研究的重要問題.

目前,典型的基于塊匹配的快速運動估計算法主要有:新3步搜索法(N TSS)[2],4步搜索法(FSS)[3],基于塊的梯度下降搜索法(BBGDS)[4],十字搜索法(DS)[5],六邊形搜索法(HEXBS)[6]等.這些算法通過限制搜索位置的數(shù)目來減少計算量.在相對小的搜索范圍和圖像尺寸時,這些算法可以達(dá)到比較好的效果,但是在搜索步長較大,以及在處理某些大的圖像尺寸和較大的搜索范圍時,以上快速搜索算法很容易落入局部最小點,從而嚴(yán)重影響編碼效率.非對稱十字型多層次六邊形格點搜索方法(UM H exagonS)[7],結(jié)合采用多層次和多模板的搜索技術(shù),在保持較好的率失真性能的同時,它的運算量相對于快速全搜索算法可節(jié)省90%以上,因此有效實現(xiàn)運動估計的快速計算.UM HexagonS算法目前已被H.264/AVC標(biāo)準(zhǔn)正式采用.

為了進(jìn)一步有效地減少運動估計時間,本文在分析運動估計成本的統(tǒng)計分布特征的基礎(chǔ)上,提出了一種改進(jìn)的UM HexagonS算法.通過探索和利用在非對稱十字型搜索階段的運動估計成本的大小及方向信息,自適應(yīng)地調(diào)整原始25點正方形搜索和16點非均勻多層次六邊形格點搜索的搜索區(qū)域,有效減少搜索點數(shù),節(jié)省運動估計的時間.大量實驗結(jié)果表明,改進(jìn)的UM H exagonS算法在大大降低編碼時間的同時,能有效保持原算法的率失真性能.

1 UM HexagonS算法

UM HexagonS算法的基本思想是采用多層次多種形狀的模板進(jìn)行宏塊匹配,同時利用時空相關(guān)性進(jìn)行運動矢量場的預(yù)測,搜索時針對不同的運動類型采用了大范圍粗搜索混合模板、細(xì)搜索中六邊形模板和精細(xì)搜索十字模板完成搜索[7].該算法率失真性能明顯優(yōu)于其它快速算法,能較好地滿足低碼率和實時性要求.

UM HexagonS算法的示意圖見圖1,其實現(xiàn)的4個主要步驟包括.

Step1 起始搜索點預(yù)測.

起始搜索點預(yù)測是依據(jù)待估計塊與周邊塊的時空相關(guān)性,利用周邊已編碼塊的運動矢量進(jìn)行當(dāng)前塊運動矢量的起始點預(yù)測.預(yù)測模式有4種:中值預(yù)測、上層預(yù)測、對應(yīng)塊預(yù)測、相鄰參考幀預(yù)測.

Step2 非對稱十字型搜索.

由于自然界圖像序列在水平方向的運動比垂直方向的運動更加普遍,因此非對稱十字型搜索可以比較精確的預(yù)測到最佳的運動矢量[8].如圖1中Step 2,非對稱十字型搜索使用一個水平搜索范圍為垂直搜索范圍2倍的非對稱十字型搜索模式,獲得當(dāng)前塊運動矢量的最佳預(yù)測起點.

Step3 非均勻多層次六邊形格點搜索.

此步分為2個子步驟:如圖1中的Step 3-1,以當(dāng)前最優(yōu)點為中心,在范圍為-2到2的方形區(qū)域進(jìn)行25點的正方形搜索;如圖1中的Step 3-2,進(jìn)行16點非均勻多層次六邊形格點搜索.通過利用伸縮系數(shù)對六邊形進(jìn)行擴(kuò)展,可以更好地處理大范圍和不規(guī)則的運動,避免過早的落入局部最優(yōu)[9].

Step4 擴(kuò)展的六邊形搜索.

此步分為2個子步驟:如圖1中的Step 4-1,以當(dāng)前最佳點為中心,進(jìn)行六邊形搜索,直至最佳點在六邊形的中心時為止;如圖1中的Step 4-2,以當(dāng)前最佳點為中心,進(jìn)行十字型搜索,直至最佳點在十字型模板的中心時為止.

2 UM H exagonS算法的改進(jìn)

原始UM H exagonS算法中的Step 3采用了25點的正方形搜索和16點的非均勻多層次六邊形格點搜索,其搜索過程并未充分考慮運動估計成本的統(tǒng)計分布特性,因此存在較大的搜索冗余.本文通過分析和探索運動估計成本存在的大小和方向信息,提出一種自適應(yīng)地搜索技術(shù),有效減少Step 3中的搜索點數(shù),從而實現(xiàn)進(jìn)一步減少運動估計的時間.

圖1 UM HexagonS算法Fig.1 UM HexagonS algo rithm

2.1 運動估計的成本大小與方向分布

將UM HexagonS算法中非對稱十字型搜索的預(yù)測起始點坐標(biāo)記為(cen tra l-x,cen tra l-y);將水平方向搜索獲得的匹配點的坐標(biāo)記為(horizon ta lx,horizon ta l-y),最小運動估計成本記為(m costhorizon ta l);將垂直方向搜索獲得的匹配點的坐標(biāo)記為(vertica l-x,vertica l-y),最小運動估計成本記為(m cost-vertica l).將水平與垂直方向上匹配點的運動估計成本進(jìn)行比較,最小者為當(dāng)前的最佳匹配點,其坐標(biāo)記為(best-x,best-y),運動估計成本記為(m cost).horizon ta l為水平方向上與預(yù)測起始點的偏移量,vertica l為垂直方向上與預(yù)測起始點的偏移量,即:

基于以上定義,將運動估計成本分布分為以下幾種情形.

當(dāng)前的最佳匹配點為水平方向上的匹配點.水平方向上搜索獲得的匹配點在X的正半軸,見圖2中的實心三角▲;垂直方向上搜索獲得的匹配點在Y的正半軸,見圖2中陰影三角.此時,運動矢量落在第2象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為水平方向上的匹配點.水平方向上搜索獲得的匹配點在X的負(fù)半軸,垂直方向上搜索獲得的匹配點在Y的正半軸.此時,運動矢量落在第1象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為水平方向上的匹配點.水平方向上搜索獲得的匹配點在X的負(fù)半軸,垂直方向上搜索獲得的匹配點在Y的負(fù)半軸.此時,運動矢量落在第4象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為水平方向上的匹配點.水平方向上搜索獲得的匹配點在X的正半軸,垂直方向上搜索獲得的匹配點在Y的負(fù)半軸.此時,運動矢量落在第3象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為垂直方向上的匹配點.水平方向上搜索獲得的匹配點在X的正半軸,垂直方向上搜索獲得的匹配點在Y的正半軸.此時,運動矢量落在第4象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為垂直方向上的匹配點.水平方向上搜索獲得的匹配點在X的負(fù)半軸,垂直方向上搜索獲得的匹配點在Y的正半軸.此時,運動矢量落在第3象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為垂直方向上的匹配點.水平方向上搜索獲得的匹配點在X的負(fù)半軸,垂直方向上搜索獲得的匹配點在Y的負(fù)半軸.此時,運動矢量落在第2象限內(nèi)的概率最大.

當(dāng)前的最佳匹配點為垂直方向上的匹配點.水平方向上搜索獲得的匹配點在X的正半軸,垂直方向上搜索獲得的匹配點在Y的負(fù)半軸.此時,運動矢量落在第1象限內(nèi)的概率最大.

2.2 25點正方形搜索改進(jìn)

運動矢量有超過80%的概率是落在以(0,0)為中心,半徑為2的圓內(nèi)[10].這也是UM H exagonS算法要在Step 3-1中采用25點正方形搜索的基本原因.在UM HexagonS算法中Step 3-1中以最佳預(yù)測起始點為中心,進(jìn)行25點的正方形搜索.本文提出的算法是根據(jù)非對稱十字型搜索獲得的運動估計成本的不同分布情況自適應(yīng)選擇搜索區(qū)域.圖3為在mcost=mcost-horizon ta l,horizon ta l＞0,vertica l＞0的條件下的搜索區(qū)域自適應(yīng)選擇示意圖.圖3中實心三角▲為經(jīng)過非對稱十字型搜索獲得當(dāng)前最佳預(yù)測起始點,為垂直方向預(yù)測的最佳點.由于此階段的運動矢量落在第2象限內(nèi)的概率最大,因此調(diào)整運動矢量搜索為只對圖中的7個空心圓對應(yīng)點進(jìn)行搜索匹配.由于避免了搜索其它實心圓●對應(yīng)點,因此有效減少了運動估計的時間.在運動估計成本分布在(1)～ (8)情況下的搜索示意圖分別見圖4中(a)～(h).

圖2 運動矢量分布區(qū)域示意圖Fig.2 M E vecto r distribu tion location

2.3 16點非均勻多層次六邊形格點搜索的改進(jìn)

在UM HexagonS算法中,Step 3-2以最佳預(yù)測起始點為中心,進(jìn)行多層次六邊形格點搜索.同樣基于以上在非對稱十字型搜索階段得到的運動估計成本分布的不同,提出自適應(yīng)地選取對應(yīng)六邊形搜索點的方法如下.圖5給出了在mcost=mcosthorizon ta l,horizon ta l＞0,vertica l＞0的條件下的六邊形搜索點選擇示意圖.圖中的實心三角▲為Step 2非對稱十字型搜索獲得最佳預(yù)測點,陰影三角為垂直方向預(yù)測的最佳點.此步搜索也調(diào)整為只對圖5中4個空心矩形點 對應(yīng)點進(jìn)行搜索.同樣由于避免搜索其它實心矩形點對應(yīng)點,從而有效的減少了運動估計的時間.圖6中(a)～ (h)分別給出了在運動估計成本在(1)～ (8)分布情況下多層次六邊形格點第一層的搜索點選擇,其它擴(kuò)展層同樣按此規(guī)律進(jìn)行搜索.

圖3 正方形搜索區(qū)域的自適應(yīng)選擇示意圖Fig.3 Search po intso f square search

圖4 不同運動估計成本分布情況下正方形搜索區(qū)域選擇示意圖Fig.4 Search po intso f square search under differentM E cost distribution

圖5 非均勻多層次六邊形格點搜索點選擇示意圖Fig.5 Search po in tsofm u lti-hexagon-grid search

圖6 不同運動估計成本分布情況下非均勻多層次六邊形格點搜索點選擇示意圖Fig.6 The search po in tsofm u lti-hexagon-g rid search under differentM E cost distribution

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

為了驗證本文算法的有效性,基于H.264參考代碼JM 12.2對該算法的性能進(jìn)行了大量的比較實驗.實驗采用的主要測試條件見表1,其它參數(shù)的設(shè)置采用JM 12.2版本中的默認(rèn)值.采用的測試序列描述見表2.本文提出的算法在選取Q P分別為8,18,28,38下進(jìn)行測試,并與UM H exagonS算法進(jìn)行比較.為了避免PC運行不穩(wěn)定的影響[11],本文將同一個序列,在相同條件下,進(jìn)行20次實驗,取其平均的整像素運動估計的時間減少的百分比來比較速度,采用信噪比下降的大小和碼率上升的百分比來比較算法的率失真性能.

表3～8給出了在不同尺寸、格式的測試序列的條件下本文算法與原始UM HexagonS算法的性能比較結(jié)果.從表9比較結(jié)果可見:不同的Q P值下均能較好的保證原有UM HexagonS算法的碼率失真性能.表10結(jié)果表明:不同測試序列在Q P為8,18,28,38時,運動估計時間平均節(jié)省32.85%,PSNR平均上升約0.002dB,碼率平均增加約為0.25%.測試結(jié)果表明,對于不同測試序列其運動估計時間的減少幅度是不同的,主要原因在于視頻場景運動變化的激烈程度不同所造成的.其中對運動復(fù)雜的序列M ob ile有更好的效果:運動估計時間平均下降了42.36%.由于M ob ile運動場景的相對激烈導(dǎo)致了運動估計成本門限判斷一直不符合提前終止條件,因此幾乎執(zhí)行了改進(jìn)后算法中的所有步驟,運動時間也就下降更多.

由以上實驗結(jié)果表明,在不同的Q P、圖像尺寸、運動復(fù)雜度的情況下,改進(jìn)后的算法都能夠很好地適應(yīng),并保持了原始UM H exagonS算法的率失真和碼率等性能.

表1 測試條件Tab.1 Testing conditions

表2 測試序列描述Tab.2 Descip tion o f test video sequences

表3 Silen t序列在不同QP值下的性能Tab.3 R-D Pefo rm ance under d ifferen tQP(Silen t)

表4 N ew s序列在不同QP值下的性能Tab.4 R-D Pefo rm ance under differen tQP(N ew s)

表5 Fo rem an序列在不同QP值下的性能Tab.5 R-D Pefo rm ance under d ifferen tQP(Fo rem an)

表6 Paris序列在不同QP值下的性能Tab.6 R-DPeformanceunderdifferentQP(Paris)

表7 Mobile序列在不同QP值下的性能Tab.7 R-DPeformanceunderdifferentQP(Mobile)

表8 Tempete序列在不同QP值下的性能Tab.8 R-DPeformanceunderdifferentQP(Tempete)

表9不同QP值下的性能比較Tab.9 R-DPeformanceunderdifferentQP

表10 各種不同測試序列的性能比較Tab.10 R-DPeformanceunderdifferentsequence

4 結(jié)語

提出了一種改進(jìn)的UMHexagonS算法.基于運動估計的成本大小和方向性信息,自適應(yīng)地調(diào)整原算法中的25點正方形搜索和16點非均勻多層次六邊形格點搜索的搜索區(qū)域,有效地實現(xiàn)減少運動估計的搜索點數(shù).測試結(jié)果表明,對于不同運動變化的序列以及在選取不同QP時,改進(jìn)后的算法在保證率失真性能的同時,能節(jié)省大約23%～42%的整像素運動估計時間.

[1] W uegand T,Su llivan G.O verview o f the H.264/AVC video cod ing standard[J]. IEEE T ransactions on C ircu its and System fo r V ideo Techno logy,2003,13(7):560-576.

[2] L iR,Zeng B,L iou M L.A new th ree-step search algo rithm fo r b lock m o tion estim ation[J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,1994,4(4):438-442.

[3] Po LM,M aW C.A novel fou r-step search algo rithm fo r fast b lock m atch ing[J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,1996,6(3):313-317.

[4] L iu L K,Feig E.A b lock based g radien t descen t search algo rithm fo r b lockm o tion estim ation in video cod ing[J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,1996,6(4):419-422.

[5] Zhu S,M a K K.A new d iam ond search algo rithm fo r fast b lock m atch ing m o tion estim ation[J]. IEEE T rans Im age Processing,2000,9(2):287-290.

[6] Zhu C,L in X,Chau L.Hexagon-based search pattern fo r fast b lock m o tion estim ation [J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,2002,12(5):349-355.

[7] Zhibo C H,Peng Z H,Yun H.Fast in teger pel and fractionalpelm o tion estim ation in fo r JV T[A].Jo in t V ideo Team (JV T)o f ISO/IEC M PEG&ITU-T VCEG,Aw aji,2002.

[8] 夏金祥,黃順吉.基于VOP的塊特性的自適應(yīng)十字搜索模式運動估計法[J].通信學(xué)報,2005,26(8):117-121.

[9] 李 榮,張其善,楊東凱.基于方向自適應(yīng)菱形搜索的運動估計算法[J].北京航空航天大學(xué)學(xué)報,2008,34(9):1065-1069.

[10] L in C C,L in Y,H sieh H J.M u lti-d irection search algo rithm fo r b lock m o tion estim ation in H.264/AVC[J]. IEEE T rans Im age Processing,2009,3(2):88-99.

[11] Xu X Z,He Y.Im p rovem en tson fastm o tion estim ation strategy fo r H.264/AVC[J].IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,2008,18(3):285-293.