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

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

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

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

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

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

0 引言

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

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

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

圖像分割技術(shù)也可以看作是數(shù)學(xué)問題，根據(jù)圖像或者是研究對(duì)象的先驗(yàn)知識(shí)，通過數(shù)學(xué)模型、理論來獲得較好的分割結(jié)果。隨著AI的迅速發(fā)展，機(jī)器學(xué)習(xí)在各行各業(yè)中得到了廣泛的重視與應(yīng)用，集成學(xué)習(xí)（En鄄semble Learning）的方法更是成為了國內(nèi)外機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)熱門，通過結(jié)合多個(gè)學(xué)習(xí)器，獲得比單個(gè)方法更優(yōu)越的穩(wěn)定性和泛化性能。它主要有三個(gè)步驟：（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í)中，用該方法對(duì)SAR對(duì)象進(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)建多個(gè)分類樹，最終的預(yù)測(cè)、分類結(jié)果是由分類樹投票決定。隨機(jī)森林可以處理數(shù)據(jù)量較大的高維訓(xùn)練集，且不需要顯式的特征選擇，就能達(dá)到較快的分類速度、不易過擬合以及較強(qiáng)的抗噪聲能力。它也是集成學(xué)習(xí)中的代表性算法之一。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[14]李慧，李正，佘堃.一種基于綜合不放回抽樣的隨機(jī)森林算法改進(jìn)[J].中國計(jì)算機(jī)學(xué)會(huì)服務(wù)計(jì)算學(xué)術(shù)會(huì)議，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é)基金項(xiàng)目（No.2016GXNSFAA380209）

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

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

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

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

梁木玲（1992-），女，廣西人，本科，研究方向?yàn)橛?jì)算機(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