趙 宏 蔣雨晨 李靖波

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

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

趙 宏 蔣雨晨 李靖波

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

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

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

0 引 言

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

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

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

1 HM中CU劃分及復(fù)雜度分析

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

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

(1)

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

(2)

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

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

2 基于深度預(yù)測的CU劃分算法

2.1CU深度預(yù)測

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

圖1 CU深度預(yù)測

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

(3)

(4)

其中，α、β、γ分別為Left_CU、Up_CU和Col_CU的預(yù)測代價，且滿足α+β+γ=1。通過對JCTVC提供的通用標(biāo)準(zhǔn)測試序列進行觀察統(tǒng)計，驗證α=0.2、β=0.2、γ=0.6為較優(yōu)取值。

2.2 基于深度預(yù)測的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的預(yù)測深度pre_dep后，若滿足cur_dep=pre_dep=0或cur_dep=pre_dep=1，且dep1≤2&&dep2≤2&&dep3≤1，即Cur_CU的預(yù)測深度pre_dep、相鄰CU的最大深度dep1和dep2以及Col_CU中子CU的最大深度dep3都比較小，說明Cur_CU內(nèi)部及其相鄰區(qū)域的紋理特性都比較簡單，此時可終止對Cur_CU的劃分。

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

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

圖2 復(fù)雜區(qū)域與平滑區(qū)域邊界分布

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

圖3 相鄰相關(guān)分割法圖例

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

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

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

圖4 算法整體流程圖

算法具體流程如下：

Step1 輸入當(dāng)前需編碼的Cur_CU。

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

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

Step4 如果cur_dep=pre_dep=0或cur_dep=pre_dep=1，轉(zhuǎn)Step5，否則轉(zhuǎn)Step6。

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

Step6 采用相鄰相關(guān)分割法分割Cur_CU，轉(zhuǎn)Step11。

Step7 如果cur_dep=pre_dep=2，轉(zhuǎn)Step11。

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

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

Step10 將Cur_CU預(yù)劃分為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，之后轉(zhuǎn)Step11，否則直接轉(zhuǎn)Step11。

Step11 終止CU劃分，轉(zhuǎn)Step12。

Step12 結(jié)束。

3 實驗結(jié)果及分析

在HEVC標(biāo)準(zhǔn)測試模型HM10中添加本文算法，同HEVC原有編碼算法進行對比測試。實驗測試平臺為：處理器Intel Core i5，主頻2.6 GHz，內(nèi)存4 GB，操作系統(tǒng)64位windows7。實驗采用4個JCTVC提供的通用標(biāo)準(zhǔn)測試序列，分別為BasketballDrive_1920x1080, ChinaSpeed_1024x768，CITY_704x576以及CREW_352x288。 實驗在encoder_intra_main配置下進行，量化參數(shù)QP值分別設(shè)置為22,27,32和37。實驗中，編碼性能使用比特率BR(Bit Rate)和峰值信噪比PSNR(Peak Signal to Noise Ratio)度量，編碼復(fù)雜度使用消耗的編碼時間度量。本文使用亮度峰值信噪比增量(▽PSNR(Y))、編碼比特率增量(▽BR)和編碼時間增量(▽T)三個參數(shù)作為評價指標(biāo)[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原有的編碼算法，本文采用的基于深度預(yù)測的CU快速劃分算法通過預(yù)測和判斷，跳過部分深度級CU的預(yù)劃分和率失真代價計算，避免額外的計算量，使得編碼效率明顯提高。在相同測試序列的不同QP值配置下，隨著QP值的增加，編碼比特率增量依次遞減，但節(jié)省的編碼時間卻在逐漸增加。對于整體的編碼效率，CU劃分時間平均減少37.37%，編碼比特率平均增加0.88%，而亮度峰值信噪比增量的波動范圍很小，僅減少0.07dB，本文算法在幾乎不影響視頻質(zhì)量的情況下，降低了編碼復(fù)雜度，具有時間效率。

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

續(xù)表1

4 結(jié) 語

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

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

[1] 雷海軍,危雄,楊張,等.一種快速HEVC幀內(nèi)預(yù)測模式?jīng)Q策算法[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] 齊美彬,陳秀麗,楊艷芳,等.高效率視頻編碼幀內(nèi)預(yù)測編碼單元劃分快速算法[J].電子與信息學(xué)報,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].西安交通大學(xué)學(xué)報,2013,47(8):104-109,140.

[12] 趙亮.HEVC幀內(nèi)模式?jīng)Q策及其核心技術(shù)的研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2011.

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

[14] 李元,何小海,鐘國韻,等.一種基于時域相關(guān)性的高性能視頻編碼快速幀間預(yù)測單元模式判決算法[J].電子與信息學(xué)報,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。國家自然科學(xué)基金項目(61262016)；甘肅省高校基本科研基金項目(14-0220)；甘肅省自然科學(xué)基金項目(1208RJZA239)。趙宏，教授，主研領(lǐng)域：網(wǎng)格計算，視頻，智能信息處理，嵌入式。蔣雨晨，碩士生。李靖波，碩士生。

TP3

A

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