面向AVS2的快速幀間預測算法

林 琪，趙海武，王國中，滕國偉，李國平

（上海大學 通信與信息工程學院，上海 200436）

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

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

由于AVS2引入了更多的模式劃分以及更多可供參考的參考幀數目，這使得幀間預測的編碼復雜度進一步增加。針對該問題，本文通過對多模式劃分的研究，在使用AMP快速決策算法的基礎上，通過減小各種劃分模式下參與運動估計計算的參考幀數目，進一步加快幀間編碼速度。

1 AVS2幀間預測

1.1 圖像的劃分

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

1.2 AVS2幀間模式選擇原理

在對CU進行編碼前，首先對該編碼單元進行模式劃分，然后對劃分的模式遍歷，分別進行運動估計和運動補償。比如，在當前模式下對CU進行編碼時，先對該CU下的PU分別做運動估計，利用式（1）從各個候選參考幀下選擇失真代價最小的參考幀作為當前PU的最佳參考圖像

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

PU最佳參考圖像得到后，完成該模式下的運動估計，再使用式（2）獲得代價最小的模式作為當前編碼塊的最優模式，完成后續的編碼

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

2 快速幀間預測算法

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

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

根據以上這些分析，本文將AMP快速決策機制與參考幀選擇算法結合在一起研究，提出一種多模式多參考幀的快速幀間預測算法，在AMP快速決策算法基礎上，適時地選用相鄰PU的最佳參考幀作為當前PU的最佳參考幀，選用運動矢量差值作為閾值判斷，進而達到減低編碼復雜度的目的幀間預測。

算法的具體實現如下：

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

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

2）編碼當前CU下第一個PU（標號為0）時，按照原始方法對參考幀緩沖區中的候選參考幀進行遍歷做運動估計，獲得最佳參考幀。

3）編碼當前CU左邊（或下邊）的PU時，首先以已編碼的標號為0的PU對應的最佳參考幀作為當前PU的參考幀，進行運動估計計算，獲得

4）將該與當前PU所處深度的對應閾值TH[i]進行比較，如果≤TH[i]，則當前預測所用的參考幀即為最佳參考幀，也就是相鄰PU的最佳參考幀，結束當前PU對參考圖像緩沖區中其余候選參考幀的遍歷；否則，＞TH[i]，遍歷參考圖像緩沖區中剩余的候選參考幀，找到最佳參考幀。

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

6）最后將該劃分模式與當前最優劃分模式比較，取代價較小的模式更新當前最優模式。若當前最優模式是水平對稱非方形劃分（或垂直對稱非方形劃分），則編碼端繼續編碼水平非對稱非方形劃分（或垂直非對稱非方形劃分），重復第2），3），4）步；否則，跳過該兩種非對稱非方形劃分模式，重復第2），3），4），5）步。

算法流程圖如圖2所示。

圖2 算法流程圖

3 實驗結果

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

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

表1 實驗測試條件

表2 本文算法在RD5.0下的實驗比較

4 結論

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

：

[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快速運動估計的視頻編碼研究[D].廣州：華南理工大學，2011.

[3]鄭蕭楨.AVS視頻提案A AVS_M3012：AMP快速決策機制/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低復雜度編碼優化算法研究[D].杭州：浙江大學，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.