基于CART決策樹的HEVC幀間CU快速劃分算法

唐浩漾, 王 婧, 孫梓巍, 段一偉

(西安郵電大學 自動化學院， 陜西 西安 710121)

高效視頻編碼(high efficiency video coding，HEVC)[1]是新一代視頻編碼標準。相同感知質(zhì)量下，HEVC比H.264的比特率降低50%，但其編碼復雜度也隨之提高。在幀間編碼過程中，HEVC采用四叉樹劃分結(jié)構(gòu)提高編碼性能，編碼單元(coding unit，CU)的尺寸由H.264的16×16變?yōu)閺?×8到64×64，增加了整個幀間編碼過程的復雜度。因此，在不影響HEVC編碼性能的情況下，降低幀間編碼復雜度是HEVC的主要研究方向之一。

針對HEVC幀間編碼中CU劃分過程率失真代價計算量大的問題，一些學者提出了在CU劃分過程中提早預判CU深度級的算法。如采用預測相鄰CU深度率失真代價模型[2]，在編碼當前CU深度后快速預測下一深度級CU的率失真代價；或者根據(jù)不同深度下CU劃分和不劃分率失真代價的值，實現(xiàn)對不同深度CU的劃分和裁剪，避免了對每一深度級CU率失真代價的計算[3]。但是，這些算法仍需計算率失真代價，計算量較大。

為了避免了率失真代價計算，近年來，一些學者采用機器學習的方法實現(xiàn)對CU的劃分?；谪惾~斯和支持向量機的方法[4-5]解決CU的劃分問題，雖然能夠降低了編碼計算復雜度，但是，該方法因誤判特征屬性導致CU劃分結(jié)果不夠準確?；跊Q策樹的CU快速劃分算法[6]以選擇CU紋理特征中的最優(yōu)特征屬性作為判斷依據(jù)，對CU實現(xiàn)快速劃分，取得了較好的效果，卻在屬性特征的選擇上忽略了CU時空域相關(guān)性的影響。

為了在保持編碼性能同時，又能避免率失真代價的計算，本文擬提出一種基于CART決策樹算法。該算法利用CU深度存在的空間相關(guān)性，建立CART決策樹模型，然后用CART模型實現(xiàn)對當前CU的快速劃分。最后，采用實驗方法驗證算法的有效性。

1 HEVC幀間CU劃分

在HEVC過程中,CU劃分可以分為正向劃分與逆向裁剪兩個過程[7]，CU是編碼的基本單元，其依次采用的大小尺寸有64×64、32×32、16×16和8×8，對應(yīng)的深度信息D分別取值0、1、2、3。首先進行正向劃分過程，從最大編碼單元(largest coding unit，LCU),尺寸為64×64開始，每個LCU被劃分為4個尺寸均為32×32的CU，以此類推，直至被劃分到尺寸為8×8的CU為止，其劃分結(jié)果如圖1所示。然后，進行逆向裁剪過程。如果4個四叉樹劃分圖尺寸CU的率失真代價之和小于其對應(yīng)的16×16尺寸CU的率失真代價，則保留8×8尺寸CU的分割狀態(tài)；否則，剪掉此分支。按照這種方式，逐級向上處理，直至64×64尺寸對應(yīng)的CU。率失真代價是編碼的碼率與圖像失真度之間的相互關(guān)系被定義為

J=(Sluma+ωchroma×Schroma)+λB，

(1)

其中，Sluma為當前的亮度塊與參考塊之間的均方差值和，Schroma為當前的色度塊與其參考塊之間的均方差值和，ωchroma為色度塊的加權(quán)因子，λ為拉格朗日因子，B為用于CU編碼所需的比特數(shù)，J為求得的當前CU的率失真代價。

在CU劃分過程中，為了確定CU的四叉樹結(jié)構(gòu)，需要進行深度從0到3完全遍歷，共計算40+41+42+43=85次率失真代價，計算過程較復雜。研究表明，CU劃分過程的率失真代價計算占HEVC整個編碼時間的40%[8]。因此，在保證視頻質(zhì)量的前提下，提前終止CU的劃分，能夠降低HEVC的幀間編碼復雜度。

圖1 CU四叉樹劃分圖

2 基于CART的幀間CU劃分算法

分類回歸樹[9](classification and regression tree,CART)算法是決策樹方法中典型算法之一，該算法選擇具有最小的特征屬性的基尼系數(shù)(Gini index)作為判斷能力的度量。本文利用空間相鄰CU的深度信息作為CART決策樹的判斷度量，來實現(xiàn)CU的快速劃分。

2.1 CART決策樹模型及測試評估

2.1.1 建立CART決策樹模型

CU劃分問題可歸為對不同尺寸CU的劃分與不劃分二分類問題。設(shè)M是對一幅圖像進行CU劃分的S個數(shù)據(jù)樣本的集合，所包含CU尺寸分別為64×64、32×32和16×16，對應(yīng)的3個數(shù)據(jù)樣本集合分別Mi(i=1,2,3)。分別將數(shù)據(jù)樣本集合Mi分為劃分和不劃分2個不同的子類Cij(j=1,2)。當j=1時表示劃分；當j=2時表示不劃分。在不同尺寸CU進行劃分的樣本集合Mi中，樣本的基尼系數(shù)[10]為

(2)

式中pj(j=1,2)表示各個樣本中CU被劃分與不劃分的概率。若Mi中包含的樣本數(shù)為Si，每個子類Cij中所含的樣本數(shù)記為Sij，則當前樣本的基尼系數(shù)可表示為

(3)

采用CART決策樹模型需要選擇數(shù)據(jù)樣本中最小特征屬性的基尼系數(shù)作為判斷能力的度量[9]?？紤]到視頻序列是由一系列連續(xù)的圖像序列組成，相鄰視頻幀之間有很強的相關(guān)性[11-12]。為了統(tǒng)計其相關(guān)性，采用表1所示的HEVC標準序列進行深度信息相關(guān)性統(tǒng)計，表2為每一幀不同深度下的深度信息統(tǒng)計結(jié)果。

表2中的概率為當前CU與相鄰CU的深度相關(guān)性概率。如表2中59.6%表示當前CU深度為0的情況下，左方LCU中深度為0的CU個數(shù)與該LCU下所有CU個數(shù)之比值。由表2可看出，相鄰CU與當前CU具有同一深度劃分的相關(guān)性概率較大。因此，將當前CU的左方CU、左上方CU和上方CU的深度信息分別記為Dl、Dl-u、Du，并作為CART決策樹模型的特征屬性。

在深度信息為Dl的條件下，可把樣本Mi分成Ci1,l和Ci2,l兩個不同類。Ci1,l和Ci2,l所包含的樣本數(shù)分別為Si1,l和Si2,l，則在該條件下，集合Mi的基尼系數(shù)為

(4)

其中，G(Ci1,l)和G(Ci2,l)分別表示在深度信息Dl情況下，樣本集合Mi劃分和不劃分2個不同子類對應(yīng)的基尼系數(shù)，可依據(jù)式(3)計算得到。

依次計算數(shù)據(jù)樣本Mi在Dl-u和Du的情況下對應(yīng)的基尼系數(shù)，以其最小值對應(yīng)深度信息作為樣本Mi的最優(yōu)特征屬性，建立CART決策樹模型。

表2 當前CU與相鄰CU的深度相關(guān)性概率/(%)

2.1.2 CART決策樹模型的測試評估

為了測試CART決策樹模型對CU劃分的準確性，利用HM編碼器HM16.0對表1的測試序列CU劃分，以評估不同分類器模型對CU的劃分性能。實驗統(tǒng)計了不同尺寸CU的劃分時間和預測準確率，其結(jié)果如表3所示。從表中可看出，利用CART模型預測CU劃分的時間較短，平均準確率高于90%，適用于編碼單元CU的快速劃分。

表3 不同尺寸CU的劃分時間和預測準確率

2.2 幀間CU的快速編碼劃分算法

利用CART決策樹分類器預測幀間CU的劃分結(jié)果，其算法可描述如下。

步驟1從CU深度為0開始編碼。

步驟2計算當前CU和其最優(yōu)特征屬性的基尼系數(shù)。

步驟3判斷當前CU的基尼系數(shù)。若當前CU的基尼系數(shù)小于其最優(yōu)特征屬性的基尼系數(shù)，則不劃分CU；否則，劃分CU。

步驟4對于已劃分的CU，判斷其深度。若深度小于3，則當前深度加1，且返回步驟2；否則，終止CU劃分過程；對于未劃分的CU，終止CU劃分過程。

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

為了驗證本文算法的有效性，在HEVC參考軟件HM16.0中實現(xiàn)了本文算法。編碼器參數(shù)為低時延P幀模式，量化參數(shù)QP值分別為22、27、32、37,測試幀數(shù)為50幀。實驗硬件條件為Inter酷睿i5處理器，內(nèi)存為8GB，采用Windows64位操作系統(tǒng)，運行環(huán)境為Microsoft Visual Studio 2010，測試序列如表1所示。

測試中采用通常的評價編碼性能參數(shù)指標，分別為峰值信噪比的變化Δγ、比特率的變化率ΔRBit和編碼時間的變化率ΔT，其定義分別為

Δγ=γ-γHM,

(5)

(6)

(7)

其中：γ、γHM、RBit、RBit,HM和T、THM分別表示本文算法和HM16.0算法峰值信噪比、比特率和編碼時間。為了評估本文算法的性能，分別采用了HM16.0算法、文獻[6]算法和本文算法的實驗測試，結(jié)果如表4。

從表4可見，相對于HM16.0，本文算法平均減少43.34%的編碼時間，RBit平均增加了1.13%,PSNR平均降低了0.051 dB。與文獻[6]算法相比，本文算法能節(jié)省10.45%的編碼時間，RBit平均降低0.79%，PSNR平均提高了0.021 dB，且本文算法較文獻[6]算法降低的0.79%的比特率。主要原因是本文算法比文獻[6]算法在CU劃分過程中選擇了最小基尼系數(shù)的特征屬性作為CU劃分的度量，考慮了最小比特率的限制條件。

表4 本文算法和文獻[6]算法分別與HM16.0算法對比

測試序列采用PeopleOnStreet，在不同QP(22、27、32、37)情況下，分別使用了上述3種算法計算出率失真和編碼時間，結(jié)果如圖2所示。

從圖2(a)可以看出，3種算法所得到的率失真曲線基本重合，說明3種編碼算法的編碼碼率和圖像質(zhì)量基本相同。而從圖2(b)可以看出，本文算法與HM16.0算法和文獻[6]算法相比，編碼時間分別減少41.24%和32.52%?？梢?，本文算法在保持視頻質(zhì)量的同時，有效地提高了HEVC幀間編碼的編碼效率。

圖2 曲線對比

4 結(jié)語

針對HEVC的幀間編碼過程CU劃分復雜度過高的問題，提出了一種基于CART決策樹的HEVC幀間CU快速劃分算法。算法在CART決策樹中利用CU的空間相關(guān)性作為判斷CU劃分的依據(jù)，實現(xiàn)對CU的快速劃分。實驗結(jié)果表明，本文算法比HM16.0算法的編碼時間平均減少了43.34%，比文獻[6]的快速算法還能節(jié)省約10.45%的編碼時間，有效提高了編碼效率。