劉學(xué)謙，張 濤，王 贊

(天津大學(xué) 電子信息工程學(xué)院，天津300072)

責(zé)任編輯:時(shí) 雯

由JVT制定的最新視頻編碼標(biāo)準(zhǔn)H.264/AVC[1]，因其采用了很多新技術(shù)、新方法，特別是幀間預(yù)測(cè)中的可變化尺寸塊運(yùn)動(dòng)估計(jì)、1/4像素精度的運(yùn)動(dòng)估計(jì)、多參考幀的使用，所以其比以往的視頻標(biāo)準(zhǔn)有更高的編碼質(zhì)量，同時(shí)也有更高的復(fù)雜性。運(yùn)動(dòng)估計(jì)所需要的時(shí)間占整個(gè)編碼器編碼時(shí)間的60%～80%[2]。為了提高編碼速度，研究運(yùn)動(dòng)估計(jì)快速算法，也非常必要。

近年來(lái)，各國(guó)學(xué)者提出多種運(yùn)動(dòng)估計(jì)的快速算法，在保證編碼質(zhì)量基本不變的前提下，提高運(yùn)動(dòng)估計(jì)的效率。比如，三步法(TSS)[3]、四步法(FSS)[4]、六邊形搜索法(HEXBS)[5]、鉆石搜索法(DS)[6]、改進(jìn)的預(yù)測(cè)式區(qū)域搜索算法(EPZS)[7]、非對(duì)稱十字型多層次六邊形格點(diǎn)搜索(UMHexagonS)算法[2]。

本文基于UMHexagonS算法，根據(jù)運(yùn)動(dòng)情況，使用動(dòng)態(tài)搜索窗口以及自適應(yīng)的搜索模板，在圖像質(zhì)量和碼率沒有太大變化的情況下，降低了算法的復(fù)雜度，大大減少了運(yùn)動(dòng)估計(jì)的時(shí)間。

1 UMHexagonS算法描述

UMHexagonS搜索算法主要包括4個(gè)步驟[2]:

1)非對(duì)稱的十字形搜索;

2)5×5小矩形搜索;

3)非均勻多層次六邊形搜索;

4)擴(kuò)展的六邊形搜索。

算法流程如圖1所示。

圖1 UMHexagonS搜索算法的步驟

在開始搜索之前，起始搜索點(diǎn)要根據(jù)當(dāng)前塊的運(yùn)動(dòng)情況，在原點(diǎn)預(yù)測(cè)值、中值預(yù)測(cè)值(MVpred_MP)、上層預(yù)測(cè)值(MVpred_UP)、相鄰參考幀預(yù)測(cè)值(MVpred_NRP)和時(shí)域?qū)?yīng)塊預(yù)測(cè)值(MVpred_CP)這5種預(yù)測(cè)模式中來(lái)進(jìn)行選擇。搜索范圍的大小通過配置文件的search_range參數(shù)設(shè)置:search_range=16/32/48/64。在搜索的同時(shí)，UMHexagonS算法中還設(shè)定了提前終止搜索和跳轉(zhuǎn)搜索步驟的閾值，這就大大減少搜索的點(diǎn)數(shù)，節(jié)省了搜索時(shí)間。

2 UMHexagonS算法的優(yōu)化

2.1 動(dòng)態(tài)的搜索范圍

最新的編碼標(biāo)準(zhǔn)中，分塊模式不再是單一的16×16。比如H.264/AVC標(biāo)準(zhǔn)有7種分塊模式，最大塊為16×16，最小塊4×4。雖然已經(jīng)引入了動(dòng)態(tài)搜索范圍[8]，但是并沒有考慮到不同模式，比如會(huì)對(duì)4×4的塊增加額外的搜索。因此為了進(jìn)一步優(yōu)化搜索范圍，可以利用MVpred_MP和MVpred_UP來(lái)針對(duì)非16×16(該模式?jīng)]有MVpred_UP)模式，再計(jì)算一個(gè)新的搜索范圍[9]，取新的搜索范圍與以前搜索范圍中的最小值作為最后的搜索范圍。動(dòng)態(tài)搜索窗口的計(jì)算方法如圖2所示。

圖2 動(dòng)態(tài)搜索窗口計(jì)算方法

A是從配置文件獲得的search_range;B是計(jì)算得出的新的動(dòng)態(tài)搜索范圍(new_search_range)，由C和D構(gòu)成;C是固定的搜索范圍。D是動(dòng)態(tài)范圍。其中，MVpred_UPX，MVpred_UPY和MVpred_MPX，MVpred_MPY分 別 是MVpred_UP，MVpred_MP的X和Y分量。C，D兩個(gè)搜索范圍的計(jì)算公式定義如下

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

2.2.1 十字模板的優(yōu)化

原始的十字搜索模板要搜索24個(gè)點(diǎn)，雖然是不對(duì)稱的模板，但在某些情況下垂直方向上發(fā)現(xiàn)最優(yōu)點(diǎn)的可能性要比水平方向大，如果使用同一個(gè)模板，不利于更快找到最優(yōu)點(diǎn)。可以根據(jù)當(dāng)前的預(yù)測(cè)運(yùn)動(dòng)矢量MVpred的X方向與Y方向的不同，選擇以下不同的模板，如圖3所示。

模板是不對(duì)稱的小十字模板，一個(gè)步長(zhǎng)是2，一個(gè)步長(zhǎng)是1。如果abs(MVpred_x)＜abs(MVpred_y)選用模板2;否則選用模板1。搜索方式是:以當(dāng)前點(diǎn)為中心，搜索周圍四個(gè)點(diǎn)，直到最優(yōu)點(diǎn)為中心點(diǎn)，停止搜索。實(shí)驗(yàn)結(jié)果顯示，采用這種方法，平均每次搜索不到5個(gè)點(diǎn)。

圖3 不對(duì)稱小十字模板

2.2.2 5×5小矩形搜索的改進(jìn)

由于運(yùn)動(dòng)矢量的最優(yōu)點(diǎn)在13點(diǎn)的菱形和25點(diǎn)的小矩形出現(xiàn)的概率分布是80.7%和82.6%[10]，所以本文采用了13點(diǎn)菱形來(lái)替代25點(diǎn)的小矩形，如圖4所示。

圖4 13點(diǎn)菱形和25點(diǎn)小矩形

2.3 多層次多角度自適應(yīng)模板

UMHexagonS中的非均勻多層次六邊形搜索，為了有效避免陷入局部最優(yōu)，每次需要檢測(cè)4×16個(gè)點(diǎn)。此步驟可以結(jié)合運(yùn)動(dòng)矢量分布的空間方向性[11]，并結(jié)合MVpred_MP來(lái)簡(jiǎn)化搜索模板的層數(shù)。具體方法如下:

1)當(dāng)Num_Big_Hexagon≥4時(shí)

如果Mv_Big_Hexagon≥12，則修改Num_Big_Hexagon=4;

如果8≤Mv_Big_Hexagon＜12，則修改Num_Big_Hexagon=3;

其他情況，則修改Num_Big_Hexagon=2。

2)當(dāng)3≤Num_Big_Hexagon＜4時(shí)

如果Mv_Big_Hexagon≥8，則修改Num_Big_Hexagon=3;

如果6≤Mv_Big_Hexagon＜8，則修改Num_Big_Hexagon=2;

其他情況，則修改Num_Big_Hexagon=1。

3)當(dāng)2≤Num_Big_Hexagon＜3時(shí)

如果Mv_Big_Hexagon≥6，則修改Num_Big_Hexagon=2;

其他情況，則修改Num_Big_Hexagon=1。

4)當(dāng)Num_Big_Hexagon≤1時(shí)

Num_Big_Hexagon=1。

其中，Mv_Big_Hexagon是MVpred_MP中X方向和Y方向的最大值;Num_Big_Hexagon為最后的搜索層次數(shù)，1即為圖5的單層，2即為在單層的基礎(chǔ)上，再向外擴(kuò)展一層，搜索點(diǎn)坐標(biāo)為單層的2倍，3層、4層以此類推;Num_Big_Hexagon=new_search_range/4。

經(jīng)過以上幾步搜索后，可以利用當(dāng)前獲得的最佳運(yùn)動(dòng)矢量與上一幀對(duì)應(yīng)位置塊的運(yùn)動(dòng)矢量的偏離方向，確定自適應(yīng)模板的搜索方向，既減少了搜索點(diǎn)數(shù)，又能準(zhǔn)確地避免陷入局部最優(yōu)。搜索方向的角度在第一/三象限，使用12，13，14，15，0，4，5，6，7，8十點(diǎn)構(gòu)成的模板;角度在第二/四象限，使用0，1，2，3，4，8，9，10，11，12十點(diǎn)構(gòu)成的模板;X軸方向，即X軸方向不為0，Y軸方向?yàn)?使用2，4，6，10，12，14六點(diǎn)構(gòu)成的模板;Y軸方向，使用1，5，0，1，7，8，9六點(diǎn)構(gòu)成的模板。模板的示意圖如圖5所示。

圖5 非均勻多層次六邊形搜索的單層模板

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

3.1 測(cè)試平臺(tái)和配置

本文采用H.264/AVC的JM11.0平臺(tái)進(jìn)行測(cè)試。實(shí)驗(yàn)所用計(jì)算機(jī)的硬件配置為:Intel(R)Core(TM)i5-2310@2.90 GHz，4 Gbyte內(nèi)存，操作系統(tǒng)為Windows XP SP3。為了更好地評(píng)價(jià)本文算法，實(shí)驗(yàn)選取幾組不同運(yùn)動(dòng)類型的、不同分辨率的標(biāo)準(zhǔn)測(cè)試序列，設(shè)定不同的搜索范圍，序列格式為YUV 420，編碼檔次為Baseline Profile。實(shí)驗(yàn)所用到的編碼參數(shù)及測(cè)試序列如表1所示。

3.2 測(cè)試結(jié)果和分析

對(duì)于運(yùn)動(dòng)估計(jì)搜索算法的復(fù)雜度，可以由搜索點(diǎn)的個(gè)數(shù)來(lái)評(píng)價(jià)。對(duì)于16×16大小的塊在搜索范圍為16時(shí)，UMHexagonS算法的搜索點(diǎn)個(gè)數(shù)至少為N1=step1+step2+step3+step4=25+24+64+10=123點(diǎn)，而本文改進(jìn)算法的搜索點(diǎn)個(gè)數(shù)至少為N2=step1+step2+step3+step4=5+12+6+10=34點(diǎn)。由上可知，本文的改進(jìn)算法能有效地降低搜索點(diǎn)個(gè)數(shù)，相應(yīng)地也極大地減少了運(yùn)動(dòng)估計(jì)時(shí)間，編碼時(shí)間也會(huì)減少，所以從理論上可以證明本文算法的有效性。

表1 實(shí)驗(yàn)用到的測(cè)試序列

測(cè)試中將本文改進(jìn)的算法與原有的UMHexagonS算法進(jìn)行了對(duì)比，實(shí)驗(yàn)數(shù)據(jù)如表2和表3所示，其中同一分辨率下的序列平均值就是統(tǒng)計(jì)表1中同一分辨率的序列測(cè)試結(jié)果的平均值作為最終測(cè)試結(jié)果。

表2 圖像運(yùn)動(dòng)緩慢的序列實(shí)驗(yàn)結(jié)果

表3 不同分辨率不同搜索范圍的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)主要是將本文算法和UMHexagonS算法在不同搜索范圍下的PSNR、碼率、編碼時(shí)間、運(yùn)動(dòng)估計(jì)時(shí)間等方面進(jìn)行了比較。從實(shí)驗(yàn)結(jié)果來(lái)看，本文算法的PSNR與UMHexagonS算法比幾乎相同，下降時(shí)的幅度也都在0.02 dB以內(nèi);本文算法的碼率與UMHexagonS算法比，幅度變化不大;從表2可以看出，本文算法在簡(jiǎn)化運(yùn)動(dòng)估計(jì)方面有很大的優(yōu)勢(shì)，特別是對(duì)圖像運(yùn)動(dòng)劇烈的序列，效果尤為明顯。一般情況下，本文算法在PSNR和碼率變化不大的同時(shí)，QCIF分辨率搜索范圍設(shè)置為32，平均可節(jié)省32.64%的運(yùn)動(dòng)估計(jì)時(shí)間;由表3可知，隨著搜索范圍的擴(kuò)大，本文算法在運(yùn)動(dòng)估計(jì)時(shí)間上優(yōu)勢(shì)就越明顯，有時(shí)都能節(jié)省47.05%。

4 小結(jié)

視頻編碼系統(tǒng)在有效提高編碼質(zhì)量的同時(shí)，也提高了其復(fù)雜性。本文對(duì)運(yùn)動(dòng)估計(jì)的UMHexagonS算法進(jìn)行了研究和分析，對(duì)不同搜索模式下的動(dòng)態(tài)搜索范圍進(jìn)行了改進(jìn)，用自適應(yīng)不對(duì)稱小十字模板替代原有的十字模板，用小菱形替代原有的小矩形搜索，又提出多層次多角度的自適應(yīng)六邊形模板，并對(duì)小菱形搜索進(jìn)行了簡(jiǎn)化，這在一定程度上減少了搜索點(diǎn)數(shù)。從實(shí)驗(yàn)結(jié)果可以看出，本文提出的新算法，在保證圖像質(zhì)量和碼率基本不變的前提下，編碼時(shí)間和運(yùn)動(dòng)估計(jì)時(shí)間都有不同程度的減少，特別是對(duì)運(yùn)動(dòng)較劇烈的序列有更好的效果，并且搜索范圍越大，本文算法在運(yùn)動(dòng)估計(jì)時(shí)間上的優(yōu)勢(shì)就越明顯。

[1]WIEGAND T，SULLIVAN G，LUTHRA A.Overview of the H.264/AVC video coding standard[J].IEEE Trans.Circuits and System for Video Technology，2003，13(7):560-576.

[2]CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integer-pel and fractionalpel motion estimation for H.264/AVC[J].Journal of Visual Communication and Image Representation，2006，17(2):264-290.

[3]KOGA T，IINUMA K，HIRANO A，et al.Motion compensated interframe coding for video conferencing[EB/OL].[2013-05-02].http://citeseer.uark.edu:8080/citeseerx/showciting;jsessionid=228570CE9CB7B FDA1E15A138A877B06C?cid=20547.

[4]PO L，MA W.A novel four-step search algorithm for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology，1996，6(3):313-317.

[5]ZHU C，LIN X，CHAU L.Hexagon-based search patten for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology，2002，12(5):349-355.

[6]ZHU Shan，MA Kaikuang.A new diamond search algorithm for fast block matching motion estimation[J].IEEE Trans.Image Processing，1997，9(2):292-296.

[7]TOURAPIS A，AU O，LIOU M.New results on zonal based motion estimation algorithms-advanced predictive diamond zonal search[C]//Proc.ISCAS 2001.Sydney，NSW:IEEE Press，2001:183-186.

[8]XU Xiaozhong，HE Yun.Modification of dynamic search range for JVT[S].2005.

[9]CHEN Z，SONG Y，IKENAGA T，et al.A dynamic search range algorithm for variable block size motion estimation in H.264/AVC[C]//Proc.6th International Conference on Information，Communications &Signal Processing.Singapore:IEEE Press，2007:1-4.

[10]LIU Haihua，XIE Changsheng，LEI Yi.An unsymmetrical dual cross search algorithm for fast block-matching motion estimation[C]//Proc.ICTAI 2005.Hong Kong:IEEE Press，2005:613-620.

[11]TOURAPIS A，AU O，LIOU M.Predictive motion vector field adaptive search technique(PMVFAST)enhancing block based motion estimation[C]//Proc.VCIP 2001.San Josc，CA:IEEE Press，2001:24-26.