基于圖像空間相關性與紋理的HEVC塊劃分快速算法

姚英彪，李曉娟

（杭州電子科技大學通信工程學院 杭州 310018）

1 引言

隨著視頻技術的發展，以H.264/AVC為代表的第二代視頻編碼標準已不能滿足人們對于實際應用的要求。在這一形勢下，VCEG和MPEG兩大標準組織成立JCT-VC（joint collaborative team on video coding）[1]，在全球范圍內征集新的視頻編碼技術提案，統一制定新一代高效率視頻編碼（high efficiency video coding，HEVC）標準。HEVC的核心目標是在H.264/AVC高檔次（high profile，HP）的基礎上壓縮效率提高1倍，即在保證相同視頻圖像質量的前提下，視頻流的碼率減少50%[2]。

HEVC沿用H.264/AVC的混合編碼框架，但在幀內編碼方面，采用新的多角度幀內預測技術和基于大尺寸四叉樹塊的分割結構，預測模式由H.264/AVC的9種增加為35種，包括33種方向模式和DC（direct current）模式、planar模式；使用編碼樹單元（coding tree unit，CTU）、編碼單元（coding unit，CU）、預測單元（prediction unit，PU）和變換單元（transform unit，TU）描述整個編碼過程[2]。大量的預測模式提高了預測精度，靈活的塊結構能更好地適應編碼圖像的內容。

對于每幀圖像，可以將其劃分為多個CTU，每個CTU又可以劃分為1個或多個CU。CU是幀內、幀間預測編碼的基本單元，最大的CU即最大編碼單元尺寸為64×64，最小編碼單元尺寸為8×8。CTU劃分深度depth范圍及CU深度范圍固定為0～3，深度0、1、2、3對應的編碼塊大小分別為64×64、32×32、16×16、8×8。CU概念便于編碼塊的遞歸劃分及四叉樹編碼結構的形成，具體編碼單元的劃分如圖1所示。PU是預測編碼的基本單元，用來傳輸與預測過程相關的信息，在CU的基礎上劃分而來。PU最多有12種不同模式，對于幀內預測而言，只有2N×2N和N×N兩種模式，若當前CU不是最小編碼單元，PU采用2N×2N模式的預測單元，即PU尺寸同當前CU尺寸，當CU尺寸為8×8即CU為最小編碼單元時，PU需要檢測2N×2N和N×N兩種模式，最終選擇率失真代價最小的模式。TU是變換和量化的基本單元，與PU相同，也是在CU的基礎上劃分而來，TU結構與CU結構類似，采用了殘差四叉樹（residual QuadTree，RQT）編碼結構。

在幀內編碼過程中，需要遍歷所有的CU、PU、TU的組合以及35種預測模式，經過率失真優化 （rate distortion optimization，RDO）過程選擇率失真代價最小的單元和預測模式進行最終編碼。率失真代價函數如下：

圖1 CU、PU塊劃分

其中，JRDO表示率失真代價，SSE表示當前塊與重建塊的殘差平方和，λ表示拉格朗日系數，B表示當前預測模式下編碼所需的比特數。

由于率失真代價的計算需要進行完整的編碼，過程復雜，而大量的預測模式和復雜的塊結構大大增加了進行率失真運算的次數，這就造成幀內編碼算法的運算復雜度和編碼時間增加，從而極大地限制了HEVC的應用范圍。因此，在保證編碼性能的前提下，如何降低HEVC幀內編碼算法的復雜度是當前HEVC實際應用的研究熱點之一。

2 HEVC幀內編碼優化算法

[3]提出經過粗選（rough mode decision，RMD）過程，利用簡化的率失真模型篩選出部分預測模式，再進行最后的RDO計算。參考文獻[4]利用空間相關性，提出最有可能預測模式（most possible mode，MPM）的概念，即鄰近塊的最佳預測模式，將RMD篩選后得到的模式與MPM一并作為最后的RDO候選模式。參考文獻[5～9]利用圖像的紋理特征篩選出部分模式進行RMD和RDO計算。以上方法都是針對給定大小的PU，從減少所要遍歷的幀內預測模式出發，實現幀內快速編碼，減少算法復雜度。

參考文獻[10～12]針對視頻內容的時間或者空間相關性，利用已編碼的上一幀對應位置的CU或者空間鄰近CU塊的劃分深度預測當前塊的劃分深度，跳過當前塊的編碼計算或者提前終止其子塊劃分。參考文獻[10]利用圖像內容的相關性，在對當前CU塊進行劃分時，跳過空間相鄰CU較少使用的深度。參考文獻[11]利用時空相鄰的CTU/CU之間的相關性，通過已編碼時空相鄰CTU/CU的最佳深度預測當前CTU/CU的深度范圍和深度值，跳過和提前終止不必要的塊劃分計算。參考文獻[12]利用視頻幀的時間相關性，通過前一幀的劃分深度預測當前幀對應位置處CTU的最小劃分深度，并計算當前CU的運動矢量差值和預測殘差系數，得到其最大劃分深度，從而跳過部分大塊CU的塊劃分和避免小塊CU的塊劃分。

參考文獻[13～17]利用每個深度CU編碼過程中計算得到的率失真代價、預測殘差、像素值的方差、熵等信息提前終止或跳過劃分塊。參考文獻[13]分析了率失真代價與塊劃分的關系，在劃分過程中將每個CU塊的率失真代價與之前設定的閾值進行比較，判斷是否提前終止該CU塊的子塊劃分。參考文獻[14]利用CU塊不同劃分深度與RMD和RDO過程中計算得到的基于SATD的代價值和RDO代價值，跳過大塊編碼計算和提前終止子塊劃分。參考文獻[15]利用預測殘差能夠反映預測準確性的思想，在每一個編碼塊進行編碼時，判斷其預測殘差是否足夠小，若小于事先設定的閾值，則提前終止其子塊劃分。參考文獻[16]利用視頻內容的平滑區域與最終編碼塊大小的相應關系，根據當前已編碼單元的編碼信息對當前區域是否平滑進行檢測，根據檢測結果提前終止一些不必要的子塊劃分。參考文獻[17]利用視頻序列第一幀像素值的方差，分析視頻紋理特性并減少部分塊劃分過程。

本文利用視頻內容的空間相關性及編碼塊大小與其紋理的關聯，提出一種基于圖像空間相關性與紋理的HEVC塊劃分快速算法。首先，通過分析不同視頻序列相鄰CTU之間的劃分深度范圍的相關性，提出CTU最有可能深度范圍（most possible depth range，MPDR）的概念及計算方法。其次，通過檢測相鄰CTU之間的主要邊緣方向來分析鄰近CTU間的紋理差異性，并根據該紋理差異判決當前待編碼CTU的劃分深度范圍是采用MPDR，還是采用HM原有算法中的0～3。最后，通過統計不同序列、不同尺寸塊的塊劃分與像素方差的概率密度，得到紋理復雜的閾值計算式；在每個CU編碼之前，計算并比較像素方差與閾值，檢測該CU的紋理復雜程度，判斷是否可以跳過該塊的編碼計算而直接劃分。與HM13.0相比，本文算法能夠保證在編碼性能幾乎不變的情況下，將編碼時間減少20%以上。

3 CTU最有可能深度范圍

3.1 CTU深度范圍與視頻內容的相關性

在HEVC幀內編碼過程中，每幀圖像都將被劃分為多個CTU，在對CTU塊劃分尋找最佳CU塊尺寸的過程中，HEVC標準算法將CTU的深度范圍固定為0～3，遞歸遍歷所有CU塊尺寸類型，并進行相關的PU、TU劃分和預測模式的選擇，最終得到率失真代價最小的塊劃分類型。但由于不同序列、不同CTU塊之間存在紋理復雜度的差別，CTU深度范圍可能小于標準規定的0～3。

為分析不同內容特性的視頻序列的CTU劃分深度范圍，選取5個不同類別、不同分辨率和不同紋理的視頻序列在不同量化參數（QP=22、27、32、37）下，統計所有CTU最小劃分深度分別為0、1、2、3的平均比重和最大劃分深度分別為0、1、2、3的平均比重，分別見表1和表2。表1中pmindepth0、pmindepth1、pmindepth2、pmindepth3分別表示最小劃分深度為0、1、2、3所占平均比重， 表2中pmaxdepth0、pmaxdepth1、pmaxdepth2、pmaxdepth3分別表示最大劃分深度為0、1、2、3所占平均比重。

從表1和表2可以看出，并非所有序列CTU的最小劃分深度都為0，最大劃分深度都為3。對于紋理復雜的序列（如序列BQSquare），應該進行較細致的劃分，塊尺寸較小；最小劃分深度為0的概率非常小，若采用原有的劃分深度范圍0～3，則有不必要的深度塊（深度0）的編碼。對于平坦序列（如序列Kimono1），塊尺寸較大；最大劃分深度為3的比重較小，若采用原有的劃分深度范圍0～3，則有不必要的深度塊（深度3）的編碼。因此，可以根據CTU之間的空間相關性縮小CTU塊劃分時的深度范圍，并且每個CTU內部由于紋理的不同，可以針對不同的紋理選擇不同的塊大小，從而避免不必要的塊劃分帶來的復雜計算（包括RDO計算）。

3.2 CTU劃分深度的相關性分析及其MPDR

由于每幀圖像存在內容的相關性，空間相鄰CTU的劃分深度之間也存在著相關性，下面的統計數據也證明了這一點。各鄰近CTU分別為上方CTU、左方CTU、左上方CTU和右上方CTU，如圖2所示。當前CTU的最小和最大劃分深度與各鄰近已編碼CTU的最小和最大劃分深度分別為mindepth、maxdepth、mindepth_a、maxdepth_a、mindepth_l、maxdepth_l、mindepth_al、maxdepth_al、mindepth_ar、maxdepth_ar。

圖2 鄰近已編碼CTU與當前CTU

定義4個鄰近已編碼CTU的最小劃分深度中的最小值為mp_mindepth，4個鄰近已編碼CTU的最大劃分深度中的最大值為mp_maxdepth，如下：

定義當前CTU的MPDR為：

即用4個鄰近已編碼CTU的最小劃分深度中的最小值mp_mindepth和4個鄰近已編碼CTU的最大劃分深度中的最大值mp_maxdepth估計當前CTU的MPDR。如果當前CTU經過HM原有算法編碼后的最佳劃分深度均在[mp_mindepth,mp_maxdepth]，說 明MPDR可 以 作 為 當 前CTU劃分深度范圍。

表1 最小劃分深度分別為0、1、2、3所占平均比重

表2 最大劃分深度分別為0、1、2、3所占平均比重

表3分別統計了當前CTU的最小劃分深度大于或等于任意一個鄰近CTU最小劃分深度即mp_mindepth的概率和最大劃分深度小于或等于任意一個鄰近CTU的最大劃分深度即mp_maxdepth的概率。表3中較大的概率值說明當前CTU的最小、最大劃分深度與利用各個鄰近CTU的最小、最大劃分深度得到的mp_mindepth、mp_maxdepth及MPDR具有較強的相關性。區間[mp_mindepth，mp_maxdepth]可以作為當前CTU的MPDR。

表3 當前CTU在不同QP下劃分深度范圍與鄰近CTU劃分深度范圍的比較

4 基于內容相關性及圖像紋理的塊劃分快速算法

以上CTU劃分深度相關性分析，驗證了可以根據鄰近已編碼CTU的劃分范圍得到當前待編碼CTU的合適的劃分范圍（即MPDR），該范圍根據空間相關性適當縮小了原來固定的劃分范圍，避免了不必要的塊劃分所引起的復雜計算。考慮到圖像紋理的區域性分布特征，即鄰近CTU的紋理可能存在明顯的差異，此種情況下，利用鄰近CTU的劃分范圍估計當前CTU的最有可能劃分范圍的方法極容易造成誤判。而如果當前CTU的劃分范圍估計錯誤（如劃分范圍被縮小），就會影響之后的CTU劃分范圍的估計，從而造成錯誤累加，最終使編碼性能大大下降。因此，需要在將MPDR作為當前CTU的劃分范圍之前，對當前CTU的紋理與鄰近CTU紋理的差異性進行分析，如果當前CTU的紋理與該紋理方向上的鄰近CTU的紋理相差較大（如垂直），則采用標準算法的深度范圍0～3進行預測，否則利用空間相關性根據式（2）～式（4）得到當前CTU的MPDR。

4.1 空間鄰近CTU的紋理差異性檢測

為了判別鄰近CTU間的紋理差異性，采用參考文獻[18]中的邊緣檢測方法，對當前CTU和鄰近CTU進行主要邊緣檢測（dominant edge detection），判別各自的主要邊緣（dominant edge，DE）隸屬于0°、45°、90°、135°的哪一種方向，CTU的主要邊緣方向如圖3所示。如果當前CTU的主要邊緣方向DEc垂直于該方向上鄰近CTU的主要邊緣DE′，則認為當前CTU與鄰近CTU的紋理差異較大，不宜采用MPDR作為當前CTU的劃分深度范圍，否則可以將MPDR作為當前CTU的劃分深度范圍。

圖3 CTU的主要邊緣方向

圖4 將CTU劃分為5個子塊

為了得到當前CTU和鄰近CTU的主要邊緣方向，將N×N（N=64）大小的CTU塊按照如圖4所示方式劃分為a、b、c、d、e共5個子塊，并分別計算5個子塊的像素平均值Pa、Pb、Pc、Pd、Pe。定義不同方向上像素差的絕對值之和為主要邊緣方向一致性（dominant edge assent，DEA），利用式（5）分別計算0°、45°、90°、135°這4個主要邊緣方向一致性DEA1、DEA2、DEA3、DEA4，并取其中最小值所對應的方向作為該CTU的主要邊緣方向DE，DE表示0°、45°、90°、135°中的一種。

對當前CTU和鄰近各個CTU（上方CTU、左方CTU、左上方CTU、右上方CTU）分別進行如式（5）所示的計算，得到各個CTU的主要邊緣方向，當前CTU的主要邊緣方向用DEc表示，各個鄰近CTU的主要邊緣方向分別表示為DEa、DEl、DEal、DEar。如前所述，如果當前CTU的主要邊緣方向DEc垂直于該邊緣方向上的CTU的主要邊緣DE′，即滿足式（6），則認為當前CTU與鄰近CTU的紋理差異較大。

由圖3可以看出，0°與90°垂直，45°與135°垂直，若當前CTU的邊緣方向DEc滿足式（7）～式（10）中的其中一個，則認為DEc⊥DE′，即當前CTU與鄰近CTU的紋理差異較大，不宜采用MPDR作為當前CTU的劃分深度范圍。

4.2 編碼單元CU的紋理復雜度檢測

如前所述，如果編碼塊較平滑，則該編碼塊適合大尺寸編碼單元進行預測；如果編碼塊紋理較復雜，宜選用小尺寸編碼單元進行預測，而實驗進一步證明[17,19]，紋理復雜的編碼塊的像素值方差較大，平滑塊的像素值方差較小。因此，在塊劃分過程中，可以通過計算比較像素值方差的大小判斷編碼塊的紋理復雜程度，進而判斷當前深度的編碼塊大小是否適合該紋理的塊，若不適合則不進行該深度塊的編碼計算，從而大大減少編碼復雜度和編碼時間。像素方差v計算如下：

其中，v表示N×N大小的塊的像素方差，pij表示N×N塊位置（i，j）處的像素值，u表示該塊的所有像素均值。

圖5給出了序列Kimono1和Vidyo1不同尺寸的CU塊的像素方差概率密度分布。從圖5可以看出，對于所有的塊尺寸，當方差達到一定值以后，隨著方差的增大，出現的概率隨之減小，最終概率急速下降趨近于0。這就表明，如果一個CU塊的像素方差大于某一個值（如某一個閾值），說明該塊內紋理復雜，這種情況下的尺寸幾乎不可能是最佳的塊尺寸，需要進一步劃分。在CU子塊劃分過程中，在CU塊進行編碼計算（RDO計算）之前，需首先進行紋理復雜度判斷，即判斷CU塊的像素方差是否大于某一個閾值Thv，如果大于，則說明該CU需要進一步分割以減少方差，對于當前深度塊無需進行編碼計算而直接進行下一深度的劃分運算；否則，在估計的深度范圍內進行正常的塊劃分過程。

從圖5可以看出，塊尺寸越大，概率急劇下降所對應的方差越大，閾值Thv應該與塊尺寸有關，且塊尺寸越大即深度越小，閾值應該設定得越大。考慮到不同量化參數QP塊劃分的不同，該閾值也應該與QP值有關，QP越大，閾值越大。通過實驗統計不同序列不同尺寸塊的像素方差值的分布，得到閾值Thv：

其中，α、β、γ為參數，實驗得到其值分別為45、93、3，depth為當前塊的編碼深度，可以取0、1、2、3，分別對應64×64、32×32、16×16、8×8塊大小，QP為量化參數。

如果計算出的v大于Thv，即滿足式（13），則認為該尺寸的編碼塊紋理復雜，需要進一步劃分，無需對該深度的CU進行編碼運算。

4.3 編碼塊快速劃分算法總體流

基于以上分析，提出一種基于圖像紋理復雜度及空間相關性的塊劃分快速算法。該算法對某一個CTU進行編碼之前，首先對該CTU的劃分范圍進行估計，即對當前CTU與鄰近CTU的紋理差異性進行分析，若差異不明顯，則利用鄰近CTU的劃分深度范圍估計得到當前CTU的MPDR并進行接下來的編碼計算；若差異明顯，則采用原有算法的深度范圍0～3進行編碼計算。其次在對每一個CU編碼之前，利用式（11）和式（12）計算其像素方差與閾值，并將兩者進行比較，判斷該尺寸塊的紋理是否非常復雜、是否可以直接進行子塊劃分。劃分深度估計算法流程如圖6所示，塊劃分快速算法的總體流程如圖7所示。

圖5 部分序列的各個尺寸編碼塊的像素方差的概率密度分布

5 實驗結果與分析

為了驗證本文算法的正確性，將該算法加載在HEVC的官方測試模型HM13.0[20]上，對不同類型的視頻測試序列實現全I幀配置，在不同量化參數QP（QP=22,27,32,37）下進行測試。

測試中，通過碼率BitRate、峰值信噪比PSNR、編碼時間T的變化情況分析算法的性能。編碼性能由BD-Rate和BD-PSNR[21]來度量，編碼時間的增減百分比ΔT用來度量編碼復雜度的減少情況，計算如下：

表4給出了本文算法及參考文獻[10]算法與HM原有算法在編碼效率和計算復雜度方面的比較結果，正數表示增加，負數表示減少。可以看出，本文算法較HM原有算法平均節約20%以上的編碼時間，而比特率平均僅增加0.84%，PSNR平均下降僅0.04 dB，編碼性能下降微乎其微。特別地，對于序列Kimono1和BQSquare，編碼時間減少得最多，可以節約30%以上，同時性能下降也很小。與參考文獻[10]相比，本文算法能夠在降低相近的編碼時間的同時，保證編碼性能下降得也很小，因此本文算法優于參考文獻[10]算法。以上數據及分析說明了本文算法能夠保證在編碼性能下降很小的情況下，減少編碼時間，降低編碼復雜度。

圖6 CTU劃分深度范圍估計算法流程

圖7 塊劃分快速算法總體流程

表4 本文算法及參考文獻[10]算法與HM13.0的性能比較

6 結束語

本文基于空間相關性及紋理復雜度提出了一種HEVC塊劃分快速算法，該算法應用于CTU塊劃分過程中。在CTU進行劃分前，通過邊緣檢測方法分析當前待編碼CTU與鄰近已編碼CTU的紋理差異，若差異明顯，則采用原有劃分范圍0～3進行編碼計算；若差異不明顯，則利用鄰近CTU的劃分范圍估計得到當前待編碼CTU的MPDR，并利用MPDR進行編碼計算。在CU劃分過程中，在每個CU編碼之前，通過比較像素方差與閾值來分析該CU的紋理復雜程度，并判斷是否可以跳過該深度塊的編碼計算而直接劃分。仿真結果表明，與HM13.0原有算法相比，本文算法能夠保證在編碼性能幾乎不變的情況下，將編碼時間減少20%以上。

參考文獻

1 ISO/IEC JTC1/SC29/WG11/N11113.ITU-T Q6/16 Visual Coding and ISO/IEC JTC1/SC29/WG11 Coding of Moving Pictures and Audio.Joint Call for Proposals on Video Compression Technology,2010

2 Sullivan G J,Ohm J,Han W J,et al.Overview of the high efficiency video coding(HEVC)standard.IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1649～1668

3 Piao Y,Min J,Chen J.Encoder Improvement of Unified Intra Prediction.JCTVC-C207,2010

4 Zhao L,Zhang L,Ma S,et al.Fast mode decision algorithm for intra prediction in HEVC.Proceedings of IEEE Visual Communications and Image Processing(VCIP),Taiwan,China,2011:1～4

5 Jiang W,Ma H,Chen Y.Gradient based fast mode decision algorithm for intra prediction in HEVC.Proceedings of the 2nd International Conference on Consumer Electronics,Communications and Networks(CECNet),Three Gorges,China,2012:1836～1840

6 Chen G,Pei Z,Sun L,et al.Fast intra prediction for HEVC based on pixel gradient statistics and mode refinement.Proceedings of IEEE China Summit and International Conference on Signal and Information Processing(ChinaSIP),Beijing,China,2013:514～517

7 Chen G,Liu Z,Ikenaga T,et al.Fast HEVC intra mode decision using matching edge detector and kernel density estimation alike histogram generation.Proceedings of IEEE International Symposium on Circuits and Systems(ISCAS),Beijing,China,2013:53～56

8 Da Silva T L,Agostini L V,Da Silva Cruz L A.Fast HEVC intra prediction mode decision based on EDGE direction information.Proceedings of the 20th European Signal Processing Conference(EUSIPCO),Bucharest,Romania,2012:1214～1218

9 Fang C M,Chang Y T,Chung W H.Fast intra mode decision for HEVC based on direction energy distribution.Proceedings of IEEE 17th International Symposium on Consumer Electronics(ISCE),Taiwan,China,2013:61～62

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

11 晏軻,滕國偉,胡錦雯等.一種基于時空相關性的編碼單元深度快速分級判決算法.光電子·激光,2014,25(1):156～162 Yan K,Teng G W,Hu J W,et al.A rapid classification decision algorithm on CU depth based on temporal-spatial correlation.Journal of Optoelectronics·Laser,2014,25(1):156～162

12 李維,張和仙,楊付正.高效率視頻編碼快速模式判決算法.西安交通大學學報,2013,47(8):104～109 Li W,Zhang H X,Yang F Z.A fast mode decision algorithm for high efficiency video coding.Journal of Xi'an Jiaotong University,2013,47(8):104～109

13 Kim J,Choe Y,Kim Y G.Fast coding unit size decision algorithm for intra coding in HEVC.Proceedings of IEEE International Conference on Consumer Electronics(ICCE),Las Vegas,NV,United States,2013:637～638

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

15 Ma S,Wang S,Wang S,et al.Low complexity rate distortion optimization for HEVC.Proceedings of 2013 Data Compression Conference(DCC),Snowbird,UT,United States,2013:73～82

16 蔣潔,郭寶龍,莫瑋等.利用平滑區域檢測的HEVC幀內編碼快速算法.西安電子科技大學學報,2013(3)Jiang J,Guo B L,Mo W,et al.Fast intra coding algorithm using smooth region detection for HEVC.Journal of Xidian University,2013(3)

17 Khan M U K,Shafique M,Henkel J.An adaptive complexity reduction scheme with fast prediction unit decision for HEVC intra encoding.Proceedings of the 20th IEEE International Conference on Image Processing(ICIP),Melbourne,VIC,Australia,2013:1578～1582

18 Tsai A C,Wang J F,Lin W G,et al.A simple and robust direction detection algorithm for fast H.264 intra prediction.Proceedings of IEEE International Conference on Multimedia and Expo(ICME),Beijing,China,2007:1587～1590

19 Tian G,Goto S.Content adaptive prediction unit size decision algorithm for HEVC intra coding.Proceedings of the 29th Picture Coding Symposium(PCS),Krakow,Poland,2012:405～408

20 McCann K,Bross B,Han W J,et al.JCTVC-O1002 High Efficiency Video Coding(HEVC)Test Model 13(HM 13)Encoder Description.JCT-VC,Tech Rep,2014