K近鄰分類指導的區域迭代圖割算法研究

管 建 王亞娟 王立功

(蘇州大學醫學部放射醫學與防護學院 江蘇 蘇州 215123)

0 引 言

圖像分割的原理是根據一定的相似性準則將圖像劃分成多個具有獨特性質區域的過程,各區域內具有相同或相似的性質，從而達到在復雜的背景環境中把感興趣的目標區域提取出來的目的。近十余年來，自動化圖像分割在許多領域得到了廣泛研究，如自然圖像分割[1]、醫學圖像分割[2]等，但在內容復雜的圖像上應用仍然存在很大的問題。理想的分割通常需要在分割過程中增加用戶指導信息來獲取目標，減少自動化分割帶來的歧義性，因此，交互式的分割方法具有更強的實用性。

由Boykov等[3]在2001年首次提出的圖割(Graph cuts)模型是目前研究和應用最為廣泛的交互式圖像分割方法之一。它解決了全局優化框架中的分割問題，并為廣泛的能量函數提供了全局最優解決方案。傳統的Graph cuts算法使用最大流算法[4-6]實施計算，將像素視為節點來構建Graph cuts模型。最壞情況下的運行時間復雜度為O(mn2|C|)，其中m、n、C分別表示邊的數目、節點的數目和圖中最小割的權值，所以傳統Graph cuts會嚴重增加算法的時間成本。本文為了減少Graph cuts算法的計算時間，在原始圖像上使用均值偏移(Meanshift)算法作為初始分割[7]，將原始圖像分成多塊同質區域，同時將這些同質區域作為加權圖的節點(超像素)來構建Graph cuts模型，進行圖像分割。Lazy snapping[8]算法也通過類似方法降低Graph cuts的運行成本，但其預分割算法使用的是基于灰度梯度信息的分水嶺變換,忽略了彩色圖像所包含的豐富信息,預分割區域的一致性不夠強, 而且分水嶺算法的過分割現象嚴重，影響后續Graph cuts的分割性能和計算效率。許多研究改進算法來降低分水嶺算法的過分割現象，如應用改進的中值濾波算法對圖像進行適當的降噪，較好地解決了分水嶺算法中過度分割的問題，同時又降低了Graph cuts的時間復雜度[9]。另外, Lazy snapping采用K-means 方法, 這種算法通過最小化均值的方差函數來實現聚類, 而并非最大似然估計,對初始聚類中心嚴重敏感, 聚類效果不夠理想。本文中將提出的分割方法與Lazy snapping就預分割和最終分割的效果做分析比較。

由于圖像信息存在不確定性,難以獲得精確的分割結果。為解決圖像分割中的不確定性問題，張喆等[10]將證據理論與馬爾可夫隨機場相結合, 以證據距離描述相鄰像素間的標號關系,利用條件迭代模型ICM(Iterated conditional mode)算法進行優化，獲得較好的圖像分割算法。Peng等[12]則結合ICM和最大后驗估計MAP(Maximum a posteriori estimation)，使用迭代區域合并方案來擴展Graph cuts算法，漸進式地進行分割而不是一次性分割整幅圖像。該算法從用戶選定的種子區域開始迭代建立傳播子圖，子圖包括已標記的超像素點和相鄰的未標記超像素點。在子圖上使用Graph cuts算法根據已標記的超像素點標定未標記的超像素點，并將標定完的超像素點歸入已標記的超像素點集中，來進行下次迭代子圖標定過程，直至所有超像素點都獲得標簽。但是，ICM算法受標簽初始化影響很大，后續迭代中會放大先前迭代分割中的錯誤[13]。而Graph cuts算法也不能達到完全精確分割，每次迭代中如果將所有新標記的超像素點加入已標記的點集，那么錯誤標記的超像素點會在后續的迭代分割中不斷放大錯誤，造成不可估量的后果。本文采用KNN半監督分類器，通過自訓練的方式迭代訓練標簽數據集，并對每次局部Graph cuts模型產生的新種子區域進行置信度評估，提取高置信度的種子區域指導下輪分割。

1 圖割算法分析

圖像分割問題是對圖像中各像素進行標簽的過程，即給定一個標定場L和一個位域集合D(如圖像像素或者超像素點)，我們的目標是給每個位域i∈D分配一個標簽αi∈L。Boykov和Jolly提出的Graph cuts模型[3]，就是構造一個馬爾可夫隨機場能量泛函, 將二元標簽分配的全局最優化問題轉化為對相應S-T加權圖的最大流/最小割問題。標簽集合α={0,1}，其中0表示背景，1表示目標，標記結果稱為標號場L={α1,α2,…,αi,…}(i∈D)。圖1描述了這類S-T圖的分割過程。

圖1 圖割算法分割圖像流程

馬爾可夫隨機場能量泛函如下：

(1)

Ri(1)=-lnPr(αi|′obj′)

(2)

Ri(0)=-lnPr(αi|′bkg′)

(3)

當超像素點i更傾向于被分為目標時，Pr(αi|′obj′)大于Pr(αi|′bkg′)，將i分給目標的懲罰比分給背景的懲罰小，即Ri(1)小于Ri(0)。當所有超像素點都被正確分配標簽，區域項被最小化。式(1)中的邊界項根據以下的等式定義[4]。

Bij(αi,αj)=ω[i,j]·δ(αi,αj)

(4)

式中：i、j為鄰近的超像素點，δ(αi,αj)定義為：

(5)

ω[i,j]定義為：

(6)

式中：Ii和Ij表示超像素點i和j的強度值，對于灰色圖像使用灰度值表示強度，彩色模型使用RGB向量Ii和Ij表示強度；σ表示鄰近超像素點間的強度變化程度，當兩超像素點強度接近時，相應的能量懲罰很高；dist(i,j)表示兩個超像素點間的距離。Boykov等[4]詳細描述了最小能量問題，S-T加權圖中的權重值定義如下：

(7)

在S-T圖中，S為源極點，T為匯極點，當超像素點的強度傾向于歸為目標對象時，其與S節點之間的權重將大于像素與T節點之間的權重，這意味著切割更可能發生在權重更小處。對于相鄰的像素，當它們的強度非常相似時，權重非常大，不可能被切割分離。因此，當從S-T圖中實現最小切割時，切割的位置接近物體邊界，同時此時能量函數值也最小。

2 K近鄰分類指導的區域迭代圖割算法

圖割算法為圖像分割提供全局最優解決方案，然而，對于復雜圖像，圖割算法難以一次性精確地分割整個圖像。Besag[11]提出的ICM是一種確定性算法，它使用貪婪策略，通過迭代局部最大化的方法來逼近馬爾可夫隨機場(MRF)的最大聯合概率。采用ICM的策略，本文首先采用均值偏移(Meanshift)算法預分割圖像，將分割區域作為超像素點構建S-T加權圖。根據用戶標記種子點建立子圖，在子圖上求能量函數最小值，并以此局部最小能量所對應的標號場作為新的種子點，迭代擴展子圖直到達到整個圖。

像ICM算法一樣，這種迭代圖割算法受初始化標簽影響很大，如果每次迭代存在錯誤的初始化標簽，后續迭代中初始標號場的錯誤將在圖像分割過程中被放大。另外，盡管圖割算法相較于自動分割算法，擁有用戶交互信息作為分割的硬性約束，能夠大大提高分割的準確性和魯棒性，更能產生令人滿意的分割結果，但仍存在錯誤分割的可能。所以直接將每次局部迭代分割結果作為初始信息指導下次迭代分割的方法并不是很合理，有可能影響整個分割算法的準確性。

本文提出算法的大致流程如圖2所示。為了解決上述問題，該算法在每次迭代分割中使用KNN算法對本次局部分割中未標記的區域進行分類標記，以超像素點的顏色空間信息和位置空間信息為特征向量，給予局部Graph cuts算法的標記結果置信度評估。另外針對實際交互式圖像分割標簽分類中有標簽的數據少而未標記的數據多的情況，使用自訓練(self-training)半監督學習方法[14]，選擇高置信度標記結果，迭代訓練KNN分類器。從迭代訓練中挑選出最合適的KNN分類器，將其訓練集數據及對應標簽作為到下次區域圖割算法的種子點，更新圖割算法的目標/背景模型。

圖2 本文算法的流程圖

2.1 圖像預處理

在Graph cuts算法中，圖像分割直接在像素上進行，在S-T加權圖中將每個像素作為節點計算，計算的成本很高。另外，分割結果不平滑，特別是邊緣處。在Wu和Leahy工作中提出的最小割對小的孤立節點集進行的分割存在偏倚[15]。許多其他的目標函數，如平均割[16]、歸一化割[17]、比率割[18]等采用新的分割標準來解決這個問題。

Lazy snapping算法[8]用分水嶺變換進行預分割，首先將圖像分成許多小的同質區域代替傳統Graph cuts算法中的像素點，作為節點構建加權圖，并以此優化加速Graph cuts過程，更好地保存目標邊界。但分水嶺算法對噪聲非常敏感，會導致嚴重的超分割現象。基于預分割的Graph cuts分割模型中，準確的初始區域分割對后續的分割性能起到至關重要的作用。為減輕分水嶺算法噪聲的影響，本文采用均值漂移算法處理圖像的預分割。根據文獻[19]中的方法，在三維的LUV彩色空間和二維的位置坐標所組成的五維特征空間上進行分析，f(x)為五維特征空間上的概率密度函數，其梯度估計為：

▽f(x)∝(avgxi∈Wh,x[xi]-x)

(8)

式中：avg表示平均，Wh,x表示以x為中心并以h={hs,hr}為帶寬的五維超球體，hs和hr分別表示位置空間和彩色空間的帶寬。對原圖像的每個像素使用梯度上升法，通過在特征空間中反復迭代尋找概率密度的極大值，再按照區域鄰接圖和彩色帶寬進行遞歸合并。這種計算方式耗時較多，但相較于分水嶺算法，均值漂移算法產生更少的過分割，且能提供更好的邊界保存，在后續的超像素點分割中能夠降低計算成本以及提高分割性能。本文預分割實驗中hs=10、hr=15。

2.2 區域迭代圖割算法模型建立

文獻[12]建立了一種區域迭代Graph cuts模型。將圖像進行如2.1節所述的預分割，分割后的圖像表示為G=V,E，V是相應預分割圖像超像素點的集合，E是連接相鄰超像素點邊的集合。由初始用戶標定的種子點開始建立子圖，包含種子點及其相鄰超像素點，子圖形式為G′=V′,E′，其中V′?V，E′?E。圖像分割問題要求的是滿足最大后驗概率的對每個超像素點的分類標記，即第1節中的標號場L。局部分割過程中必須遵循馬爾可夫性，在相鄰位置上標簽取值已知的條件下，標定過程只取決于相鄰的標簽，即P(αi|αD-{i})=P(αi|αNi)(i∈D)，Ni是i的鄰近系統。在MAP-MRF框架下通過最大化條件概率P(αi|di,αD-{i})獲取每個標簽αi。

(9)

當d給定時，P(d)是一個標準化常量，所以:

P(αi|di,αD-{i})∝P(di|αi)·P(αi|αNi)

(10)

而后驗概率滿足:

P(αi|di,αD-{i})∝e-U(αi|di,αNi)

(11)

U(αi|di,αNi)為后驗能量，結合式(10)和式(11)可得：

U(αi|di,αNi)=U(di|αi)+U(αi|αNi)

(12)

(13)

αk+1=argminαU(α|d,αk)

(14)

αk+1為第k+1次迭代中標定區域的標簽，該迭代過程不斷標記新的未標記超像素點，直至整幅圖像被全部標記。具體算法流程見算法1。

算法1區域迭代圖割算法

輸入：

原始圖像的預分割圖像；

2.3.3 精密度試驗 取“2.2.1”項下對照品溶液適量，分別加甲醇制成低、中、高質量濃度（3.84、7.68、15.36 μg/mL）對照品溶液，以甲醇為空白，于322 nm波長處測定吸光度，連續測定6次。結果，米索硝唑吸光度的RSD分別為0.93%、0.62%、0.48%（n＝6），表明儀器精密度良好。

種子點區域X0=Ro∪Rb；

種子點的鄰近未標記區域Y0。

輸出：圖像分割結果。

1.根據標記的種子區域構建前景和背景模型；

2.建立子圖G′=〈V′,E′〉，其中V′包括種子點區域X0和Y0；

3.使用圖割算法求出子圖G′中的最大流/最小割，給予鄰近未分割超像素點分割標簽；

4.根據表2中算法評估步驟3中的標簽，選擇具有高置信度標簽的超像素點加入對應的種子點集合，更新前景和背景模型；

5.返回步驟2，直至整幅圖像中沒有未標記的超像素點；

6.返回最終的分割結果；

while 1

Labels_neighbor = Graphcuts(X0, Y0);

//圖割算法獲取鄰近未標記區域標簽

[Flabels,Blabels] = KNN(X0, Labels_neighbor);

//KNN分類器自訓練過程算法，實現算法見表2

X0= X0+Flabels+ Blabels;

Y0= Y0-Flabels-Blabels;

if Y0= 0

break;

end

F = F+ Flabels;

B = B+ Blabels;

//F為分割的前景區域，B為分割的背景區域

end

//迭代局部圖割算法

Labels_neighbor = Graphcuts(X0, Y0)

{

for i = 1:numel(Y0)

U(i) = A(i)+T(i);

//U為所求后驗能量

end

[Umin,labels_new] = min(U,[],2);

labels_neighbor = [neighbors,labels_new];

//最低能量時鄰近未標記區域的分配標簽

}

2.3 自訓練K近鄰算法評估分割標簽

任何分割算法都不能保證準確無誤地分割性能，本文方法采用的ICM模型，將每次局部分割結果作為指導信息，迭代入下次局部分割。這就有可能將之前迭代分割中的錯誤在后續分割中不斷放大，進而影響整個算法分割的準確性。

為此，本文中訓練一個KNN分類器，使用超像素點的顏色空間信息和位置空間信息作為特征向量訓練分類器。隨后對每次區域迭代圖割中的鄰近未標記區域進行分類，并根據分類結果給予本次局部圖割標記結果相應的置信度。選擇擁有高置信度標簽的超像素點，作為到下次分割的種子點，更新圖割的目標前景/背景模型。

但由于KNN算法不能直接處理大量含有無標記數據的數據集，根據半監督分類學習的定義及文獻[20]，本文采用自訓練的學習算法把未標記的數據逐步分類，并將分類好的數據加到已標記數據集中去，擴大訓練樣本集，同時了縮小待測樣本集，繼續訓練KNN分類器。根據分類器每次置信度評估結果計算平均置信度，訓練器不斷迭代直到得到最適合所分割圖像的分類器，以此減少局部分割中產生的錯誤，提高迭代圖割模型的分割性能。KNN分類器的自訓練算法見算法2。

算法2KNN分類器的自訓練過程算法

輸入：

種子點區域X0=Ro∪Rb及相應的標簽FS；

種子點的鄰近未標記區域Y0；

分類器迭代訓練次數T；

獲取置信區域比例s；

輸出：FS′

for iter = 1:T

mdl =ClassificationKNN.fit(X0,FS,′NumNeighbors′,3);

//訓練KNN分類器

[label_pred,score] = predict(mdl,Y0);

//預測鄰近未標記區域的分類標簽

Conf = zeros(size(Y0),3);

Conf(:,1) = FS(:,1);

for i = 1:size(Y0)

if FS(i) ～= label_pred(i,1)

Conf(i,2) = 0;

elseif (FS(i,2) == label_pred(i,1))&&(label_pred(i,1)==0)

Conf(i,2) = score(i,1);

Conf(i,3) = 0;

else

Conf(i,2) = score(i,2);

Conf(i,3) = 1;

end

end

//使用KNN分類器評估圖割分割標簽置信度

PU = sortrows(Conf,-2);

//按置信度從高到低排序

S = ceil(size(Conf,1)*s);

PU = PU(1:S,:);

AvgConf(iter) = mean(PU(:,2),1);

//計算平均置信度

end

[AvgConf_MAX,index_MAX] = max(AvgConf,[],1);

//選擇平均置信度最高的分類器的分類結果FS’

如算法2所描述，自訓練學習方法同時在有類別標簽數據集和無類別標簽數據集上進行特征選擇。首先，該算法在有類別標簽數據集上進行特征選擇，產生初始候選特征子集。然后在該特征子集上用有類別標簽數據集訓練一個帶置信度輸出的KNN分類器C。接著用C對無類別標簽數據集上的數據進行分類預測，從而獲得其類別標簽，從中選擇出置信度從高到低的占比s的數據，加入到原始訓練集中形成一個新的訓練集，迭代訓練分類器。最終選擇平均置信度最高的分類器作為最合適的KNN分類器，其預測標簽作為新的分割種子點，進而更新局部圖割算法中的目標前景/背景模型。通過實驗，本文中s取0.5，訓練的KNN分類器的K值取3。

圖3展示了本文提出的區域圖割算法在KNN分類器指導下分割圖像的過程。通過用戶輸入種子點，分割種子點鄰近區域，分配相應的對象和背景標簽，并將新分割的區域作為新的種子點，更新圖割算法的前景/背景模型。并且在新的前景/背景模型下分割相鄰未標記區域，迭代上述過程，直至將整幅圖像完全分割開，從而獲得我們所期望的目標區域。圖3中，(a)為用戶在原始圖像中標記的種子點，(b)-(j)為分割過程中的迭代分割結果。子圖中每次迭代新分割區域以紅色表示，背景區域以藍色表示(顏色以灰度表示)。(k)則展示了目標對象的最終分割結果。

圖3 迭代分割過程

3 實驗與結果分析

本節主要展示本文提出的算法與Lazying Snapping算法圖像分割實驗結果的比較，并且進行定量評估的對比分析。另外，還將提出的算法在使用KNN分類器評估置信度和不使用KNN分類器評估置信度兩種情況下的分割結果進行比對，探討KNN分類器對本文所提出算法的影響。

本文實驗平臺為Intel Core i5-4460 CPU 3.20 GHz的CPU和4 GB的內存，實驗使用MATLAB R2017a對Berkeley圖像數據庫中的50幅基準彩色圖像進行測試，其中10張具有簡單背景內容，其余圖像具有相對復雜的背景內容。這些實驗圖像的大小分辨率有兩種，分別為321×481(像素)和481×321(像素)。數據庫中每張圖像都有人為標記的目標-背景分布作為參考標準。

本文中的位置空間帶寬hs和hr兩個參數越大，分割的整體性越好，分割產生的區域數越小，分割結果越平滑，但對弱邊界的識別能力越弱。反之，這兩個參數越小，分割精細度越高，對弱邊界的識別能力越強，但分割所產生的過分割現象越嚴重，為了控制分割質量，經過預分割實驗效果比較，取hs=10、hr=15。

自訓練過程中，KNN分類器選擇的K值小，分類器的近似誤差會減小，但估計誤差會增大，容易發生過擬合；相反，K值大，近似誤差會增大，估計誤差會減小，從而有可能忽略訓練集中的有用信息。這里近似誤差指的是目標點對于其原樣本點的可信度，也就是說，K值越小，與目標點鄰近的點的標簽對于其目標點的影響也就越大，其標簽的一致性就越高。估計誤差是原模型本身的真實性，即該模型所表現出的分類特性，是否為真實的分類特性，噪點影響、錯誤數據或者本身分布不是很好的數據，都會影響估計誤差。如果K值比較大，那么以上缺陷就會盡可能被平均，從而減小對最終結果的影響。經過實驗比較，本文中取K=3。

3.1 與Lazying Snapping算法分割效果比較

本節中將提出的算法與Lazying Snapping算法的分割效果作對比，圖4中包括背景簡單的圖像((a)、(b))和背景相對復雜的圖像((c)-(e))。圖4中第一列為原始圖像上用戶種子點信息，第二列為Lazying Snapping算法的分割結果，第三列為本文所提出算法的分割結果。由圖可知，給定相同數量的種子點，提出的方法較Lazying Snapping算法能取得更好的分割結果，分割效果也更符合人們的主觀需求。

圖4 Lazying Snapping算法和擔出算法的圖像分割效果

Lazying Snapping算法使用圖割算法分割整個圖像，需要人工交互信息指導，特別是對于背景相對復雜的圖像，圖像中很多未標記的背景區域可能會對圖像分割優化產生不可預測的負面影響，往往需要更多用戶標記的種子點，才能獲得令人滿意的分割結果。而本文中提出的算法通過在局部子圖使用圖割算法分割，子圖顯著降低圖像中背景內容的復雜度，并阻擋遠離標記區域的未知區域，降低背景干擾。因此如圖4中五組對比圖所示，在相同的用戶交互量下本文中提出的算法可以獲得更好的分割結果。

3.2 與無KNN分類指導的迭代圖割算法分割效果比較

本節中對比的兩種算法在預分割和迭代分割的方法都是一樣的，差別在于是否使用自訓練的KNN分類器對每次局部圖割分割結果進行評估。圖5展示了對比實驗結果,其中：第一列為原始圖像上用戶種子點信息；第二列為無KNN分類指導信息的局部迭代算法的分割結果；第三列為本文所提出算法的分割結果。有KNN分類指導的局部迭代圖割算法較無KNN分類指導的算法能取得更好的分割結果。

圖5 無KNN分類器指導的局部迭代圖割算法和本文算法的圖像分割效果

根據KNN分類器基于每次局部區域分割的結果標簽置信度，并用置信度信息指導下次迭代的種子點選取，可以減少局部分割中產生錯誤標定的可能性，避免形成的分割錯誤在后續迭代步進過程中被放大，進而提升分割性能和魯棒性。

3.3 計算時間

表1顯示了前文所對比的三種算法在圖割算法階段的計算時間比較。因為Lazying Snapping算法采用的是分水嶺算法進行預分割，而本文提出的算法采用Meanshift算法進行預分割，直接比較兩種算法的總計算時間不是很合理，所以我們對比了不同算法在圖割算法階段的計算時間。

表1 圖割算法階段的計算時間比較

續表1

本文提出的方法在時間上消耗是Lazy snapping算法的20倍左右，是未使用KNN分類器指導的1.8倍左右。但Lazy snapping算法要達到理想的分割效果，往往需要進行多次交互，每次交互都需要給予新的交互信息，所以本文方法在實際圖像分割應用中具有更強的實用性。

3.4 定量評估

分割定量評估是通過與數據庫參考標準分割對比，分割質量四個參數來度量，分別是TPF、FPF、TNF和FNF,定義如下：

(15)

(16)

(17)

(18)

表2是上述三種方法對50幅基準圖像分割結果定量評估的平均水平。比較表中的TPF、FPF、TNF、FNF值可以看出，有KNN指導的區域迭代圖割算法可以獲得最佳的TPF、FPF、TNF、FNF值，較另外兩種分割算法擁有更好的準確性。

表2 數據庫50幅基準圖像分割結果的定量評估 %

表3是三種算法對圖4中5幅圖像分割的定量評估，為了直觀展現算法定量評估值的對比，圖6為三種算法在5幅實驗圖像中定量評估值的折線圖。

表3 三種算法對五組圖像分割結果的定量評估 %

圖6 三種算法定量評估值對比

結合表2和表3分割算法定量評估數據，Lazying snapping算法雖然有些情況下也能產生不錯的分割，但對初始用戶交互需求較大，特別對于背景復雜的圖像，其魯棒性低于本文提出的算法；而不使用KNN分類器指導分割的算法雖然對魯棒性沒有明顯影響，但其準確性不如使用KNN分類器指導分割的算法。

4 結 語

本文基于超像素構建Graph cuts加權圖和局部迭代的Graph cuts模型，使用自訓練KNN分類器學習指導更新目標/背景模型，以置信度為衡量標準減少迭代模型中產生的分割錯誤，避免錯誤被放大。通過實例自然圖像對不同算法進行比較，實驗結果表明本文算法在準確性和魯棒性等方面具有更好的性能。除了在自然圖像分割上的應用，本文中的算法為進行交互式醫學圖像分割提供了新的思路。隨著醫學影像技術的發展，醫學圖像分辨率越來越高，細節越來越多，自動圖像分割技術難以獲得令人滿意的結果。本文算法可以通過用戶輸入信息準確地從復雜背景中分割出感興趣目標，如腫塊分割、腫瘤靶區勾畫，提升圖像分割的性能。

本文仍有一些問題有待進一步研究：提升分割算法對初始種子點選取的魯棒性；KNN分類學習訓練時，除了顏色空間和位置空間的特征向量，是否有其他的特征向量能進一步提高分類器評估標簽的置信水平；除了使用KNN學習外，其他半監督學習是否也能提升graph cuts分割的準確性和魯棒性。