基于HEVC的幀內預測模式決策和編碼單元劃分快速算法

郭 磊,王曉東,徐博文,王 健

0 引言

隨著超高清晰度電視﹑3D視頻﹑高清移動視頻等視頻服務需求的日益增長,高清視頻編碼和傳輸日益成為研究的主要問題,視頻編碼聯合工作組(Joint Collaborative Team on Video Coding, JCT-VC)在2013年正式推出了新一代高效視頻編碼(High Efficiency Video Coding,HEVC)標準[1]。HEVC采用了靈活的四叉樹分割﹑樣點自適應補償等多項新編碼方案[2]。在HEVC編碼標準中,分別使用編碼單元(Coding Unit, CU)﹑預測單元(Prediction Unit, PU)和變換單元(Transform Unit, TU)實現編碼﹑預測和變換;為了獲得較好的預測結果,PU中的預測模式比H.264/AVC(Advanced Video Coding)[3]增加了26種。在保證相同視頻圖像質量的條件下,HEVC的編碼碼率比H.264降低了50%左右,但相應也急劇增加了編碼的復雜度,不利于HEVC的實時應用。因此在不影響視頻編碼質量情況下,有效降低編碼復雜度成為當前HEVC的研究熱點。

為了降低HEVC編碼復雜度,許多學者從CU快速分割和PU角度模式選擇兩方面提出了許多優化算法。文獻[4]通過梯度信息減少預測模式個數,并通過CU的紋理平坦性提前終止劃分。Feng等[5]計算每個最大編碼單元(Largest Coding Unit, LCU)的顯著性,再比較LCU顯著圖子塊的各個熵值,進行PU尺寸的提前判定,具有較好的適用性但求取熵值較復雜。Cuenca[6]提出了一種紋理方向檢測算法,利用離散點陣的斜率集合計算編碼單元局部紋理方向方差(Mean Directional Variance, MDV),MDV較為準確地表示CU的紋理方向,但需要獲得相應矩陣并平方,間接增加了復雜度。Marzuki等[7]根據上層CU和相鄰PU的預測模式自適應地降低當前編碼單元粗選擇模式的個數,將由率失真平均值得到的自適應閾值應用到率失真優化(Rate Distortion Optimization,RDO)和殘差四叉樹變換(Residual Quad-tree Transform, RQT)過程中進行提前終止判斷,但僅僅利用空域相關性來預判使編碼復雜度的降低相對有限。Zhang等[8]首先分析了四叉樹中CU劃分深度,提出了一種靈活的CU深度選擇結構,并通過支持向量機訓練獲得最優參數,來實現CU尺寸選擇；訓練本身具有一定復雜度,同時也會因為誤判導致率失真下降。文獻[9]中提出了基于圖像紋理特征的CU劃分和PU模式快速選擇算法,通過提取編碼塊的紋理特征以及沿特定方向的方向能量分布，提前判定CU尺寸。文獻[10]中提出了一種利用預測殘差統計信息實現快速編碼四叉樹的方法,相對于原始平臺獲得了較好的編碼性能,但復雜度減少有限。文獻[11]提取了空間相關性以及原始編碼特征,利用支持向量機預測不同權重,通過加權后判斷當前CU是否往下分割。文獻[4-13]僅僅是利用視頻圖像紋理特性、統計特性或空域相關性中的部分特性進行快速實現。

為了進一步降低CU遞歸分割復雜度,本文綜合利用了統計特性、紋理特征對CU進行劃分快速決策;并相應地對參與粗模式選擇(Rough Mode Decision,RMD) 過程中的模式個數進行判決。

1 幀內預測快速算法

HEVC采用固定大小尺寸范圍的CU來編碼一個視頻序列，且采用了較為靈活的四叉樹等技術,因此HEVC獲得了較高的壓縮效率,但也相應增加了計算復雜度。相對于H.264/AVC中使用的9種幀內預測模式，HEVC將幀內預測模式擴展為35種(如圖1所示),包括33種方向性預測模式、DC模式和Planar模式。為了找出PU最佳模式,編碼框架不得不遍歷這35種模式來計算每一個PU的率失真代價,這樣導致了高計算復雜度。

圖1 HEVC的35種幀內預測模式

一般來說,在HEVC編碼處理過程中,CU尺寸的選擇、PU模式選擇與視頻內容紋理特征有關。如圖2所示,在量化參數(Quantization Parameter, QP)為32時,顯示了序列BasketballPass第4幀的CU最終分割和PU的最優預測模式結果。從圖2(a)可以看出,平坦光滑的區域(如墻面、地板)較大概率地采用大尺寸的CU編碼;而對于運動員、籃球等紋理復雜的區域需要較小尺寸單元編碼。從圖2(b)可以看出，PU的預測模式大多沿著圖像的紋理方向,對于那些紋理特別平坦光滑的區域(如墻面、地板),會較大概率地選擇DC模式或Planar模式。

圖2 BasketballPass第4幀CU分割和PU預測模式示意圖

1.1 CU快速分割算法

考慮到上面這些因素,本文在每一深度層計算該CU紋理方向時引入像素方差參數variance來表示紋理復雜度。像素方差一般可用式(1)表示:

(1)

其中:N表示塊的尺寸大小;I(i,j)表示在(i,j)位置上的像素點亮度值。為了避免式(1)的平方運算,減少運算量,CU塊的紋理復雜度[14]可定義為:

(2)

其中:I(i,j)表示在CU塊(i,j)位置上像素點亮度值;Imean表示CU塊像素點平均亮度值。本文在考慮文獻[15]中紋理方向表達式的基礎上結合式(2),定義了CU塊紋理方向復雜度的表達式:

(3)

(4)

(5)

(6)

其中:C0﹑C1﹑C2和C3分別表示CU塊在水平﹑垂直﹑45°和135°方向的紋理復雜度;N表示塊的尺寸大小;I(i,j)表示在(i,j)位置上的像素點亮度值。

選取C0﹑C1﹑C2和C3中的最大值記為Cmax,表示該CU塊的紋理復雜度。分別計算各個紋理方向的數值,值越小說明紋理方向越突出。本文需要計算四個方向,如果四個方向值都小于某一值時,能夠說明該塊的平坦性,所以選擇其中的最大值作為該CU塊的紋理復雜度,通過選取閾值Th1來判斷CU塊的紋理平坦性。

由于8×8的CU還要繼續劃分成4個4×4的PU,當視頻序列被劃分成許多8×8的CU時,若能夠提前終止劃分成4個PU，將會減少更多時間。當幀內CU塊為8×8時,其對應有兩種PU模式即2N×2N和N×N,所以本文可以用閾值Th1來決定8×8的CU是否繼續劃分為4個PU以及使用其中的一種模式。

圖3為本文算法對每一深度層的CU進行處理的流程。計算并選取C0﹑C1﹑C2和C3中的最大值Cmax,然后與Th1比較,判斷下一步是否劃分。當depth為3時,若紋理主方向強度值小于Th1,則直接選擇2N×2N模式,而不再考慮N×N模式,節省了相當一部分時間。

圖3 每一深度層的CU劃分流程

圖4 PU的模式選取

1.2 PU預測模式選擇算法

由于HEVC采用35種幀內PU預測模式，這在編碼過程中無疑增加了計算復雜度。HEVC幀內預測編碼過程首先要進行RMD,遍歷35種預測模式,然后根據對應的PU尺寸選擇最有可能的預測模式,將當前塊的最有可能模式(Most Probable Mode, MPM)加入到候選模式集中一起進行高精度的率失真優化RDO計算,最終選擇出最優幀內預測模式。根據上述模式預測過程,從兩個方面采取不同的選取策略來減少預測模式數量。

如圖4所示,三幅圖片是圖2(b)中的某一PU塊的對應放大部分,在一致性區域部分如地板、籃球服沒有特殊的紋理方向,所以選擇DC和Planer模式作為該塊的最優預測模式;而在包含有木紋方向的地板、有顏色邊緣的球衣根據其紋理方向使用不同的預測模式。考慮到PU最終預測模式的方向一般服從圖像的紋理方向分布,本文利用1.1節得到的四個紋理方向的復雜度來提前減少PU預測模式個數。

在RMD過程中,根據1.1節計算得到的四個方向的紋理復雜度,當PU塊紋理極為平坦時選擇模式DC、Planar的概率極大,當滿足式(7):

Cmax-Cmin<0.1Cmin;Cmax

(7)

本文直接選取選取模式DC、Planar且不再經過RMD過程,若不滿足式(7)則從四個方向中選取水平方向復雜度C0、垂直方向復雜度C1,利用C0和C1之間的關系將35種PU預測模式分為兩組,即垂直方向(模式18～34)和水平方向(模式2～18)。將水平方向和豎直方向的復雜度關系表示為:

a=C0/C1

(8)

通過比較C0與C1的關系,判斷當前PU塊的角度模式處于水平方向范圍還是豎直方向范圍。按照a與閾值m1、m2的關系進行模式分組:

(9)

當m1≤a≤m2時,考慮到相鄰模式的PU會采用相同的參考像素,其對應的RD-cost數值不會相差很大，所以本文在與文獻[16]相同的實驗條件下，對35種PU預測模式中的偶數模式和奇數模式所對應的RD-cost關系進行了統計分析。表1顯示了在RMD過程中,不同QP下,奇模式對應的RD-cost值在其相鄰兩個偶模式對應的RD-cost值范圍之間的概率結果分別為P22、P27、P32、P37,85%的奇模式的RD-cost值處于其相鄰偶模式范圍之間。故在m1≤a≤m2時,本文為Group3選取17種偶模式和DC、 Planer模式來進行原始平臺處理并獲得相應RD-cost值,其余剩下的奇模式RD-cost值定義為:

(10)

這樣就不用經過原始平臺處理,跳過奇模式的遍歷，通過式(10)進行估計直接獲得，能節省相當一部分時間。如表2所示,本文給出了各個分組的角度模式組成。

本文按表2給出的分組,在RMD過程中選取RD-cost值最小的N(根據CU深度0～3;N依次為3、3、3、8)個模式,作為進行下一階段RDO過程的粗模式選擇集合RMDs。

在RDO過程中,一些最有可能模式集合MPMs會加入到最終的模式列表中進行遍歷,個數可能為1或2。從RMD過程中得到的候選集合中除了模式DC、Planer外其他模式將相應分配到水平模式集合H(范圍2～18)和垂直模式集合V(范圍18～34)中。在文獻[14]的實驗條件下，對當(RMDs∪MPMs)中僅含有模式10或模式26時進行統計分析,實驗發現,RMD過程中得到的候選模式集合包含模式10或模式26的概率為70%,且對于不同的視頻序列其概率變化不大。另一方面,模式10和模式26都是直角模式，具有最小的相關性,所以當RMDs的候選模式集合僅包含模式10或模式26時,本文只選擇相應的模式集合H或V(2～18或18～34)進行RDO處理。

表1 奇數模式所對應的RD-cost值在相鄰兩偶數模式的RD_cost值之間的概率

如表3所示,當(RMDs∪MPMs)僅包含模式10而不包含模式26時,RDO選擇低于模式18的預測模式概率大約為90%;而當(RMDs∪MPMs)僅包含模式26時而不包含模式10時,RDO選擇高于模式18的預測模式概率大約為95%。所以當模式10或模式26僅存于(RMDs∪MPMs)中時,RDO的候選模式集合將選擇對應的集合H或者集合V以及可能存在的DC、Planar模式。

表2 RMD候選模式子集

表3 當只包含模式10或模式26時其相應模式集合選擇的概率

而當模式10和模式26都存在于(RMDs∪MPMs)中時,本文利用集合H的模式個數α、集合V模式個數β的關系及a來確定RDO最終預測模式集合:

(11)

表4給出了當模式10、模式26都存在時,根據不同條件RDO最終候選預測模式。

表4 RDO候選模式子集

當模式10和26都不存在(RMDs∪MPMs)中時,本文就按照原始平臺的方法進行RDO模式選取。

1.3 閾值的選取

本文中閾值Th1用來判斷CU塊紋理方向的復雜性。閾值的選取對CU尺寸判定至關重要,也是在編碼質量和復雜度之間保持平衡的一個重要參數。本文選取了A～E五種不同分辨率的序列內容進行實驗訓練，為了表示CU的正確劃分,本文定義一個正確匹配率Rdepth:

(12)

其中:ndepth表示depth為0、1、2、3下的與編碼平臺HM15.0正確匹配的塊數;mdepth表示HM15.0總的CU劃分塊數。

實驗結果如圖5所示,閾值選取太大或太小都會影響到CU塊的正確劃分。當QP為37﹑32﹑27﹑22時,對應深度層為2的閾值Th1選取分別為1 536﹑1 024﹑896﹑704。對于每一深度的閾值,由于后一深度層的CU尺寸大小是前一深度層的1/4,且結合式(3)～(6)特征,所以本文取上一深度層閾值的1/4。

對于m1、m2閾值的選取,在前面基礎上同樣對上面不同類序列進行訓練。如圖6所示m1越小、m2越大,則模式預測選取的正確性概率right越大；但考慮到算法的時間復雜度,所以本文選擇圖中矩陣標記區域。故本文取m1、m2分別為0.85、1.5。

圖5 閾值Th1與正確匹配率的關系

圖6 閾值m1、m2與正確匹配率的關系曲面

2 本文CU分層算法

本文算法流程如下:

步驟1 首先計算CU各個方向的紋理復雜度,得到其中的最大值Cmax,與閾值Th1比較判斷當前CU平坦性,如小于Th1則直接提前終止，不再進入下一層劃分。

步驟2 獲得當前PU的紋理復雜度最大值Cmax和最小值Cmin。若滿足式(7)中的關系,則直接選取模式DC、Planer作為RDO處理的候選模式,轉步驟4;否則轉步驟3。

步驟3 利用式(8)得到a比較m1、m2的關系;根據式(9)選擇相應的候選模式集合Groupi。

步驟4 隨之得到候選模式集合RM=(RMDs∪MPMs),判斷當前RM是否含有模式10、26,分成4種情況選擇相應的候選模式集合。

步驟5 注意當深度depth=3時,通過Cmax值可以選取當前CU對應的PU模式,若強度值小于Th1,則選擇2N×2N模式。

算法流程如圖7所示。

圖7 本文算法流程

3 實驗與分析

為了評估本文算法的有效性,將其移入HEVC參考軟件HM15.0上進行實現來驗證編碼性能和計算復雜性。

本文實驗平臺硬件配置為Intel Core i3-3220 CPU 3.3 GHz,內存4 GB。實驗在全I幀編碼模式(All Intra Main, AI-Main)下進行,本文采用了由JCT-VC推薦的A～E五個類的18個標準測試序列,分別對應不同的應用場合,編碼幀數為50幀,QP分別為22﹑27﹑32﹑37,GOP(Group Of Pictures)為8。

本文選取不同類別的測試序列來驗證該算法對不同場合的適用性。通過BDBR(Bjontegaard Delta Bit Rate)和BDPSNR(Bjontegaard Delta Peak Signal-to-Noise Rate)[17]來評估本文算法的編碼效率和視頻質量好壞;同時采用編碼節省時間ΔT來驗證所提算法的編碼復雜度,則編碼節省時間可定義為:

(13)

其中:Timeproposed表示本文算法的運行時間；TimeHM15.0表示原始平臺的運行時間。

為了驗證本文算法的編碼性能,與標準算法HM15.0、文獻[18]算法和文獻[19]算法進行了對比,表5為其中10個序列的對比結果。從表5的實驗結果可看出：本文算法與標準平臺相比,BDBR平均上升了1.018%,而編碼時間平均節省了51.24%,BDPSNR損失為0.059 2 dB,視頻質量基本不變,綜合效果要優于文獻[18]算法和文獻[19]算法。

表5 本文算法與文獻[18-19]算法相比HM15.0的編碼性能提升

表6 本文算法與文獻[20]算法相比HM15.0的編碼性能提升

圖8 3種典型測試序列的RD曲線

表6為A～E類的18個測試序列的實驗結果,與文獻[20]算法相比,本文算法的BDBR降低了2.75%,編碼時間平均節省了45.64%,這是由于本文從CU劃分和幀內模式選擇兩方面降低了編碼復雜度,對平坦區域不再向下劃分和減少預測模式數量。

由表5可知,對于FourPeople、BasketballPass紋理相對平坦的序列,預測模式更容易精確獲得,其相應的編碼時間要減少較多;對于BlowingBubbles﹑PartyScene這類紋理比較復雜的序列,需要劃分成更深層次的CU,所以在編碼時間上減少得比其他序列偏少,但其對應的BDBR值也比較小,保持了較好的率失真性能。

圖8為本文方法與平臺HM15.0的率失真性能比較,給出了3種類別視頻序列的對比,其中YPSNR表示視頻編碼后的亮度峰值信噪比，Bitrate表示視頻編碼率。由圖8可看出：Cactus的RD曲線幾乎是重合的,說明在本文算法下編碼性能幾乎沒有降低；BQmall的RD曲線中間部分有微小的偏差；BQSquare其RD曲線與HM曲線有稍微偏差,但不會對視頻質量造成很大影響。

圖9是在QP=32時,序列RaceHorses第4幀分別在原始平臺算法和本文算法中對應的CU劃分結果,可以對比發現本文算法與HM平臺的CU劃分基本一致,劃分效果更好。

圖9 原始平臺HM15.0與本文算法的劃分塊和模式選擇對比

4 結語

本文提出了基于紋理方向復雜度的CU尺寸選擇和幀內PU預測模式快速選擇算法,主要包含兩方面:一方面,計算每一深度層CU四個方向的紋理復雜度,選取其中的最大值Cmax作為判斷紋理復雜度的依據,比較閾值Th1判斷CU是否應繼續劃分;另一方面,從得到的四個方向復雜度中獲取水平、垂直方向復雜度C0、C1,以及依據統計35種模式被選為最優模式的概率,進一步減少預測模式數量,降低幀內編碼復雜度。本文算法在BDPSNR幾乎不變﹑平均比特率增加1.167%的情況下,平均編碼時間比原始編碼平臺減少了51.997%。下一步要對紋理比較復雜、運動程度較為劇烈的視頻序列進行研究，進一步降低編碼比特率。

參考文獻(References)

[1] SULLIVAN G J, OHM J R, HAN W J, et al. Overview of the High Efficiency Video Coding(HEVC) standard [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2012, 22(12): 1649-1668.

[2] UGUR K, ANDERSSON K, FULDSETH A, et al. High performance, low complexity video coding and the emerging HEVC standard [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2010, 20(12): 1688-1697.

[3] WIEGAND T, SULLIVAN G J, BJONTEGAARD G, et al. Overview of the H.264/AVC video coding standard [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2003, 13(7): 560-576.

[4] ZHANG T, SUN M, ZHAO D, et al. Fast intra mode and CU size decision for HEVC [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2016, 27(8): 1714-1726.

[5] FENG L, DAI M, ZHAO C, et al. Fast prediction unit selection method for HEVC intra prediction based on salient regions [J]. Optoelectronics Letters, 2016, 12(4): 316-320.

[6] CUENCA P. Fast intra mode decision algorithm based on texture orientation detection in HEVC [J]. Signal Processing Image Communication, 2016, 44(C): 12-28.

[7] MARZUKI I, MA J, AHN Y J, et al. A context-adaptive fast intra coding algorithm of High-Efficiency Video Coding (HEVC) [EB/OL].[2017- 05- 10]. https://doi.org/10.1007/s11554-016-0571-5.

[8] ZHANG Y, KWONG S, WANG X, et al. Machine learning-based coding unit depth decisions for flexible complexity allocation in high efficiency video coding [J]. IEEE Transactions on Image Processing, 2015, 24(7): 2225-2238.

[9] SUN X, CHEN X, XU Y, et al. Fast CU size and prediction mode decision algorithm for HEVC based on direction variance [J]. Journal of Real-Time Image Processing, 2017: 1-14.

[10] TAN H L, CHI C K, RAHARDJA S. Fast coding quad-tree decisions using prediction residuals statistics for High Efficiency Video Coding (HEVC) [J]. IEEE Transactions on Broadcasting, 2016, 62(1): 128-133.

[11] LIU Y C, CHEN Z Y, FANG J T, et al. SVM-based fast intra CU depth decision for HEVC [C]// Proceedings of the 2015 Data Compression Conference. Piscataway, NJ: IEEE, 2015: 458-458.

[12] 張峻,董蘭芳, 余家奎. 高效率視頻編碼快速幀內預測算法[J]. 計算機應用, 2015, 35(8): 2327-2331.(ZHANG J, DONG L F, YU J K. Fast intra prediction algorithm for high efficiency video coding [J]. Journal of Computer Applications, 2015, 35(8): 2327-2331.)

[13] 祝世平, 張春燕. 基于機器學習的HEVC幀內模式快速決策算法[J]. 光電子·激光, 2016, 27(11): 1199-1207.(ZHU S P, ZHANG C Y. A fast HEVC intra mode decision algorithm based on machine learning[J]. Journal of Optoelectronics·Laser, 2016, 27(11): 1199-1207.)

[14] MIN B, CHEUNG R C C. A fast CU size decision algorithm for the HEVC intra encoder [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2015, 25(5): 892-896.

[15] WON C S W, DONG K P P, PARK S J P. Efficient use of MPEG7 edge histogram descriptor [J]. Etri Journal, 2002, 24(1): 23-30.

[16] FINI M R, ZARGARI F. Two stage fast mode decision algorithm for intra prediction in HEVC [J]. Multimedia Tools & Applications, 2016, 75(13): 7541-7558.

[17] BJONTEGAARD G. Calculation of average PSNR difference between RD-curves [EB/OL]. [2015- 01- 15]. http: //wftp3.itu.int/av-arch/video-site/0104_Aus/.

[18] JAMALI M, COULOMBE S. Coding unit splitting early termination for fast HEVC intra coding based on global and directional gradients[C]// Proceedings of the 2016 IEEE 18th International Workshop on Multimedia Signal Processing. Piscataway, NJ: IEEE, 2017: 1-5.

[19] LIM K, LEE J, KIM S, et al. Fast PU skip and split termination algorithm for HEVC intra prediction [J]. IEEE Transactions on Circuits & Systems for Video Technology, 2015, 25(8): 1335-1346.

[20] SHI H, LIANG F, CHEN H. A fast CU size decision algorithm based on adaptive depth selection for HEVC encoder[C]// Proceedings of the 2014 International Conference on Audio, Language and Image Processing. Piscataway, NJ: IEEE, 2015: 143-146.

This work is partially supported by the National Natural Science Foundation of China (U1301257), the National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2012BAH67F01).