K近鄰分類(lèi)指導(dǎo)的區(qū)域迭代圖割算法研究

管 建 王亞娟 王立功

(蘇州大學(xué)醫(yī)學(xué)部放射醫(yī)學(xué)與防護(hù)學(xué)院 江蘇 蘇州 215123)

0 引 言

圖像分割的原理是根據(jù)一定的相似性準(zhǔn)則將圖像劃分成多個(gè)具有獨(dú)特性質(zhì)區(qū)域的過(guò)程,各區(qū)域內(nèi)具有相同或相似的性質(zhì)，從而達(dá)到在復(fù)雜的背景環(huán)境中把感興趣的目標(biāo)區(qū)域提取出來(lái)的目的。近十余年來(lái)，自動(dòng)化圖像分割在許多領(lǐng)域得到了廣泛研究，如自然圖像分割[1]、醫(yī)學(xué)圖像分割[2]等，但在內(nèi)容復(fù)雜的圖像上應(yīng)用仍然存在很大的問(wèn)題。理想的分割通常需要在分割過(guò)程中增加用戶(hù)指導(dǎo)信息來(lái)獲取目標(biāo)，減少自動(dòng)化分割帶來(lái)的歧義性，因此，交互式的分割方法具有更強(qiáng)的實(shí)用性。

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

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

1 圖割算法分析

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

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

馬爾可夫隨機(jī)場(chǎng)能量泛函如下：

(1)

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

(2)

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

(3)

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

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

(4)

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

(5)

ω[i,j]定義為：

(6)

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

(7)

在S-T圖中，S為源極點(diǎn)，T為匯極點(diǎn)，當(dāng)超像素點(diǎn)的強(qiáng)度傾向于歸為目標(biāo)對(duì)象時(shí)，其與S節(jié)點(diǎn)之間的權(quán)重將大于像素與T節(jié)點(diǎn)之間的權(quán)重，這意味著切割更可能發(fā)生在權(quán)重更小處。對(duì)于相鄰的像素，當(dāng)它們的強(qiáng)度非常相似時(shí)，權(quán)重非常大，不可能被切割分離。因此，當(dāng)從S-T圖中實(shí)現(xiàn)最小切割時(shí)，切割的位置接近物體邊界，同時(shí)此時(shí)能量函數(shù)值也最小。

2 K近鄰分類(lèi)指導(dǎo)的區(qū)域迭代圖割算法

圖割算法為圖像分割提供全局最優(yōu)解決方案，然而，對(duì)于復(fù)雜圖像，圖割算法難以一次性精確地分割整個(gè)圖像。Besag[11]提出的ICM是一種確定性算法，它使用貪婪策略，通過(guò)迭代局部最大化的方法來(lái)逼近馬爾可夫隨機(jī)場(chǎng)(MRF)的最大聯(lián)合概率。采用ICM的策略，本文首先采用均值偏移(Meanshift)算法預(yù)分割圖像，將分割區(qū)域作為超像素點(diǎn)構(gòu)建S-T加權(quán)圖。根據(jù)用戶(hù)標(biāo)記種子點(diǎn)建立子圖，在子圖上求能量函數(shù)最小值，并以此局部最小能量所對(duì)應(yīng)的標(biāo)號(hào)場(chǎng)作為新的種子點(diǎn)，迭代擴(kuò)展子圖直到達(dá)到整個(gè)圖。

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

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

圖2 本文算法的流程圖

2.1 圖像預(yù)處理

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

Lazy snapping算法[8]用分水嶺變換進(jìn)行預(yù)分割，首先將圖像分成許多小的同質(zhì)區(qū)域代替?zhèn)鹘y(tǒng)Graph cuts算法中的像素點(diǎn)，作為節(jié)點(diǎn)構(gòu)建加權(quán)圖，并以此優(yōu)化加速Graph cuts過(guò)程，更好地保存目標(biāo)邊界。但分水嶺算法對(duì)噪聲非常敏感，會(huì)導(dǎo)致嚴(yán)重的超分割現(xiàn)象?；陬A(yù)分割的Graph cuts分割模型中，準(zhǔn)確的初始區(qū)域分割對(duì)后續(xù)的分割性能起到至關(guān)重要的作用。為減輕分水嶺算法噪聲的影響，本文采用均值漂移算法處理圖像的預(yù)分割。根據(jù)文獻(xiàn)[19]中的方法，在三維的LUV彩色空間和二維的位置坐標(biāo)所組成的五維特征空間上進(jìn)行分析，f(x)為五維特征空間上的概率密度函數(shù)，其梯度估計(jì)為：

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

(8)

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

2.2 區(qū)域迭代圖割算法模型建立

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

(9)

當(dāng)d給定時(shí)，P(d)是一個(gè)標(biāo)準(zhǔn)化常量，所以:

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

(10)

而后驗(yàn)概率滿(mǎn)足:

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

(11)

U(αi|di,αNi)為后驗(yàn)?zāi)芰?，結(jié)合式(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次迭代中標(biāo)定區(qū)域的標(biāo)簽，該迭代過(guò)程不斷標(biāo)記新的未標(biāo)記超像素點(diǎn)，直至整幅圖像被全部標(biāo)記。具體算法流程見(jiàn)算法1。

算法1區(qū)域迭代圖割算法

輸入：

原始圖像的預(yù)分割圖像；

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

種子點(diǎn)區(qū)域X0=Ro∪Rb；

種子點(diǎn)的鄰近未標(biāo)記區(qū)域Y0。

輸出：圖像分割結(jié)果。

1.根據(jù)標(biāo)記的種子區(qū)域構(gòu)建前景和背景模型；

2.建立子圖G′=〈V′,E′〉，其中V′包括種子點(diǎn)區(qū)域X0和Y0；

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

4.根據(jù)表2中算法評(píng)估步驟3中的標(biāo)簽，選擇具有高置信度標(biāo)簽的超像素點(diǎn)加入對(duì)應(yīng)的種子點(diǎn)集合，更新前景和背景模型；

5.返回步驟2，直至整幅圖像中沒(méi)有未標(biāo)記的超像素點(diǎn)；

6.返回最終的分割結(jié)果；

while 1

Labels_neighbor = Graphcuts(X0, Y0);

//圖割算法獲取鄰近未標(biāo)記區(qū)域標(biāo)簽

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

//KNN分類(lèi)器自訓(xùn)練過(guò)程算法，實(shí)現(xiàn)算法見(jiàn)表2

X0= X0+Flabels+ Blabels;

Y0= Y0-Flabels-Blabels;

if Y0= 0

break;

end

F = F+ Flabels;

B = B+ Blabels;

//F為分割的前景區(qū)域，B為分割的背景區(qū)域

end

//迭代局部圖割算法

Labels_neighbor = Graphcuts(X0, Y0)

{

for i = 1:numel(Y0)

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

//U為所求后驗(yàn)?zāi)芰?/p>

end

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

labels_neighbor = [neighbors,labels_new];

//最低能量時(shí)鄰近未標(biāo)記區(qū)域的分配標(biāo)簽

}

2.3 自訓(xùn)練K近鄰算法評(píng)估分割標(biāo)簽

任何分割算法都不能保證準(zhǔn)確無(wú)誤地分割性能，本文方法采用的ICM模型，將每次局部分割結(jié)果作為指導(dǎo)信息，迭代入下次局部分割。這就有可能將之前迭代分割中的錯(cuò)誤在后續(xù)分割中不斷放大，進(jìn)而影響整個(gè)算法分割的準(zhǔn)確性。

為此，本文中訓(xùn)練一個(gè)KNN分類(lèi)器，使用超像素點(diǎn)的顏色空間信息和位置空間信息作為特征向量訓(xùn)練分類(lèi)器。隨后對(duì)每次區(qū)域迭代圖割中的鄰近未標(biāo)記區(qū)域進(jìn)行分類(lèi)，并根據(jù)分類(lèi)結(jié)果給予本次局部圖割標(biāo)記結(jié)果相應(yīng)的置信度。選擇擁有高置信度標(biāo)簽的超像素點(diǎn)，作為到下次分割的種子點(diǎn)，更新圖割的目標(biāo)前景/背景模型。

但由于KNN算法不能直接處理大量含有無(wú)標(biāo)記數(shù)據(jù)的數(shù)據(jù)集，根據(jù)半監(jiān)督分類(lèi)學(xué)習(xí)的定義及文獻(xiàn)[20]，本文采用自訓(xùn)練的學(xué)習(xí)算法把未標(biāo)記的數(shù)據(jù)逐步分類(lèi)，并將分類(lèi)好的數(shù)據(jù)加到已標(biāo)記數(shù)據(jù)集中去，擴(kuò)大訓(xùn)練樣本集，同時(shí)了縮小待測(cè)樣本集，繼續(xù)訓(xùn)練KNN分類(lèi)器。根據(jù)分類(lèi)器每次置信度評(píng)估結(jié)果計(jì)算平均置信度，訓(xùn)練器不斷迭代直到得到最適合所分割圖像的分類(lèi)器，以此減少局部分割中產(chǎn)生的錯(cuò)誤，提高迭代圖割模型的分割性能。KNN分類(lèi)器的自訓(xùn)練算法見(jiàn)算法2。

算法2KNN分類(lèi)器的自訓(xùn)練過(guò)程算法

輸入：

種子點(diǎn)區(qū)域X0=Ro∪Rb及相應(yīng)的標(biāo)簽FS；

種子點(diǎn)的鄰近未標(biāo)記區(qū)域Y0；

分類(lèi)器迭代訓(xùn)練次數(shù)T；

獲取置信區(qū)域比例s；

輸出：FS′

for iter = 1:T

mdl =ClassificationKNN.fit(X0,FS,′N(xiāo)umNeighbors′,3);

//訓(xùn)練KNN分類(lèi)器

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

//預(yù)測(cè)鄰近未標(biāo)記區(qū)域的分類(lèi)標(biāo)簽

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分類(lèi)器評(píng)估圖割分割標(biāo)簽置信度

PU = sortrows(Conf,-2);

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

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

PU = PU(1:S,:);

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

//計(jì)算平均置信度

end

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

//選擇平均置信度最高的分類(lèi)器的分類(lèi)結(jié)果FS’

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

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

圖3 迭代分割過(guò)程

3 實(shí)驗(yàn)與結(jié)果分析

本節(jié)主要展示本文提出的算法與Lazying Snapping算法圖像分割實(shí)驗(yàn)結(jié)果的比較，并且進(jìn)行定量評(píng)估的對(duì)比分析。另外，還將提出的算法在使用KNN分類(lèi)器評(píng)估置信度和不使用KNN分類(lèi)器評(píng)估置信度兩種情況下的分割結(jié)果進(jìn)行比對(duì)，探討KNN分類(lèi)器對(duì)本文所提出算法的影響。

本文實(shí)驗(yàn)平臺(tái)為Intel Core i5-4460 CPU 3.20 GHz的CPU和4 GB的內(nèi)存，實(shí)驗(yàn)使用MATLAB R2017a對(duì)Berkeley圖像數(shù)據(jù)庫(kù)中的50幅基準(zhǔn)彩色圖像進(jìn)行測(cè)試，其中10張具有簡(jiǎn)單背景內(nèi)容，其余圖像具有相對(duì)復(fù)雜的背景內(nèi)容。這些實(shí)驗(yàn)圖像的大小分辨率有兩種，分別為321×481(像素)和481×321(像素)。數(shù)據(jù)庫(kù)中每張圖像都有人為標(biāo)記的目標(biāo)-背景分布作為參考標(biāo)準(zhǔn)。

本文中的位置空間帶寬hs和hr兩個(gè)參數(shù)越大，分割的整體性越好，分割產(chǎn)生的區(qū)域數(shù)越小，分割結(jié)果越平滑，但對(duì)弱邊界的識(shí)別能力越弱。反之，這兩個(gè)參數(shù)越小，分割精細(xì)度越高，對(duì)弱邊界的識(shí)別能力越強(qiáng)，但分割所產(chǎn)生的過(guò)分割現(xiàn)象越嚴(yán)重，為了控制分割質(zhì)量，經(jīng)過(guò)預(yù)分割實(shí)驗(yàn)效果比較，取hs=10、hr=15。

自訓(xùn)練過(guò)程中，KNN分類(lèi)器選擇的K值小，分類(lèi)器的近似誤差會(huì)減小，但估計(jì)誤差會(huì)增大，容易發(fā)生過(guò)擬合；相反，K值大，近似誤差會(huì)增大，估計(jì)誤差會(huì)減小，從而有可能忽略訓(xùn)練集中的有用信息。這里近似誤差指的是目標(biāo)點(diǎn)對(duì)于其原樣本點(diǎn)的可信度，也就是說(shuō)，K值越小，與目標(biāo)點(diǎn)鄰近的點(diǎn)的標(biāo)簽對(duì)于其目標(biāo)點(diǎn)的影響也就越大，其標(biāo)簽的一致性就越高。估計(jì)誤差是原模型本身的真實(shí)性，即該模型所表現(xiàn)出的分類(lèi)特性，是否為真實(shí)的分類(lèi)特性，噪點(diǎn)影響、錯(cuò)誤數(shù)據(jù)或者本身分布不是很好的數(shù)據(jù)，都會(huì)影響估計(jì)誤差。如果K值比較大，那么以上缺陷就會(huì)盡可能被平均，從而減小對(duì)最終結(jié)果的影響。經(jīng)過(guò)實(shí)驗(yàn)比較，本文中取K=3。

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

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

圖4 Lazying Snapping算法和擔(dān)出算法的圖像分割效果

Lazying Snapping算法使用圖割算法分割整個(gè)圖像，需要人工交互信息指導(dǎo)，特別是對(duì)于背景相對(duì)復(fù)雜的圖像，圖像中很多未標(biāo)記的背景區(qū)域可能會(huì)對(duì)圖像分割優(yōu)化產(chǎn)生不可預(yù)測(cè)的負(fù)面影響，往往需要更多用戶(hù)標(biāo)記的種子點(diǎn)，才能獲得令人滿(mǎn)意的分割結(jié)果。而本文中提出的算法通過(guò)在局部子圖使用圖割算法分割，子圖顯著降低圖像中背景內(nèi)容的復(fù)雜度，并阻擋遠(yuǎn)離標(biāo)記區(qū)域的未知區(qū)域，降低背景干擾。因此如圖4中五組對(duì)比圖所示，在相同的用戶(hù)交互量下本文中提出的算法可以獲得更好的分割結(jié)果。

3.2 與無(wú)KNN分類(lèi)指導(dǎo)的迭代圖割算法分割效果比較

本節(jié)中對(duì)比的兩種算法在預(yù)分割和迭代分割的方法都是一樣的，差別在于是否使用自訓(xùn)練的KNN分類(lèi)器對(duì)每次局部圖割分割結(jié)果進(jìn)行評(píng)估。圖5展示了對(duì)比實(shí)驗(yàn)結(jié)果,其中：第一列為原始圖像上用戶(hù)種子點(diǎn)信息；第二列為無(wú)KNN分類(lèi)指導(dǎo)信息的局部迭代算法的分割結(jié)果；第三列為本文所提出算法的分割結(jié)果。有KNN分類(lèi)指導(dǎo)的局部迭代圖割算法較無(wú)KNN分類(lèi)指導(dǎo)的算法能取得更好的分割結(jié)果。

圖5 無(wú)KNN分類(lèi)器指導(dǎo)的局部迭代圖割算法和本文算法的圖像分割效果

根據(jù)KNN分類(lèi)器基于每次局部區(qū)域分割的結(jié)果標(biāo)簽置信度，并用置信度信息指導(dǎo)下次迭代的種子點(diǎn)選取，可以減少局部分割中產(chǎn)生錯(cuò)誤標(biāo)定的可能性，避免形成的分割錯(cuò)誤在后續(xù)迭代步進(jìn)過(guò)程中被放大，進(jìn)而提升分割性能和魯棒性。

3.3 計(jì)算時(shí)間

表1顯示了前文所對(duì)比的三種算法在圖割算法階段的計(jì)算時(shí)間比較。因?yàn)長(zhǎng)azying Snapping算法采用的是分水嶺算法進(jìn)行預(yù)分割，而本文提出的算法采用Meanshift算法進(jìn)行預(yù)分割，直接比較兩種算法的總計(jì)算時(shí)間不是很合理，所以我們對(duì)比了不同算法在圖割算法階段的計(jì)算時(shí)間。

表1 圖割算法階段的計(jì)算時(shí)間比較

續(xù)表1

本文提出的方法在時(shí)間上消耗是Lazy snapping算法的20倍左右，是未使用KNN分類(lèi)器指導(dǎo)的1.8倍左右。但Lazy snapping算法要達(dá)到理想的分割效果，往往需要進(jìn)行多次交互，每次交互都需要給予新的交互信息，所以本文方法在實(shí)際圖像分割應(yīng)用中具有更強(qiáng)的實(shí)用性。

3.4 定量評(píng)估

分割定量評(píng)估是通過(guò)與數(shù)據(jù)庫(kù)參考標(biāo)準(zhǔn)分割對(duì)比，分割質(zhì)量四個(gè)參數(shù)來(lái)度量，分別是TPF、FPF、TNF和FNF,定義如下：

(15)

(16)

(17)

(18)

表2是上述三種方法對(duì)50幅基準(zhǔn)圖像分割結(jié)果定量評(píng)估的平均水平。比較表中的TPF、FPF、TNF、FNF值可以看出，有KNN指導(dǎo)的區(qū)域迭代圖割算法可以獲得最佳的TPF、FPF、TNF、FNF值，較另外兩種分割算法擁有更好的準(zhǔn)確性。

表2 數(shù)據(jù)庫(kù)50幅基準(zhǔn)圖像分割結(jié)果的定量評(píng)估 %

表3是三種算法對(duì)圖4中5幅圖像分割的定量評(píng)估，為了直觀(guān)展現(xiàn)算法定量評(píng)估值的對(duì)比，圖6為三種算法在5幅實(shí)驗(yàn)圖像中定量評(píng)估值的折線(xiàn)圖。

表3 三種算法對(duì)五組圖像分割結(jié)果的定量評(píng)估 %

圖6 三種算法定量評(píng)估值對(duì)比

結(jié)合表2和表3分割算法定量評(píng)估數(shù)據(jù)，Lazying snapping算法雖然有些情況下也能產(chǎn)生不錯(cuò)的分割，但對(duì)初始用戶(hù)交互需求較大，特別對(duì)于背景復(fù)雜的圖像，其魯棒性低于本文提出的算法；而不使用KNN分類(lèi)器指導(dǎo)分割的算法雖然對(duì)魯棒性沒(méi)有明顯影響，但其準(zhǔn)確性不如使用KNN分類(lèi)器指導(dǎo)分割的算法。

4 結(jié) 語(yǔ)

本文基于超像素構(gòu)建Graph cuts加權(quán)圖和局部迭代的Graph cuts模型，使用自訓(xùn)練KNN分類(lèi)器學(xué)習(xí)指導(dǎo)更新目標(biāo)/背景模型，以置信度為衡量標(biāo)準(zhǔn)減少迭代模型中產(chǎn)生的分割錯(cuò)誤，避免錯(cuò)誤被放大。通過(guò)實(shí)例自然圖像對(duì)不同算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明本文算法在準(zhǔn)確性和魯棒性等方面具有更好的性能。除了在自然圖像分割上的應(yīng)用，本文中的算法為進(jìn)行交互式醫(yī)學(xué)圖像分割提供了新的思路。隨著醫(yī)學(xué)影像技術(shù)的發(fā)展，醫(yī)學(xué)圖像分辨率越來(lái)越高，細(xì)節(jié)越來(lái)越多，自動(dòng)圖像分割技術(shù)難以獲得令人滿(mǎn)意的結(jié)果。本文算法可以通過(guò)用戶(hù)輸入信息準(zhǔn)確地從復(fù)雜背景中分割出感興趣目標(biāo)，如腫塊分割、腫瘤靶區(qū)勾畫(huà)，提升圖像分割的性能。

本文仍有一些問(wèn)題有待進(jìn)一步研究：提升分割算法對(duì)初始種子點(diǎn)選取的魯棒性；KNN分類(lèi)學(xué)習(xí)訓(xùn)練時(shí)，除了顏色空間和位置空間的特征向量，是否有其他的特征向量能進(jìn)一步提高分類(lèi)器評(píng)估標(biāo)簽的置信水平；除了使用KNN學(xué)習(xí)外，其他半監(jiān)督學(xué)習(xí)是否也能提升graph cuts分割的準(zhǔn)確性和魯棒性。