基于改進的隨機森林的人體部件識別

郭天楚，吳曉雨，楊磊，黃向生

(1.中國傳媒大學(xué)信息工程學(xué)院，北京100024；2.中國科學(xué)院自動化研究所，北京 100190)

1 引言

人體姿態(tài)估計與識別是現(xiàn)在自然人機交互最為重要的一個環(huán)節(jié)。攝像頭捕捉人體影像，估計與擬合人體姿態(tài)，分析用戶動作含義，理解用戶主觀意愿，不通過任何接觸媒介，達到了自然交互的目的。姿態(tài)估計近十年中一直是計算機視覺領(lǐng)域中的一個研究目標(biāo)?，F(xiàn)有的姿態(tài)估計方法有[6][21][22][23][24]。但微軟采用人體部件識別的姿態(tài)估計效果最為突出[20]。微軟采用Kinect的深度攝像頭，捕捉人體深度數(shù)據(jù)，先將人體分為若干部件，以隨機森林的方式識別出人體各個部分，再將每部分用mean shift算法尋找出部件質(zhì)心作為關(guān)鍵點做的骨骼追蹤。微軟Kinect骨骼追蹤的成功也證實了隨機森林是一個高效準(zhǔn)確的分類器。

傳統(tǒng)隨機森林的分裂準(zhǔn)則是尋找全局最優(yōu)特征作為分裂特征。對于類別間差異較小的案例，全局特征很容易引起類間差異較小的類別的分類錯誤。在人體部件識別中，上肢的各個部件差異性較小，而上下肢差異性較大。傳統(tǒng)隨機森林尋找的是全局最優(yōu)，對于上肢各部件的區(qū)分度低，故而本文提出分層預(yù)測的思想，引入分層森林。對于特征空間較大時，本文提出了特征預(yù)篩選的方案，提高了森林的分類性能。

本文融合了前人的研究經(jīng)驗，對于人體部件識別的案例，將人體劃分為26個部件，用深度數(shù)據(jù)提取深度上下文為特征進行分類。訓(xùn)練數(shù)據(jù)為11個人在真實場景下的深度數(shù)據(jù)。本文在第二章詳細講述了特征預(yù)篩選的方式。在第三章中，提出了分層隨機森林的方式，以及對應(yīng)的錯誤衡量標(biāo)準(zhǔn)。第四章和第五章分別為實驗與結(jié)論。

2 隨機森林原理

隨機森林是由若干決策樹通過一定方式組成。決策樹被認為是一種有效的分類方法。為了接近完美的訓(xùn)練出決策樹模型，我們通常會加大樹的深度。然而這樣的方式會使得決策樹在訓(xùn)練樣本集上有接近完美的預(yù)測，但是在預(yù)測樣本集中有著較差的效果，即決策樹過擬合。盡管后續(xù)提出了許多決策樹剪枝的方式，但是對于多類別區(qū)分，即使使用CART代替?zhèn)鹘y(tǒng)離散類別決策樹，單棵樹還是略顯薄弱。

隨機森林算法隨機森林算法是Leo Breiman和Adele Cutler于2001年共同提出的一種分類算法[1]，它集成了由Breiman 提出的Bagging[2]、CART 決策樹思想[3]以及貝爾實驗室的Tin Kam Ho 和Geman分別提出的特征隨機選取思想[4]。該方法利用若干棵相互獨立的決策樹共同表決得到預(yù)測結(jié)果，回避單棵決策樹造成過擬合問題。隨機森林利用bagging模型，采用訓(xùn)練樣本集隨機，特征集隨機的雙隨機方式構(gòu)造出若干顆獨立的樹，組成森林。在樹的構(gòu)造過程中，從總的訓(xùn)練樣本空間中隨機抽取一部分為子集作為單棵樹的訓(xùn)練數(shù)據(jù)，在訓(xùn)練樣本上保證了樹與樹之間的獨立性。對于每一個分裂節(jié)點(非葉子節(jié)點)，都在總特征空間中隨機抽取特征子集作為每個節(jié)點的候選特征集，使得樹與樹的節(jié)點之間，以及每棵樹的各個節(jié)點之間的特征子集都不同，在特征集上保證了樹的獨立性。由于參與訓(xùn)練每棵樹的樣本集與特征集都不會完全覆蓋樣本空間及特征空間，每棵樹對訓(xùn)練樣本集的噪聲有很大的容忍性。隨機森林的精髓在于每棵樹之間的獨立。獨立的直觀反映是每棵樹的分工不同，每棵樹相當(dāng)于是對于某個或者某少部分領(lǐng)域的專家。預(yù)測過程中，是由各個專家綜合投票決定出預(yù)測樣本所屬的類別。

在隨機森林的發(fā)展中，大多研究者在以下幾個方面對隨機森林進行了深入研究。如何構(gòu)建每一棵樹才能使得森林中樹與樹之間獨立性更強，如何對每棵樹的訓(xùn)練樣本子集進行劃分[7]，如何篩選更為高效的特征以及特征組合能提高樹的效率，如何組合樹使得隨機森林的模型具有更高的預(yù)測準(zhǔn)確性，如何設(shè)定訓(xùn)練樣本子集與特征子集的大小才能既保證訓(xùn)練速度，也保證預(yù)測準(zhǔn)確性。文獻[8]中，對隨機森林的發(fā)展進行了一定的梳理。王全才，對特征選擇方法歸為了Filter方法，Wrapper方法和集成方法三類[9]。劉曉東對組合特征“和特征”進行了研究與性能測試[10]。馬景義[11]細致的描述了隨機森林的分類意義。在樹與樹之間的組合模型中，研究者們又提出了對于原始隨機森林的派生。其中，文獻[12]中提出了隨機生存森林。

3 特征預(yù)篩選

3.1 特征

與Kinect骨骼追蹤的案例一致[20]，我們利用背景減除法得到了較為干凈的人物數(shù)據(jù)。訓(xùn)練數(shù)據(jù)為僅人體上含有采集到的深度信息，背景的深度為極大值(實驗中，設(shè)定為10的9次方)以深度上下文為特征。該特征定義如公式(1)

其中，F(xiàn)(x，I)表示圖像I中x像素點的特征，d(x，I)表示圖像I中x的深度值，u和v分別代表偏移量。那么圖像I中x像素點的特征可以描述為，隨機產(chǎn)生u，v兩個偏移量，且u，v均包含水平垂直信息，像素x偏移u之后的深度值減去像素x偏移v后的深度值。需要強調(diào)的是，為了消除人與攝像頭之間距離對特征產(chǎn)生的影響，這里x偏移u，v后的深度值要進行歸一化，即除以x像素處的深度值。如圖1(a)。

(a)

(b)圖1

如上文所說，偏移量(offset)u，v有多個取值，若限定u，v偏移范圍為以像素點x的坐標(biāo)為中心，水平垂直均為100個像素的區(qū)域內(nèi)，則u，v取值都有100*100個，對于同一個圖片上同一個像素點，其特征空間為10000*10000個。由于特征空間非常龐大，訓(xùn)練過程中不可能窮舉特征空間中的所有特征進行一一計算再篩選出最有效的特征作為樹節(jié)點的分裂特征。根據(jù)隨機森林特征的選取方式，我們隨機選取特定數(shù)目的特征，組成特征子集，再從特征子集中選取最有效的特征作為樹節(jié)點的分裂特征。然而，特征空間過于龐大，且特征空間中包含許多已知的無效特征。在訓(xùn)練中，我們希望特征子集可以包含更多的有效特征，這樣才會得到相對最優(yōu)特征，避免特征子集中無效特征占大多數(shù)，使得有效特征受到特征子集大小的限制，并沒有被包含在其中。這里所定義的無效特征為所有訓(xùn)練數(shù)據(jù)對該特征響應(yīng)均一致的特征，如無論x點在哪里，特征相應(yīng)均為0，如圖1(b)中，u，v偏移量過大時，偏移u后的歸一化深度與偏移v后的歸一化深度均訪問到背景，則x像素點的特征為0。

3.2 基于Bin方差的篩選

在分類中，特征響應(yīng)越分散越好。樣本對某一特征的響應(yīng)直方圖的橫坐標(biāo)是不確定，若遍歷求取整個特征響應(yīng)直方圖的方差，引入了較大的計算量。本例采用人體于背景分割后的數(shù)據(jù)，當(dāng)特征偏移量u偏移到背景上，v偏移到人體上時，特征有極大的正響應(yīng)；相反的，有極大的負響應(yīng)；當(dāng)u，v均偏移到人體上時，特征響應(yīng)在一個中間值區(qū)間內(nèi)。依據(jù)此現(xiàn)象，將響應(yīng)分布定義為三類，1為極大正響應(yīng)部分，2為極大負響應(yīng)部分，3為中間部分?；诜讲詈Y選的判定準(zhǔn)則為，對于某一特征的響應(yīng)分布，越均勻的分布在這三類中越為有效特征。公式定義如下

BinVariance(f0，X)=

在實驗中，該特征篩選方式是高效的，尤其對于小樣本訓(xùn)練及少類別訓(xùn)練。當(dāng)訓(xùn)練樣本空間較小時，很容易造成特征響應(yīng)分布區(qū)域一致，該方法大約可以篩選掉10%的無效特征。隨著樣本空間的增大，特征響應(yīng)趨于多樣化，無效特征率會降低。當(dāng)樹節(jié)點越遠離根節(jié)點時，節(jié)點包含類別越少，越趨于一致化，該方法可以篩選掉更多的無效特征。詳細實驗結(jié)果在第四章說明。

4 分層隨機森林

4.1 節(jié)點分裂準(zhǔn)則

結(jié)點分裂是生成決策樹的重要步驟，只有根據(jù)不同的特征將結(jié)點分開，才能將樣本數(shù)據(jù)劃分為多個類別，因此，整個問題的核心就是如何選擇分裂特征。選擇分裂特征的算法有ID3，C4.5，CART，分裂準(zhǔn)則分別為信息增益(information gain)，信息增益比(information gain ratio)，Gini 指標(biāo)(Gini Index)。早期提出的基于主軸的構(gòu)建[13]是按照類別的歐式距離進行分割，計算量較大。

本文采用CART思想，以熵增益為準(zhǔn)則[20]，定義判定標(biāo)準(zhǔn)如下：

上式將樹定義為二叉樹，特征f0將樣本劃分為左右兩個子集，L代表左子集，R代表右子集。

對于每棵樹完全生長，不剪枝。當(dāng)節(jié)點剩余數(shù)據(jù)純凈時，停止分裂。當(dāng)節(jié)點剩余數(shù)據(jù)小于某個特定閾值時，停止分裂。當(dāng)節(jié)點深度大于某個閾值時，停止分裂。當(dāng)前不分裂的節(jié)點為樹的葉子節(jié)點。葉子節(jié)點保存的信息是當(dāng)前節(jié)點中剩余數(shù)據(jù)屬于各個標(biāo)簽的分布概率，并不是某一個特定的標(biāo)簽。一個森林包含了T個決策樹，每棵樹包含了分裂節(jié)點和葉子節(jié)點。每個非葉子節(jié)點包含了分裂特征f 以及一個閾值t，每個葉子節(jié)點包含了一個標(biāo)簽分布率。

對于像素x的分類，先根據(jù)第二章的特征公式(1)計算x像素點的特征，根據(jù)節(jié)點分裂閾值TS(Threshold of Split)判斷x屬于節(jié)點的左分支或者右分支，依次判定直到到達樹的葉子節(jié)點。這時獲取葉子節(jié)點對于標(biāo)簽的分布概率。將按公式(4)森林中所有樹對于該像素x的標(biāo)簽分布概率加權(quán)求平均，即得x在被森林預(yù)測屬于各個標(biāo)簽的概率分布。按公式(5)取概率最大的標(biāo)簽為x像素的標(biāo)簽。

Label(x)=arg max(P(c；x))

(5)

公式(4)(5)表示了對于像素x，由森林中的每棵樹投票表決，概率最大的標(biāo)簽即為x的標(biāo)簽。

4.2 分層森林

在本例中，根據(jù)人體動作復(fù)雜度可以看出，人的四肢動作較豐富，而上半身與下半身交叉動作較少。在手臂彎曲角度較大時，會把手與肩膀分類錯誤，如圖2。這都是由于在區(qū)分26個部件時，短小特征沒有被選取造成的。在特征子集中，樹節(jié)點分裂選取的是對于所有部件有較大區(qū)分能力的特征。但是某些動作手部靠的太近，只有微小特征，即偏移向u，v較小時才會有所區(qū)分，而這樣的特征在區(qū)分全局26個部件時并不是最有效的。為了解決這樣的問題，我們采取分層分類的思想。先將人體分為上下兩部分，在分別對上半身即下半身的部件分類。定義區(qū)分上下半身的森林為第一層分類器，再分別區(qū)分上下半身各個部件的森林為第二層分類器。這種組合策略可以根據(jù)樣本的實際情況提前對特征進行分類，缺點是第二層分類是否準(zhǔn)確完全依賴于第一層，若第一層將某一屬于上半身的像素x錯分為下半身，那么無論第二層分類器如何高效，x均為錯分樣本。

圖2

預(yù)測流程圖如3。

圖3

分層森林由三部分組成，分別為，分層分類器，上分類器，下分類器。每個分類器均為進行特征預(yù)篩選過的隨機森林，隨機森林包含兩棵樹。對于像素x，先經(jīng)過分層分類器預(yù)測，根據(jù)預(yù)測結(jié)果(屬于上半身或者下半身，流程圖中用紅綠兩種顏色表示)，再對應(yīng)傳入上下肢分類器進行預(yù)測。經(jīng)上下肢分類器預(yù)測后的結(jié)果為x的最終類別。

4.3 森林的誤差評定

本文用分類錯誤概率總和來衡量分類誤差。公式(6)描述的PEC(Probability Error of Classification)為類別概率誤差，表示樣本空間X中所有像素x本為類別j，卻被錯分為其他類別的概率之和。公式(7)描述的PEF(Probability Error of Forests)表示森林的總錯誤概率，為所有類別權(quán)重乘以對應(yīng)類別概率誤差之和，權(quán)重系數(shù)為該類別所有樣本點數(shù)除以總樣本空間大小。

以上兩個公式在下一章的實驗中均用于測試樣本集的誤差計算。

5 實驗

5.1 訓(xùn)練樣本

本例中的訓(xùn)練數(shù)據(jù)分為大樣本與小樣本，大樣本來自11個人的真實深度數(shù)據(jù)2079張，包含8個組別的動作，小樣本來自同一組別的428張圖片。深度數(shù)據(jù)利用背景減除法得到較為干凈的人體數(shù)據(jù)，手動標(biāo)注人體包含26個部件。圖4為標(biāo)準(zhǔn)T字動作的標(biāo)注示意圖。將非人體背景的深度全部置為一個極大值，實驗中設(shè)定為10的9次方。訓(xùn)練樣本集僅包含人體上肢動作。每個森林包含6棵樹，大樣本每棵樹10度深，每棵樹的每個節(jié)點隨機抽取500個有效的特征，小樣本每棵樹7度深，每棵樹的每個節(jié)點隨機抽取100個有效的特征。每張圖片隨機采樣2000個點。26個部件每個部件的采樣率約為0.3。

圖4

5.2 閾值過濾

在樹的節(jié)點分裂時，需要選取一個閾值進行左右叉子集的分割。一個特征對于該節(jié)點所有剩余樣本均產(chǎn)生一個特征響應(yīng)值，其響應(yīng)值空間不固定，若遍歷響應(yīng)值區(qū)間來尋找分裂閾值是十分低效的方法。根據(jù)第四章提出的樹節(jié)點分裂準(zhǔn)則，落入某一分裂特征響應(yīng)值中的樣本數(shù)目越多，該特征響應(yīng)值對熵增益影響越大。以特征響應(yīng)值為橫坐標(biāo)，在該特征響應(yīng)值下樣本個數(shù)為縱坐標(biāo)建立直方圖。將樣本個數(shù)較多的前50%的特征響應(yīng)取出，組成構(gòu)造閾值子集。將構(gòu)造閾值子集中的特征響應(yīng)按大小排序，取其兩兩之間的中點作為閾值子集。遍歷閾值子集，找到在該特征下，產(chǎn)生熵增益最大的閾值，記為該特征對樣本產(chǎn)生的熵增益。選取熵增益最大的特征作為該節(jié)點的分裂特征，對應(yīng)的閾值，為該節(jié)點的分裂閾值。

Label(x)=arg max(P(c；x))

(8)

5.3 特征預(yù)篩選對比

圖5為特征預(yù)篩選的實驗結(jié)果。采用包含人體上肢動作的大樣本作為訓(xùn)練數(shù)據(jù)，一組采用基于方差的特征與篩選，一組未采用，分別訓(xùn)練6棵樹的傳統(tǒng)隨機森林。測試集由每個動作組別中抽取若干數(shù)據(jù)組成，測試集未參與訓(xùn)練。按第四章提到的公式(6)計算每個部件的誤差及森林的總誤差。上圖可以看出，與未預(yù)篩選的森林相比，進行特征預(yù)篩選的森林對于大多數(shù)部件的錯誤率要更低一些。無效特征率約為10%(無效特征率定義為N個總特征中的無效特征的比率)。

圖5

5.4 分層預(yù)測對比

在分層森林的訓(xùn)練中，分層樹2棵，作用是先將人體分為上下半身兩部分，上下半身各2棵樹，共6棵樹組成森林。圖6(a)為6棵樹按分層方式組合為2層分類器，與6棵樹并列組成傳統(tǒng)隨機森林分類器的預(yù)測圖比較結(jié)果。訓(xùn)練數(shù)據(jù)為小樣本，測試集為該動作類別中的一組未參與訓(xùn)練的數(shù)據(jù)。

從左至右分別為原始標(biāo)注結(jié)果，傳統(tǒng)森林預(yù)測結(jié)果，分層森林預(yù)測結(jié)果。對于肢體與肢體靠的很近的動作，分層森林的小特征引入可以更好的區(qū)分出各個關(guān)節(jié)，不會造成混亂。

各個部件分類錯誤概率圖如圖6(b)。

上述數(shù)據(jù)顯示，分層森林對于同等棵樹的森林預(yù)測性能要比傳統(tǒng)隨機森林好一些。這證明該組合模型方式對分類器整體性能有貢獻。需要強調(diào)的是本文所提到的誤差評定方式本身會引入一些誤差。因為對于原始數(shù)據(jù)，相鄰關(guān)節(jié)會引入邊界誤差，即該像素x被判定為兩個部件從主觀評定上均為正確，但客觀評定很會被計算為錯誤分類。

(a)

(b)圖6

6 結(jié)論

本文提出了隨機森林中一種特征預(yù)篩選的方式，分析他的有效性及篩選效率，并驗證了方差篩選對本實例是高效。在森林組合模型中，提出了一種分層森林的組合方式來引入小特征，分層次對人體部件預(yù)測在實驗中量化的證明了，分層森林的組合模型對于分類性能是有提高的。不足的是并沒有給出一個公式來規(guī)范分層分類方法。在未來的探索與實踐中，應(yīng)更加注重尋找出一個指導(dǎo)性的公式。

[1]Breiman L. Random forests[J]. Machine learning，2001，45(1)：5-32.

[2]Breiman L. Bagging predictors[J]. Machine learning，1996，24(2)：123-140.

[3]Breiman L，F(xiàn)riedman J，Stone C J，et al. Classification and regression trees[M]. Chapman& Hall/CRC，1984.

[4]Ho T K. The random subspace method for constructing decision forests[J]. IEEE Transactions on Pattern Analysisand Machine Intelligence，1998，20(8)：832-844.

[5]Han J，Shao L，Xu D，et al. Enhanced computer vision with microsoft kinect sensor：A review[J]. IEEE Transaction on Cybernetics,2013,43(5):1318-1334.

[6]Dantone M，Gall J，Leistner C，et al. Human pose estimation using body parts dependent joint regressors[C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)，2013：3041-3048.

[7]Genuer R，Poggi J M，Tuleau-Malot C. Variable selection using random forests[J]. Pattern Recognition Letters，2010，31(14)：2225-2236.

[8]Scornet E，Biau G，Vert J P. Consistency of Random Forests[J]. arXiv preprint arXiv：1405.2881，2014.

[9]王全才. 隨機森林特征選擇[D]. 大連理工大學(xué)，2011.

[10]劉曉東. 基于組合策略的隨機森林方法研究[D]. 大連理工大學(xué)，2013.

[11]馬景義，謝邦昌. 用于分類的隨機森林和 Bagging 分類樹比較[J]. 統(tǒng)計與信息論壇，2010，25(010)：18-22.

[12]Ishwaran H，Kogalur U B，Blackstone E H，et al. Random survival forests[J]. The Annals of Applied Statistics，2008：841-860.

[13]Ho T K. Random decision forests[C].IEEE Proceedings of the Third International Conference on Document Analysis and Recognition，1995，1：278-282.

[14]宋麗. 基于決策樹的組合分類器的研究[D]. 西安電子科技大學(xué)，2012.

[15]劉艷麗.隨機森林綜述[D].南開大學(xué)碩士學(xué)位論文，2008：1-5.

[16]李建更，高志坤. 隨機森林針對小樣本數(shù)據(jù)類權(quán)重設(shè)置[J]. 計算機工程與應(yīng)用，2009，45(26)：131-134.

[17]董立巖，李真，周靈艷. 特定信息增益決策森林分類器研究[J]. 計算機工程與應(yīng)用，2010，46(26).

[18]李建更，高志坤.隨機森林針對小樣本數(shù)據(jù)類權(quán)重設(shè)置[J].計算機工程與應(yīng)用，2009，45(26)：131-134.

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

[20] Shotton J，F(xiàn)itzgibbon A，Cook M，etal.Real-Time Human Pose Recognition in Parts from a Single Depth Image[C].Proc IEEE Conf on Computer Vision and Pattern Recognition，2011：1297-1304.

[21]Girshick R，Shotton J，Kohli P，etal.Efficient Regression of General-Activity Human Poses from Depth Images[C].IEEE International Conference on Computer Visionl(ICCV)，2011.

[22]Taylor J，Shotton J，Sharp T，F(xiàn)itzgibbon A.The Vitruvian Manifold：Inferring Dense Correspondences for One-Shot Human Pose Estimation[C].IEEE Conference on Computer Visionl and Recognition(CVPR)，2012：103-110，2012.

[23]Ye M，Wang X，Yang R，etal.Accurate 3D Pose Estimation from A Single Depth Image[C].IEEE International Conference on Computer Visionl(ICCV)，2011：731-738.

[24]Deng K，Bai X，Leyvand T.Exemplar-Based Human Action Pose Correction and Tagging Proc[C]. IEEE Conf on Computer Vision and Pattern Recognition，2012：1784-1791.