AVS的自適應(yīng)提前終止運(yùn)動(dòng)估計(jì)算法

王園園，張 剛，李付江

(太原理工大學(xué)信息工程學(xué)院，山西 太原 030024)

責(zé)任編輯:哈宏疆

AVS(Advanced Video Standard)標(biāo)準(zhǔn)［1］，是我國(guó)自主研發(fā)的視頻壓縮標(biāo)準(zhǔn)。AVS視頻編碼主要包括運(yùn)動(dòng)估計(jì)、DCT變換、量化、掃描、熵編碼等模塊。由于運(yùn)動(dòng)估計(jì)采用了高精度的運(yùn)動(dòng)矢量，使得運(yùn)算量大幅增加，因此，縮短運(yùn)動(dòng)估計(jì)時(shí)間是提高AVS視頻編碼實(shí)時(shí)性的重要內(nèi)容。運(yùn)動(dòng)估計(jì)研究主要分兩個(gè)方向:一是整像素運(yùn)動(dòng)估計(jì)［2-4］，參考文獻(xiàn)［5］中根據(jù)中心偏移特性提出了在起始搜索點(diǎn)預(yù)測(cè)中加入原點(diǎn)預(yù)測(cè);另一個(gè)是亞像素運(yùn)動(dòng)估計(jì)［1］。本文針對(duì)UMHexagonS搜索算法提出了搜索的提前終止判斷以及SAD計(jì)算的提前結(jié)束條件判斷，提高了最佳匹配塊的搜索速度;在模式選擇中提出了代價(jià)值的提前比較，有效減小了搜索量。

1 AVS運(yùn)動(dòng)估計(jì)過(guò)程

在視頻編碼中，幀間預(yù)測(cè)編碼就是找出每個(gè)編碼塊在鄰近幀中的位置，并得到兩者空間位置的相對(duì)偏移量即運(yùn)動(dòng)矢量。運(yùn)動(dòng)估計(jì)就是得到運(yùn)動(dòng)矢量的過(guò)程［6］。在AVS標(biāo)準(zhǔn)中幀間預(yù)測(cè)模式有5種:skip模式、16×16模式、16×8模式、8×16模式和8×8模式。運(yùn)動(dòng)估計(jì)過(guò)程分為運(yùn)動(dòng)搜索和模式選擇兩個(gè)步驟。

AVS的運(yùn)動(dòng)搜索主要是基于塊的搜索，在搜索算法中，經(jīng)典的UMHexagonS搜索算法是通過(guò)多種搜索模型的混合使用［7］，得到比較準(zhǔn)確的最佳匹配塊，運(yùn)算量也相對(duì)較小。每種搜索模型搜索得到的SAD的最小值記為min_sad，SAD閾值的上限和下限記為threshold1和threshold2。UMHexagonS搜索算法主要流程如圖1所示。

除skip預(yù)測(cè)模式外，每種預(yù)測(cè)模式通過(guò)運(yùn)動(dòng)搜索得到最佳匹配塊后，按16×16模式、8×8模式、16×8模式和8×16模式順序分別得到各種模式的代價(jià)值，逐一進(jìn)行比較，代價(jià)取值最小的預(yù)測(cè)模式即為當(dāng)前塊的最佳預(yù)測(cè)模式。

2 運(yùn)動(dòng)估計(jì)算法優(yōu)化

2.1 運(yùn)動(dòng)估計(jì)分析

經(jīng)過(guò)深入的研究發(fā)現(xiàn)，UMHexagonS搜索算法和模式選擇仍存在以下4點(diǎn)不足:

1)SAD閾值是固定的，使得運(yùn)動(dòng)劇烈的視頻序列過(guò)早終止搜索，運(yùn)動(dòng)緩慢的視頻序列不能很好地提前結(jié)束搜索。

圖1 UMHexagonS搜索算法流程圖

2)經(jīng)測(cè)試發(fā)現(xiàn)，視頻序列中靜止塊的SAD值小于SAD閾值下限的約有98%。此值通常是參考幀的搜索區(qū)域中候選搜索起始點(diǎn)(0，0)所對(duì)應(yīng)的塊計(jì)算得到，候選搜索起始點(diǎn)之后的搜索有些多余。

3)據(jù)統(tǒng)計(jì)約有80%的搜索塊，當(dāng)計(jì)算了塊中約50%像素點(diǎn)數(shù)時(shí)，累加值就已經(jīng)大于已有最小SAD值，塊中另外50%像素點(diǎn)的計(jì)算是多余的。

4)模式選擇時(shí)，靜止或者運(yùn)動(dòng)緩慢的塊，通常選擇16×16模式。算法中先是計(jì)算16×16預(yù)測(cè)模式的代價(jià)值me16x16.cost。然后，無(wú)條件的計(jì)算8×8模式4個(gè)塊代價(jià)值的累加和i_cost8x8。實(shí)際1個(gè)8×8塊的代價(jià)值已經(jīng)大于me16x16.cost，所以，多余計(jì)算了其余3個(gè)8×8塊的代價(jià)值。

2.2 運(yùn)動(dòng)估計(jì)優(yōu)化

本文根據(jù)前文提到的幾點(diǎn)不足，提出以下4個(gè)方面的優(yōu)化:

1)自適應(yīng)地選擇SAD閾值。UMHexagonS搜索算法中SAD閾值是固定的，其中16×16預(yù)測(cè)模式的SAD閾值threshold1和threshold2分別為2000和500。以16×16模式為基準(zhǔn)，得到16×8預(yù)測(cè)模式和8×16預(yù)測(cè)模式SAD的閾值threshold1＞＞1和threshold2＞＞1，8×8預(yù)測(cè)模式SAD的閾值為threshold1＞＞2和threshold2＞＞2。本文提出了以下改進(jìn)方法:根據(jù)物體運(yùn)動(dòng)的空間和時(shí)間相關(guān)性，當(dāng)前塊的最佳匹配塊的SAD值和候選搜索起始點(diǎn)對(duì)應(yīng)塊所得到的SAD值密切相關(guān)。所以，SAD閾值的設(shè)定可以根據(jù)候選搜索起始點(diǎn)得到的SAD值來(lái)確定。因此，SAD閾值的設(shè)定如下:

根據(jù)16×8模式、8×16模式和8×8模式的SAD閾值與16×16模式閾值的關(guān)系得到如下3個(gè)數(shù)組:

(1)data500［4］={500，250，250，125};

(2)data1000［4］={1000，500，500，250};

(3)data2000［4］={2000，1000，1000，500}。

其中，data500［4］表示4種預(yù)測(cè)模式閾值下限的最小取值;data1000［4］表示4種預(yù)測(cè)模式閾值下限的最大取值以及上限和下限的差值;data2000［4］表示4種預(yù)測(cè)模式閾值上限的最大取值。

通過(guò)候選搜索起始點(diǎn)得到的SAD的最小值記為min_sad。自適應(yīng)選擇SAD閾值的流程如圖2所示。其中，4種預(yù)測(cè)模式 i_pixel取值分別為 0，1，2，3。該方法可使每種預(yù)測(cè)模式的閾值上限和下限都不再是固定值，而是存在一定的取值范圍。采用上述自適應(yīng)的SAD閾值，能有效地減少搜索點(diǎn)數(shù)，更快地搜索到最優(yōu)點(diǎn)，使得計(jì)算量大大降低。

圖2 自適應(yīng)選擇SAD閾值流程圖

2)搜索提前終止判斷。經(jīng)候選起始點(diǎn)得到自適應(yīng)SAD閾值上限threshold1和下限threshold2后加入條件判斷語(yǔ)句“if(sad＜threshold2)”，滿足條件則提前終止搜索。在不影響視頻質(zhì)量的前提下，可以平均減少24～36個(gè)搜索點(diǎn)的計(jì)算量。

3)SAD計(jì)算的優(yōu)化。UMHexagonS搜索算法中每一種搜索模型都是通過(guò)一定的宏定義函數(shù)實(shí)現(xiàn)的。宏定義中用的SAD值計(jì)算函數(shù)的主要代碼如下:

針對(duì)4 種預(yù)測(cè)模式(lx，ly)分別為(16，16)，(16，8)，(8，16)和(8，8)。將SAD值比較提前放入SAD計(jì)算函數(shù)中，每累加一個(gè)絕對(duì)差值進(jìn)行一次“if(sum ＞=bcost)”比較，如果滿足條件則跳出循環(huán)，提前結(jié)束計(jì)算，可以節(jié)省m－count次循環(huán)的計(jì)算量。

4)模式選擇的提前結(jié)束判斷。在幀間模式選擇時(shí)，在函數(shù)xavs_mb_analyse_inter_p8x8()中每累加一個(gè)8×8塊的代價(jià)執(zhí)行一次條件判斷“if(a-＞l0.i_cost8x8＞=a-＞l0.me16x16.cost)”，如果已有8×8代價(jià)值不小于16×16預(yù)測(cè)模式的代價(jià)值，則可以提前結(jié)束對(duì)代價(jià)值的計(jì)算，便可省去對(duì)其余8×8塊的運(yùn)動(dòng)搜索和代價(jià)值計(jì)算。這種優(yōu)化算法對(duì)靜止或運(yùn)動(dòng)緩慢的視頻序列改善較為明顯。

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

實(shí)驗(yàn)分別從峰值信噪比(PSNR)、碼率(BR)和幀率(FR)3個(gè)方面將優(yōu)化后算法和優(yōu)化前算法進(jìn)行了比較。主要參數(shù)設(shè)置:參考幀為1幀，I幀的QP設(shè)為28，編碼序列為IPPP格式，其中P幀預(yù)測(cè)模式不包括幀內(nèi)預(yù)測(cè)模式。本實(shí)驗(yàn)測(cè)試了不同格式(QCIF，CIF，D1)和不同運(yùn)動(dòng)劇烈程度(如運(yùn)動(dòng)幅度較小的bridge序列，運(yùn)動(dòng)幅度中等的coastguard序列，運(yùn)動(dòng)幅度較大的football序列)的經(jīng)典測(cè)試序列在不同QP(28，30)下的峰值信噪比、碼率和幀率的變化。實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表1～表6。

表1 QP=28時(shí)QCIF格式的實(shí)驗(yàn)結(jié)果

表2 QP=30時(shí)QCIF格式的實(shí)驗(yàn)結(jié)果

表3 QP=28時(shí)CIF格式的實(shí)驗(yàn)結(jié)果

表4 QP=30時(shí)CIF格式的實(shí)驗(yàn)結(jié)果

表5 QP=28時(shí)D1格式的實(shí)驗(yàn)結(jié)果

表6 QP=30時(shí)D1格式的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果中前兩項(xiàng)數(shù)據(jù)均為:變化率 =(優(yōu)化后-優(yōu)化前 )/優(yōu)化前×100%，其中“-”號(hào)表示降低，“+”號(hào)表示增加，對(duì)于信噪比“+”號(hào)表示視頻質(zhì)量得到提高，而對(duì)于碼率“-”號(hào)表示壓縮率越大。由測(cè)試結(jié)果可以看出，所有測(cè)試序列信噪比降低不超出0.3%，碼率增加不超出0.4%，幀率都有了明顯提高，并且針對(duì)同一種格式的序列，QP越小時(shí)幀率提高越大。另外，部分測(cè)試序列的信噪比有所增加，也有部分測(cè)試序列碼率有所減小。總體來(lái)看，在峰值信噪比和碼率變化不明顯的情況下，幀率平均提高1.4倍，更好地滿足了視頻壓縮編碼的實(shí)時(shí)性要求。

4 小結(jié)

本文通過(guò)對(duì)AVS編碼器中整像素運(yùn)動(dòng)估計(jì)算法的深入研究和分析，分別針對(duì)運(yùn)動(dòng)搜索的UMHexagonS搜索算法和模式選擇在SAD閾值選擇、搜索的終止判斷、SAD計(jì)算和代價(jià)值比較幾方面進(jìn)行了改進(jìn)。實(shí)驗(yàn)表明，對(duì)于不同格式和量化參數(shù)的測(cè)試序列，在峰值信噪比和碼率基本不變的情況下，編碼速度大幅度提高，增強(qiáng)了編碼器的實(shí)時(shí)性，更有利于視頻的實(shí)時(shí)編碼傳輸。

［1］周波，王力波，劉東華，等.用于AVS視頻編碼的快速子像素運(yùn)動(dòng)搜索算法［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(7):2238-2240.

［2］劉易，李太君.H.264中快速運(yùn)動(dòng)估計(jì)UMHexagonS算法的改進(jìn)［J］.計(jì)算機(jī)技術(shù)與應(yīng)用，2011，37(8):128-130.

［3］ZHU Shang，MA Kaikuang.A new diamond search algorithm for fast block-matching motion estimation［J］.IEEE Trans.Image Processing，2000，9(2):287-290.

［4］王超，于洪珍，厲丹，等.帶有閥值的自適應(yīng)混合搜索算法的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(9):1968-1970.

［5］楊齊，李子印.一種改進(jìn)的UMHexagonS運(yùn)動(dòng)估計(jì)算法［J］.電視技術(shù)，2012，36(5):15-17.

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

［7］黃春慶，邱曉彬.基于x264的快速運(yùn)動(dòng)估計(jì)算法優(yōu)化［J］.控制工程，2010，17(6):820-823.