毋笑蓉，師智斌，雷海衛(wèi)，杜 博

1.中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，太原 030051 2.中北大學(xué) 儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室，太原 030051

基于隨機(jī)森林分類的HEVC幀內(nèi)CU快速劃分算法

毋笑蓉1，師智斌1，雷海衛(wèi)2，杜 博1

1.中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，太原 030051 2.中北大學(xué) 儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室，太原 030051

針對(duì)HEVC幀內(nèi)編碼中遞歸式四叉樹編碼單元（Coding Unit，CU）劃分引起的高計(jì)算復(fù)雜度問(wèn)題，提出了基于隨機(jī)森林分類（Random Forest Classifier，RFC）的CU快速劃分算法。該算法包括模型離線訓(xùn)練和CU快速編碼算法兩部分。在模型離線訓(xùn)練中，將CU最佳劃分結(jié)果（+1，-1）作為分類標(biāo)簽，將當(dāng)前CU的對(duì)比度、逆差矩和熵信息作為特征屬性，訓(xùn)練RFC模型。在編碼時(shí)，提取當(dāng)前CU的特征屬性值，利用訓(xùn)練好的RFC模型快速預(yù)測(cè)當(dāng)前CU的劃分結(jié)果。實(shí)驗(yàn)結(jié)果表明，該算法與HEVC的標(biāo)準(zhǔn)算法相比，在保證編碼質(zhì)量的前提下，平均可以節(jié)約45.18%的編碼時(shí)間。

隨機(jī)森林；快速編碼；離線訓(xùn)練；CU劃分；HEVC

1 引言

近年來(lái)，高清、超高清視頻應(yīng)用逐漸走進(jìn)人們的視野，各式各樣的直播平臺(tái)屢見不鮮，視頻的高清化和應(yīng)用場(chǎng)景的多樣化對(duì)視頻壓縮技術(shù)提出了更高的要求。2013年，視頻編碼聯(lián)合組（JCT-VC）制定了新一代視頻編碼標(biāo)準(zhǔn)——H.265/HEVC，與前代編碼標(biāo)準(zhǔn)H.264/AVC相比，HEVC在同樣的編碼質(zhì)量下能夠節(jié)約50%的碼率[1-2]。

HEVC實(shí)現(xiàn)高壓縮率的關(guān)鍵技術(shù)之一是采用靈活的四叉樹結(jié)構(gòu)來(lái)組織編碼單元CU、預(yù)測(cè)單元（Prediction Unit，PU）和變換單元（Transform Unit，TU），四叉樹結(jié)構(gòu)有多種劃分層次，HEVC編碼需要遍歷所有的劃分情況，并計(jì)算它們的率失真代價(jià)（Rate-Distortion Cost，RDCost），然后選擇RDCost最低的劃分作為最終編碼方式，給編碼器帶來(lái)極高的計(jì)算復(fù)雜度，這也給實(shí)時(shí)性要求高的視頻傳輸應(yīng)用帶來(lái)了很大的挑戰(zhàn)。

目前，許多國(guó)內(nèi)外學(xué)者針對(duì)以上問(wèn)題提出了多種CU快速編碼算法，這些算法主要分為兩類：一類是基于圖像的紋理特性或統(tǒng)計(jì)思想獲得閾值來(lái)判斷CU劃分的深度級(jí)。文獻(xiàn)[3]根據(jù)CU空間和相鄰幀之間的紋理相關(guān)性，結(jié)合亮度直方圖的密集度特征設(shè)置閾值，提高對(duì)CU劃分深度的預(yù)測(cè)精度；文獻(xiàn)[4]通過(guò)分析低量化參數(shù)（Quantization Parameter，QP）值時(shí)圖像中不同CU尺寸的RDCost獲取相應(yīng)的終止閾值，提早結(jié)束CU遞歸劃分。文獻(xiàn)[5]利用貝葉斯方法統(tǒng)計(jì)不同層次下CU劃分和不劃分的RDCost，實(shí)現(xiàn)不同深度CU的早劃分和早裁剪。這種通過(guò)對(duì)HEVC參考軟件代碼的優(yōu)化方法可以使編碼速度提升，但是實(shí)時(shí)應(yīng)用的空間仍然有限。

另一類是采用機(jī)器學(xué)習(xí)的方法，在編碼中將CU劃分問(wèn)題建模為分類問(wèn)題，利用智能分類算法加快CU的預(yù)測(cè)劃分。在HEVC編碼方面，該方法的應(yīng)用相對(duì)較少。文獻(xiàn)[6]根據(jù)編碼塊的紋理特征，選擇灰度差分統(tǒng)計(jì)熵和 SATD（Sum of Absolute Transformed Difference）的最小值為屬性特征，利用決策樹實(shí)現(xiàn)對(duì)CU的快速劃分；文獻(xiàn)[7]以互信息為標(biāo)準(zhǔn)統(tǒng)計(jì)編碼塊的特征，提出了基于貝葉斯分類的CU快速選擇算法，以F-score方法統(tǒng)計(jì)CU的特征向量，提出了基于加權(quán)支持向量分類器的CU劃分模型，快速?zèng)Q策當(dāng)前CU的劃分結(jié)果，降低HEVC的編碼復(fù)雜度。

然而，在基于機(jī)器學(xué)習(xí)的算法中，單一的智能分類算法（決策樹、貝葉斯和支持向量機(jī)）訓(xùn)練模型容易產(chǎn)生過(guò)擬合現(xiàn)象，預(yù)測(cè)準(zhǔn)確率不是很高，最終影響視頻播放的質(zhì)量。因此，在集成學(xué)習(xí)的思想指導(dǎo)下，本文提出了基于隨機(jī)森林分類的CU快速劃分算法。本文算法包括兩部分：模型離線訓(xùn)練和CU快速編碼算法。在離線訓(xùn)練中，將CU的“劃分（+1）”與“不劃分（-1）”作為分類結(jié)果，選擇能刻畫CU的統(tǒng)計(jì)特征（對(duì)比度、逆差矩和熵）作為特征屬性，構(gòu)建RFC模型。在HEVC編碼過(guò)程中，計(jì)算當(dāng)前CU的特征屬性值，導(dǎo)入線下訓(xùn)練好的RFC模型，預(yù)測(cè)當(dāng)前CU的劃分結(jié)果，在保證視頻編碼質(zhì)量的同時(shí)，降低編碼復(fù)雜度，推進(jìn)編碼標(biāo)準(zhǔn)的實(shí)時(shí)應(yīng)用。

2 相關(guān)工作

2.1 HEVC幀內(nèi)編碼分析

HEVC編碼時(shí)，每幀圖像都被劃分成一系列的編碼樹單元（Coding Tree Unit，CTU），編碼時(shí)按照Z(yǔ)-Scan的方式，在CTU內(nèi)部，采用基于四叉樹的循環(huán)分層結(jié)構(gòu)，CTU的劃分示意圖如圖1所示。對(duì)于HEVC幀內(nèi)編碼，CTU(2N×2N,N∈{32,16,8,4})可以迭代地劃分成四個(gè)CU，一直劃分到最小編碼單元（8×8），每一深度的CU又可以劃分成2N×2N和N×N兩種PU，每種PU進(jìn)行35種幀內(nèi)預(yù)測(cè)編碼，并根據(jù)RDCost選擇最佳PU模式。

判定一個(gè)CTU的最佳劃分方式，一般需要進(jìn)行1+4+42+43=85次RDCost計(jì)算，如圖1中序號(hào)所示。

具體計(jì)算步驟如下：

（1）將CTU作為CU，計(jì)算其最小RDCost（最優(yōu)PU模式時(shí)）。

（2）對(duì)當(dāng)前CU進(jìn)行四叉樹劃分，計(jì)算每個(gè)子CU的RDCost，并對(duì)該CU內(nèi)所有子CU的最小RDCost求和，得到該CU的RDCost。

（3）每個(gè)子CU作為當(dāng)前CU重復(fù)步驟（2）。

（4）重復(fù)步驟（3）直到最大編碼深度。

（5）從最大編碼深度，比較4個(gè)子CU與CU的RDCost，自底向上依次確定出當(dāng)前CU的最佳劃分方式。

圖1 CTU四叉樹遞歸劃分結(jié)構(gòu)示意圖

由此可見，整個(gè)CTU的遞歸劃分過(guò)程繁瑣，計(jì)算量很大，研究CU快速劃分算法具有重要的現(xiàn)實(shí)價(jià)值。

由以上分析可知，對(duì)CTU中的每個(gè)CU，都要考慮“劃分（+1）”與“不劃分（-1）”兩類情況，由此想到，可以將CU的劃分問(wèn)題建模為一個(gè)二分類問(wèn)題，選擇適用的分類算法實(shí)現(xiàn)CU的快速劃分預(yù)測(cè)。

分類算法眾多，神經(jīng)網(wǎng)絡(luò)算法預(yù)測(cè)精確但是計(jì)算量大，決策樹分類簡(jiǎn)單易實(shí)現(xiàn)卻容易陷入局部最優(yōu)，預(yù)測(cè)性能會(huì)隨著數(shù)據(jù)量的增大而下降。這些單一的分類算法往往會(huì)產(chǎn)生過(guò)擬合現(xiàn)象，而隨機(jī)森林[8]（Random Forest，RF）可以避免這種現(xiàn)象，其實(shí)質(zhì)是一個(gè)包含多個(gè)決策樹的分類器，每棵樹具有相同的分布，可以進(jìn)行獨(dú)立分類運(yùn)算得到各自的分類結(jié)果，最終分類結(jié)果按決策樹投票眾數(shù)而定。隨機(jī)森林作為一種新型集成分類器，具有用戶設(shè)置參數(shù)少、人工干預(yù)少、分類精度高等優(yōu)點(diǎn)，可以處理高維數(shù)據(jù)并快速得到分類結(jié)果，相對(duì)于其他傳統(tǒng)分類方法具有良好的魯棒性。

2.2 隨機(jī)森林算法

隨機(jī)森林算法是利用多棵樹對(duì)樣本進(jìn)行學(xué)習(xí)訓(xùn)練并預(yù)測(cè)的一種組合分類器，森林中的每棵樹是一個(gè)獨(dú)立同分布的基本分類單元，隨機(jī)森林是由兩大隨機(jī)化思想決定的，即1996年Breimans提出的Bagging思想[9]和1998年Ho提出的隨機(jī)子空間（random subspace）思想[10]。

Bagging算法是基于自助聚集（Bootstrap aggregating）方法重采樣產(chǎn)生多個(gè)訓(xùn)練集，即采用有放回的方式，從原始訓(xùn)練樣本集中隨機(jī)等量抽取樣本，重復(fù)K次，生成K個(gè)新的訓(xùn)練樣本集。隨機(jī)子空間思想是在對(duì)每棵決策樹的每個(gè)節(jié)點(diǎn)（非葉節(jié)點(diǎn)）進(jìn)行分裂時(shí)，從所有特征屬性集中隨機(jī)等概率地抽取一個(gè)子屬性集，然后從這個(gè)子屬性集中選擇一個(gè)最優(yōu)屬性來(lái)分裂節(jié)點(diǎn)。森林中的每棵決策樹由隨機(jī)抽取樣本和隨機(jī)抽取屬性的方式建立，多棵樹組合起來(lái)稱為“隨機(jī)森林”。

隨機(jī)森林生成后，取一個(gè)新的樣本進(jìn)行測(cè)試，森林中的每棵樹都會(huì)獨(dú)立判定分類結(jié)果，最終決策取相同判定最多的分類類別，用公式表示如下：

公式（1）中，H(x)表示組合分類模型，hi(x)是單個(gè)分類樹模型，Y表示輸出變量，I(?)為示性函數(shù)（即當(dāng)集合內(nèi)有此數(shù)時(shí)，函數(shù)值為1，否則為0）[11]。

2.3 節(jié)點(diǎn)分裂算法

節(jié)點(diǎn)分裂是隨機(jī)森林算法的核心步驟，在隨機(jī)決策樹的訓(xùn)練過(guò)程中，需要一次次地將訓(xùn)練數(shù)據(jù)集分裂成兩個(gè)子數(shù)據(jù)集，每棵樹的分支的生成，都是按照某種分裂規(guī)則選擇屬性。本文隨機(jī)森林算法采用CART（Classification And Regression Tree）節(jié)點(diǎn)分裂算法，分裂規(guī)則是gini指標(biāo)最小原則。gini值越小，說(shuō)明劃分的子集純度越高。計(jì)算過(guò)程如下：

（1）計(jì)算樣本的gini指標(biāo)

其中，P(Ci)代表類別，Ci∈{+1,-1}在樣本集S中出現(xiàn)的概率，l=2。

（2）計(jì)算每次劃分的gini指標(biāo)

S被分割成兩個(gè)子集S1與S2，則此次劃分的gini系數(shù)為：

3 基于隨機(jī)森林分類的幀內(nèi)CU快速劃分算法

編碼單元CU的劃分問(wèn)題可以建模為二分類問(wèn)題，“+1”表示劃分，“-1”表示不劃分，利用圖像紋理信息與CU劃分的密切關(guān)系，選擇圖像的統(tǒng)計(jì)特征對(duì)比度、逆差矩和熵作為分類的特征屬性，離線訓(xùn)練RFC模型。編碼時(shí)，提取當(dāng)前CU的特征值，輸入到RFC模型中，得到當(dāng)前CU的預(yù)測(cè)值，再根據(jù)該預(yù)測(cè)值決定當(dāng)前CU的劃分過(guò)程。

3.1 RFC模型建立

3.1.1 屬性選擇

在分類問(wèn)題中，模型分類效果的優(yōu)劣取決于屬性特征的選取。本文選擇表3中的測(cè)試序列“Traffic”、“ParkScene”、“RaceHorses”、“BasketballDrill”和“Johnny”進(jìn)行HEVC編碼。圖2給出了“RaceHorses”第五幀的CU劃分結(jié)果。從編碼實(shí)例分析可知，編碼塊的某些統(tǒng)計(jì)特征與CU的劃分尺寸有著密切的關(guān)系，灰度級(jí)共生矩陣可用來(lái)描述編碼塊的紋理特征信息，它可以反映出圖像灰度關(guān)于方向、相鄰間隔、變化幅度等綜合信息，經(jīng)統(tǒng)計(jì)，其中四個(gè)方向（0°、45°、90°、135°）上的特征量（對(duì)比度、逆差矩和熵）與編碼單元CU的劃分結(jié)果關(guān)系最密切。因此，本文選擇編碼單元在以上4個(gè)方向上的對(duì)比度、逆差矩和熵作為輸入數(shù)據(jù)的特征屬性變量，建立更加準(zhǔn)確的分類器，進(jìn)而提升編碼器的編碼性能。

圖2 HEVC編碼器的CU劃分結(jié)果示意圖

3.1.2 參數(shù)設(shè)置

CTU采用基于四叉樹的分層遞歸劃分方式，尺寸大小為8×8的CU不需要進(jìn)行劃分，根據(jù)CU的層次不同，需要建立3個(gè)分類器，即CU大小分別為64×64（CuDepth=0）、32×32（CuDepth=1）和16×16（CuDepth=2）的RFC模型。

隨機(jī)森林算法中，訓(xùn)練樣本集的大小會(huì)影響RFC模型的訓(xùn)練時(shí)間和分類性能。本文選用HEVC通用測(cè)試序列（表3）中不同分辨率、不同幀率的五個(gè)測(cè)試序列Traffic、ParkScene、RaceHorses、BasketballDrill和 Johnny作為訓(xùn)練序列，每個(gè)訓(xùn)練序列編碼前50幀，提取不同CU深度的特征屬性，其中前20幀作為訓(xùn)練樣本集S，余下30幀作為測(cè)試集T。由于CU的劃分層次不同，訓(xùn)練樣本集 S分為三類：S0、S1和 S2，分別表示CuDepth=i的訓(xùn)練樣本集(i=0,1,2)，同樣測(cè)試集T可以分為T0、T1和T2。

RFC模型訓(xùn)練中，決策樹的數(shù)量（nTrees）和特征屬性的隨機(jī)選取個(gè)數(shù)（nFeatures）這兩個(gè)參數(shù)對(duì)隨機(jī)森林的分類精度都有極大的影響。目前對(duì)于隨機(jī)森林參數(shù)的選擇多采用經(jīng)驗(yàn)值方式，經(jīng)驗(yàn)值往往不夠準(zhǔn)確，為了在運(yùn)行效率可接受的范圍內(nèi)選擇出最佳的參數(shù)組合（nTrees，nFeatures），本文采用了基于網(wǎng)格搜索的參數(shù)尋優(yōu)方法，以訓(xùn)練樣本的分類準(zhǔn)確率（Accuracy）為目標(biāo)，通過(guò)大量實(shí)驗(yàn)分析，同時(shí)考慮RFC分類性能和訓(xùn)練模型的復(fù)雜度，最終選擇（22，5）作為最佳參數(shù)組合值。

RFC模型建立的相關(guān)訓(xùn)練參數(shù)設(shè)置如表1所示。

表1 訓(xùn)練參數(shù)設(shè)置

3.1.3 離線訓(xùn)練

根據(jù)表1設(shè)定參數(shù)，RFC模型進(jìn)行離線訓(xùn)練，建立過(guò)程如圖3所示。

具體步驟描述如下：

（1）給定訓(xùn)練樣本集S和測(cè)試集T。

（2）利用Bootstrap法重采樣數(shù)據(jù)樣本集S，生成K個(gè)訓(xùn)練樣本集{S*1,S*2,…,S*K}，每次沒有被抽到的樣本組成K個(gè)袋外數(shù)據(jù)集；將生成的每個(gè)訓(xùn)練集S*i作為根節(jié)點(diǎn)，生成對(duì)應(yīng)的決策樹{T1,T2,…,TK}。

圖3 隨機(jī)森林分類模型的生成

（3）從根節(jié)點(diǎn)開始訓(xùn)練，在決策樹的每個(gè)中間節(jié)點(diǎn)（非葉節(jié)點(diǎn)）上隨機(jī)選擇m個(gè)屬性（m?M,M為特征屬性變量個(gè)數(shù)），遍歷計(jì)算每個(gè)屬性的gini指標(biāo)系數(shù)，從中選擇gini值最小的屬性作為當(dāng)前節(jié)點(diǎn)的最優(yōu)分裂屬性，以當(dāng)前gini值為分裂閾值，劃分為左右子樹。

（4）重復(fù)步驟（3），訓(xùn)練K次，直到K棵決策樹訓(xùn)練完成，每棵決策樹都完整生長(zhǎng)而不進(jìn)行剪枝。

（5）將生成的多棵決策樹組成隨機(jī)森林，用隨機(jī)森林分類器（RFC）對(duì)測(cè)試集T進(jìn)行判別分類，分類結(jié)果采用投票方式，將K棵決策樹輸出最多的類別作為測(cè)試集T的所屬類別。

3.1.4 訓(xùn)練測(cè)試評(píng)估

利用HM編碼器對(duì)CU的劃分結(jié)果，選擇測(cè)試集T和10折交叉驗(yàn)證法（Cross Validation，CV）法來(lái)測(cè)試評(píng)估不同訓(xùn)練模型對(duì)CU的劃分性能，實(shí)驗(yàn)過(guò)程中統(tǒng)計(jì)不同RFC模型的訓(xùn)練時(shí)間，所得RFC(0)、RFC(1)和RFC(2)的平均訓(xùn)練時(shí)間如表2所示，RFC(i)表示CUdepth=i時(shí)的RFC模型(i=0,1,2)，RFC模型訓(xùn)練屬于離線訓(xùn)練過(guò)程，訓(xùn)練好的模型被導(dǎo)入到HM編碼器中用于CU的預(yù)測(cè)劃分，因此，訓(xùn)練時(shí)間不計(jì)入序列的編碼時(shí)間。表2還列出了訓(xùn)練好的模型在不同CU層次下預(yù)測(cè)的準(zhǔn)確率。從表2可看出利用RFC模型預(yù)測(cè)CU劃分的平均準(zhǔn)確率為90.18%，綜合考慮編碼性能和編碼復(fù)雜度，基于隨機(jī)森林的分類模型適合編碼單元CU的劃分判定。

表2 不同RFC模型的訓(xùn)練時(shí)間和預(yù)測(cè)準(zhǔn)確率

3.2 基于隨機(jī)森林分類的CU快速劃分算法

將CU的劃分問(wèn)題建模為分類問(wèn)題，本文利用隨機(jī)森林分類器預(yù)測(cè)CU的劃分結(jié)果，其算法流程如圖4所示，具體步驟描述如下。

圖4 基于隨機(jī)森林分類的CU劃分算法流程圖

步驟1對(duì)于一個(gè)CTU，從CuDepth=0開始編碼。

步驟2計(jì)算當(dāng)前CU的特征屬性值。

步驟3加載訓(xùn)練好的RFC(i)，對(duì)當(dāng)前CU預(yù)測(cè)劃分結(jié)果(i=0,1,2)。

步驟4如果判定當(dāng)前CU劃分，CuDepth加1，并將當(dāng)前CU劃分成4個(gè)Sub-CUs，然后返回步驟2繼續(xù)執(zhí)行；否則，編碼當(dāng)前層次下一個(gè)CU，返回步驟2執(zhí)行。

步驟5結(jié)束當(dāng)前CTU的編碼，開始編碼下一個(gè)CTU。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)參數(shù)配置與算法性能評(píng)定

本文實(shí)驗(yàn)在配置為4.00 GHz，內(nèi)存為8.00 GB計(jì)算機(jī)上的Visual Studio 2012環(huán)境上運(yùn)行。

本文算法基于HEVC參考軟件HM-16.0[12]實(shí)現(xiàn)。編碼方案采用通用測(cè)試條件[13]中的全幀內(nèi)編碼模式，即All-Intra-Main（AI-Main）配置文件。量化參數(shù)QP分別選用22，27，32，37，測(cè)試序列選擇表3中除用于訓(xùn)練序列（Traffic、ParkScene、RaceHorses、BasketballDrill和Johnny）之外的剩余序列，每個(gè)測(cè)試序列編碼100幀。

實(shí)驗(yàn)中對(duì)本文算法的峰值信噪比變化量BDPSNR（dB）和碼率變化率BDBR（%）[14]進(jìn)行統(tǒng)計(jì)，分析了算法的率失真性能。為了衡量計(jì)算復(fù)雜度[15]的變化，實(shí)驗(yàn)統(tǒng)計(jì)了使用本文算法的編碼時(shí)間變化率ΔT，計(jì)算方法如公式（4）：

公式（4）中，timeHM16.0(Q Pi)，timeproposed(Q Pi)分別表示HM16.0編碼器和本文算法在不同QP值時(shí)的編碼時(shí)間，ΔT為4個(gè)QP值下編碼時(shí)間的均值。

表3 HEVC通用測(cè)試序列

4.2 算法性能比較分析

為了全面評(píng)估本文算法的性能，將本文算法與HM編碼器和文獻(xiàn)[6]算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表4所示。

從表4中可以看出，與HM16.0編碼器算法相比，本文算法平均減少45.18%的編碼時(shí)間，同時(shí)保持了與HM16.0相近的率失真性能，BDBR平均增加了1.23%，BDPSNR平均降低了0.048 dB。此外，本文算法在編碼時(shí)間和率失真性能方面都優(yōu)于文獻(xiàn)[6]中的方法。文獻(xiàn)[6]中的算法是利用單一決策樹實(shí)現(xiàn)對(duì)CU的預(yù)測(cè)劃分，決策規(guī)則簡(jiǎn)單易實(shí)現(xiàn)，但是在訓(xùn)練模型尤其是遇到噪音數(shù)據(jù)時(shí)，很容易出現(xiàn)過(guò)擬合現(xiàn)象，降低分類精度。本文算法將多棵樹集成森林，利用集成學(xué)習(xí)中的隨機(jī)森林分類算法，多數(shù)投票實(shí)現(xiàn)對(duì)CU的預(yù)測(cè)劃分，在提高預(yù)測(cè)精度的同時(shí)還降低了編碼復(fù)雜度。

表4 本文算法和文獻(xiàn)[6]算法在AI-Main環(huán)境下與HM性能比較

圖5 不同算法在AI-Main編碼配置環(huán)境下的率失真性能比較

圖5 以視頻序列“PeopleOnStreet”（2 560×1 600）和“BQMall”（832×480）為例，給出了HM16.0編碼器、文獻(xiàn)[6]算法和本文算法在AI-Main編碼配置環(huán)境下的率失真性能比較。其中Y-PSNR為亮度Y峰值信噪比，Bitrate為每秒碼流的大小。

從圖5（a）、（b）兩組實(shí)驗(yàn)可看出，與HM和文獻(xiàn)[6]相比，PeopleOnStreet和BQMall序列在不同的碼率下表現(xiàn)略有差異，但是本文算法的編碼性能與HM相比沒有顯著的下降，而且比文獻(xiàn)[6]的效果要好。在算法編碼性能損失幾乎可以忽略的情況下，比文獻(xiàn)[6]算法還能減少約11.51%的時(shí)間。因此，本文提出的快速編碼算法能夠?qū)崿F(xiàn)較好的編碼器性能。

5 結(jié)束語(yǔ)

本文針對(duì)HEVC幀內(nèi)編碼過(guò)程中，編碼單元CU劃分過(guò)程計(jì)算復(fù)雜度高的問(wèn)題，提出了基于機(jī)器學(xué)習(xí)隨機(jī)森林分類的CU快速劃分算法。該算法包括RFC模型訓(xùn)練和CU快速編碼兩部分。在離線訓(xùn)練時(shí)，根據(jù)視頻內(nèi)容與CU劃分的密切關(guān)系，選擇當(dāng)前CU的統(tǒng)計(jì)特性（對(duì)比度、逆差矩和熵）作為模型訓(xùn)練的特征屬性，以CU是否劃分{1，-1}為分類結(jié)果，進(jìn)行學(xué)習(xí)訓(xùn)練。在編碼過(guò)程中，計(jì)算當(dāng)前CU的特征屬性值，利用離線訓(xùn)練好的RFC模型快速判斷當(dāng)前CU的劃分結(jié)果，從而降低HEVC的編碼復(fù)雜度。實(shí)驗(yàn)證明，在幾乎相同的率失真性能情況下，本文算法比HEVC編碼器提高了45.18%的編碼速度，而且本文算法比文獻(xiàn)[6]的快速算法，還能提高約11.51%的編碼速度。下一步將繼續(xù)研究幀間編碼過(guò)程中CU劃分與編碼塊的統(tǒng)計(jì)特性間的關(guān)系，最終選擇更合適的編碼方法，進(jìn)一步加快HEVC的編碼速度。

[1]萬(wàn)帥，楊付正.新一代高效視頻編碼H.265/HEVC：原理、標(biāo)準(zhǔn)與實(shí)現(xiàn)[M].北京：電子工業(yè)出版社，2014：12.

[2]Sullivan G J，Ohm J，Han W J，et al.Overview of the high efficiency video coding（HEVC） standard[J].IEEE Transactions on Circuitsamp;Systems for Video Technology，2012，22（12）：1649-1668.

[3]金智鵬，代紹慶，王利華.HEVC幀內(nèi)編碼單元快速劃分算法[J].南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，35（2）：58-63.

[4]劉柱寨.新一代視頻編碼標(biāo)準(zhǔn)HEVC參考幀設(shè)置與塊劃分快速算法研究[D].廣州：華南理工大學(xué)，2014.

[5]Cho S，Kim M.Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[J].IEEE Transactions on Circuitsamp;Systems for Video Technology，2013，23（9）：1555-1564.

[6]Zheng Xing，Zhao Yao，Bai Huihui，et al.Fast algorithm for intra prediction of HEVC using adaptive decision trees[J].Ksii Transactions on Internetamp;Information Systems，2016，10（7）：3286-3300.

[7]沈曉琳.HEVC低復(fù)雜度編碼優(yōu)化算法研究[D].杭州：浙江大學(xué)，2013.

[8]Breiman L.Random forests[J].Machine Learning，2001，45（1）：5-32.

[9]Breiman L.Bagging predictors[J].Machine Learning，1996，24（2）：123-140.

[10]Ho T K.The random subspace method for constructing decision forests[J].IEEE Transactions on Pattern Analysisamp;Machine Intelligence，1998，20（8）：832-844.

[11]方匡南，吳見彬，朱建平，等.隨機(jī)森林方法研究綜述[J].統(tǒng)計(jì)與信息論壇，2011，26（3）：32-38.

[12]JCT-VC of ISO/IEC and ITU-T.HM reference software16.0[EB/OL].（2014）.https：//hevc.hhi.fraunhofer.de/trac/hevc/browser#tags/HM-16.0.

[13]Bossen F.Document JCTVC-L1100：Common test conditions and software reference configurations[C]//Proceedings of the 12th Meeting of Joint Collaborative Team on Video Coding（JCT-VC） of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11，2013.

[14]B?ntegaard G.Document VCEG-M33：Calculation of average PSNR differences between RD-curves[C]//VCEG Meeting（ITU-T SG16 Q.6），2001.

[15]Bossen F，Bross B，Suhring K，et al.HEVC complexity and implementation analysis[J].IEEE Transactions on Circuitsamp;Systems for Video Technology，2012，22（12）：1685-1696.

WU Xiaorong1,SHI Zhibin1,LEI Haiwei2,DU Bo1

1.School of Computer and Control Engineering,North University of China,Taiyuan 030051,China 2.Key Laboratory of Instrumentation Scienceamp;Dynamic Measurement,Ministry of Education,North University of China,Taiyuan 030051,China

Fast CU partition algorithm for HEVC intra-frame based on random forest classifier.Computer Engineering and Applications,2017,53（21）：115-120.

To reduce the coding computational complexity of the quadtree structured Coding Unit（CU）partition process forintra-framein High Efficiency Video Coding（HEVC）,a fast CU splitting algorithm based on Random Forest Classifier（RFC）is proposed.The algorithm includes two parts:model off-line training and CU fast coding algorithm.In the process of off-line training,a RFC model is constructed,where the optimal partition result of current CU is utilized as class label（+1,-1）,and the contrast,the inverse different moment and the entropy information of current CU are treated as feature vectors.In the process of encoding,characteristic attribute values of current CU are extracted,then,a trained RFC model is used to predict the class label.The experimental results show that the proposed algorithm can save 45.18%coding time on average under the premise of guaranteeing the coding quality compared with HEVC standard algorithm.

random forest;fast encoding;offline training;CU partition;High Efficiency Video Coding（HEVC）

A

TN919.81

10.3778/j.issn.1002-8331.1704-0115

2015年度山西省高校科技創(chuàng)新項(xiàng)目（No.20151101）。

毋笑蓉（1992—），女，碩士研究生，主要研究領(lǐng)域?yàn)橐曨l編碼、智能分類算法，E-mail：1035737097@qq.com；師智斌（1971—），女，博士，副教授，主要研究領(lǐng)域?yàn)槿斯ぶ悄?、?shù)據(jù)挖掘、模式識(shí)別；雷海衛(wèi)（1980—），男，博士研究生，講師，主要研究領(lǐng)域?yàn)橐曨l信號(hào)處理、3D視頻編碼；杜博（1990—），男，碩士研究生，主要研究領(lǐng)域?yàn)橐曨l信號(hào)處理、3D視頻編碼。

2017-04-11

2017-06-19

1002-8331（2017）21-0115-06