改進(jìn)的基于空間模式聚類的圖像分割

摘 要：為了提高算法在含有一定噪聲的圖片中的分割功能，將一種隸屬度函數(shù)計(jì)算方法加入到一種空間模式聚類算法當(dāng)中，使原本已經(jīng)充分挖掘圖像空間信息的聚類算法，在含有一定噪聲的圖片上得到較好的分割效果。實(shí)驗(yàn)證明，修改后的算法提高了抗噪性能。

關(guān)鍵詞：圖像分割； 聚類； 噪聲； 空間模式； 隸屬度

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)06-2396-02

doi:10.3969/j.issn.1001-3695.2009.06.120

Image segmentation by improved clustering of spatial patterns

ZHU Wei-peng， WANG Shi-tong

(School of Information Technology， Jiangnan University， Wuxi Jiangsu 214122，China)

Abstract:

In order to improve the segmentation capability of algorithm in noisy images， this paper introduced a kind of membership functions with their robustness capability into the clustering procedure of spatial patterns for images，so the proposed algorithm could dig out the space information fully and produced good segmentation results for noisy images. Experiments prove that the modified algorithm has good performance in noisy images.

Key words：image segmentation； clustering； noise； space pattern； membership

圖像分割是圖像分析和模式識(shí)別的第一步，是圖像分析及模式識(shí)別基本和關(guān)鍵的組成部分，也是圖像分析中最困難的任務(wù)之一，它決定著分析的質(zhì)量和最終的結(jié)果。可將圖像分割的過(guò)程看成是把一幅圖像分離成一系列不重疊的區(qū)域，并且相鄰兩個(gè)區(qū)域間并不一致的過(guò)程。由于圖像本身的多樣和復(fù)雜性，要想順利地完成這樣的工作并不容易。影響分割效果的不僅有圖像間結(jié)構(gòu)空間上的差別，還有圖像中的噪聲和尺寸等。

總的來(lái)說(shuō)，大多數(shù)圖像分割算法建立在圖像本身的相似性、特殊性上，可以大致分為閾值^[1]、模板匹配^[2]、區(qū)域增長(zhǎng)^[3]、邊緣檢測(cè)^[4]和聚類^[5]幾種。這些方法在許多應(yīng)用領(lǐng)域獲得了成功，但是沒(méi)有一種算法適用于所有的圖像，并且對(duì)于一些特殊的應(yīng)用要求來(lái)說(shuō)，不同的算法在處理效果上有顯著的不同。圖像本身提供了豐富的結(jié)構(gòu)空間特征信息，好的算法應(yīng)當(dāng)盡量充分地挖掘這些信息，以便算法能夠準(zhǔn)確地進(jìn)行分割。

本文介紹的是一種改進(jìn)的比較強(qiáng)健的聚類算法，在充分考慮到圖像本身空間結(jié)構(gòu)特征的基礎(chǔ)上，具有一定的抗噪能力，使分割的效果更準(zhǔn)確。本文先介紹一種空間模式聚類算法^[6]，然后再介紹修改后的算法，最后展示了實(shí)驗(yàn)結(jié)果。

1 空間聚類算法

傳統(tǒng)的模糊聚類算法是通過(guò)定義在顏色空間上的歐拉距離公式進(jìn)行不相似性計(jì)算的，公式如下：

d=X－Vr2(1)

其中：X代表像素的顏色值；Vr代表聚類中心。 式（1）僅僅考慮了圖像的顏色信息。一種擴(kuò)展的新的距離公式挖掘了更豐富的圖像信息：

drs=dF(xiàn)rs+α×dSrs(2)

式(2)由兩個(gè)部分組成，dF(xiàn)rs代表式（1）中的顏色空間信息，dSrs則代表了圖像的位置空間信息。如果一個(gè)像素位于一個(gè)目標(biāo)區(qū)域內(nèi)，它就被認(rèn)為是與那個(gè)目標(biāo)的聚類更相似。對(duì)于每一個(gè)像素來(lái)說(shuō)，它的位置能夠從其空間上下文推理得到。在一幅圖像中，相鄰像素之間具有一定的聯(lián)系，因此，一個(gè)像素的空間上下文能夠從它的鄰域中進(jìn)行描述。如果一個(gè)像素鄰域中的所有像素都屬于第r個(gè)聚類，則認(rèn)為該像素也位于第r個(gè)區(qū)域中，并讓標(biāo)準(zhǔn)化的空間不相似性dSrs為1；相反，如果鄰域中沒(méi)有一個(gè)像素屬于第r個(gè)聚類，視該像素位于第r個(gè)區(qū)域之外并令dSrs為0。另一方面，dSrs的值位于0和1之間，對(duì)應(yīng)于鄰域有多少像素是位于第r個(gè)聚類中的。空間不相似性dSrs的計(jì)算公式如下：

dSrs=1－∑t∈ηsurtβt/（∑Cc=1∑t∈ηsurtβt）(3)

其中：C是預(yù)期的聚類數(shù)；βt是鄰接像素的貢獻(xiàn)因子；urs是像素S屬于第r個(gè)聚類Vr的隸屬度，表明了該像素屬于這個(gè)類的可能性大小，它位于0和1之間，同時(shí)它也滿足如下兩個(gè)限制

urs≥0，1≤r≤R，s∈S(4)

∑Rr=1urs=1，s∈S(5)

因子βt代表鄰接X(jué)t的隸屬度對(duì)于整個(gè)空間不相似性的影響。一般說(shuō)來(lái)，相鄰模式越靠近，相互之間的影響就越大，它的影響效果也越大。因此，對(duì)于每個(gè)鄰接模式Xt(t∈βt)，βt是坐標(biāo)t和s間非遞增的距離函數(shù)，在本文中其定義如下：

βt=1/[1+exp(θ×s－t)](6)

其中：因子θ決定兩個(gè)位置處的像素隨著距離的增加，它們之間相互減弱的程度。一個(gè)小的θ會(huì)導(dǎo)致不同鄰接像素間有相似的影響，一個(gè)大的θ會(huì)使得空間不相似性在很大程度上依賴于那些相近的鄰接像素。

α因子如下：

α(n)=0.2/[0.1+exp(-(n-n0)/ω)](7)

隸屬度矩陣更新如下：

u(n+1)rs=∑Cc=1(d(n)rs/d(n)cs)2/(m-1)－1c，d(n)cs>01c，s，d(n)cs=0 and r=c0c，s，d(n)cs=0 and r≠c (8)

聚類中心計(jì)算如下：

v(n)r=∑s∈S[(u(n)rs)mXs]/∑s∈S(u(n)rs)m， 1≤r≤C(9)

其中：v(n)r表示第n迭代時(shí)的聚類中心，聚類算法先隨機(jī)初始化一組聚類中心，然后進(jìn)入循環(huán)，計(jì)算各個(gè)像素點(diǎn)與相應(yīng)聚類型中心的距離，再用這些距離更新隸屬度函數(shù)，如此反復(fù)地迭代。出循環(huán)可有兩個(gè)條件：a）本次聚類中心與上一次聚類中間的誤差小于一個(gè)設(shè)定的極小閾值，表明聚類中心已經(jīng)在本次運(yùn)算當(dāng)中趨于穩(wěn)定，以后也不會(huì)有顯著的變化；b）設(shè)定一個(gè)整數(shù)，限定迭代的次數(shù)，當(dāng)達(dá)到這個(gè)數(shù)值時(shí)，表明聚類效果已經(jīng)達(dá)到可以接受的程度。

2 算法的改進(jìn)

隸屬度矩陣在模糊聚類算法中起著重要作用，它存儲(chǔ)了每個(gè)像素點(diǎn)屬于不同類的可能性大小。傳統(tǒng)的隸屬度矩陣計(jì)算如下：

ur，s=∑Ck=1(dr，s/dk，s)2/(m－1)－1(10)

實(shí)驗(yàn)當(dāng)中，m一般取2，所以上述函數(shù)就可以轉(zhuǎn)換為

ur，s=1/∑Ck=1(d2r，s/d2k，s)(11)

這樣看來(lái)可能要更直觀一些。在上面的距離公式中，兩個(gè)部分均用到了歐拉公式，分別用它來(lái)計(jì)算每個(gè)像素點(diǎn)在顏色空間上與聚類中心間的距離以及在位置空間中與鄰域像素點(diǎn)間的相互影響大小。由文獻(xiàn)[7]的結(jié)論可以知道，帶有平方的歐拉距離對(duì)于噪聲是極其敏感的，這就導(dǎo)致了上面的算法本身在抗噪性能上會(huì)有很大的損失。

當(dāng)把一個(gè)像素點(diǎn)歸于某一類時(shí)是理所當(dāng)然的，像素在這個(gè)類上的隸屬度值是最大的，可以把這個(gè)值認(rèn)為是盡可能地接近于1，而在其他類上的隸屬度值盡可能接近于0。從這個(gè)意義上看，該像素的隸屬度值應(yīng)該是一個(gè)單峰的曲線。然而，由式(11)產(chǎn)生的隸屬度值卻并不簡(jiǎn)單地滿足這個(gè)條件，如圖1所示。



圖中有三條線，分別表示聚類中心在1、3、8位置處時(shí)，用式(11)實(shí)際分割后的效果。毫無(wú)疑問(wèn)，隸屬度函數(shù)對(duì)于所有聚類中心的支持都應(yīng)該是具有相同功效的。但圖1卻表明聚類中心在3時(shí)的曲線具有較好的性能，而聚類中心在1、8時(shí)都產(chǎn)生了一些誤差，使圖中又出現(xiàn)了較小的波峰，尤其如中心為3時(shí)，在5附近體現(xiàn)較為明顯。由于聚類元素不可能是性質(zhì)一致的，一些其他派生元素會(huì)干擾聚類的隸屬度值。在圖像當(dāng)中，這些不一致的元素主要表現(xiàn)為噪聲等一些因素。可以對(duì)隸屬度值加入一個(gè)可調(diào)節(jié)的參數(shù)，起到抗噪的效果，同時(shí)在一定程序上它也會(huì)降低隸屬度值的指示作用，降低聚類的精確性，這與參數(shù)的選擇是相關(guān)的。

首先看一下下面的目標(biāo)函數(shù):

J=∑nj=1∑ci=1u2i，jd2(xj，ci)－∑ni=1aj∑cj=1(ui，j－1/2)2(12)

這個(gè)目標(biāo)函數(shù)由兩個(gè)部分組成。其中，第一部分實(shí)際上是傳統(tǒng)的目標(biāo)函數(shù)，第二部分是增添的部分。如果一個(gè)像素xj確定屬于聚類中心ci，那么ui，j=1且uk，j=0(k≠i)。對(duì)于所有這種情況，第二部分就變成了－aj/4。如果隸屬度越模糊，那么第二部分就會(huì)增長(zhǎng)，最終的目標(biāo)是要使目標(biāo)函數(shù)值達(dá)到最小，而通過(guò)這樣的修改會(huì)起到很大的作用。第二部分并沒(méi)有增加與ci相關(guān)的參數(shù)，所以隸屬度值在迭代更新時(shí)的速率與原算法相同。

根據(jù)式（12）的原則，提出如下隸屬度值公式：

ur，s=1/[∑Ck=1(d2r，s－aj)/(d2k，s－aj)](13)

證明過(guò)程可以參考文獻(xiàn)[7，8]。其中aj的選擇是個(gè)關(guān)鍵，如果不當(dāng)，可能導(dǎo)致ur，s為負(fù)值，它的意義是無(wú)法解釋的。為了確保不出現(xiàn)負(fù)的隸屬度值，將aj取如下值:

min d2*，s=min{d2r，s|r∈{1，NA1AD，c}}－η，η>0

如果沒(méi)有η>0，那么總會(huì)有一個(gè)s使得d2r，s－min d2*，s=0，則ur，s=1。所以，當(dāng)η=0時(shí)，會(huì)得到一個(gè)比較脆弱的分割。因此，η在一定程度上也決定著分割的效果。

那么隸屬度函數(shù)最終變?yōu)?/p>

ur，s=1/[∑Ck=1(d2r，s－min d2*，s)/(d2k，s－min d2*，s)](14)

在聚類過(guò)程中，式(11)可以完全被式(14)取代，從而提高算法的抗噪能力，加強(qiáng)分割的準(zhǔn)確性。下面將通過(guò)一些實(shí)驗(yàn)來(lái)檢驗(yàn)算法的功能。

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

在實(shí)驗(yàn)當(dāng)中，上面提到的一些公式參數(shù)取如下經(jīng)驗(yàn)值:η為0.01，θ為0.7，n0一般取40，ω取9。

圖2是原始圖片，圖3為原始算法運(yùn)行后的效果圖，圖4為改進(jìn)后的算法運(yùn)行效果圖。可以看到改進(jìn)后，在處理一些無(wú)噪聲的圖片時(shí)算法不輸給原算法。現(xiàn)對(duì)兩幅圖均加入一定的噪聲（斑點(diǎn)噪聲）再運(yùn)行，可以有圖5~7的結(jié)果。

其中，圖5為加了噪聲的原始圖，圖6為原算法運(yùn)行效果圖，圖7為改進(jìn)后算法運(yùn)行效果圖。可以看到算法改進(jìn)后，在抗噪性能上有很大的提高。



在圖8~10中，均加入了一定的高斯噪聲。其中，圖8為原圖，圖9為原算法處理后的圖片，圖10為改進(jìn)后算法處理的圖片。

通過(guò)實(shí)驗(yàn)圖片看到，對(duì)于一些沒(méi)有噪聲或者噪聲很少的圖片，改進(jìn)后的算法在分割效果上并沒(méi)有顯著的退步，仍然能夠很好地達(dá)到要求。而對(duì)于那些含有噪聲的圖片來(lái)說(shuō)，改進(jìn)算法分割的優(yōu)越性就顯得尤為顯著，充分證實(shí)了算法在抗噪方面的能力。 當(dāng)然，修改后的算法并不能保證對(duì)不含噪聲的圖片一定比原算法產(chǎn)生更好的分割效果，對(duì)于一些結(jié)構(gòu)特殊的圖片，修改后的算法在分割效果上可能產(chǎn)生倒退。因此如何保持算法原有的分割效果，值得進(jìn)一步研究。

參考文獻(xiàn)：

[1]BARADEZ M O， McGUCKIN C P，F(xiàn)ORRAZ N，et al. Robust and automated unimodal histogram thresholding and potential applications[J].Pattern Recognition，2004，37（4）：1131-1148.

[2]ZENG Xiang-yan，CHEN Y W， NAKAO Z， et al. Texture representation based on pattern map[J]. Signal Process，2004，84(3):589-599.

[3]CHANTAL R，MICHEL J. A new minimum variance region growing algorithm for image segmentation[J].Pattern Recognition Letters，1997，18(3):249-258.

[4]HEATH M， SARKAR S， SANOCKI T， et al. Comparison of edge detectors:a methodology and initial study[J]. Comput Vision Image Understanding，1998，69(1):38-54.

[5]CINQUE L， FORESTI G， LOMBARDI L. A clustering fuzzy approach for image segmentation[J]. Pattern Recognition， 2004，37(9):1797-1807.

[6]XIA Yong，F(xiàn)ENG Da-gan， WANG Tian-jiao，et al. Image segmentation by clustering of spatial patterns[J]. Pattern Recognition Letters，2007，28(12):1548-1555.

[7]HOPPNER F， KLAWONN F. Improved fuzzy partitions for fuzzy regression models[J].International Journal of Approximate Reasoning，2003，32(2-3):85-102.

[8]ZHANG Yang， CHUNG Fu-lai， WANG Shi-tong. Robust fuzzy clustering-based image segmentation[J]. Applied Soft Computing，2009，9(1):80-84.