基于深度特性的幀間預測快速算法

彭同壯，劉立程，楊關水

（廣東工業(yè)大學 信息工程學院，廣東 廣州 510006）

隨著5G商用的到來，超高清視頻的應用將會越來越廣泛，同時對視頻傳輸和壓縮帶來了挑戰(zhàn)。為此2013年由JCT-VC (Joint Collaborative Team on Video Coding)小組制定的下一代高效視頻編碼標準HEVC(High Efficiency Video Coding，H.265/HEVC)應運而生，并采納成國際標準。HEVC標準相比上一代視頻編碼H.264/AVC在同等視頻質量下可以節(jié)省50%的碼率[1-2]，其編碼框架沿用H.264/AVC技術，增加了更先進的編碼技術，當然復雜的編碼技術需要大量的時間進行編解碼，在性能上，其復雜度是H.264/AVC的4～10倍，對于實時視頻應用則是5 000倍，這對于技術推廣和實際運用帶來巨大的挑戰(zhàn)，并引起了學術界和工業(yè)界的極大關注。幀間預測編碼是HEVC重要的一部分，也是影響編碼計算復雜度高的模塊之一，大約占視頻編碼時間的69%[3]，因此，優(yōu)化幀間預測過程很有必要。

對于幀間編碼的優(yōu)化，許多學者進行了深入的研究。在文獻[4]中，提出了一種早期的MERGE模式決策算法，針對父CU(Coding Unit，CU)提出了早期的MERGE模式決策；然后，通過考慮父CU和子CU之間的模式選擇的相關性，為子CU提出早期MERGE模式決策，能有效地提升編碼速度。文獻[5]提出了一種使用編碼CU深度歷史(AECH)的自適應提前終止算法。AECH計算所有CU深度值的平均值，并從平均值中找到CU深度歷史記錄的標準偏差，自適應地選擇目標CU深度范圍。該算法雖然能降低時間復雜度，但是沒有很好地利用到空域特性，且利用時域歷史深度的平均值會使編碼當前深度進入局部最優(yōu)狀態(tài)，從而將誤差擴散下去，造成較高的誤碼率。文獻[6]提出了一種新穎的方法，提出CTU(Coding Tree Unit，CTU)中的CU也可以逆序遍歷，從下到上的訪問順序進行自適應訪問，使用逆序訪問順序時從較高深度獲得的編碼信息，降低HEVC中深度選擇，模式決策和幀間預測的復雜度具有較好的效果，但是算法提升時間有限，且在紋理簡單的視頻未能很好地發(fā)揮性能。在文獻[7]中，報告了基于貝葉斯決策規(guī)則的早期終止方法，其中聯合應用在線學習和離線學習來生成分類器的模型參數，此類基于機器學習的方式雖然在時間上能有較大的提高，但是編碼結果不精確，誤碼率較高，并在視頻紋理復雜場景下的誤碼率更大，不適用于場景突變或內容紋理復雜的視頻序列。在文獻[8]中提出了一種快速CU深度決策算法，首先，提出了HEVC零深度CU檢測方法作為早期終止算法，其次，根據統(tǒng)計時空深度信息的標準差自適應地確定了CU深度劃分策略。最后，當鄰居不可用或相關性很弱時，編碼樹單元CTU的邊緣梯度被認為是CU深度劃分方法的主要因素，雖然算法有很好的提升，但是在不同序列上降低編碼時間復雜度的差異較大，通用性不強，在視頻紋理復雜的情況下，誤碼率較高。文獻[9]提出了一種HEVC的快速幀間模式決策算法，利用序列的相關性，包括四叉樹結構和時空相關性，共同用于確定塊大小的范圍，并跳過一些特殊的塊。此類在編碼過程中對特殊信息提取的方式，準確率難以保證，帶來的誤碼率較高。文獻[10]提出了一種快速幀間CU決策方案，其中設計了一種新穎的ME(Motion Estimation，ME)方法，并定義了一種名為運動補償RD(Rate distortion，RD)成本的新概念。為了減少RD優(yōu)化的時間，文獻[11]在基于統(tǒng)計信息的Hadamard變換之后采用零塊檢測方案。文獻[12]提出了一種基于內容相似度的快速參考幀選擇算法，以減少基于多個參考幀的幀間預測的計算復雜性?；诟讣夘A測單元Inter_2N×2N和子級預測單元Inter_2N×N，Inter_N×2N，Inter_N×N，Inter_2N×nU，Inter_2N×nD，Inter_nL×2N和Inter_nR×2N的內容相似度，通過學習子預測單元的父預測單元的結果來獲得子預測單元的參考幀選擇信息，但在進行四叉樹劃分時，父塊劃分為4個子塊，那么根據父子塊信息之間的繼承關系來進行子塊模式的判定往往存在誤差。

以上幀間預測模式快速算法一方面根據父子PU模式的相關性，利用父PU的模式來預測子PU模式過程，從而減少子PU不必要的遍歷過程來降低時間復雜度。另一方面通過時空域的相關性，利用時域PU模式來跳過當前PU非必要模式的遍歷。本文通過統(tǒng)計深度信息與PU模式之間的相關性，根據時空域相鄰CTU的深度信息判斷場景是否復雜，結合當前CU深度來對PU模式進行預測，算法在不同視頻序列下誤碼率極小，時間節(jié)省明顯，具有通用性。

1 HEVC幀間預測模式劃分特性分析

為適應高分辨率的需求，HEVC的編碼塊CU采用了靈活的四叉樹編碼結構，一個CTU可以劃分的尺寸為64×64～ 8×8的矩形編碼塊，其對應尺寸的深度為d，d的取值為0，1，2，3。HEVC編碼結構如圖1所示。

圖1 CTU遞歸四叉樹劃分Fig.1 CTU recursive quadtree partition

HEVC進行幀間預測利用了視頻序列的時間相關特性，通過去除時域冗余來達到高壓縮率的效果。在幀間預測中需要在參考幀中找到最優(yōu)的匹配塊，然后對編碼塊CU從深度0到3進行遞歸劃分，每個深度下的CU都需要進行遍歷不同大小的PU模式，計算每種模式下的率失真代價，選出最優(yōu)的模式作為當前編碼模式。其率失真代價計算為

其中， D(Motion)、R (Motion)分別表示采用不同的運動模式下的失真和比特數，λMode為拉格朗日因子，率失真最小的模式即為最優(yōu)預測模式。

幀間預測有8種預測模式，如圖2所示，包括4種對稱分割模式2N×2N，2N×N，N×2N，N×N和4種非對稱分割模式2N×nU，2N×nD，nL×2N，nR×2N。每種模式下需要進行運動估計、運動補償等過程，運動估計會進行運動矢量搜索，找到最優(yōu)的匹配塊，記錄最優(yōu)的運動矢量MV(Motion Vector，MV)，然后需要對當前運動矢量與預測運動矢量MVP(Motion Vector Prediction，MVP)進行差分編碼，得到運動向量殘差MVD(Motion Vector Difference，MVD)，即最后是通過編碼MVD和像素殘差信息進行編碼。進行幀間預測過程中，深度為0、1、2的CU需要至少進行6次率失真計算，至多進行8次率失真計算(水平非對稱劃分標志Test_AMVPHor為真，只進行2N×nU，2N×nD的非對稱遍歷；垂直非對稱劃分標志Test_AMVPVer為真，只進行nL×2N，nR×2N的非對稱遍歷)，深度為3的CU只需要進行對稱模式的劃分，需要進行4次率失真計算，那么一個完整的CTU最少需要進行(1+4+16+64)×6=510次的率失真計算，并且分辨率越高的視頻，其劃分的CTU的數目越多，帶來的計算復雜度越高，若能優(yōu)化PU模式的遍歷過程，則能大幅降低計算過程，對節(jié)省編碼時間具有重要意義。

圖2 PU幀間預測劃分模式Fig.2 Inter-prediction partition mode

2 基于深度特性的幀間預測快速算法

2.1 PU統(tǒng)計特性分析

為分析不同深度下的PU特性，在官方測試軟件HM16.9平臺下統(tǒng)計PU在不同深度下的分布情況，測試的量化參數QP(Quantization Parameter, QP)設置32，CTU尺寸設置為64，最大深度設置3，編碼配置LD模式下，測試統(tǒng)計數據如表1所示。對于較大的CU塊，當前深度為0或1時，定義深度為SD(Small Depth，SD)；較小的CU塊，當前深度為2或3時，定義深度為HD(High Depth，HD)。將幀間2N×N，N×2N，2N×nU，2N×nD，nL×2N，nR×2N等不規(guī)則尺寸模式劃分統(tǒng)一用nN×mM表示，同時定義幀間2N×2N，N×N等規(guī)則尺寸模式劃分統(tǒng)一用N×N表示。

表1 N×N、nN×mM分別在SD、HD深度下的概率統(tǒng)計Table 1 Statistics of N×N and nN×mM at depths of SD and HD respectively %

分析上表可知，當視頻處于SD深度時，幀間規(guī)則的劃分模式的比例高達87.32%～94%，而幀間不規(guī)則的劃分模式比例僅達6%～12.68%；而在視頻處于HD深度時，幀間規(guī)則的劃分模式比例達66.22%～85.53%，幀間不規(guī)則模式比例達14.47%～33.78%。明顯可以看出在深度SD下規(guī)則劃分遠遠大于深度為HD下的規(guī)則劃分，深度SD下的不規(guī)則劃分遠遠小于深度HD下的不規(guī)則劃分。在深度SD下，不規(guī)則劃分比例最高不超過13%，即在深度SD下，不規(guī)則劃分可以適當優(yōu)化，進行跳過；且BasketballDrill (分辨率832×480)是籃球比賽場景，運動較劇烈，紋理相對簡單，在HD深度下不規(guī)則的模式比例達27.44%；ChinaSpeed (分辨率1 024×768)是游戲中賽車場景，紋理細膩，運動特性劇烈，在HD深度下不規(guī)則的模式比例達33.78%；KristenAndSara (分辨率為1 280×720)是會議對話場景，運動簡單，人物只有面部表情變化，紋理簡單，在HD深度下不規(guī)則的模式比例僅達14.47%；BQTerrace(分辨率為1 920×1 080)是茶餐廳場景，背景簡單，運動量較小，紋理較復雜，在HD深度下不規(guī)則的模式比例達28.04%；Traffic (分辨率為2 560×1 600)是大樓和馬路，背景固定，運動不復雜，紋理簡單，在HD深度下不規(guī)則的模式比例達27.85%。所以在不同紋理復雜度下，處于HD深度的不規(guī)則模式的比例有所不同，復雜場景下不規(guī)則塊明顯偏高。針對以上分析，可以對不同深度的視頻跳過不規(guī)則的PU模式選擇過程，達到優(yōu)化目的，在SD深度下不規(guī)則塊模式可以忽略；在HD深度下，不規(guī)則塊模式是否可忽略需要進一步分析。

2.2 基于時空域的PU特性分析

視頻在時空域呈現一定的特性，如圖3是QP為32時ChinaSpeed視頻序列的第5幀的部分截圖，如圖4是QP為32時ChinaSpeed視頻序列的第6幀部分截圖，圖3和圖4同一視頻中前后相鄰兩幀正常編碼的視頻圖像，利用分析軟件[13]框出了每一個CU的PU大小。從圖3和圖4可以看出，當前塊為SD深度的周圍(左邊、上鄰域)，很少出現不規(guī)則的PU劃分方式，而當前塊為HD深度的周圍存在不規(guī)則的劃分方式明顯偏多。對比圖3和圖4在時域同一位置處，當前塊位于深度為SD，且PU模式為規(guī)則劃分，其相鄰同位塊的PU模式的劃分方式也都是規(guī)則劃分；而深度位于HD，當前PU雖為規(guī)則劃分，其相鄰同位塊的PU模式不一定為規(guī)則劃分模式。

圖3 QP為32時ChinaSpeed視頻序列的第5幀Fig.3 Frame 5 of ChinaSpeed video sequence under QP=32

圖4 QP為32時ChinaSpeed視頻序列的第6幀Fig.4 Frame 6 of ChinaSpeed video sequence under QP=32

經過上述直觀的觀察后，為進一步驗證，編碼了不同級別視頻各10幀進行測試，測試的量化參數QP設置32，CTU尺寸設置為64，最大深度設置3，編碼配置為LD模式[14]。定義上一幀同位PU規(guī)則劃分為事件A，當前幀周圍鄰域規(guī)則劃分為事件B，當前幀PU規(guī)則劃分為事件C，P(C|A)表示在A事件發(fā)生的情況下，B事件發(fā)生的概率，P(C|B)同理。統(tǒng)計數據如表2所示。

表2 在QP為32時條件概率P(C|A)、P(C|B)統(tǒng)計Table 2 Statistics of conditional probability P (C | A) and P (C | B)under QP = 32 %

一般當前CU的鄰域深度越深，即有較多HD深度出現時，說明當前塊的紋理復雜度越高，可以通過鄰域深度特性得知當前塊的復雜度。通過不同級別視頻下所得出的數據，在深度為SD下，P(C|A)的值處于97.88%～99.21%，在深度為HD下，P(C|A)的值處于82.64%～89.31%，在深度為SD下，P(C|B)的值處于95.21%～98.93%，在深度為HD下，P(C|B)的值處于81.46%～91.26%?？芍卩徲蚓哂袕碗s紋理特性時，深度HD下的視頻序列其可能劃分成不規(guī)則塊的比例明顯偏高；在鄰域具有簡單紋理特性時，在深度為SD下，大都是規(guī)則塊劃分；則可以對紋理復雜塊和簡單塊的PU模式進一步優(yōu)化。所以可以對具有不同紋理、不同運動特性的視頻制定自適應的幀間模式優(yōu)化方案。若當前運動和紋理特性都簡單，可以跳過不規(guī)則的劃分方式，否則需要在HD深度下對紋理復雜的塊，進行不規(guī)則的PU劃分方式的遍歷。

2.3 基于深度特性的幀間預測模式快速算法

通過上節(jié)的分析，可以制定幀間預測模式的快速算法，算法將針對不同紋理復雜度的CTU制定自適應的PU模式算法。首先需要進行當前區(qū)域復雜度的判斷，通過統(tǒng)計上一幀相鄰同位CTU的深度和當前空域相鄰CTU的深度，來確定當前CTU的復雜度，具體地，如圖5所示。

圖5 當前CTU的時空關系圖Fig.5 Current CTU spatiotemporal diagram

CTUcur為當前CTU，CTUabove為當前CTU的上方CTU，CTUleft為當前CTU的左方CTU，CTUabove-left為當前CTU左上方CTU，CTUabove-right為當前CTU右上方CTU，CTUcol為當前CTU的同位參考CTU。當前相鄰幀的同位CTU的深度值用dcol表示，當前空間上鄰域CTU深度值用da表示，當前空間左鄰域CTU深度值用dl表示，若dcol值為3或者da和dl的值為2或3，即認定當前CTU為復雜塊；然后根據不同復雜度CTU在不同深度進行不同的PU模式遍歷。當前CTU復雜度δ計算方式見式(2)。

具體算法實現步驟如下：

(1) 按式(2)判斷當前CTU紋理是否復雜，若復雜，進行第(2)步；若簡單，進行第(3)步。

(2) 若當前CU深度為SD，嘗試進行幀間2N×2N等規(guī)則劃分，分別計算率失真代價，并跳過其他不規(guī)則模式劃分，從規(guī)則劃分模式中計算最優(yōu)的率失真代價，將其劃分模式作為當前最佳PU模式；若當前深度為HD，遍歷所有的幀間PU模式，計算最優(yōu)的率失真代價，將其劃分模式作為當前最佳PU模式；進行第(4)步。

(3) 對所有深度下的CU進行幀間2N×2N，N×N等規(guī)則模式劃分，分別計算率失真代價，并跳過其他不規(guī)則模式劃分，從規(guī)則劃分模式中計算最優(yōu)的率失真代價，將其劃分模式作為當前最佳PU模式；進行第(4)步。

(4) 當前CU深度小于3，若是，則按步驟(1)進行子CU的PU遍歷；若否，結束劃分過程。

3 實驗與結果分析

在操作系統(tǒng)為Windows10，CPU為Inter? Core?i5-38300H @ 2.3GHz，內存8 G的硬件平臺下進行了仿真實驗，配置主要參數為：最大編碼單元尺寸為64×64(深度d = 3)，編碼配置為低時延和隨機訪問，量化參數(QP)為22、27、32和37，通過HEVC測試軟件HM16.9對算法進行了仿真實驗。本文測試了不同分辨率下的5種級別視頻序列，根據分辨率的不同，2 560×1 600為Class A，1 920×1 080為Class B，832×480為Class C，416×240為Class D，1 280×720為Class E。

本算法采用的評價標準為平均峰值信噪比BD-PSNR和BD-Bitrate[15]，平均編碼時間時間差為 Δt，見式(3)。

其中， QPi∈{22, 27, 32, 37}， to(QPi)表示HM16.9算法在 QPi的編碼時間，ts(QPi) 表示本文算法在Q Pi的編碼時間。本算法與標準對比實驗結果見表3。從表3中可以看出，在低時延編碼結構配置下，5個級別的視頻序列在本文算法下相比HM16.9，編碼時間節(jié)省了25.7%～31.72%，平均降低了28.6%，同時BDPSNR平均下降了0.03 dB，BDBR平均增加了1.1%；在隨機接入編碼結構配置下，編碼時間節(jié)省了19.4%～28.7%，平均降低了23.6%，同時BDPSNR平均下降了0.02 dB，BDBR平均增加了0.73%。特別是，對于不同級別的視頻均不會造成大的誤碼率，時間節(jié)省大致相同且效果明顯，對于各類場景及分辨率下的視頻具有通用性。

表3 實驗仿真結果Table 3 Experimental results

為了展現本算法對編碼器編碼性能的影響，本文做出HM16.9和本文算法下編碼器的RD曲線，圖6和圖7是不同級別的視頻序列的RD曲線。從圖6和圖7中可以看出，在不同級別的視頻序列中，本算法的RD曲線與HM16.9的RD曲線基本重合，相差微小，這說明本算法對比HM16.9來說，編碼器的編碼性能基本不變，即對率失真曲線的影響極小。本算法可以在保證編碼性能不受太大影響的條件下，對降低編碼時間取得較顯著的效果。且不同視頻序列下，比特損失，節(jié)省時間差異不大，可應用于各類場景下，通用性強。

圖6 隨機接入配置下RD曲線Fig.6 RD performance with random access

圖7 低時延配置下RD曲線Fig.7 RD performance with low delay

4 結語

本文深入研究了幀間預測模式的流程，分析不同場景不同深度下視頻序列的幀間PU模式，提出基于深度特性的幀間預測快速算法。通過統(tǒng)計不同深度下PU劃分特性，對深度進行分層為SD區(qū)和HD區(qū)，對紋理簡單的塊只進行規(guī)則劃分；對于紋理復雜的塊進行不同深度的細化，在SD深度下，只進行規(guī)則劃分，在HD深度下，遍歷所有不規(guī)則的劃分。實驗結果表明，本文提出的算法與HM16.9相比，在基本不影響視頻編碼質量情況下，可以顯著降低了編碼時間，對于各類場景及分辨率下的視頻具有通用性。