一種改進的HEVC編碼單元劃分方法

謝曉燕，王 歡，石鵬飛

(西安郵電大學 計算機學院,陜西 西安 710061)

?

·信息科學·

一種改進的HEVC編碼單元劃分方法

謝曉燕，王 歡，石鵬飛

(西安郵電大學 計算機學院,陜西 西安 710061)

針對高效率視頻編碼(HEVC)幀內預測中的率失真優化(RDO)算法計算復雜度高的問題，該文提出了一種基于統計學的率失真優化的改進方法。通過對不同量化參數的率失真代價概率分布圖產生的閾值進行統計，得到最大編碼單元(LCU)劃分過程中不同深度的閾值方程，并利用該閾值提前終止編碼單元的劃分從而達到降低計算復雜度的目的。實驗表明該文所提出的改進方法與HEVC的測試模型HM10.0相比，在保證視頻質量和碼率基本不變的前提下(碼率僅增加了0.5%，Y-PSNR只降低了0.019dB)，減少了26.7%的編碼時間，提高了編碼效率。

HEVC；幀內預測；編碼單元劃分；率失真優化

近年來，數字視頻已經成為許多電子應用媒體的主要形式[1]，高清晰率、高幀率、高壓縮率的發展趨勢愈加明顯，而已頒布的視頻標準H.264/AVC在這些方面呈現出一定的局限性[2]。因此在2010年1月，ITU-T VCEG(video coding experts group)視頻編碼專家組和ISO/IEC MPEG(moving picture experts group)運動圖像專家組成立了JCT-VC(joint collaborative team on video coding)聯合小組，制定了新一代高效率視頻編碼標準：HEVC(high efficiency video coding)[3]，其核心目的是在H.264/AVC的基礎上，將壓縮效率提高一倍[4]。HEVC的設計繼續沿用了經典的基于塊的混合編碼方式，在編碼結構上，HEVC放棄了H.264/AVC中宏塊的概念，采用了具有四叉樹結構的編碼單元(CU)以及預測單元(PU)和變換單元(TU)。這使得HEVC的編碼性能和效率得到顯著的提高，但同時也增加了編碼的復雜度。

HEVC的測試模型(HEVC Test Model)HM[5]是由JCT-VC編寫的一個標準代碼庫，可以對不同的測試場景進行仿真編碼。HM采用了遞歸的方式對最大編碼單元(Largest CU, LCU)進行四叉樹結構的劃分[6]。在一個LCU塊中，遞歸遍歷所有深度的CU，根據拉格朗日率失真優化的策略選擇最佳的CU尺寸，實現LCU與相關PU塊的劃分[7]。雖然這種全部遍歷搜索的算法可以得到最優的編碼參數，但是它僅根據圖像的像素點信息進行LCU劃分，并且大大的增加了計算復雜度[8]。近年來，在相關領域眾多學者開展了大量優化研究來降低計算復雜度。文獻[9]提出了自適應CU深度遍歷的算法，利用空域相關性來預測當前編碼塊的深度值，而大部分的編碼塊還是要遍歷3個CU以上的深度，所以該方法節省的時間相當有限。文獻[10]采用時域空域相結合的預測方式，通過相鄰編碼塊深度值加權方式來預測當前編碼塊的深度值。雖然這種方法在很大程度上減少了遍歷范圍，但沒有考慮到不同視頻序列之間的差異性，用固定權重求得的預測深度與預先設定的遍歷區間仍存在一定的改善空間。文獻[11]利用CU四叉樹編碼的特點，縮短了參考像素和預測像素間的距離，提高了幀內預測的精度，針對紋理豐富的圖像，這種方法明顯提高了編碼效率，但對于一般的圖像沒有普適性。文獻[12]提出了一種基于CU深度的快速算法，主要通過前一幀同一位置編碼塊(co-located CTU)和當前編碼塊的時間相關性來預測當前LCU的深度，使得編碼時間平均減少了21.3%。但Lee的方法僅從時域考慮了co-located CTU的深度值對當前編碼塊的影響，可能會造成誤判的偏差。文獻[13]從幀內預測的角度出發，提出對CU自下而上的修剪進行預先判斷來提前終止LCU的劃分過程，但沒有考慮到在有限的深度遍歷區間上提前終止LCU劃分。

目前，大部分的研究僅停留在用時域和空域的相關性來預測當前編碼塊的深度，關于對率失真代價的優化研究并未深入開展。本文通過對不同深度間的率失真代價進行相關統計研究，提出一種基于統計學的率失真優化的改進方法。該方法與HEVC的測試模型HM10.0相比，使得優化后的結果在基本不改變圖像的質量與輸出碼率的情況下，編碼時間平均減少了26.7%。

1 HEVC的CU劃分編碼過程

HEVC創新的采用了具有四叉樹結構的編碼單元CU來提高幀內編碼精度，如圖1所示。在HM編碼器中，每一幀圖像都從LCU的劃分編碼開始，LCU作為CU劃分的根節點，其初始尺寸是64×64，深度Depth=0。通過對LCU進行預測編碼，可以得到其率失真代價RD-Cost(rate distortion cost)。接著對LCU進行分割，得到4個子CU，每個子CU的大小為32×32，深度Depth=1，對這4個子CU再分別進行預測編碼，得到各自的RD-Cost；如此遞歸的劃分下去，直到子CU的大小為8×8，劃分深度Depth=3時結束。

圖1 CU的劃分及對應的四叉樹結構Fig.1 CU split and the quard-tree structure

HEVC采用拉格朗日率失真優化的策略決定LCU最終四叉樹結構的劃分形式。這樣在不影響視頻質量的前提下得到最小的輸出碼率。率失真是指編碼的碼率與圖像失真度之間的相互關系,率失真代價函數J(CUd)定義如下

J(CUd)=SSE(s,c,m|QP)+

λ·R(s,c,m|QP)，

(1)

式中d是深度值,QP是量化參數,λ是拉格朗日乘子,R(·)是利用模式m進行編碼的比特數,SSE(·)是原始亮度塊與重建塊之間的差值平方和,如式2所示

(2)

其中,BlockA(i,j)為當前編碼塊s的像素值,BlockB(i,j)為重建塊c的像素值。

接著對已完成劃分的LCU進行自下向上修剪,如圖2所示。從Depth=3開始,如果4個8×8子CU的 RD-Cost之和小于其對應的16×16的父CU的 RD-Cost,則保留這個8×8的CU分割,否則繼續往上修剪。以此類推,直至回溯到Depth=0。

圖2 LCU的分割與修剪Fig.2 LCU splitting and prunning

采用 64×64的LCU四叉樹劃分方式比H.264采用的16×16宏塊劃分減少了12%的碼率[14];然而,在HM模型中要想確定一個LCU的最終劃分方式,則需要完成四叉樹的全遍歷,并進行40+41+42+43=85次CU尺寸選擇的RD-Cost計算,且每個CU還需要進行各種PU預測和幀內模式選擇的RD-Cost計算。這使得計算復雜度非常高,大大增加了編碼時間。

2 基于統計學的率失真優化方法

針對前節中的分析,提出一種基于統計學的率失真優化改進方法,通過對不同QP下的RD-Cost概率分布圖產生的閾值進行統計,得到LCU劃分過程中不同深度的閾值方程,利用該閾值來提前終止CU的劃分從而達到降低計算復雜度的目的。

通過在HM10.0上對視頻序列進行測試,對不同深度的CU在分割和不分割的情況下進行窮舉搜索,得到了RD-Cost概率分布圖。從圖3可以觀察到:不進行分割的CU率失真代價值偏小;而進行分割的CU率失真代價值比較高并且分布比較均勻。由此說明,一個CU若不能分割成子CU,它肯定比已劃分的CU擁有更小的RD-Cost值。因此,可以通過判斷RD-Cost是否低于某一閾值,來提前終止不必要的CU劃分。文獻[13]說明此閾值VQP正好是兩條曲線的交點所對應的率失真代價值,如圖3的測試序列在CU劃分深度Depth等于1時,其閾值VQP在35 000左右。圖3測試條件:視頻序列BQTerrace-1 920×1 080, QP=37,幀率60幀/s。

圖3 Depth=1時CU分割與不分割RD-Cost概率分布圖Fig.3 CU split and non-split RD-Cost probability distribution when Depth=1

因為不同的QP產生相應的RD-Cost概率分布,閾值一定隨著QP的變化而變化。基于上述的分析,對HM10.0代碼庫中自帶的18個通用視頻標準序列設定不同的QP,按公式3進行統計,得到不同劃分深度下的的閾值。

QP=0～51)

(3)

表1 不同深度的閾值表Tab.1 Threshold of different depth

為了能更直觀的描述QP與ThDepth=i之間的關系,將表1繪制成圖4所示的折線圖,橫坐標是量化參數QP,縱坐標是RD-Cost值,繪出的3條曲線分別是Depth等于0,1,2時的閾值。

從圖4可以清晰的看到閾值隨著QP增大而增大,Depth=0的曲線增長幅度最大,Depth=2的曲線增長幅度相對較小。其中的每條曲線都可以擬合為關于QP的指數函數,方程如下

ThDepth=0=1182e121·QP，

ThDepth=1=177.243e0.146·QP，

(4)

ThDepth=1=177.243e0.146·QP，

(5)

ThDepth=2=20.443e0.186·QP。

(6)

根據以上的實驗分析,可以通過閾值來提早結束LCU的劃分,改進后塊劃分的算法流程如下:

步驟1 計算Depth=0時LCU的RD-Cost值，記為RC0。

步驟2 判斷RC0是否小于Depth=0時的閾值ThDepth=0；若RC0< ThDepth=0，則終止當前LCU劃分，并對當前塊進行預測編碼，然后結束本次LCU劃分編碼；否則，直接跳過第0層編碼，執行步驟3，進入第1層編碼。

步驟3 進行一次四叉樹劃分，得到Depth=1時的4個子CU，并計算其RD-Cost值之和，記為RC1。

步驟4 判斷RC1是否小于Depth=1時的閾值ThDepth=1；若RC1< ThDepth=1，則終止當前LCU劃分，并對第1層CU進行選擇和預測編碼，然后結束本次LCU劃分編碼；否則，直接跳過第1層編碼，執行步驟5，進入第2層編碼。

步驟5 進行一次四叉樹劃分，得到Depth=2時的4個子CU，并計算其RD-Cost值之和，記為RC2。

步驟6 判斷RC2是否小于Depth=2時的閾值ThDepth=2；若RC2< ThDepth=2，則終止當前LCU劃分，并對第2層CU進行選擇和預測編碼，然后結束本次LCU劃分編碼；否則，直接跳過第2層編碼，執行步驟7，進入第3層編碼。

步驟7 進行一次四叉樹劃分，得到Depth=3時的4個子CU，進行塊選擇和預測編碼，然后結束本次LCU劃分編碼。

3 仿真與驗證

為了驗證文中所提方法的有效性,將改進的方法集成到HEVC的測試環境HM10.0上,在全I幀的結構下,采用18個通用視頻標準序列進行實驗,量化參數QP取值點分別為:22，27，32，37,每個序列測試10幀。這里主要從所提方法帶來的速度增益以及付出的相應代價——峰值信噪比與編碼碼率來考慮方法的性能,具體包括Δtime,Δbitrate和ΔY-PSNR[15]。

1)Δtime指本文所提出的方法與HM的編碼時間之差的百分比,編碼器計算復雜度的度量采用編碼器平均執行時間的減少量Δtime表示,定義如下

Δtime=

(7)

2)Δbitrate指本文所提出的方法與HM的編碼碼率之差的百分比,定義如下

Δbitrate=

(8)

其中,bitrateproposed(QPi)表示文中方法的編碼碼率,bitrateHM(QPi)表示HM編碼器得到的編碼碼率;編碼碼率越小說明視頻圖像的壓縮效率越好。

3)ΔY-PSNR指本文所提出的方法與HM的峰值信噪比的百分比,定義如下

Y-PSNRpro(QPi)×100%。

(9)

其中，Y-PSNRpro(QPi)表示文中方法的亮度峰值信噪比，Y-PSNRHM(QPi)表示HM編碼器得到的亮度峰值信噪比。PSNR表示視頻圖像的質量，PSNR越高，表明圖像的質量越好。

由于本文的方法是通過跳過部分編碼模式來達到減少計算復雜度的目的，所以從原理上講選擇出來的最終編碼模式有可能不是最優的，必然會導致編碼性能的降低，即峰值信噪比的下降或者輸出碼率增大。但是，所提出的方法在降低編碼時間的同時只有極小的峰值信噪比PSNR下降和很小的碼率bitrate增加。表2的數據可以看出本文所提出的方法與HM10.0相比，編碼時間平均減少了26.7%,而bitrate僅增加了0.5%，Y-PSNR只降低了0.019dB，可見對視頻圖像質量的影響非常小，可以忽略不計。因此，本文的方法在保證視頻質量和碼率幾乎不變的前提下，有效地降低了編碼時間，提高了編碼效率。

表2 節省的編碼時間與編碼質量的對比Tab.2 Differences of encoding time and coding efficiency

4 結 語

為了降低HEVC的計算復雜度， 本文提出了一種基于統計學的率失真優化方法，通過大量實驗統計獲得不同深度下的閾值，利用該閾值提前結束LCU的劃分。實驗結果證明本文的方法在保證視頻質量和碼率幾乎不變的前提下，節省了26.7%的編碼時間，提高了編碼效率，為將來多視點、高效率視頻編碼的研究及應用打下基礎。

[1] SHEN Li-quan, ZHANG Zhao-yang, AN Ping. Fast CU size decision and mode decision algorithm for HEVC intra coding[J].IEEE Transactions on Consumer Electronics,2013, 59(1):207-213.

[2] KIM J,CHOE Y,KIM Y G. Fast coding unit size decision algorithm for intra coding in HEVC[C]∥2013 IEEE International Conference Consumer Electronics(ICCE)，Piscataway:IEEE,2013:637-638.

[3] LAINEMA J, BOSSEN F, HAN W J,et al. Intra coding of the HEVC standard[J].IEEE Transactions on Circuits and Systems for video technology,2012, 22(12):1792-1801.

[4] 田小平,田永召. 面向交互應用的HEVC編碼性能分析[J].西安郵電大學學報,2014,19(3):6-10.

[5] 嚴順卿.HEVC幀內預測快速模式選擇算法研究[D].上海：上海交通大學，2012.

[6] SULLIVAN G.J,OHM J,WOO-JIN Han,et al.Overview of the high efficiency video coding (HEVC) standard[J].IEEE Transactions on Circuits and systems for video technology,2012,22(12):1649-16 68.

[7] JIANG Gang-yi, YANG Xiao-xiang, PENG Zong-ju, et al. Fast CU depth range selection and early CU pruning for HEVC[J].Optics and Precision Engineering,2014,22(5): 1322-1330.

[8] WEI Jiang ,MA Han-jie, CHEN Yao-wu.Gradient based fast mode decision algorithm for intra prediction in HEVC[C]∥2012 2nd International Conference on CECNet,Piscataway:IEEE,2012:1836-1840.

[9] LI X, AN J C, GUO X, et al.Adaptive CU depth range[C]∥5th JCT-VC Meeting, Geneva:[s.n.], 2011.

[10] SHEN L Q, LIU Z, ZHANG X P, et al.An effective CU size decision method for HEVC encoders[J].IEEE Transactions on Multimedia, 2013, 15(2):465-470.

[11] CAO Xiao-ran , LAI Chang-cai , WANG Yun-fei, et al. Short distance intra coding scheme for HEVC[C]∥Proceedings of Picture Coding Symposium.[s.l.]: IEEE Press, 2012: 501-504.

[12] LEE H S, KIM K Y,KIM T R,et al.Fast encoding algorithm based on depth of coding-unit for high efficiency video coding[J].Optical Engineering,2012,51(6):1-11.

[13] 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.

[14] BAI Cai-xia, YUAN Chun. Fast coding tree unit decision for HEVC intra coding[C]∥2013 IEEE ICCE China Workshop,Piscataway:IEEE,2013:28-31.

[15] 蔣潔,郭寶龍,莫瑋，等.利用平滑區域檢測的HEVC幀內編碼快速算 法[J].西安電子科技大學學報(自然科學版),2013,40(3):194-200.

(編 輯曹大剛)

An improved division method of HEVC coding units

XIE Xiao-yan, WANG Huan, SHI Peng-fei

(School of Computer, Xi′an University of Posts and Telecommunications, Xi′an 710061， China)

To further reduce the high computational complexity in High Efficiency Video Coding ( HEVC) intra prediction, an improved method of rate distortion optimization (RDO) based on statistics was proposed in this paper. Based on statistical analysis of the rate distortion cost under different quantization parameter probabilities distribution, threshold equations of different depths in the process of Large Code Unit (LCU) division were given, which were used to end the division of code unit, and then reduce the computational complexity. The experimental results show that, compared with HEVC HM10.0 testing models, the proposed algorithm can save an average 26.7% of encoding time with negligible loss of coding efficiency (only 0.5% bitrate increasing, and 0.0019 dB Y-PSNR(Y-Peak Signal-to-Noise Ratio) loss), promoting the coding efficiency.

HEVC, intra prediction; code unit division; rate distortion optimization

2014-03-11

國家自然科學基金面上項目(61272120);陜西省自然科學基礎研究計劃基金資助項目(2013JC2-32)

謝曉燕，女，陜西西安人，西安郵電大學副教授，從事視頻編解碼算法研究。

TN919.81

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-009