基于方向自適應(yīng)模板的UMHexagonS算法改進(jìn)*

趙子武，鄒雪妹，程 飛，魏小文

（上海大學(xué) 通信與信息工程學(xué)院，上海 200072）

責(zé)任編輯:孫 卓

1 引言

在視頻壓縮編碼中，時(shí)域冗余主要通過運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償來消除，它也是整個(gè)編碼器比較耗時(shí)的部分。針對(duì)運(yùn)動(dòng)估計(jì)最先提出的全搜索算法[1]:在參考幀預(yù)先定義好的搜索區(qū)域中，將當(dāng)前幀與搜索區(qū)域中所有的候選塊進(jìn)行比較，最小匹配誤差的塊為最優(yōu)塊。全搜索法（FS）能夠獲得非常高的搜索精度，但運(yùn)算量十分巨大，之后的運(yùn)動(dòng)搜索算法都以在不影響精度的同時(shí)減少計(jì)算量為目標(biāo)。 三步搜索法（TSS）、兩維對(duì)數(shù)法（LOGS）、十字型搜索法（CS）、四步搜索法（FSS）、梯度下降法（BBGDS）[2]、鉆石搜索法（DS）[3]和六邊形搜索法（HEXBS）[4]等的搜索速度比全搜索有了提高，但它們沒有充分考慮時(shí)間和空間上相鄰塊的信息，搜索時(shí)容易陷入局部最小值，從而導(dǎo)致匹配精度差。之后提出的運(yùn)動(dòng)估計(jì)算法主要集中于以下幾個(gè)方面:充分考慮時(shí)間和空間上的相鄰宏塊信息，針對(duì)視頻中靜止宏塊較多的情況提出自適應(yīng)提前終止策略，改變搜索模板，根據(jù)初始預(yù)測運(yùn)動(dòng)矢量自適應(yīng)修改搜索區(qū)域大小等。例如MPEG-4標(biāo)準(zhǔn)第7部分已經(jīng)采用的MVFAST[5]和改進(jìn)算法 PMVFAST[6]。

基于上述研究，H.264標(biāo)準(zhǔn)采用了UMHexagonS算法[7]，該算法能同時(shí)適應(yīng)小運(yùn)動(dòng)和大運(yùn)動(dòng)情況下的運(yùn)動(dòng)估計(jì)，并能得到與全搜索基本一樣的精度和率失真特性，同時(shí)最多能比全搜索節(jié)省90%的時(shí)間。因此，H.264/AVC標(biāo)準(zhǔn)采納了該運(yùn)動(dòng)估計(jì)算法。文獻(xiàn)[8]中UMHexagonS算法改變了搜索模板，一定程度上減少了運(yùn)動(dòng)估計(jì)時(shí)間。

2 UMHexagonS算法

非對(duì)稱十字型多層次六邊形格點(diǎn)搜索算法（UMH-exagonS）搜索步驟[1]如下:

1）初始搜索點(diǎn)預(yù)測。取對(duì)應(yīng)費(fèi)用函數(shù)最小的點(diǎn)為初始搜索點(diǎn)（預(yù)測搜索法包括針對(duì)空間相關(guān)性的中值預(yù)測、上層預(yù)測、前一幀對(duì)應(yīng)塊預(yù)測和鄰近參考幀預(yù)測），然后判斷是否提前截止。

2）非對(duì)稱十字型搜索。由于一般物體水平方向運(yùn)動(dòng)要比垂直方向運(yùn)動(dòng)劇烈，所以將垂直方向設(shè)置為水平方向搜索范圍的一半，判斷是否提前終止搜索。

3）非均勻多層次六邊形格點(diǎn)搜索分步進(jìn)行5×5小矩形窗全搜索和擴(kuò)展的多層次六邊形格點(diǎn)搜索，同時(shí)也要判斷是否提前終止搜索。

4）采用擴(kuò)展多層次六邊形格點(diǎn)搜索和小菱形搜索模式循環(huán)進(jìn)行搜索，持續(xù)搜索到最小費(fèi)用函數(shù)值的點(diǎn)位于菱形搜索窗口的中心點(diǎn)為止。

該算法充分考慮了空間和時(shí)間的相關(guān)性以及H.264采用的宏塊劃分技術(shù)中不同尺寸塊的運(yùn)動(dòng)矢量相關(guān)性，進(jìn)行初始點(diǎn)預(yù)測，針對(duì)運(yùn)動(dòng)幅度的大小采用自適應(yīng)的六邊形格點(diǎn)搜索和菱形搜索，具有很強(qiáng)的內(nèi)容適應(yīng)性，同時(shí)應(yīng)用提前終止策略避免了不必要的運(yùn)算，這些都取得了很好的效果。

3 改進(jìn)UMHexagonS算法

要保證同樣的編碼效果，同時(shí)進(jìn)一步減小UMHexagonS算法的運(yùn)算量，筆者提出了改進(jìn)方法，主要使初始運(yùn)動(dòng)矢量更準(zhǔn)確，減少5×5全搜索點(diǎn)數(shù)，通過精確的運(yùn)動(dòng)矢量確定搜索方向并改用擴(kuò)展的梯形格點(diǎn)進(jìn)行搜索。

3.1 初始運(yùn)動(dòng)矢量改進(jìn)

在原算法4種初始搜索點(diǎn)預(yù)測模式基礎(chǔ)上提出第5種預(yù)測模式:當(dāng)前塊的左、上、右上塊的運(yùn)動(dòng)矢量分別為 MV1，MV2，MV3，參考幀同位置塊的運(yùn)動(dòng)矢量為 MV′1，MV′2，MV′3。

1）中值預(yù)測 。 PMV1=mediam（MV1，MV2，MV3），PMV2=mediam（MV′1，MV′2，MV′3），取兩者中的最小SAD作為初始MV。

2）PMV=mediam（MV1，MV2，MV3，MV′1，MV′2，MV′3）。

3）Weighted 預(yù)測。PMV1=0.375（MV1+MV2）+0.25MV3，PMV2=0.375（MV′1+MV′2）+0.25MV′3，取兩者中的最小SAD做為初始MV。

對(duì)上述3種方法進(jìn)行實(shí)驗(yàn)測試證明第3種方法比較好，則本算法采用Weighted預(yù)測。

3.2 5×5全搜索改進(jìn)

5×5模式因?yàn)椴捎昧巳阉髂Ｊ剑孕枰?jì)算25個(gè)搜索點(diǎn)，運(yùn)算量相對(duì)較大。在文獻(xiàn)[8]中，筆者對(duì)常用視頻序列的運(yùn)動(dòng)矢量做了詳細(xì)的統(tǒng)計(jì)分析，發(fā)現(xiàn)運(yùn)動(dòng)矢量大部分落于[-2，2]區(qū)域中，且以不同比例集中分布在中心附近的特定區(qū)域內(nèi)。如圖1所示，有大約81.8%的運(yùn)動(dòng)矢量分布在中心附近范圍±2的正方形區(qū)域內(nèi)（25個(gè)點(diǎn)），大約77.52%的運(yùn)動(dòng)矢量分布在中心附近范圍±2的菱形區(qū)域內(nèi)（13個(gè)點(diǎn)），大約74.76%的運(yùn)動(dòng)矢量集中分布在中心附近范圍±2的十字形區(qū)域內(nèi)（9個(gè)點(diǎn)），而且匹配點(diǎn)在中心點(diǎn)的概率最高，其次為中心點(diǎn)上、下、左、右4個(gè)點(diǎn)，而在周圍右上、左上、右下、左下對(duì)角點(diǎn)概率相對(duì)較小。本算法參考以上研究結(jié)果，在基本保持搜索精度的情況下，通過采用六邊形、八邊形或大小菱形相結(jié)合等方法進(jìn)行比較實(shí)驗(yàn)測試后共采用17個(gè)點(diǎn)（如圖2中的小三角形）代替5×5全搜索（如圖2中的小三角形和小圓點(diǎn)）模式25個(gè)點(diǎn)，減少了32%的運(yùn)算量。

3.3 六邊形格點(diǎn)搜索改進(jìn)

首先根據(jù)3.1節(jié)中得到的最優(yōu)初始運(yùn)動(dòng)矢量（MVx，MVy）計(jì)算 MvRatio=MVx/MVy，根據(jù) MvRatio判斷運(yùn)動(dòng)矢量所在的區(qū)域，采用可變搜索模板進(jìn)行搜索從而減少搜索點(diǎn)。 比如（MVx，MVy）=（1，2），則 MvRatio=0.5，用不斷擴(kuò)大搜索模板搜索第 1，2 象限；（MVx，MVy）=（-2，1），則用不斷擴(kuò)大的搜索模板搜索第2，3象限。在進(jìn)行搜索模板的選擇時(shí)，對(duì)半六邊形、三角形、梯形和矩形等模板進(jìn)行實(shí)驗(yàn)測試，在考慮搜索精度和時(shí)間的情況下，最終選擇梯形模板。非對(duì)稱六邊形要搜索16個(gè)點(diǎn)，而本算法的梯形只需搜索7個(gè)點(diǎn)，在保證搜索質(zhì)量的同時(shí)能減少56.25%的運(yùn)算量。圖3為改進(jìn)UMHexagonS算法的搜索步驟。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證改進(jìn)UMHexagonS算法的有效性，采用JVT參考軟件JM8.6進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)采用不同運(yùn)動(dòng)類型的標(biāo)準(zhǔn)視頻序列bus_cif，mobile_cif，flower_cif，stefan_cif，foreman_cif，coastguard_cif等作為測試序列。表1是本實(shí)驗(yàn)采用的JM代碼的編碼控制參數(shù)。

表1 JM編碼控制參數(shù)

本實(shí)驗(yàn)分別采用標(biāo)準(zhǔn)算法和改進(jìn)算法對(duì)不同視頻序列的前28幀進(jìn)行編碼。表2給出了兩種方法的運(yùn)動(dòng)估計(jì)總耗時(shí)并進(jìn)行比較，表3給出了兩種算法的亮度平均峰值信噪比。從兩表中可以看出，采用改進(jìn)算法的PSNR基本不變，在保持圖像質(zhì)量的同時(shí)有效降低了運(yùn)動(dòng)估計(jì)時(shí)間，對(duì)運(yùn)動(dòng)很緩慢的序列效果提高不大，但對(duì)劇烈運(yùn)動(dòng)序列效果很明顯。表4給出了兩種算法的平均比特率的比較，可以看出改進(jìn)算法經(jīng)過視頻編碼后的比特?cái)?shù)有極其微小的增加。綜上所述，改進(jìn)算法在降低運(yùn)動(dòng)估計(jì)時(shí)間的同時(shí)非常好地保持了原算法的率失真性能，碼率基本不變，對(duì)圖像質(zhì)量沒有影響。

表2 視頻編碼耗時(shí)和運(yùn)動(dòng)估計(jì)耗時(shí)

表3 視頻亮度分量的平均峰值信噪比

表4 視頻編碼平均比特率

5 小結(jié)

筆者對(duì)運(yùn)動(dòng)估計(jì)經(jīng)典算法和H.264采用的UMHexagonS算法進(jìn)行了簡單的分析，并提出了一種改進(jìn)算法。該算法同時(shí)考慮了視頻序列的時(shí)域和空域的相關(guān)性，使初始運(yùn)動(dòng)矢量預(yù)測更準(zhǔn)確，減少5×5全搜索中的相對(duì)不重要搜索點(diǎn)和運(yùn)算量，根據(jù)初始運(yùn)動(dòng)矢量的方向使用可變方向的梯形模型搜索，加快搜索速度。在不影響搜索精度，碼率基本不變的情況下大幅減少運(yùn)動(dòng)估計(jì)的運(yùn)算量，取得了很好的效果。

[1]畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)——H.264/AVC[M].北京:人民郵電出版社，2005.

[2]LIU L K，F(xiàn)EIG E.A block-based gradient descent search algorithm for block motion estimation in video coding[J].IEEE Trans.Circuits and Systems for Video Technology，1996，6（4）:419-422.

[3]ZHU S，MA K K.A new diamond search algorithm for fast blockmatching motion estimation[J].IEEE Trans.Image Processing，2000，9（2）:287-290.

[4]ZHU C， LIN X， CHAU L.Enhanced hexagonal search for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology， 2004，14（10）:1210-1214.

[5]ISO/IEC JEC1/SC29/WG11 M5453，Report on performance of fast motion estimation using motion vector field adaptive search techni-que（MVFAST）[S].1999.

[6]TOURAPIS A M，AU O C，LIOU M L.Predictive motion vector field adaptive search technique-enhancing block based motion estimation[EB/OL].[2009-11-09].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.9457&rep=rep1&type=pdf.

[7]CHEN Z B， XU J F， HE Y， et al.Fast integerpel and fractionalpel motion estimation for H.264/AVC[EB/OL].[2009-11-09].http://linkinghub.elsevier.com/retrieve/pii/S1047320305000787.

[8]段青青，宋瑞.一種H.264/AVC中的快速運(yùn)動(dòng)估計(jì)算法[J].計(jì)算機(jī)工程，2008，34（16）:244-246.