基于隨機森林和隨機游走的交互式圖像分割

呂律

摘要：基于隨機游走的交互式圖像分割在計算相鄰像素相似度時，僅考慮了顏色空間的差異。針對這一問題，利用圖像中廣泛存在的對稱結構，提出一種基于隨機森林進行對稱檢測的方法。通過基于相似邊的特征，將對稱檢測轉化為結構化標簽問題。在得到對稱軸的基礎上，通過期望最大算法，建立對稱軸與相鄰像素之間的關系，以提高交互式分割的精確度。實驗表明，該方法不僅能有效地提取圖像中的對稱軸，而且能得到較高精度的交互式分割結果。

關鍵詞：交互式圖像分割；隨機森林；隨機游走；對稱檢測；期望最大算法

中圖分類號：TP391.41? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2023）31-0014-04

開放科學（資源服務）標識碼（OSID）

0 引言

圖像分割是圖像處理的基礎性問題，是圖像理解的基石，可以被應用于自動駕駛系統中的街景識別與理解，無人機系統中的著陸點識別[1]。近幾年基于深度學習的語義分割（semantic segmentation） ，即對圖像中表達的語義（不同的物體）進行分割，取得了很高的精確度[2]。但是對于下面2種情況，如果沒有人的交互，還是很難達到滿意的效果。1） 在背景比較雜亂的情況下，圖像中的物體有很多細小的枝節（如圖1中的鹿角）；2） 需要將物體的不同部分進一步劃分（如圖1的鹿頭和黑色的頸部劃分為同一個部分）。交互式圖像分割正是研究解決這一類問題的方法。

交互式圖像分割與圖像分割的區別在于，需要人在圖像中用不同顏色標注出需要分開的區域[3]，如圖1中不同顏色的點（黃色和綠色點），下文稱之為交互點。因為深度學習是一種端到端的學習方法，現有的深度學習方法還沒辦法處理交互點這種先驗知識[4]。現有文獻也沒有采用深度學習方法進行交互式圖像分割，所以本文提出的是一種基于隨機游走（random walk） 的方法。

現有基于隨機游走的交互式圖像分割方法是一種非監督的分割方法，根據圖像中相鄰像素的相似度計算轉移概率矩陣，當隨機游走達到穩定時，得到圖像中的像素所對應的人工標注[1]。雖然圖像分割是一種非監督的問題，但是利用圖像中的對稱結構，可以提高分割的效果。如圖1所示，人工標注的點，落在了對稱區域（鹿角的主干，鹿的頸部），該區域可以作為人工標注處理，與該區域相鄰點的相似度也應該相應提高。所以將人工交互點擴展到這些交互點所在的對稱區域，直觀上通過增加了交互點的數量，應該能提高分割的精度?，F有的交互式圖像分割文獻，并沒有利用圖像中的對稱性進行分割，于是本文提出一種基于對稱區域改進現有的隨機游走方法，并通過實驗表明比現有方法的結果更好。

對稱檢測在圖像處理中不是一個熱門的研究領域，相關的文獻比圖像分割要少得多[5]。這些研究的共同特點是提出不同的圖像特征，基于這些特征計算圖像中的對稱軸?，F有的數據集SYMMAX-300[5]，數據量很小，不適合深度學習方法（關于利用深度學習方法處理交互式圖像分割和對稱檢測，本文在最后一節結束語，作為未來的研究進行討論）。通過仔細分析這些文獻中的圖像特征，可以發現現有方法并沒有考慮對稱區域的邊界的相似性（如圖2（a） 邊ab與cd） 。本文提出的方法利用相似邊界等多種特征，改進了隨機森林算法進行對稱檢測，最后通過實驗證明，比現有方法的結果更好。綜上所述本文的工作有以下2點：1） 通過圖像中的相似邊等多種特征，改進隨機森林算法得到對稱軸；2） 利用對稱區域，改進隨機游走算法得到圖像的分割區域。

1 基于隨機森林的對稱檢測

本節首先介紹現有的對稱檢測方法，然后介紹本文改進的對稱檢測方法。

1.1 現有對稱檢測方法

在現有關于對稱檢測的文獻中，SYMMAX-300[5]是廣泛被使用的數據集。這些研究的共同特點是通過以下2步檢測圖像中的對稱信息：1） 提取不同的圖像特征；2） 基于標注了對稱信息的數據集和1中提取的特征，通過不同的學習算法得到對稱模型?，F有文獻中用的特征主要有：尺度不變特征變換（Scale-invariant feature transform，SIFT） 特征：圖形的顏色、材質等特征。其中Tsogkas等人提出的一種專門針對對稱問題的直方圖特征[5]，因為1.2節本文方法用到了這種特征，所以簡要介紹一下。

以圖像中的點（x，y）為中心作邊長為a的正方形區域，并分割成三個相鄰的面積相等的矩形，即矩形的邊長為a和a/3。對于任意兩個矩形，可以定義相異度函數[DHi，j（x，y）]（該相異度函數就是直方圖特征）：

[DHi，j=12t（Ri（t）-Rj（t））2Ri（t）+Rj（t）]? ? ? ? ? ? （1）

其中，[i，j∈{1，2，3}]表示三個矩形的標號。[Ri]、[Rj]分別表示矩形i和矩形j區間中的直方圖（histogram） ，t是直方圖中的分組數，實驗中t=64。

1.2 基于隨機森林的對稱檢測

從前面對直方圖特征的介紹可以知道，因為計算的是矩形區域，所以現有方法沒有考慮到對稱區域的邊界是相似的（圖2（a） 中邊ab，cd，中間的實線是對稱軸），并且相似邊到對稱軸區域的顏色，材質是相似的（圖2（a） 中區域abs2s1，區域cds2s1） 。本節方法的第1個貢獻是提出多種基于相似邊的特征。隨機森林是利用多種特征進行分類、回歸較好的方法[6]，但是對稱軸是1條曲線（圖2是示意圖，簡化為直線），不是簡單的分類數值，或者回歸數值，本節方法的第2個貢獻是提出一種方法，改進隨機森林，計算對稱軸這種結構化的目標。

1） 基于相似邊的特征?，F有的數據集（SYMMAX-300） 只包含對稱軸信息，如果人工提取對稱軸相應的相似邊數據，不僅困難而且非常費時。所以，本方法利用相似邊與對稱軸的關系，去掉明顯不相似的邊，從而得到基于相似邊的特征。

圖2（a） （b） 是數據集中2種主要的對稱模式，相似邊（ab，cd） 反轉對稱，相似邊（ef，gh） 平移對稱，對稱軸窗口取8×8像素，所以對稱軸都是弧度較小的曲線或者近似的直線。首先構造候選區域，先通過現有邊緣檢測方法提取對稱軸兩側的邊，下文稱之為候選邊，分別連接候選邊的兩個端點得到兩條直線（ac，bd） ，對稱軸至少要與其中1條相交。當與兩條直線相交時（如圖2（a）） ，區域abs2s1和區域cds2s1是候選區域；當只與1條直線相交時（如圖2（b） 中間實線是對稱軸，虛線是延長線），區域efs4s3和區域ghs4s3是候選區域。候選區域的面積是第一種特征。

過候選邊上一點（如圖2（a） 點k） 做垂直于對稱軸的線段作為距離di（如圖2（a） kl） ，平均距離[d=i∈Edi/|E|]是第2種特征，其中，[i∈E]表示邊E上所有的點，|E|表示邊上所有點的個數。

將候選邊所在窗口（8×8像素）中的邊自上而下掃描，每1行向左和向右擴大1個像素，即將邊變粗，變粗后的邊的面積為S1和S2。該面積是第三種特征。

將不滿足下面三個條件的候選邊去掉，剩下的就是相似邊：

[|A1-A2|min{A1，A2}<20% ，? ? ? ?|d1-d2|min{d1，d2}<20% ， ]

[max{S1?S2}min{S1，S2}>70%]? ?（2）

其中，A1、A2表示對稱軸兩側候選區域的面積，d1、d2表示對稱軸兩側候選區域的平均距離，[max{S1?S2}]表示S1、S2分別反轉和不反轉共4種情況下最大的相交的面積。

訓練模型時，對稱軸是已知的。但是測試時，對稱軸是要計算的目標未知。這時已知的是8×8像素區域，計算對稱軸是否在這個區域。分別連接候選邊的2個端點構造直線L1、L2，然后連接L1和L2的中點，以這條線為對稱軸，并通過（2） 式中3個條件得到相似邊。

通過（2） 式去掉不相似的候選邊后，剩下的候選邊即相似邊，該相似邊對應的候選區域即為對稱區域。連接相似邊的中點和對稱軸上任一點的距離記為ds（如圖2（a） 中ms的距離），這是第4種特征。ds與水平線的夾角[α]是第5種特征。分別連接相似邊兩個端點和對稱軸上任一點圍成的區域是第6種特征（如圖2（a） 中區域csd） ?；诘?種特征區域，可以得到相應的顏色，材質的直方圖特征（第7種特征），即[DHLi，j]、[DHai，j]、[DHbi，j]、[DHti，j] （其中L、a、b分別是CIELAB顏色空間中的L、a、b信息，t是材質）。材質t的計算采用文獻[7]中的方法。

2） 計算對稱軸。前面已經介紹了對稱軸（如圖2（a）） 所示是一條曲線，既不是分類數值，也不是回歸數值。通過分析對稱軸數據集，可以發現非水平對稱（如圖2（a） 所示）的情況下，每行只占1個像素值。水平對稱是指對稱軸是一條水平線，這時每列只占一個像素。圖2（c） 將對稱軸所在的8×8像素目標區間按行分為8行，或者按列分為8列。所以計算對稱軸相當于在每一行（或者一列）8個像素中找出對稱軸的那個像素，即分類問題。于是可以將對稱軸所在區域（8×8像素）分為按行或者按列劃分兩種情況，每種情況根據不同的行（列）建立相應的隨機森林模型。下面，首先給出按行或者按列進行計算的判定條件。

訓練時，因為對稱軸是已知的，連接對稱軸兩個端點所得直線與水平線的夾角[β]，[β>20°]按行計算，否則按列計算。測試時，因為對稱軸未知，連接相似邊兩個端點所得直線與水平線的夾角[γi]，[i∈SEγi/|SE|>20°]按行計算，否則按列計算，其中[i∈SE]表示該對稱軸對應的所有相似邊，|SE|表示相似邊的個數。

對于第i行（或者第i列），針對不同行（列）構造相應的特征?；诘?、4、5、6、7種特征，構造隨機森林中每一個節點的函數：

[h（x，θj）=[f（x，k）<τ]， θj=（k，τ），k=3，4，5，6，7f（x，3）=max{S1?S2}min{S1，S2}， f（x，4）=|ds1-ds2|min{ds1，ds2}，f（x，5）=|α1-α2|min{α1，α2}， f（x，6）=|AS1-AS2|min{AS1，AS2}，f（x，7）=DH*i，j， *=L，a，b，t]? ?（3）

其中，[.]是指示函數，[τ]表示閾值，k對應第幾種特征。訓練決策樹時，對于一個節點和訓練集[Sj?X×Y]，目標是找到[h（x，θj）]中的[θj]能夠很好地將數據進行劃分。數據劃分的標準是信息增益：

[Ij=H（Sj）-k∈{L，R}SkjSjH（Skj）]? ?（4）

其中，[SLj={（x，y）∈Sj|h（x，θj）=0}]，[SRj=Sj＼SLj]，[H（S）=-ypylog（py）]，py表示S中標記為y的概率。通過最大化Ij可以計算出[θj] 。

2 基于隨機游走的交互式圖像分割

本節介紹利用前面得到的對稱軸與相似邊，對傳統隨機游走模型進行改進。

Grady對于交互式圖像分割問題，首先提出隨機游走算法[8]。他通過無向圖[G=（V，E）]對圖像進行建模，其中節點[v∈V]，邊[e∈E?V×V]。每一個節點[vi]代表圖像像素[xi]，邊[eij]表示[vi]與其相鄰的8個節點[vj]構成的邊，[wij]表示隨機游走通過邊[eij]的權值。

[wij=exp（-||Ii-Ij||2σ）]? ?（5）

其中，[Ii]和[Ij]分別表示節點[xi]和[xj]對應于CIELAB顏色空間的值。實驗中[σ]是控制參數，令[σ=22]。D是對角矩陣，其中[Dii=di]，[di=j～iwij]表示節點[vi]的度， [i～j]表示與[vi]相鄰的節點[vj]。因為在第1節計算得到對稱軸和相似邊，當交互點落在對稱區域（圖2（a） 區域abdc） ，該區域的所有點被作為交互點處理（即具有相同的標簽）。并將對稱區域的面積（區域中的像素個數）增大1倍，相應區域記為V，區域V中節點[vi]到[vj]的權值計算如下：

1） 基于第1節計算的對稱區域，得到的直方圖作為初始值，通過期望最大算法（Expectation maximization） [9]計算對稱區域對應的標簽k的均值[μkt]，方差[θkt]和先驗概率[πkt]，t是直方圖分組數，實驗中t=64。

2） 對于區域V中的每一個像素[Ii]，對每一個分組t，計算：

[Jkit=-logπkt+0.5×（log|θkt|+Ii-μktθkt）]? ?（6）

其中，[|θkt|]是[θkt]的行列式的值。

3） 對于全部分組t，[mintJkit]表示同一k值下，取最小的[Jkit]，[100-mintJkit]為了方便計算，[Ji=maxk{100-mintJkit}] ，[gij]表示節點[vi]到[vj]的權值：

[gij=exp（-||Ji-Jj||2σ）]? （7）

其中，G是對角矩陣，其中[Gii=gi]，[gi=j～igij]。（7） 式與（6） 式相同，只是將I換成J，實驗中令[σ=22]。

所以圖像中任意兩點i，j的轉移概率為

[q（i，j）=ci，當i=j（1-ci）gijGi，當j～i∈V（1-ci）wijDi，當j～i?V0，其他情況]? ?（8）

其中，ci表示，當i=j時，當前點轉移回自己的概率，參考文獻[10]，實驗中令ci=c=0.000 4。設隨機游走從第m個交互點[xlkm]（其標記為lk） 開始，[rlkim]表示隨機游走達到穩定態時停在xi的概率，

[rlkim=（1-ci）j～i∈VrgijGirlkjm+（1-ci）j～i?（Vr，V）wijDirlkjm+ciblkim]? （9）

其中，[blkim=[bi]N×1]，當[xi=xlkm]，[bi=1]，其他情況，[bi=0]。所以每個節點的標簽實際是求（10） 式：

[Ri=argmaxlkrlki]? ?（10）

其中，[rlki=[rlkim]N×1]，即每個節點對應的標記的最大值。

3 實驗結果與分析

本節首先測試第1節中對稱檢測算法，并與現有方法進行比較；再測試本文所提出的交互式圖像分割算法，并與現有方法進行比較。

3.1 對稱檢測實驗

本節對稱檢測采用SYMMAX-300數據集[5]，該數據集是在BSDS-300[7]的基礎上手工加上對稱軸信息，并廣泛應用于對稱檢測中。測試的標準采用文獻[11]中的ODS（Optimal Dataset Scale） ，OIS（Optimal Image Scale） 和AP（Average Precision） 。ODS是對整個數據集的一個最優尺度下的F值度量（F-Measure） 。OIS是對每一幅圖像在最優尺度下的F值度量。F值度量計算如下：

[F值=2×正確率×召回率正確率+召回率]? （11）

其中，正確率=（計算得到的正確數目）/（計算得到的數目），召回率=（計算得到的正確數目）/（樣本的數目），AP是平均正確率。

本節將第1節中方法與文獻[5]和[12]進行比較，見表1。其中第1節用到的直方圖特征就是文獻[5]提出的。只比較了兩種相關的方法的原因有兩個：1） 現有對稱檢測的文獻中，很多論文的結果是定性的，如圖3所示，從圖中比較結果，于是本文實現了文獻[5，12]的方法并進行比較；2） 本文的目的是交互式圖像分割，有些對稱信息如圖3（a） 人體和草裙上的人工標注的對稱軸對圖像分割作用不大，所以在交互式圖像分割實驗部分與更多其他方法進行比較，見表2。如表1所示，很明顯本文方法在3個標準比文獻[5]和 [12]都好。但是本方法3個標準的值還是比較低，原因如圖3所示。圖3（a） 是手工標注作為測試的真實值，但是很明顯圖中人的背部，草裙中的分叉是否對稱軸，是有爭議的，對圖像分割的作用不大，本方法并不計算這種分叉。圖3（b、c、d） 給出文獻[5]、[12]和本方法的實例。

圖3（b） 是采用文獻[5]方法，因為沒有考慮相似邊因素，很多邊界也被計算為對稱軸，比如圖左上的塔除了中間的對稱軸，還將左右兩條邊界也誤判為對稱軸。圖3（c） 是采用文獻[12]方法，該方法基于一種可變形的圓盤（deformable discs） 來描述對稱區域，但是圖3（c） 中右邊一些樹林也被認為是對稱結構。圖3（d） 是本文方法，除了人物背部和草裙上有爭議的對稱軸，本方法將湖水的一部分判斷為對稱軸，雖然這可能不是對稱軸，但是對于圖像分割是有意義的。

3.2 交互式圖像分割實驗

交互式圖像分割實驗，采用的是GrabCut數據集[13]，該數據集廣泛地應用于交互式圖像分割中[3]。這里將本文方法與RW[8]、RWR[10]、LC[14]、LRW[15]、NsubRW[1]進行比較，結果見表2。其中，RW、RWR、LC、LRW的結果摘自文獻[1]，因為文獻[1]將文獻[8，10，14，15]的方法都實現了，而且文獻[1]發表在圖像處理的重要期刊IEEE TRANSACTIONS ON IMAGE PROCESSING。測試標準采用的是文獻[14]中的RI（Rand Index） ，GCE（Global Consistency Error） ，VoI（Variation of Information） 和錯誤率。RI統計分割結果與手工標注具有相同標簽像素對的個數，是一個比值，取值范圍[0，1]，取值越大，分割效果越好。GCE計算分割結果與手工標注，其中一個能否看作另一個細化后得到的程度，取值范圍[0，1]，取值越小，分割效果越好。VoI計算分割結果和手工標注之間的相對熵，取值越接近0，分割效果越好。錯誤率就是被錯誤標注像素的百分數，取值越低，分割效果越好。

通過表2的比較，很明顯因為加入了對稱軸信息，本文方法在4個標準都比現有方法要好。本文實現了RWR[10]和LRW[15]方法，圖4是分割實例。圖4（a） 是手工結果，圖4（b） 是LRW結果，圖4（c） 是RWR結果，圖4（d） 是本文方法。很明顯RWR和LRW，因為沒有考慮圖像中對稱信息，將汽車周圍的一些區域也一起分割了。對比本文方法圖4（d） 和手工結果圖4（a） 可以發現，只有汽車右下部分涉及輪胎的部分存在差異。

4 結論

本文通過計算圖像中的對稱信息，改進傳統基于隨機游走的交互式圖像分割方法，得到更精確的分割結果。本文對現有的對稱檢測方法也進行了改進，提出基于相似邊的特征，并提出一種通過隨機森林學習結構化目標的方法，實驗證明該方法比現有方法得到更精確的對稱軸。

未來的工作有2個方向：1） 因為對稱檢測的數據集比較小，改進深度學習方法，使其能適用于數據集小的領域，這個也是深度學習一個研究方向；2） 因為交互式圖像分割，涉及交互點這種先驗知識，將先驗知識融入深度學習方法，這個也是深度學習一個研究方向。

參考文獻：

[1] BAMPIS C G，MARAGOS P，BOVIK A C.Graph-driven diffusion and random walk schemes for image segmentation[J].IEEE Transactions on Image Processing，2017，26（1）：35-50.

（下轉第21頁）

（上接第17頁）

[2] PAPANDREOU G，CHEN L C，MURPHY K P，et al.Weakly-and semi-supervised learning of a deep convolutional network for semantic image segmentation[C]//2015 IEEE International Conference on Computer Vision （ICCV）.IEEE，2016：1742-1750.

[3] SPINA T V，DE MIRANDA P A V，Xavier Falc?o A.Hybrid approaches for interactive image segmentation using the live markers paradigm[J].IEEE Transactions on Image Processing，2014，23（12）：5756-5769.

[4] REZENDE D J，MOHAMED S，WIERSTRA D.Stochastic backpropagation and approximate inference in deep generative models[J].31st International Conference on Machine Learning，ICML 2014，2014，4：3057-3070.

[5] TSOGKAS S，KOKKINOS I.Learning-based symmetry detection in natural images[M].Computer Vision – ECCV 2012.Berlin，Heidelberg：Springer Berlin Heidelberg，2012：41-54.

[6] GEURTS P，ERNST D，WEHENKEL L.Extremely randomized trees[J].Machine Learning，2006，63（1）：3-42.

[7] MARTIN D R，FOWLKES C C，MALIK J.Learning to detect natural image boundaries using local brightness，color，and texture cues[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（5）：530-549.

[8] GRADY L.Random walks for image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（11）：1768-1783.

[9] BISHOP， CHRISTOPHER M.Pattern Recognition and Machine Learning[M].Springer New York，2006.

[10] KIM T H，LEE K M，LEE S U.Generative image segmentation using random walks with restart[M]//Lecture Notes in Computer Science.Berlin，Heidelberg：Springer Berlin Heidelberg，2008：264-275.

[11] ARBELAEZ P，MAIRE M，FOWLKES C，et al.From contours to regions：an empirical evaluation[C]//2009 IEEE Conference on Computer Vision and Pattern Recognition.IEEE，2009：2294-2301.

[12] LEE T S H，FIDLER S，DICKINSON S.Detecting curved symmetric parts using a deformable disc model[C]//2013 IEEE International Conference on Computer Vision.IEEE，2014：1753-1760.

[13] ROTHER C，KOLMOGOROV V，BLAKE A.“GrabCut”：interactive foreground extraction using iterated graph cuts[C]//SIGGRAPH '04：ACM SIGGRAPH 2004 Papers.New York：ACM，2004：309-314.

[14] CASACA W，NONATO L G，TAUBIN G.Laplacian coordinates for seeded image segmentation[C]//2014 IEEE Conference on Computer Vision and Pattern Recognition.IEEE，2014：384-391.

[15] SHEN J B，DU Y F，WANG W G，et al.Lazy random walks for superpixel segmentation[J].IEEE Transactions on Image Processing，2014，23（4）：1451-1462.

【通聯編輯：唐一東】