基于深度預測的HEVC編碼單元快速劃分算法

趙 宏 蔣雨晨 李靖波

(蘭州理工大學計算機與通信學院 甘肅 蘭州 730050)

基于深度預測的HEVC編碼單元快速劃分算法

趙 宏 蔣雨晨 李靖波

(蘭州理工大學計算機與通信學院 甘肅 蘭州 730050)

高效視頻編碼HEVC(High Efficiency Video Coding)采用計算復雜度較高的率失真優化方法對編碼單元CU(Coding Unit)劃分進行判決，具有較高的時間復雜度，編碼所需時間較長。為降低HEVC編碼復雜度，加快編碼速度，提出一種基于深度預測的CU快速劃分算法。首先依據當前CU與周圍相鄰CU和參考幀中當前位置CU的深度相關性，預測當前CU的最優深度，然后使用相鄰相關分割法或依據當前CU深度和預測深度的關系對當前CU進行遞歸劃分。為減少預測帶來的誤判，在CU深度級別由2級到3級的劃分中，使用率失真或百分比的方式進行二次判定。實驗結果表明，該算法與原始的HEVC編碼方法相比，在亮度峰值信噪比減小0.07 dB，編碼比特率增加0.88%的情況下，整體編碼單元劃分時間縮短37.7%，具有較高的時間效率。

高效視頻編碼(HEVC) 深度預測 快速劃分 編碼單元(CU)

0 引 言

高效視頻編碼HEVC主要面向高清(1 920×1 080)，甚至超高清分辨率(7 680×4 320)視頻的應用[1-2]。為了更有效地對視頻信息進行壓縮，HEVC在沿用經典的基于塊的混合編碼方式的基礎上，采用靈活的四叉樹結構組織編碼單元CU(Coding Unit)、預測單元PU和變換單元TU(Transform Unit)[3]，其中，CU是編碼的基本單元，大小是以2的冪次方為寬高的正方形，有64×64、32×32、16×16、8×8等四種尺寸，對應深度級別分別為0級到3級。按照四叉樹結構，采用遞歸的方式對CU進行劃分，使得HEVC編碼效率得到顯著提高，但編碼復雜度也隨之增加。

HEVC標準測試模型HM10[4]在對測試場景進行仿真編碼時，按照四叉樹結構，由64×64的最大編碼單元開始，采用遞歸的方式對CU進行劃分。通過遍歷每一個深度的CU，并使用所有可能的預測模式計算其率失真代價RD-Cost(Rate Distortion Cost)，選擇最小RD-Cost的劃分結構作為最佳CU劃分模式，這一過程導致較高的計算復雜度。文獻[5-6]通過在CU劃分過程中設置閾值，并且和率失真代價相比較，確定是否進一步劃分，這種方式并未考慮視頻圖像紋理的特殊性，同時對視頻壓縮質量影響較大。文獻[7-8]分別從幀內預測和幀間預測的角度，對CU劃分進行預判，但是忽略了在特定深度區間上提前終止CU分割。

本文提出一種基于深度預測的CU快速劃分算法。該算法根據Cur_CU(當前編碼CU)的Left_CU(與左邊界相鄰的CU)和Up_CU(與上邊界相鄰的CU)以及Col_CU(參考幀中當前位置CU)的深度來預測Cur_CU的最優深度，依據當前深度與預測深度的關系決定是否對Cur_CU繼續劃分，減少不必要的遍歷和率失真代價計算，以保證壓縮后視頻質量為前提，最大程度降低計算復雜度，縮短視頻編碼時間。

1 HM中CU劃分及復雜度分析

文獻[9]詳細介紹了HM10的CU劃分過程。HM10中，首先分割一幀圖像為若干最大編碼單元LCU(Largest CU)，LCU尺寸為64×64，深度為0。對LCU計算其RD-Cost，然后將LCU分割成4個尺寸為32×32，深度為1的子CU，并分別計算其RD-Cost。之后以Z字形掃描順序，按照深度優先的方式對4個子CU繼續劃分，直至子CU尺寸為8×8，深度為3時結束。對已完成劃分的LCU，從深度為3的子CU開始，采用率失真優化方法進行劃分模式判決，如果4個8×8子CU的RD-Cost之和小于其對應的16×16的父CU的RD-Cost，則保留這個8×8分割，否則合并為16×16的模式。按照這種方式，逐級向上處理，回溯至深度為0的LCU時，判決結束。率失真是指編碼的碼率與圖像失真度之間的相互關系，率失真代價函數定義為：

J(CUd)=(SSEluma+wChroma·SSEChroma)+λd·Bd

(1)

其中，d是Cur_CU的深度，Bd是編碼Cur_CU的候選預測模式中的總比特數，λd表示拉格朗日乘數。在幀內預測中，wchroma為0.57[10-11]，SSEluma和SSEchroma分別是亮度和色度的原始輸入圖像塊和預測塊之間的誤差平方和，如式(2)所示：

(2)

其中，IO(i,j)是原始輸入圖像塊的像素值，IR(i,j)是重建塊的像素值。

在HM10的CU劃分過程中，確定LCU的最優四叉樹結構，需要遍歷85種CU模式(1個64×64模式，4個32×32模式，16個16×16模式，64個8×8模式)[12]，并且需進行106(85+16+4+1)次相關RD-Cost計算和比較。在計算RD-Cost時，每一種CU模式又需遍歷35種幀內預測模式，以及4×4、8×8像素等不同大小的TU模式[13]。如此帶來的計算復雜度，限制了HEVC的實際應用。因此，以不降低視頻質量為前提，為HEVC編碼建立一種快速CU劃分算法，是非常必要的。

2 基于深度預測的CU劃分算法

2.1CU深度預測

HM10中，CU的深度級別為0到3，深度較大的CU模式適用于處理圖像紋理較復雜的區域，深度較小的CU模式適用于處理平滑區域。對比區域圖像紋理特性與其CU模式發現，如圖1所示，Cur_CU的最優深度與其Unit單元(左上角8×8像素塊)關于左邊界線對稱的8×8像素塊所在的最小編碼單元Left_CU的深度left_dep，關于上邊界線對稱的8×8像素塊所在的最小編碼單元Up_CU的深度up_dep以及在參考幀中當前位置的8×8像素塊所在的最小編碼單元Col_CU的深度col_dep存在密切關系。已知left_dep，up_dep和col_dep，定義通過式(3)和式(4)可得到Cur_CU的預測深度pre_dep。依據pre_dep和cur_dep(Cur_CU的當前深度)的關系，確定是否對Cur_CU進一步劃分。

圖1 CU深度預測

temp=α·left_dep+β·up_dep+γ·col_dep

(3)

(4)

其中，α、β、γ分別為Left_CU、Up_CU和Col_CU的預測代價，且滿足α+β+γ=1。通過對JCTVC提供的通用標準測試序列進行觀察統計，驗證α=0.2、β=0.2、γ=0.6為較優取值。

2.2 基于深度預測的CU劃分判決

將Cur_CU所在的LCU表示為Cur_LCU，同理可得Left_LCU、Up_LCU和Col_LCU。分別用dep1、dep2表示與Cur_CU左邊界和上邊界相鄰的所有CU(不包含left_CU和Up_CU)的最大深度，用dep3表示Col_CU中子CU的最大深度。獲得Cur_CU的預測深度pre_dep后，若滿足cur_dep=pre_dep=0或cur_dep=pre_dep=1，且dep1≤2&&dep2≤2&&dep3≤1，即Cur_CU的預測深度pre_dep、相鄰CU的最大深度dep1和dep2以及Col_CU中子CU的最大深度dep3都比較小，說明Cur_CU內部及其相鄰區域的紋理特性都比較簡單，此時可終止對Cur_CU的劃分。

當cur_dep=pre_dep=0或cur_dep=pre_dep=1,而dep1=3||dep2=3||dep3≥2時，說明Cur_CU內部總體較平滑，但在邊緣位置可能存在紋理較復雜的區域。此時采用相鄰相關分割法對Cur_CU進行劃分。即參照相關CU的深度，直接將Cur_CU邊緣紋理復雜區域劃分至相應深度，之后采用率失真優化方法進行驗證，以消除誤判。

相鄰相關分割法中涉及平滑區域與復雜區域的邊界在相鄰CU中的分布，分別有三種情況，如圖2所示。由于每幀圖片中的圖像紋理特性具有隨機性，所以絕大部分情況如圖2中a或c所示，即相鄰CU公共邊附近區域的紋理復雜度差異性較小。

圖2 復雜區域與平滑區域邊界分布

相鄰相關分割法 如圖3所示，Up_LCU和Left_LCU為已編碼的LCU。假設編碼前Cur_CU的深度cur_dep=0，且求得pre_dep=0。由于與Cur_CU左邊界相鄰的2、4號CU的深度較大，預測Cur_CU中左下角陰影部分為紋理復雜區域，深度與相鄰2、4號CU的深度相等，虛線部分為預劃分結果。但實際可能出現以下情況，復雜區域與平滑區域的邊界包含于2、4號CU或陰影部分中，邊界的左側是復雜區域，右側是平滑區域，這種情況將導致對Cur_CU中陰影部分深度的誤判。為消除這種誤判，對預劃分結果使用率失真優化方法進行驗證，決定是否合并不必要的劃分，逐級向上判斷，確定最優CU模式。

圖3 相鄰相關分割法圖例

如果pre_dep>cur_dep，采用遞歸的方式對Cur_CU進行劃分，在深度級別0到1和1到2的劃分過程中，不采取任何判斷，直接劃分。深度較大的CU模式計算復雜度高，編碼時間長，因此在深度級別2到3的劃分過程中，需進一步驗證以減少誤判。首先通過計算參考幀中Col_CU所在的深度為1的CU中，深度為3的CU所占百分比pro，預測Cur_CU的紋理復雜程度。如果pro大于50%，表明該區域紋理特性復雜，可以直接劃分。如果pro小于50%，則采取率失真優化方法，判斷是否需要進一步劃分。

2.3 基于深度預測的CU快速劃分算法的整體流程

對于一幀圖像，首先將其完全分割為若干LCU，然后以Z掃描順序對所有LCU進行劃分。劃分過程中，最先輸入的Cur_CU是LCU，然后獲取相應Left_CU、Up_CU及Col_CU的深度并計算Cur_CU的預測深度pre_dep。如果pre_dep較小，而周邊相鄰CU深度較大，采用相鄰相關分割法對Cur_CU進行劃分；如果pre_dep較大，采用遞歸的方式進行劃分。算法具體流程如圖4所示。

圖4 算法整體流程圖

算法具體流程如下：

Step1 輸入當前需編碼的Cur_CU。

Step2 確定其Left_CU、Up_CU以及Col_CU，并獲得相應深度left_dep、up_dep和col_dep。

Step3 根據式(3)和式(4)計算Cur_CU的預測深度pre_dep。

Step4 如果cur_dep=pre_dep=0或cur_dep=pre_dep=1，轉Step5，否則轉Step6。

Step5 如果滿足條件dep1≤2&&dep2≤2&&dep3≤1轉Step11，否則轉Step6。

Step6 采用相鄰相關分割法分割Cur_CU，轉Step11。

Step7 如果cur_dep=pre_dep=2，轉Step11。

Step8 如果cur_dep<2&&pre_dep>cur_dep,分割Cur_CU為4個子CU，按照Z字形掃描順序分別表示為CU1、CU2、CU3、CU4，以CU1、CU2、CU3、CU4為輸入的Cur_CU并轉Step1。

Step9 如果cur_dep=2&&pre_dep=3，求出參考幀中Col_CU所在的深度為1的CU中，深度為3的CU所占百分比pro。如果pro大于50%，分割Cur_CU為4個子CU，轉Step11，否則轉Step10。

Step10 將Cur_CU預劃分為4個子CU，按照Z字形掃描順序分別表示為CU1、CU2、CU3、CU4，如果滿足RD_Cost(Cur_CU)>RD_Cost(CU1) + RD_Cost(CU2) + RD_Cost(CU3) + RD_Cost(CU4)，分割Cur_CU為4個子CU，之后轉Step11，否則直接轉Step11。

Step11 終止CU劃分，轉Step12。

Step12 結束。

3 實驗結果及分析

在HEVC標準測試模型HM10中添加本文算法，同HEVC原有編碼算法進行對比測試。實驗測試平臺為：處理器Intel Core i5，主頻2.6 GHz，內存4 GB，操作系統64位windows7。實驗采用4個JCTVC提供的通用標準測試序列，分別為BasketballDrive_1920x1080, ChinaSpeed_1024x768，CITY_704x576以及CREW_352x288。 實驗在encoder_intra_main配置下進行，量化參數QP值分別設置為22,27,32和37。實驗中，編碼性能使用比特率BR(Bit Rate)和峰值信噪比PSNR(Peak Signal to Noise Ratio)度量，編碼復雜度使用消耗的編碼時間度量。本文使用亮度峰值信噪比增量(▽PSNR(Y))、編碼比特率增量(▽BR)和編碼時間增量(▽T)三個參數作為評價指標[14]，對比本文算法和HM10原有的編碼算法，其計算公式如下：

▽PSNR(Y)=PSNR(Y)p-PSNR(Y)HM10

(5)

(6)

(7)

其中，PSNR(Y)p，Bp和Tp是本文提出的快速劃分算法的亮度分量的PSNR，比特率和總編碼時間；PSNR(Y)HM10.0，BHM10.0和THM10.0是HM10原有編碼算法的亮度分量的PSNR，比特率和總編碼時間。

如表1所示，在encoder_intra_main配置和不同QP值情況下，相比于HM10原有的編碼算法，本文采用的基于深度預測的CU快速劃分算法通過預測和判斷，跳過部分深度級CU的預劃分和率失真代價計算，避免額外的計算量，使得編碼效率明顯提高。在相同測試序列的不同QP值配置下，隨著QP值的增加，編碼比特率增量依次遞減，但節省的編碼時間卻在逐漸增加。對于整體的編碼效率，CU劃分時間平均減少37.37%，編碼比特率平均增加0.88%，而亮度峰值信噪比增量的波動范圍很小，僅減少0.07dB，本文算法在幾乎不影響視頻質量的情況下，降低了編碼復雜度，具有時間效率。

表1 本文算法與HM10編碼算法性能比較

續表1

4 結 語

HM10原有的CU劃分過程計算復雜度高，編碼效率低。針對該問題，本文提出一種CU快速劃分算法，通過參考與當前CU左邊界和上邊界相鄰的CU以及參考幀中當前位置的CU的深度，預測當前CU的最優深度，根據預測的最優深度對當前CU進行劃分，跳過不必要的CU遍歷和率失真代價比較。實驗結果驗證了本文算法的高效性，相比HM10原有的編碼算法，可在編碼比特率平均上升0.88%的情況下，編碼單元劃分時間縮短37.37%，在幾乎不影響視頻質量的情況下，縮短編碼時間，降低編碼復雜度，具有良好的實際應用價值。

本文優化算法的實質是在視頻壓縮質量和編碼時間之間做一個均衡，通過反復的對比實驗和算法改進，實現在對視頻壓縮質量影響較小的前提下，加快編碼速度，縮短編碼時間，最終達到實際應用。本文根據相鄰圖像幀的相同位置以及同一圖像幀中相鄰區域的紋理特征的相關性，在CU劃分中增加預判過程。預判過程不可能達到每次都能準確的判斷，總會存在一定概率的誤判，如果在圖像紋理復雜區域誤判出CU的深度較小，將導致該區域編碼失真，影響編碼后的畫面質量。本文通過采用相鄰相關分割算法雖然可以大幅減少誤判，但誤判無法從根本上消除。因此，本文方法的缺點之一為產生誤判導致的編碼失真，但在編碼總體效果上是可以接受的。此外，本文的優化算法建立在HM10的基礎上，在其他HEVC模型中的應用效果需要做進一步驗證。

[1] 雷海軍,危雄,楊張,等.一種快速HEVC幀內預測模式決策算法[J].計算機工程,2014,40(5):270-273.

[2] Wiegand T,Ohm J R,Sullivan G J,et al.Special Section on the Joint Call for Proposals on High Efficiency Video Coding (HEVC) Standardization[J].IEEE Transactions on Circuits and Systems for Video Technology,2010,20(12):1661-1666.

[3] Bross B,Han W J,Ohm J R,et al.High Efficiency Video Coding (HEVC) text specification draft 10 (for FDIS & Consent)[C]//12th Joint Collaborative Team on Video Coding Meeting,Geneva,Switzerland,2013:179-201.

[4] McCann K,Bross B,Han W J,et al.High Efficiency Video Coding (HEVC) Test Model 10 (HM 10) encoder description[C]//12th Joint Collaborative Team on Video Coding Meeting,Geneva,Switzerland,2013:195-234.

[5] Cassa M B,Naccari M,Pereira F.Fast rate distortion optimization for the emerging HEVC standard[C]//Proceedings of 2012 Picture Coding Symposium. Piscataway,NJ,USA:IEEE,2012:493-496.

[6] Kim J,Choe Y,Kim Y G.Fast coding unit size decision algorithm for intra coding in HEVC[C]//2013 IEEE International Conference on Consumer Electronics (ICCE),Las Vegas,NV,USA,2013:637-638.

[7] Cho S,Kim M.Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[J].IEEE Transactions on Circuits and Systems for Video Technology,2013,23(9):1555-1564.

[8] Tan H L,Liu F,Tan Y H,et al.On fast coding tree block and mode decision for High-Efficiency Video Coding (HEVC)[C]//2012 IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP),Kyoto,Japan,2012:825-828.

[9] 齊美彬,陳秀麗,楊艷芳,等.高效率視頻編碼幀內預測編碼單元劃分快速算法[J].電子與信息學報,2014,36(7):1699-1705.

[10] Shen L,Zhang Z,An P.Fast CU size decision and mode decision algorithm for HEVC intra coding[J].IEEE Transactions on Consumer Electronics,2013,59(1):207-213.

[11] 李維,張和仙,楊付正.高效率視頻編碼快速模式判決算法[J].西安交通大學學報,2013,47(8):104-109,140.

[12] 趙亮.HEVC幀內模式決策及其核心技術的研究[D].哈爾濱:哈爾濱工業大學,2011.

[13] 蔣剛毅,楊小祥,彭宗舉,等.高效視頻編碼的快速編碼單元深度遍歷選擇和早期編碼單元裁剪[J].光學精密工程,2014,22(5):1322-1330.

[14] 李元,何小海,鐘國韻,等.一種基于時域相關性的高性能視頻編碼快速幀間預測單元模式判決算法[J].電子與信息學報,2013,35(10):2365-2370.

FAST PARTITION ALGORITHM FOR HEVC CODING UNIT BASED ON DEPTH PREDICTION

Zhao Hong Jiang Yuchen Li Jingbo

(SchoolofComputerandCommunication,LanzhouUniversityofTechnology,Lanzhou730050,Gansu,China)

A rate-distortion optimization method with high computational complexity is used for CU (coding unit) mode decision in HEVC (High Efficiency Video Coding), which has high time complexity and needs a long encoding time. In order to decrease the coding complexity of HVEC and accelerate the coding speed, a CU fast partition algorithm based on depth prediction is proposed. First, according to the depth correlation between the current CU and the surrounding CU and the current position CU in the reference frame, the optimal depth of the current CU is predicted. Then, the adjacent splitting method or partition decisions based on the relationship between the current depth and the predict depth of the current CU are used to split recursively the current CU. In order to reduce the misjudgment caused by the prediction, in the CU depth level by the two to three levels of division, we use rate distortion or percentage of the way to determine again. Experimental results show that compared with the original HEVC coding method, the algorithm reduced the coding time by 37.7% when the peak signal-to-noise ratio is reduced by 0.07 dB and the coding bit rate is increased by 0.88%, which has high time efficiency.

High efficiency video coding (HEVC) Depth prediction Fast partition Coding unit (CU)

2016-01-14。國家自然科學基金項目(61262016)；甘肅省高校基本科研基金項目(14-0220)；甘肅省自然科學基金項目(1208RJZA239)。趙宏，教授，主研領域：網格計算，視頻，智能信息處理，嵌入式。蔣雨晨，碩士生。李靖波，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.05.040