熊承義,白 云

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

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

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

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

1 UM HexagonS算法

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

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

Step1 起始搜索點(diǎn)預(yù)測(cè).

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

Step2 非對(duì)稱十字型搜索.

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

Step3 非均勻多層次六邊形格點(diǎn)搜索.

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

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

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

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

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

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

2.1 運(yùn)動(dòng)估計(jì)的成本大小與方向分布

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

基于以上定義,將運(yùn)動(dòng)估計(jì)成本分布分為以下幾種情形.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

表1 測(cè)試條件Tab.1 Testing conditions

表2 測(cè)試序列描述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 各種不同測(cè)試序列的性能比較Tab.10 R-DPeformanceunderdifferentsequence

4 結(jié)語

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

[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)十字搜索模式運(yùn)動(dòng)估計(jì)法[J].通信學(xué)報(bào),2005,26(8):117-121.

[9] 李 榮,張其善,楊東凱.基于方向自適應(yīng)菱形搜索的運(yùn)動(dòng)估計(jì)算法[J].北京航空航天大學(xué)學(xué)報(bào),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.