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

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

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

1 引言

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

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

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

2 隨機森林原理

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

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

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

3 特征預篩選

3.1 特征

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

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

(a)

(b)圖1

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

3.2 基于Bin方差的篩選

在分類中，特征響應越分散越好。樣本對某一特征的響應直方圖的橫坐標是不確定，若遍歷求取整個特征響應直方圖的方差，引入了較大的計算量。本例采用人體于背景分割后的數據，當特征偏移量u偏移到背景上，v偏移到人體上時，特征有極大的正響應；相反的，有極大的負響應；當u，v均偏移到人體上時，特征響應在一個中間值區間內。依據此現象，將響應分布定義為三類，1為極大正響應部分，2為極大負響應部分，3為中間部分。基于方差篩選的判定準則為，對于某一特征的響應分布，越均勻的分布在這三類中越為有效特征。公式定義如下

BinVariance(f0，X)=

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

4 分層隨機森林

4.1 節點分裂準則

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

本文采用CART思想，以熵增益為準則[20]，定義判定標準如下：

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

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

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

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

(5)

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

4.2 分層森林

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

圖2

預測流程圖如3。

圖3

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

4.3 森林的誤差評定

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

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

5 實驗

5.1 訓練樣本

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

圖4

5.2 閾值過濾

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

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

(8)

5.3 特征預篩選對比

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

圖5

5.4 分層預測對比

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

從左至右分別為原始標注結果，傳統森林預測結果，分層森林預測結果。對于肢體與肢體靠的很近的動作，分層森林的小特征引入可以更好的區分出各個關節，不會造成混亂。

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

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

(a)

(b)圖6

6 結論

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

[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，Friedman 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]. 大連理工大學，2011.

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

[11]馬景義，謝邦昌. 用于分類的隨機森林和 Bagging 分類樹比較[J]. 統計與信息論壇，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]. 西安電子科技大學，2012.

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

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

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

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

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

[20] Shotton J，Fitzgibbon 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，Fitzgibbon 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.