基于隨機(jī)森林的圖像語(yǔ)義分割算法的研究

張萬(wàn)福

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

基于隨機(jī)森林的圖像語(yǔ)義分割算法的研究

張萬(wàn)福

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

文中提出了基于隨機(jī)森林的圖像語(yǔ)義分割的算法，從訓(xùn)練庫(kù)圖像中隨機(jī)地采樣出固定大小的窗口作為特征，通過(guò)窗口中隨機(jī)的選取兩個(gè)像素點(diǎn)的像素值對(duì)比，將這些特征量化為數(shù)值向量，這樣的向量集合被用于訓(xùn)練隨機(jī)森林分類(lèi)器。在測(cè)試階段，以每個(gè)像素點(diǎn)作為中心，提取一個(gè)窗口，在這個(gè)窗口中提取一個(gè)向量集合，利用隨機(jī)森林的葉子節(jié)點(diǎn)對(duì)這些向量分別進(jìn)行投票，根據(jù)投票結(jié)果選舉產(chǎn)生該像素點(diǎn)最可能的歸屬類(lèi)別。該算法直接利用了圖像低級(jí)的像素信息，而不是去計(jì)算復(fù)雜的濾波器組響應(yīng)或局部描述子，這可大幅提高了算法訓(xùn)練和測(cè)試速度。在MSRC數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，該算法有效地實(shí)現(xiàn)了圖像的語(yǔ)義分割。

計(jì)算機(jī)視覺(jué)；機(jī)器學(xué)習(xí)；隨機(jī)森林；語(yǔ)義分割

對(duì)于計(jì)算機(jī)，圖像只是一些縱橫交錯(cuò)的像素排列，每個(gè)像素點(diǎn)都是由紅、綠、藍(lán)3種顏色通道混合組成的，每個(gè)顏色通道取值0～255。這些數(shù)值在決定物體存在與否的同時(shí)，還受到一些干擾因素的影響，譬如拍攝視角、光照的條件、背景的復(fù)雜度、目標(biāo)的集合特征等。幸運(yùn)的是，監(jiān)督機(jī)器學(xué)習(xí)提供了一種的全新的方法，替代了原先認(rèn)為可手工編寫(xiě)這無(wú)數(shù)種可能性的想法。通過(guò)收集圖像的訓(xùn)練集，并人工正確標(biāo)注每張圖像的內(nèi)容，文中可使用擅長(zhǎng)的機(jī)器學(xué)習(xí)算法來(lái)算出訓(xùn)練集中每一塊像素圖案所屬的類(lèi)別，以及其的干擾因素。更進(jìn)一步，本文希望通過(guò)學(xué)習(xí)歸納識(shí)別出從未訓(xùn)練過(guò)的圖像中的對(duì)象，且依然不受干擾因素的影響，實(shí)現(xiàn)對(duì)圖像的語(yǔ)義分割[1]?，F(xiàn)階段無(wú)論是對(duì)新的視覺(jué)學(xué)習(xí)算法的發(fā)掘，還是對(duì)大量數(shù)據(jù)集的采集和標(biāo)注，都已經(jīng)取得了相當(dāng)大的進(jìn)步。

解決語(yǔ)義分割的方法眾多，其中一個(gè)有效的工具就是基于簡(jiǎn)單的像素對(duì)比分類(lèi)：通過(guò)訓(xùn)練一個(gè)分類(lèi)器來(lái)預(yù)測(cè)每一個(gè)像素的類(lèi)別(如汽車(chē)、道路、樹(shù)木、墻等)分布。但當(dāng)圖像包含大量像素時(shí)，例如現(xiàn)在最普通的智能手機(jī)的拍攝像素均在1 200萬(wàn)像素以上，這就帶來(lái)了計(jì)算量的問(wèn)題，可能使得訓(xùn)練和測(cè)試的計(jì)算是樣本數(shù)的上億倍。令人欣慰的是，機(jī)器學(xué)習(xí)算法在解決計(jì)算機(jī)視覺(jué)方面提供了一種有效的分類(lèi)模型，隨機(jī)森林[2-3]。

本文研究了基于隨機(jī)森林的圖像語(yǔ)義分割算法，在閱讀前人大量文獻(xiàn)的基礎(chǔ)上，改善了算法的模型，在構(gòu)建隨機(jī)森林的過(guò)程中，提出了一種基于線(xiàn)性組合的節(jié)點(diǎn)分裂算法，優(yōu)化了隨機(jī)森林算法分類(lèi)性能[4-5]。

1 隨機(jī)森林理論

隨機(jī)森林[6](RondomFroest，RF)是Leo Breiman結(jié)合Bagging集成學(xué)習(xí)理論[7]和隨機(jī)子空間方法[8]在2001年發(fā)表的一種機(jī)器學(xué)習(xí)算法。RF是一種統(tǒng)計(jì)學(xué)習(xí)理論，其利用bootstrap重抽樣方法從原始樣本中抽取多個(gè)樣本，對(duì)每個(gè)bootsrap樣本進(jìn)行決策樹(shù)建模，然后組合多棵決策樹(shù)的預(yù)測(cè)，通過(guò)投票得出最終預(yù)測(cè)結(jié)果。RF具有分析復(fù)雜分類(lèi)特征的能力，對(duì)于噪聲數(shù)據(jù)和存在缺失值的數(shù)據(jù)具有很好的魯棒性，并具有較快的學(xué)習(xí)速度，其變量重要性度量可作為高維數(shù)據(jù)的特征選擇工具，近年來(lái)已經(jīng)被廣泛應(yīng)用于各種分類(lèi)、預(yù)測(cè)、特征選擇以及異常點(diǎn)檢測(cè)問(wèn)題中[9-11]。

RF是一個(gè)由一組決策樹(shù)分類(lèi)器組成的集成分類(lèi)器，如式(1)，其中 是服從獨(dú)立同分布的隨機(jī)向量，K表示隨機(jī)森林中決策樹(shù)的個(gè)數(shù)，在給定輸入自變量X下，每個(gè)決策樹(shù)分類(lèi)器通過(guò)投票來(lái)決定最優(yōu)的分類(lèi)結(jié)果

{h(X,θk),k=1,2,…,K}

(1)

RF的構(gòu)建過(guò)程如下：

(1)在給定的原始訓(xùn)練數(shù)據(jù)集中，利用Bootstrap方法有放回的抽取K個(gè)樣本，且每個(gè)樣本的樣本容量都和原始訓(xùn)練數(shù)據(jù)集相同；

(2)利用K個(gè)樣本集構(gòu)建K個(gè)決策樹(shù)模型，組合成RF模型。

每顆決策樹(shù)的構(gòu)建過(guò)程：

1)在分裂節(jié)點(diǎn)n，從m個(gè)樣本特征中隨機(jī)的抽取mtry個(gè)特征(mtry<

2)計(jì)算特征向量V的一個(gè)分裂函數(shù)f的值，根據(jù)隨機(jī)產(chǎn)生的閾值t，將訓(xùn)練數(shù)據(jù)集In遞歸的分裂成左右兩個(gè)子集Il和Ir

Il={i∈In|f(VI)

(2)

Ir=InIl

(3)

3)計(jì)算根據(jù)此分裂函數(shù)f和閾值t分裂，節(jié)點(diǎn)n的信息增益，信息增益的計(jì)算公式如下

(4)

其中,E(I)是樣本集I的香農(nóng)熵；

4)因有多個(gè)分裂函數(shù)f和閾值t，所以選擇產(chǎn)生信息增益ΔE最大的那一對(duì)分裂函數(shù)f和閾值t進(jìn)行分裂；

5)樣本集遞歸的沿著決策樹(shù)向下訓(xùn)練，直到到達(dá)樹(shù)的最大深度D或者不再產(chǎn)生信息增益。

(3)對(duì)新的數(shù)據(jù)進(jìn)行分類(lèi)時(shí)，分類(lèi)結(jié)果根據(jù)K個(gè)決策樹(shù)決策結(jié)果來(lái)進(jìn)行投票，得票最多的類(lèi)別為RF決策的結(jié)果

(5)

其中，H(x)表示組合分類(lèi)器模型；hi表示單個(gè)決策樹(shù)模型；Y表示輸出變量；I(°)表示示性函數(shù)。上式是使用投票系統(tǒng)來(lái)確定最終分類(lèi)的原理。

圖1 隨機(jī)森林

2 基于隨機(jī)森林的圖像語(yǔ)義分割算法

在圖像分類(lèi)領(lǐng)域，常采用方法框架是，首先提取感興趣的特征點(diǎn)，利用特征點(diǎn)周邊信息將特征點(diǎn)量化為數(shù)值向量，這些數(shù)值向量被用于模型的學(xué)習(xí)或分類(lèi)測(cè)試圖像?；陔S機(jī)森林的像素對(duì)比圖像語(yǔ)義分割算法在將特征點(diǎn)量化為數(shù)值向量的過(guò)程中，直接利用了圖像的低級(jí)像素信息(像素值對(duì)比)，而不是通過(guò)計(jì)算復(fù)雜的濾波器組相應(yīng)或局部描述子，在算法速度上，隨機(jī)森林在訓(xùn)練和測(cè)試均較快，尤其是與k-meas聚類(lèi)算法、特征描述子的最近鄰賦值算法比較。該算法在訓(xùn)練階段，從訓(xùn)練庫(kù)圖像中隨機(jī)地采樣出固定大小的窗口作為特征，通過(guò)窗口中隨機(jī)的選取的兩個(gè)像素點(diǎn)的像素值對(duì)比，將這些特征量化為數(shù)值向量，這樣的向量集合被用于訓(xùn)練隨機(jī)森林分類(lèi)器；在測(cè)試階段，以每個(gè)像素點(diǎn)作為中心，提取一個(gè)窗口，在這個(gè)窗口中提取一個(gè)向量集合，利用隨機(jī)森林的葉子節(jié)點(diǎn)對(duì)這些向量分別進(jìn)行投票，根據(jù)投票結(jié)果選舉產(chǎn)生該像素點(diǎn)最可能的歸屬類(lèi)別，通過(guò)對(duì)整個(gè)圖像的每一個(gè)像素進(jìn)行類(lèi)別預(yù)測(cè)，可快速的對(duì)圖像完成語(yǔ)義分割[12-14]?；陔S機(jī)森林的像素對(duì)比圖像語(yǔ)義分割算法步驟：

2.1 提取訓(xùn)練圖像塊

從訓(xùn)練集合中采用滑動(dòng)窗口方法提取出大量的圖像塊，如圖3所示，每個(gè)圖像塊的類(lèi)別為其中心像素點(diǎn)在groudtruth中指定的類(lèi)別。

P=

(6)

其中，patchVector表示圖像塊在顏色空間中的像素值，如塊的寬度為d，則patchVector可表示為d×d×3，c為groudtruth中指定的類(lèi)別。

2.2 計(jì)算每個(gè)類(lèi)別的權(quán)重

在一些數(shù)據(jù)集上，可能有大量的數(shù)據(jù)明顯的偏向某些特定的類(lèi)別。因此，在此數(shù)據(jù)集上學(xué)習(xí)的分類(lèi)器將會(huì)相應(yīng)的偏向這些特定的類(lèi)別。為了修正這些偏差，文中給每一個(gè)訓(xùn)練樣本一個(gè)相應(yīng)的權(quán)重ωi，權(quán)重為對(duì)應(yīng)樣本所屬的類(lèi)別占總樣本的頻率

ωi=ξci

(7)

ξc=(∑i∈I[c=ci])-1

(8)

利用這些權(quán)重訓(xùn)練而來(lái)的分類(lèi)器能更好的決策出每一個(gè)類(lèi)別。經(jīng)過(guò)訓(xùn)練，文中利用訓(xùn)練數(shù)據(jù)集I而不是隨機(jī)的自己子集I′，得到了一個(gè)改善的類(lèi)別分布估計(jì)?？奢p微的提升分類(lèi)器的綜合性能，尤其是當(dāng)數(shù)據(jù)集較少時(shí)。

2.3 不變性學(xué)習(xí)

盡管利用原始的像素值作為特征比計(jì)算描述子或?yàn)V波器組響應(yīng)更快，卻導(dǎo)致失去了固有的不變性特征。為此，采用仿射變換的形式，對(duì)訓(xùn)練集合中的圖像進(jìn)行幾何變換和光照變換。通過(guò)幾何變換和光照變換，可對(duì)特定的問(wèn)題學(xué)習(xí)到適當(dāng)?shù)牟蛔冃蕴卣?，提升分?lèi)器的分類(lèi)性能。在實(shí)驗(yàn)當(dāng)中，探索了幾何變換中的旋轉(zhuǎn)、縮放、左右翻轉(zhuǎn)等變換，以及光照仿射變換。圖2展示了對(duì)MSRC數(shù)據(jù)集中的一張圖片所進(jìn)行的變換。從左往右，從上往下，圖2(a)進(jìn)行了高斯變換，圖2(b)加入了噪點(diǎn)，圖2(c)加入了旋轉(zhuǎn)變換，圖2(d)加入了縮放變形，圖2(e)光照仿射變換，圖2(j)為處理完成的圖片，圖2(h)為原圖，圖2(i)是相應(yīng)標(biāo)記圖像的處理后結(jié)果。

圖2 圖像變換

2.4 訓(xùn)練隨機(jī)森林

根據(jù)隨機(jī)森林理論，對(duì)提取的圖像塊數(shù)據(jù)集進(jìn)行訓(xùn)練，在決策樹(shù)分裂節(jié)點(diǎn)n處，直接隨機(jī)選取圖像塊p上兩個(gè)像素點(diǎn)px1,y1,b1和px2,y2,b2組成特征向量V，如圖3所示，其中像素(x1,y1)和像素(x2,y2)可能來(lái)自不同的顏色通道b1和b2。圖像塊p上，分裂函數(shù)f有4種表示方式:(1) 單個(gè)像素(x,y)在顏色通道b的值px,y,b;(2) 兩個(gè)像素的和px1,y1,b1+px2,y2,b2;(3)兩個(gè)像素的差值px1,y1,b1-px2,y2,b2;(4)兩個(gè)像素的絕對(duì)差值|px1,y1,b1-px2,y2,b2|。

圖3 圖像塊 ，大小

在RF中，引入隨機(jī)性，可減少相關(guān)性而保持強(qiáng)度不變，提高預(yù)測(cè)精度。顧在此改進(jìn)了上述分裂函數(shù)f的選取方式，引入隨機(jī)性，將上面4種分裂方式線(xiàn)性組合起來(lái)，產(chǎn)生一個(gè)隨機(jī)的分裂函數(shù)f，如式(9)，其中λ1,λ2,λ3,λ4隨機(jī)選取從-1～1的值

f=λ1px,y,b+λ2(px1,y1,b1+px2,y2,b2)+

λ3(px1,y1,b1-px2,y2,b2)+λ4(|px1,y1,b1-px2,y2,b2|)

(9)

由于每一個(gè)圖像塊p的特征向量V和分裂函數(shù)f的選取都是隨機(jī)的，相互獨(dú)立的，當(dāng)圖像塊p的數(shù)量足夠多時(shí)，根據(jù)數(shù)理統(tǒng)計(jì)中的中心極限定理可知，f(V)服從正態(tài)分布N(μ,σ2)，隨機(jī)閾值t根據(jù)此正太分布隨機(jī)產(chǎn)生。根據(jù)分裂函數(shù)f和閾值t分裂，計(jì)算節(jié)點(diǎn)n的信息增益ΔE，選取產(chǎn)生最大信息增益ΔE最大的那一對(duì)分裂函數(shù)f和閾值t進(jìn)行分裂。樣本集遞歸的沿著決策樹(shù)向下訓(xùn)練，直到到達(dá)樹(shù)的最大深度D或者不再產(chǎn)生信息增益[15]。

每顆決策樹(shù)根據(jù)以上規(guī)則充分的生長(zhǎng)，不需要剪枝，直到訓(xùn)練完所有決策樹(shù)，組合成隨機(jī)森林，圖1所示。

3 實(shí)驗(yàn)分析

MRSC-v2 (Microsoft Research Cambridg)圖像庫(kù)是一個(gè)按像素標(biāo)記的圖像公共數(shù)據(jù)集，含有591張圖片和23類(lèi)目標(biāo)，用于場(chǎng)景分割和目標(biāo)分割。文中在Intel Core 3.3 GHz、4.0 GB 內(nèi)存、 Windows 7、Matlab 2012實(shí)驗(yàn)平臺(tái)上，在此數(shù)據(jù)集上針對(duì)上述提出的算法進(jìn)行了驗(yàn)證，對(duì)于實(shí)驗(yàn)結(jié)果采用兩種精度標(biāo)準(zhǔn)進(jìn)行驗(yàn)證，類(lèi)別平均精度和全局分類(lèi)精度。

表1是原算法和改進(jìn)后算法的類(lèi)別平均精度和全局分類(lèi)精度的對(duì)比，可看出在采用線(xiàn)性組合的節(jié)點(diǎn)分裂算法，能提高分類(lèi)器的分類(lèi)性能。

表1 原算法和改進(jìn)后算法對(duì)比

其中,Average表示平均分類(lèi)精度;Total表示全局分類(lèi)精度。

實(shí)驗(yàn)還對(duì)節(jié)點(diǎn)分裂函數(shù)f選取的個(gè)數(shù)numf進(jìn)行了驗(yàn)證，如圖4所示。隨著節(jié)點(diǎn)處選取的分裂函數(shù)的個(gè)數(shù)增加，測(cè)試集的分類(lèi)平均精度和全局分類(lèi)精度均會(huì)增加，可看到在節(jié)點(diǎn)n處分裂函數(shù)f隨機(jī)選取20個(gè)，可以得到更好的精度效果。

圖4 分割精度與分裂函數(shù)選取的個(gè)數(shù)的關(guān)系

圖5是算法分割的結(jié)果圖，其中圖5(a)是原圖，圖5(b)是Ground Truth標(biāo)記圖，圖5(c)是原算法的語(yǔ)義分割圖，圖5(d)是改進(jìn)后算法的語(yǔ)義分割圖。可看出改進(jìn)后的算法，比原算法更精確的將牛分割出來(lái)，在腿，脖子等處可看出原算法分割的比較稀疏，說(shuō)明改進(jìn)后的算法效果更好。圖6是MRSC-v2數(shù)據(jù)集中標(biāo)示的每一種類(lèi)別對(duì)應(yīng)的顏色表示，可看出算法分割正確[12-15]。

圖5 算法分割示意圖

圖6 MRSC-v2數(shù)據(jù)集中類(lèi)別標(biāo)記參考

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

本文介紹了一種機(jī)器學(xué)習(xí)的算法在計(jì)算機(jī)視覺(jué)方

面的應(yīng)用，主要研究了基于隨機(jī)森林的圖像語(yǔ)義分割的算法，該算法通過(guò)直接利用圖像低級(jí)的像素信息，而不是去計(jì)算復(fù)雜的濾波器組響應(yīng)或者局部描述子，大幅提高了算法訓(xùn)練和測(cè)試速度，本文在節(jié)點(diǎn)分裂的選擇上通過(guò)引入線(xiàn)性組合的節(jié)點(diǎn)分裂算法，改進(jìn)了算法的分類(lèi)性能，在MRSC-v2數(shù)據(jù)集的實(shí)驗(yàn)表明，可提高算法精度。

[1] Johnson M,Shotton J,Cipolla R. Semantic texton forests for image categorization and segmentation[C].PF,USA:IEEE Conference on Computer Vision & Pattern Recognition,2008.

[2] Bosch A, Zisserman A, Muoz X. Image classification using random forests and ferns[C].Germany:IEEE International Conference on Computer Vision. IEEE Computer Society, 2007.

[3] Amit Y,Geman D. Shape quantization and recognition with randomized trees[J].Neural Computation,1997,9(7):1545-1588.

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

[5] 董師師,黃哲學(xué).隨機(jī)森林理論淺析[J].集成技術(shù),2013,2(1):1-7.

[6] Breiman L.Random forests[J].Machine Learning,2001,45(1):5-32.

[7] Breiman L.Bagging predictors[J].Machine Learning,1996,24(2):123-140.

[8] Ho T.The random subspace method for constructing decisionforests [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(8):832-844.

[9] 蔣黎星,侯進(jìn).基于集成分類(lèi)算法的自動(dòng)圖像標(biāo)注[J].自動(dòng)化學(xué)報(bào),2012,38(8):1257-1262.

[10] 黃婷,趙自明.基于隨機(jī)森林和MR8濾波器的圖像分類(lèi)研究[J].嘉應(yīng)學(xué)院學(xué)報(bào),2015,33(2):26-32.

[11] 楊樂(lè),廖家平.基于隨機(jī)聚類(lèi)森林的圖像分類(lèi)識(shí)別[J].湖北工業(yè)大學(xué)學(xué)報(bào),2011,26(1):106-110.

[12] 姚登舉,楊靜,詹曉娟.基于隨機(jī)森林的特征選擇算法[J].吉林大學(xué)學(xué)報(bào):工學(xué)版,2014, 44(1):137-141.

[13] 曹正鳳.隨機(jī)森林算法優(yōu)化研究[D].北京:首都經(jīng)濟(jì)貿(mào)易大學(xué),2014.

[14] 趙自明.隨機(jī)森林在圖像分類(lèi)和主義分割中的應(yīng)用[D].廈門(mén):廈門(mén)大學(xué),2012.

[15] 李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社, 2012.

Semantic Segmentation Algorithm Based on Random Forests

ZHANG Wanfu

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,
Shanghai 200093, China)

An image semantic segmentation algorithm base on random forests is proposed. Windows of fixed size are sampled randomly from training image data-set as features, and two pixel points are randomly picked through the window for comparison. These features are quantified as the numerical vector for training random forest classifier. In the test stage, each pixel point is taken as the center to extract a window, from which a vector set is extracted. Leaves node of random forest are used for voting these vector respectively to elect category of the pixel most likely belonging. The algorithm uses the low-level pixel image information, instead of calculating complex filter bank response, or local descriptor, thus greatly improving the speed of training and testing. The MSRC datasets lab results show that the algorithm effectively implements image semantic segmentation.

computer vision; machine learning; random forest; semantic segmentation

2016- 03- 28

張萬(wàn)福(1990-)，男，碩士研究生。研究方向：數(shù)字圖像處理與計(jì)算機(jī)視覺(jué)。

10.16180/j.cnki.issn1007-7820.2017.02.019

TP391.41

A

1007-7820(2017)02-072-04