劉步實(shí)，劉致錦，覃曉，褚徐濤,梁木玲

（廣西師范學(xué)院計算機(jī)與信息工程學(xué)院，南寧 530023）

隨機(jī)森林在圖像分割中的應(yīng)用研究

劉步實(shí)，劉致錦，覃曉，褚徐濤,梁木玲

（廣西師范學(xué)院計算機(jī)與信息工程學(xué)院，南寧 530023）

圖像分割是計算機(jī)視覺領(lǐng)域尤為關(guān)鍵的任務(wù)之一，在很多醫(yī)學(xué)CT、數(shù)字媒體等領(lǐng)域都有著舉足輕重的作用。通過對2000年后出現(xiàn)的一些主要的圖像分割方法進(jìn)行整理研究，著重闡述基于集成學(xué)習(xí)框架下隨機(jī)森林方法的主要性質(zhì)，并廣泛調(diào)研隨機(jī)森林方法在圖像分割領(lǐng)域中的應(yīng)用成果，以及對其可以改進(jìn)的方向進(jìn)行論述。

0 引言

圖像分割作為機(jī)器視覺領(lǐng)域尤為關(guān)鍵的任務(wù)之一，受益于現(xiàn)代數(shù)字媒體化的快速發(fā)展，一直頗受眾多學(xué)者的重視和研究。圖像分割通過實(shí)現(xiàn)共享一定的相似屬性，將圖像中有意義的、感興趣的區(qū)域提取出來，該區(qū)域與其他區(qū)域之間一般會呈現(xiàn)較明顯的特征差異，這使得它在很多醫(yī)學(xué)CT、MRI、數(shù)字媒體等領(lǐng)域都是不可或缺的。

研究學(xué)者們對原有算法的不斷改進(jìn)以及融入新的理論方法，尤其是2000年后出現(xiàn)了不少新的分割方法。而對于圖像分割方法的分類也會有所差異，一般意義上，我們會將這些方法分為：基于區(qū)域、基于閾值、基于邊緣的分割方法。2000年后，許多學(xué)者們根據(jù)不同的圖像分割新技術(shù)，可以將它們劃分為：基于聚類的、基于圖論的、基于ACM的、基于Markov Random Fields（MFRs）等。此外，不少學(xué)者們還新穎地將機(jī)器學(xué)習(xí)方法融入到視覺系統(tǒng)中，利用機(jī)器學(xué)習(xí)方法，特別是集成學(xué)習(xí)解決圖像分割問題，逐漸地成為一種重要的學(xué)習(xí)趨勢。本文針對這種基于集成學(xué)習(xí)框架下的隨機(jī)森林（RF）算法作了更細(xì)致的論述了，并介紹了該方法在圖像分割領(lǐng)域的應(yīng)用與改進(jìn)方向。

1 基于集成學(xué)習(xí)的框架

圖像分割技術(shù)也可以看作是數(shù)學(xué)問題，根據(jù)圖像或者是研究對象的先驗(yàn)知識，通過數(shù)學(xué)模型、理論來獲得較好的分割結(jié)果。隨著AI的迅速發(fā)展，機(jī)器學(xué)習(xí)在各行各業(yè)中得到了廣泛的重視與應(yīng)用，集成學(xué)習(xí)（En鄄semble Learning）的方法更是成為了國內(nèi)外機(jī)器學(xué)習(xí)領(lǐng)域的一個熱門，通過結(jié)合多個學(xué)習(xí)器，獲得比單個方法更優(yōu)越的穩(wěn)定性和泛化性能。它主要有三個步驟：（1）生成具有差異性的分類成員；（2）選擇最合適的集成分類器；（3）按照一定的策略組合分類器。集成學(xué)習(xí)不僅在預(yù)期結(jié)果精度上得到非常顯著的提升，而且還提高了魯棒性。其中，Bagging和Boosting是集成學(xué)習(xí)的代表性算法，本文介紹的隨機(jī)森林（RF）就屬于Bag鄄ging思想上的一種延伸。

Jianhua Jia和Licheng Jiao[1]等作者提出了一種選擇性譜聚類集成算法，并把Bagging算法用在有監(jiān)督學(xué)習(xí)中，用該方法對SAR對象進(jìn)行分割取得了很好的效果。Franek L[2]等人提出了一種集成聚類框架，與其他有監(jiān)督算法的不同之處在于可以自適應(yīng)地解決組合分割的問題。Song Xiangfa[3]等人使用基于稀疏編碼和集成學(xué)習(xí)的多實(shí)例學(xué)習(xí)（MIL）來解決圖像分類問題。

2 隨機(jī)森林方法概述

隨機(jī)森林 （Random Forests）是由Leo Breiman和Adele Cutler提出的集群分類器算法。該方法在訓(xùn)練集中隨機(jī)抽取若干樣本，通過重采樣的方法，并構(gòu)建多個分類樹，最終的預(yù)測、分類結(jié)果是由分類樹投票決定。隨機(jī)森林可以處理數(shù)據(jù)量較大的高維訓(xùn)練集，且不需要顯式的特征選擇，就能達(dá)到較快的分類速度、不易過擬合以及較強(qiáng)的抗噪聲能力。它也是集成學(xué)習(xí)中的代表性算法之一。

定義1 隨機(jī)森林含有若干樹狀分類器h（x，θk），k=1，…組成的分類器，其中x指輸入變量，θk是各自獨(dú)立的且滿足同分布bootstrap集上的隨機(jī)向量，每個分類器為輸入變量x投票，將獲得投票數(shù)量最多一個分類作為x的分類結(jié)果。

定義2給定分類器h1（X），h2（X），…，hk（X），從原始數(shù)據(jù)集（X，Y）隨機(jī)抽取的樣本集合。得到余量函數(shù)為：

余量函數(shù)反映了（X，Y）的正確分類投票率與錯誤分類投票率的差異水平。余量函數(shù)得到的值越大，表示分類器的性能越準(zhǔn)確可靠。

定義3 分類器的泛化誤差（錯誤率）：

隨機(jī)森林采用作為基預(yù)測器的集成分類器，通過傳統(tǒng)的分類樹生長規(guī)則來生成若干個分類樹。與傳統(tǒng)方法的生長規(guī)則又有所不同，隨機(jī)森林的生長過程如下：

（1）設(shè)數(shù)據(jù)集中含有N個樣本，我們有放回的隨機(jī)選擇N個樣本。這選擇好的N個樣本作為個別樣本訓(xùn)練集用來訓(xùn)練一顆分類樹，作為分類樹根節(jié)點(diǎn)處的全部樣本數(shù)據(jù)。。

（2）在分類樹的每個節(jié)點(diǎn)需要分裂時，從每個樣本的所有屬性中隨機(jī)選出m個屬性，接著從這m個屬性中采用某種分裂策略（例如Gini、IG方法）選擇其中一個作為根節(jié)點(diǎn)屬性。Gini公式：

（3）分類樹形成過程中每個節(jié)點(diǎn)都要按照步驟2進(jìn)行分裂 （即如果下一次該節(jié)點(diǎn)選出來的那個屬性是剛剛其父節(jié)點(diǎn)分裂時用過的屬性，則該節(jié)點(diǎn)已經(jīng)達(dá)到了葉子節(jié)點(diǎn)，無需繼續(xù)分裂），直到不能再分裂為止。整個形成過程中不需要進(jìn)行剪枝操作，使其充分生長。

（4）按照步驟1~3訓(xùn)練出大量分類樹。將待預(yù)測的數(shù)據(jù)樣本放進(jìn)訓(xùn)練好的模型中作分類處理，統(tǒng)計每個樹分類器的預(yù)測并按照投票數(shù)量最多一個作為最終分類結(jié)果。

構(gòu)建過程如圖1所示。

圖1 隨機(jī)森林構(gòu)建圖

隨機(jī)森林算法（RF）不僅對于擁有龐大數(shù)據(jù)量、多維特征的訓(xùn)練集保持高效的訓(xùn)練效果，處理精確度高，而且可以有效地處理訓(xùn)練集中數(shù)據(jù)缺失、特征遺漏等現(xiàn)象，這在已有的許多機(jī)器學(xué)習(xí)算法中是無法替代的。

在RF中有兩項是隨機(jī)的：（1）每個樹的訓(xùn)練樣本都是隨機(jī)選取的；（2）每個節(jié)點(diǎn)的分類屬性都是隨機(jī)的。這兩個性質(zhì)不僅大大提升了訓(xùn)練速度，對離散型數(shù)據(jù)和連續(xù)型數(shù)據(jù)都可以很好地適應(yīng)，還能避免出現(xiàn)過擬合的情況。而有放回的采樣過程，使數(shù)量本來就較小的樣本被抽中的概率低于數(shù)量較多的樣本，這么做就增強(qiáng)了整個過程不被噪聲影響的能力。

每次Bagging抽樣產(chǎn)生的樣本集合，原始數(shù)據(jù)集N中就會有概率的樣本（約1/3左右）未被抽中，這些未被抽中的數(shù)據(jù)就是袋外數(shù)據(jù)（OOB）。這些數(shù)據(jù)作為袋外數(shù)據(jù)估計，用來判斷集群分類的精確度，通過測試個別訓(xùn)練集中樣本數(shù)據(jù)從而對集群分類器整體的最終分類效果作評估。RF方法在整個圖像處理的分類過程中，為每個輸入變量都設(shè)定了一個特殊的值來評定其重要性。在構(gòu)造RF時，對于不平衡的訓(xùn)練集一般會使用OOB的誤差估計生成泛化誤差的一種無偏的內(nèi)部估計，不必像其他算法作交叉驗(yàn)證（CV），有效地平衡了數(shù)據(jù)的誤差。

目前，判斷隨機(jī)森林的性能指標(biāo)主要有分類精度（Accuracy）、靈敏度（Sensitivity）、幾何均值（G-mean）等；算法的運(yùn)行效率一般是關(guān)注時間復(fù)雜度、空間復(fù)雜度的角度，不過以隨機(jī)森林現(xiàn)在的發(fā)展現(xiàn)狀，更值得考慮的是其時間復(fù)雜度的問題。

3 隨機(jī)森林在圖像分割中的應(yīng)用

隨機(jī)森林方法的圖像處理技術(shù)在計算機(jī)視覺領(lǐng)域的研究人員中間也掀起了一股研究熱潮，主要原因有以下幾點(diǎn)：

（1）隨機(jī)森林相比當(dāng)下流行的算法具有更優(yōu)異的分類準(zhǔn)確性。能夠在大規(guī)模的圖像紋理等特征復(fù)雜的情況下很好地處理這些高維數(shù)據(jù)，對于平衡數(shù)據(jù)和非平衡數(shù)據(jù)都可以保證較為穩(wěn)定的誤差，并且隨機(jī)森林方法可以抑制過擬合現(xiàn)象。

（2）隨機(jī)森林會提供一些對數(shù)據(jù)的分析評價。 隨機(jī)森林在整個圖像處理的分類過程中，為每個輸入變量都設(shè)定了一個特殊的值來評定其重要性。不僅能生成泛化誤差的一種無偏的內(nèi)部估計，還可以有效地處理訓(xùn)練集中數(shù)據(jù)缺失、特征遺漏等現(xiàn)象，具有較強(qiáng)的抗噪能力。

（3）隨機(jī)森林處理精度高，運(yùn)算速度快。集群分類器的樹與單個分類器的樹，它們的計算量和學(xué)習(xí)深度是成正比的，使其可以更好地適用在分類、回歸等問題，且集群分類器里所有的樹是可執(zhí)行并行化的。

Xiao Liu[4]等作者提出了一種幾何先驗(yàn)的隨機(jī)森林方法來獲得分割對象的自適應(yīng)幾何先驗(yàn)，不僅取得了較好的分割效果，分割速度也非?？臁ri Huynh[5]等作者提出一種結(jié)構(gòu)化的隨機(jī)森林方法對CT圖像通道結(jié)構(gòu)化輸出，實(shí)現(xiàn)剛性配準(zhǔn)。Bowen Zhao[6]等作者提出了一種基于隨機(jī)森林分類器和稀疏自動編碼特征的肺部圖像分割方法，對于臨床肺血管CT圖像的分割有著非常重要的意義。M.Yaqub[7]等作者提出了一個隨機(jī)森林分類框架內(nèi)的三維分割技術(shù)，通過特征選取以及加權(quán)的改進(jìn)方法，使得該技術(shù)在醫(yī)學(xué)圖像的分割精度上有著顯著地改善。Piotr Dollár[8]等作者充分利用局部圖像塊的實(shí)時結(jié)構(gòu)優(yōu)勢，在結(jié)構(gòu)化學(xué)習(xí)框架里采用隨機(jī)決策森林的方法，解決局部邊緣檢測的預(yù)測問題。雷震[9]將旋轉(zhuǎn)不變性引入霍夫投票（HV），結(jié)合隨機(jī)森林方法應(yīng)用在了遙感圖像領(lǐng)域，為遙感目標(biāo)的檢測節(jié)省了上百倍的計算量。

4 隨機(jī)森林方法的改進(jìn)方向

得益于隨機(jī)森林算法良好的性質(zhì)，在視覺機(jī)器、圖像處理、醫(yī)學(xué)、管理學(xué)等方面都引起了研究人員的關(guān)注和學(xué)習(xí)。不過由于它的理論與應(yīng)用的結(jié)合還處于完善的階段，因此人們對于其性能的改進(jìn)也提出了許多新穎的思路，國內(nèi)外的改進(jìn)研究大致包含三個方向：第一，將其它方法與隨機(jī)森林算法融合。Gall[10]等人提出結(jié)合Hough變換和隨機(jī)森林RF，得到霍夫森林算法（Hough forests）應(yīng)用到目標(biāo)跟蹤、行為識別領(lǐng)域，不僅檢測精度高，匹配時間也非?？?。Ishwaran[11]等人提出了一種適用于高維數(shù)據(jù)的RF衍生算法，隨機(jī)生存森林算法（RSF），它的特點(diǎn)是對每個樣本構(gòu)造生存樹，然后對這些樹分析預(yù)測效果。馬景義[12]等人分析了RF算法與AdaBoost算法的優(yōu)缺點(diǎn)，提出了一種擬自適應(yīng)分類隨機(jī)森林算法，該方法可以不區(qū)分訓(xùn)練集測試集就能達(dá)到很好地收斂效果。第二，在隨機(jī)森林算法的前期對樣本進(jìn)行預(yù)處理。吳瓊[13]等人提出先將NCL（Neigh鄄borhood Cleaning Rule）技術(shù)進(jìn)行預(yù)處理，再把已經(jīng)處理好的樣本引入到隨機(jī)森林算法中進(jìn)行分類預(yù)測；第三，優(yōu)化隨機(jī)森林算法的生成過程。李慧[14]等人針對訓(xùn)練集的樣本數(shù)量和樣本抽樣方法進(jìn)行了改進(jìn)，對于大數(shù)據(jù)的分析與處理效果都有著顯著的提高。

5 結(jié)語

隨著人工智能、數(shù)字媒體技術(shù)的高速發(fā)展，圖像分割作為機(jī)器視覺領(lǐng)域的重中之重，亟需越來越多性能高、魯棒性強(qiáng)的優(yōu)秀方法來促進(jìn)和提高自身的發(fā)展。本文重點(diǎn)介紹的隨機(jī)森林方法近幾年得到了不少研究學(xué)者的關(guān)注，由于它在預(yù)期結(jié)果精度上有著非常顯著的提升，魯棒性好，越來越廣泛地被運(yùn)用在各個研究領(lǐng)域。此外，本文還論述了隨機(jī)森林方法的構(gòu)造過程、性能特征以及評價指標(biāo)，對隨機(jī)森林算法未來的發(fā)展方向和趨勢進(jìn)行了總結(jié)。

[1]Jian-hua JIA，Li-cheng JIAO etal.Bagging-Basd Spectral Clustering Ensemble Selection.Pattern Recognition Letters,2011,32:1456-1467.

[2]Franek L etal.Image Segmentation Fusion Using General Ensemble Clustering Methods.10th Asian Conference on Computer Vision, 2010.

[3]Song Xiang-fa，Jiao LC etal.Sparse Coding and Classifier Ensemble Based Multi-Instance Learning for Image Categorization.Signal Processing,2013,93(1):1-11.

[4]Xiao Liu，Ming-li Song，Da-cheng Tao etal.Random Geometric Prior Forest for Multiclass Object Segmentation.IEEE Trans.on Image Processing,2015,24(10):3060-3070.

[5]Tri Huynh，Yao-zong GAO et al.Estimating CT Image from MRIData Using Structured Random Forest and Auto-Context Model. IEEE Trans.on Medical Imaging，2016，25(1):174-183.

[6]Bo-wen Zhao，zhu-lou Cao，Si-cheng Wang.Lung Vessel Segmentation Based on Random Forests.Electronics Letters，2017,53(4): 220-222.

[7]M.Yaqub，M.k.Javaid，C.Cooper，J.A.Noble.Investigation of the Role of Feature Selection and Weighted Voting in Random Forest for 3-D Volumetric Segmentation.IEEE Trans.on Medical Imaging，2014，33(2):258-271.

[8]Piotr Dollár，C.Lawrence Zitnick.Fast Edge Detection Using Structured Forests.IEEE Trans.on Pattern Analysis and Machine Intelligence，2015，37(8):1558-1570.

[9]雷震.隨機(jī)森林及其在遙感影像處理中應(yīng)用研究[D].上海:上海交通大學(xué)，2012.

[10]Gall J，Yao A et al.Hough Forest for Object Detection,Tracking,and Action Recognition[J].IEEE Trans.on Pattern Analysis and Machine Intelligence,2011,33(11):2188-2202.

[11]Ishwaran H，Kogalur U B，Blackstone E H，Lauer M S.Random Survival Forest[J].The Annals of Applied Statistics,2008,2.

[12]馬景義，吳喜之，謝邦昌.擬自適應(yīng)分類隨機(jī)森林算法[J].數(shù)理統(tǒng)計與管理，2010,9.29(5):805-811.

[13]吳瓊，李運(yùn)田，鄭獻(xiàn)衛(wèi).面向非平衡訓(xùn)練集分類的隨機(jī)森林算法優(yōu)化[J].工業(yè)控制計算機(jī)，2013,26(7):89-90.

[14]李慧，李正，佘堃.一種基于綜合不放回抽樣的隨機(jī)森林算法改進(jìn)[J].中國計算機(jī)學(xué)會服務(wù)計算學(xué)術(shù)會議，2014.

Research on the App lication of Random Forest in Image Segmentation

LIU Bu-shi，LIU Zhi-jin，QIN Xiao，CHU Xu-tao，LIANGMu-ling
（College of Computer and Information Engineering，Guangxi Teachers Education University，Nanning 530032）

Image segmentation is one of themost important tasks in the domain of computer vision;it plays an important role inmany fields such as medical CT,digitalmedia and so on.Introduces some of themainmethod in image segmentation technology after2000,emphatically focuses on the properties of the Random Forestmethod based on ensemble learning framework.Investigates the application results of using Random Forestmethod in the fieldsof image segmentation,also discusses the direction thatcan be improved.

廣西自然科學(xué)基金項目（No.2016GXNSFAA380209）

劉步實(shí)（1991-），女，江西樂平人，碩士研究生，研究方向?yàn)橛嬎銠C(jī)圖像處理

劉致錦（1991-），男，山東臨沂人，碩士研究生，研究方向?yàn)橛嬎銠C(jī)圖像處理

覃曉（1973-），女，廣西河池人，碩士研究生導(dǎo)師，副教授，研究方向?yàn)閿?shù)據(jù)挖掘、計算機(jī)圖像處理

褚徐濤（1993-），男，浙江寧波人，碩士研究生，研究方向?yàn)橛嬎銠C(jī)圖像處理

梁木玲（1992-），女，廣西人，本科，研究方向?yàn)橛嬎銠C(jī)圖像處理

2017-03-31

2017-05-02

1007-1423（2017）13-0003-04

10.3969/j.issn.1007-1423.2017.13.001

圖像分割；聚類；集成學(xué)習(xí)；隨機(jī)森林

Image Segmentation;Clustering;Ensemble Learning;Random Forest