面向AVS2的快速幀間預(yù)測(cè)算法

林 琪，趙海武，王國(guó)中，滕國(guó)偉，李國(guó)平

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

AVS標(biāo)準(zhǔn)是中國(guó)“數(shù)字音視頻編解碼技術(shù)標(biāo)準(zhǔn)工作組”自主研發(fā)，擁有自主知識(shí)產(chǎn)權(quán)的第二代視頻壓縮標(biāo)準(zhǔn)。隨著壓縮技術(shù)不斷地提升，標(biāo)準(zhǔn)工作組在完成AVS標(biāo)準(zhǔn)制定后，現(xiàn)又以超高清晰度視頻為應(yīng)用目標(biāo)，積極地制定壓縮效率更高的新一代視頻編碼標(biāo)準(zhǔn)AVS2。該標(biāo)準(zhǔn)在制定中引入了多種先進(jìn)技術(shù)來(lái)提升編碼效率。例如，編碼塊大小由原來(lái)的16×16擴(kuò)展到64×64，并且采用了靈活的四叉樹結(jié)構(gòu)對(duì)編碼塊進(jìn)行自適應(yīng)劃分[1]；引入多參考幀技術(shù)，規(guī)定了P幀可以參考前向的多幀，B幀可以參考前后兩幀等。這些技術(shù)的引入大幅地提高了視頻編碼的效率，與此同時(shí)編碼復(fù)雜度也成倍地增加。因此，有效地提高編碼速度是AVS2標(biāo)準(zhǔn)成功推廣的關(guān)鍵所在。

AVS2仍然沿用了上一代編碼標(biāo)準(zhǔn)的混合編碼框架，其中幀間預(yù)測(cè)仍然占據(jù)著大量的編碼時(shí)間，如何減少幀間預(yù)測(cè)的復(fù)雜度依然是許多專家學(xué)者關(guān)注的重點(diǎn)。目前，對(duì)于幀間預(yù)測(cè)快速算法的研究主要集中在兩類：第一類是快速運(yùn)動(dòng)搜索算法，如著名的三步搜索算法（TSS）、非對(duì)稱十字型多層次六邊形格點(diǎn)搜索算法（UMHexa?gonS）[2]等；第二類則是快速幀間模式選擇算法，主要通過減小幀間候選模式搜索數(shù)目來(lái)加快編碼的速度，如AVS2提案M3012采用了一種AMP快速?zèng)Q策機(jī)制[3]，利用水平（垂直）非方形劃分模式上的相似性，在編碼圖像塊的時(shí)候，使用對(duì)稱非方形劃分模式作為判斷是否使用非對(duì)稱非方形劃分的依據(jù)，從而降低編碼的復(fù)雜性。文獻(xiàn)[4]則將運(yùn)動(dòng)估計(jì)快速算法與幀間模式選擇算法結(jié)合在一起研究，打破了傳統(tǒng)的將快速運(yùn)動(dòng)搜索算法與快速幀間模式選擇算法獨(dú)立研究的現(xiàn)象，避免了兩種方法單獨(dú)研究時(shí)存在的不足。

由于AVS2引入了更多的模式劃分以及更多可供參考的參考幀數(shù)目，這使得幀間預(yù)測(cè)的編碼復(fù)雜度進(jìn)一步增加。針對(duì)該問題，本文通過對(duì)多模式劃分的研究，在使用AMP快速?zèng)Q策算法的基礎(chǔ)上，通過減小各種劃分模式下參與運(yùn)動(dòng)估計(jì)計(jì)算的參考幀數(shù)目，進(jìn)一步加快幀間編碼速度。

1 AVS2幀間預(yù)測(cè)

1.1 圖像的劃分

AVS2依然采用分塊的編碼方式，但是塊的尺寸可以自適應(yīng)地改變。其中包含了3類處理單元，分別是編碼單元（Coding Unit，CU），預(yù)測(cè)單元（Prediction Unit，PU）以及變換單元（Transform Unit，TU）。視頻圖像被劃分成一系列編碼樹（Coding Tree Blocks，CTB），它是進(jìn)行預(yù)測(cè)、變換、量化和熵編碼等處理的基本單元，其尺寸可以是2N×2N，N∈(32,16,8)。而一個(gè)亮度CTB和相應(yīng)的兩塊色度CTB，再加上相應(yīng)的語(yǔ)法元素組成了一個(gè)編碼樹單元（Coding Tree Units，CTU）。CTU以四叉樹遞歸的結(jié)構(gòu)，被劃分成尺寸大小相同的4個(gè)方塊，即4個(gè)葉節(jié)點(diǎn)，每個(gè)葉節(jié)點(diǎn)，就是1個(gè)CU，共有64×64，32×32，16×16等3種尺寸。CU是幀內(nèi)、幀間、Skip等預(yù)測(cè)模式的基本單元。在做幀間預(yù)測(cè)時(shí)，CU又可以被劃分成一個(gè)或者多個(gè)用于幀間預(yù)測(cè)的PU。在一個(gè)大小為2N×2N的CU下，PU幀間模式劃分有8種不同的劃分：4個(gè)對(duì)稱劃分（NO_SPLIT，CROSS_SPLIT，HOR_SYM，VER_SYM）以及4個(gè)非對(duì)稱劃分（PHOR_UP，PHOR_DOWN，PVER_LEFT，PVER_RIGHT），如圖1所示。

1.2 AVS2幀間模式選擇原理

在對(duì)CU進(jìn)行編碼前，首先對(duì)該編碼單元進(jìn)行模式劃分，然后對(duì)劃分的模式遍歷，分別進(jìn)行運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償。比如，在當(dāng)前模式下對(duì)CU進(jìn)行編碼時(shí)，先對(duì)該CU下的PU分別做運(yùn)動(dòng)估計(jì)，利用式（1）從各個(gè)候選參考幀下選擇失真代價(jià)最小的參考幀作為當(dāng)前PU的最佳參考圖像

式中：λmotion=，是拉格朗日因子；mv是當(dāng)前PU相對(duì)于所選的參考圖像塊的運(yùn)動(dòng)向量；ref是當(dāng)前所選的參考圖像在參考幀隊(duì)列中的索引值；SAD是當(dāng)前編碼塊與參考圖像塊差值的絕對(duì)值之和；r(ref,mv)是參考圖像塊；R（mvd）+R（ref）表示的是碼率，第一項(xiàng)表示對(duì)運(yùn)動(dòng)向量殘差進(jìn)行編碼所需要的比特率，第二項(xiàng)表示對(duì)選擇的參考圖像的索引值進(jìn)行編碼所需的比特率。

PU最佳參考圖像得到后，完成該模式下的運(yùn)動(dòng)估計(jì)，再使用式（2）獲得代價(jià)最小的模式作為當(dāng)前編碼塊的最優(yōu)模式，完成后續(xù)的編碼

式中：SAD表示在給定量化參數(shù)QP的條件下，該模式的預(yù)測(cè)單元與重建圖像塊的差值平方和；s是當(dāng)前預(yù)測(cè)單元；c是重建圖像塊；mode是所選的幀間編碼的模式；R是在該模式下編碼所需要的比特?cái)?shù)，包括了表示模式所需的比特?cái)?shù)、運(yùn)動(dòng)向量的殘差和變換塊的信息；拉格朗日因子λmotion是根據(jù)量化參數(shù)QP獲得的。

2 快速幀間預(yù)測(cè)算法

在對(duì)CU進(jìn)行編碼時(shí)，遍歷參考圖像緩沖區(qū)的候選參考圖像獲得最佳參考圖像，以及對(duì)CU的多種劃分模式進(jìn)行遍歷獲得最優(yōu)模式，編碼器的編碼復(fù)雜度會(huì)隨著參考幀數(shù)目和模式劃分?jǐn)?shù)目增加而大幅度增大。針對(duì)多模式劃分產(chǎn)生的計(jì)算復(fù)雜度增加問題，提案M3012提出的AMP快 速 決 策 機(jī) 制 ，根 據(jù) HOR_SYM，HOR_UP，HOR_DOWN及VER_SYM，VER_LEFT，VER_RIGHT在劃分模式上的相似性，提出在編碼圖像塊時(shí)使用對(duì)稱非方形劃分模式作為判斷是否使用非對(duì)稱非方形劃分的依據(jù)。若水平對(duì)稱非方形劃分（或垂直對(duì)稱非方形劃分）是當(dāng)前最優(yōu)模式，則編碼端繼續(xù)編碼兩種水平非對(duì)稱非方形劃分（或垂直非對(duì)稱非方形劃分）模式；否則，跳過該兩種非對(duì)稱非方形劃分模式[3]。這種方法有效地降低了AMP的編碼復(fù)雜度，然而它只是對(duì)幀間模式選擇進(jìn)行了快速運(yùn)算，降低的時(shí)間有限，在多參考幀的幀間預(yù)測(cè)下，仍有較大的改進(jìn)空間。

視頻圖像具有空間相關(guān)性，相鄰塊之間也有一定相關(guān)性，AMP快速?zèng)Q策機(jī)制正是鑒于該種特性，有效減低編碼復(fù)雜度。研究相鄰塊的這一特性中，對(duì)同一CU下的PU的參考幀選擇進(jìn)行分析，統(tǒng)計(jì)相鄰PU之間選擇同一參考幀的概率，發(fā)現(xiàn)相鄰PU不同CU深度選擇參考幀呈現(xiàn)相同的規(guī)律，選擇同一參考幀的概率較大。文獻(xiàn)[5]也根據(jù)這一現(xiàn)象，深度挖據(jù)相鄰PU之間參考幀的相關(guān)性，通過運(yùn)動(dòng)矢量mv判斷是否緩沖區(qū)的參考幀進(jìn)行遍歷。然而該方法使用mv作為閾值判斷，并不能很好地反映相鄰PU之間的相關(guān)性。而文獻(xiàn)[6]則提到運(yùn)動(dòng)矢量差值mvd（預(yù)測(cè)mv與當(dāng)前mv的差值）反映了運(yùn)動(dòng)的復(fù)雜度，表示了當(dāng)前PU與相鄰PU的運(yùn)動(dòng)平緩度，mvd越小，物體運(yùn)動(dòng)越平緩，選用鄰近參考幀最為最佳參考幀的概率就越大，該方法在使用時(shí)，通過參考幀的概率分布，預(yù)先為當(dāng)前編碼幀初始化一個(gè)參考幀集（RFS）來(lái)減小參與運(yùn)動(dòng)估計(jì)的參考幀數(shù)目，其編碼速度的快慢很大程度上取決于參考幀集中元素的個(gè)數(shù)以及mvd閾值的選定。如果在編碼某一劃分模式下的PU，對(duì)參考圖像緩沖區(qū)的候選參考幀進(jìn)行遍歷搜索，就會(huì)浪費(fèi)大量的運(yùn)算。

根據(jù)以上這些分析，本文將AMP快速?zèng)Q策機(jī)制與參考幀選擇算法結(jié)合在一起研究，提出一種多模式多參考幀的快速幀間預(yù)測(cè)算法，在AMP快速?zèng)Q策算法基礎(chǔ)上，適時(shí)地選用相鄰PU的最佳參考幀作為當(dāng)前PU的最佳參考幀，選用運(yùn)動(dòng)矢量差值作為閾值判斷，進(jìn)而達(dá)到減低編碼復(fù)雜度的目的幀間預(yù)測(cè)。

算法的具體實(shí)現(xiàn)如下：

1）確定每一層CU的運(yùn)動(dòng)矢量殘差（運(yùn)動(dòng)估計(jì)獲得的運(yùn)動(dòng)矢量與預(yù)測(cè)獲得的運(yùn)動(dòng)矢量的差值）的曼哈頓距離（=|mvd_x|+|mvd_y|）的閾值TH[i]，其中i代表CTU的深度，取值為0～2。對(duì)序列的初始兩幀按照原始的方法進(jìn)行編碼，記錄不同深度（不同CU尺寸），并分別對(duì)每層的求和，取其均值Mean_mvd[i]。TH[i]計(jì)算如式（3）所示

式中：k是常系數(shù)，本文中k均取1。確定閾值后，開始對(duì)各劃分模式進(jìn)行遍歷，執(zhí)行第2）步，編碼端首先對(duì)水平對(duì)稱非方形和垂直對(duì)稱非方形劃分進(jìn)行分析。

2）編碼當(dāng)前CU下第一個(gè)PU（標(biāo)號(hào)為0）時(shí)，按照原始方法對(duì)參考幀緩沖區(qū)中的候選參考幀進(jìn)行遍歷做運(yùn)動(dòng)估計(jì)，獲得最佳參考幀。

3）編碼當(dāng)前CU左邊（或下邊）的PU時(shí)，首先以已編碼的標(biāo)號(hào)為0的PU對(duì)應(yīng)的最佳參考幀作為當(dāng)前PU的參考幀，進(jìn)行運(yùn)動(dòng)估計(jì)計(jì)算，獲得

4）將該與當(dāng)前PU所處深度的對(duì)應(yīng)閾值TH[i]進(jìn)行比較，如果≤TH[i]，則當(dāng)前預(yù)測(cè)所用的參考幀即為最佳參考幀，也就是相鄰PU的最佳參考幀，結(jié)束當(dāng)前PU對(duì)參考圖像緩沖區(qū)中其余候選參考幀的遍歷；否則，＞TH[i]，遍歷參考圖像緩沖區(qū)中剩余的候選參考幀，找到最佳參考幀。

5）當(dāng)前模式是方形對(duì)稱模式時(shí)，則編碼右下方PU時(shí)，若其上邊、左邊PU的最佳參考幀相同，則以該參考幀作為當(dāng)前PU的最佳參考幀；否則，遍歷參考圖像緩沖區(qū)中的所有候選參考幀。

6）最后將該劃分模式與當(dāng)前最優(yōu)劃分模式比較，取代價(jià)較小的模式更新當(dāng)前最優(yōu)模式。若當(dāng)前最優(yōu)模式是水平對(duì)稱非方形劃分（或垂直對(duì)稱非方形劃分），則編碼端繼續(xù)編碼水平非對(duì)稱非方形劃分（或垂直非對(duì)稱非方形劃分），重復(fù)第2），3），4）步；否則，跳過該兩種非對(duì)稱非方形劃分模式，重復(fù)第2），3），4），5）步。

算法流程圖如圖2所示。

圖2 算法流程圖

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

為了驗(yàn)證本文提出快速幀間預(yù)測(cè)算法的有效性，在AVS2參考軟件RD5.0中加入本文算法，通過使用本文算法所需的編碼時(shí)間（time）與使用AMP快速?zèng)Q策算法以及原始搜索算法兩種算法的編碼時(shí)間分別進(jìn)行比較，測(cè)試不同量化參數(shù)（QP）、不同序列下的編碼性能。具體配置如表1所示。表2為本方法的實(shí)驗(yàn)結(jié)果，本文主要從編碼時(shí)間與文獻(xiàn)[3]方案以及全搜索方案進(jìn)行對(duì)比。此外采用RD曲線對(duì)編碼性能進(jìn)行對(duì)比。

表2中，Δtime表示總編碼時(shí)間的變化，如果為負(fù)，表示編碼時(shí)間減小，反之則增加。由表2可知，本文提出的算法較全搜索算法相比編碼時(shí)間有大幅度下降，平均下降36%左右。若視頻較為平緩如Video1，本文方法時(shí)間則節(jié)省約40.6%；與文獻(xiàn)[3]中AMP快速?zèng)Q策算法相比，本文方法的編碼時(shí)間也有明顯的下降，平均下降約為14%，如Video1這類運(yùn)動(dòng)較為平緩的會(huì)議視頻，其編碼時(shí)間下降有17%，如RaceHorses這類運(yùn)動(dòng)較為劇烈的視頻，其編碼時(shí)間下降也有10%。性能方面，由圖3～圖8可知，本文方法對(duì)編碼效率基本沒有影響。

表1 實(shí)驗(yàn)測(cè)試條件

表2 本文算法在RD5.0下的實(shí)驗(yàn)比較

4 結(jié)論

本文重點(diǎn)研究了在AVS2的幀間預(yù)測(cè)中，使用多劃分模式、多參考幀技術(shù)帶來(lái)的編碼復(fù)雜度增加問題。針對(duì)這一問題，本文在已有的AMP快速?zèng)Q策算法的基礎(chǔ)上，對(duì)其進(jìn)一步研究，并將其與降低多參考幀數(shù)目方法相結(jié)合，利用同一CU下相鄰PU的相關(guān)性，減小各模式下PU對(duì)參考圖像緩沖區(qū)中的候選參考圖像的搜索概率，進(jìn)而降低幀間的編碼時(shí)間。實(shí)驗(yàn)結(jié)果表明，本文提出的算法應(yīng)用于AVS2參考軟件中，可以使編碼時(shí)間平均下降36%左右。比原始AMP快速?zèng)Q策算法的編碼時(shí)間平均下降14%，編碼性能基本保持不變。由此可見，本文方法對(duì)解決AVS2標(biāo)準(zhǔn)中使用多種先進(jìn)技術(shù)而帶來(lái)的編碼復(fù)雜度大幅度升高問題有一定地幫助，從而促進(jìn)AVS2的進(jìn)一步發(fā)展。

：

[1]SUNIL L.AVS視頻提案A AVS_M2973:Proposal for AVS2.0 refer?ence software[EB/OL].[2014-02-17].http://www.avs.org.cn/index.asp?meetingid=65＆filetype=proposal.

[2]陳超峰.基于AVS快速運(yùn)動(dòng)估計(jì)的視頻編碼研究[D].廣州：華南理工大學(xué)，2011.

[3]鄭蕭楨.AVS視頻提案A AVS_M3012：AMP快速?zèng)Q策機(jī)制/Fast mode decision for AMP[EB/OL].[2014-02-10].http://www.avs.org.cn/index.asp?meetingid=65＆filetype=proposal.

[4]BELGHITH F，KIBEYA H，LOUKIL H，et al.A new fast motion estimation algorithm using fast mode decision for high-efficiency video coding standard[J].Journal of Real-Time Image Processing，2014:1-17.

[5]沈曉琳.HEVC低復(fù)雜度編碼優(yōu)化算法研究[D].杭州：浙江大學(xué)，2013.

[6]WANG Shanshe，MA Siwei，WANG Shiqi，et al.Fast multi reference frame motion estimation for high efficiency video coding[C]//Proc.20th IEEE International Conference.Melbourne:IEEE Press，2013：2005-2009.

[7]BJONTEGAARD G.Calculation of average PSNR differences be?tween RD curves[R].[S.l]：Joint Video Team （JVT） of ISO/IEC MPEG and ITU-TVCEG，2001.