趙 鳳劉漢強(qiáng)范九倫

①(西安郵電大學(xué)通信與信息工程學(xué)院 西安 710061)

②(陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院 西安 710062)

基于互補(bǔ)空間信息的多目標(biāo)進(jìn)化聚類圖像分割

趙 鳳*①劉漢強(qiáng)②范九倫①

①(西安郵電大學(xué)通信與信息工程學(xué)院 西安 710061)

②(陜西師范大學(xué)計算機(jī)科學(xué)學(xué)院 西安 710062)

現(xiàn)有的多目標(biāo)進(jìn)化聚類算法應(yīng)用于圖像分割時，沒有考慮圖像的任何空間信息，使得該類算法在含噪圖像上的分割性能不理想。該文鑒于圖像的局部空間信息和非局部空間信息的互補(bǔ)性，試圖將這兩種空間信息同時引入到聚類有效性函數(shù)中，構(gòu)造了融合互補(bǔ)空間信息的目標(biāo)函數(shù)，進(jìn)而提出了應(yīng)用于圖像分割的基于互補(bǔ)空間信息的多目標(biāo)進(jìn)化聚類算法。該算法采用染色體可變長編碼策略在進(jìn)化過程中自動確定圖像分割數(shù)目，減少了人為干預(yù)。自然圖像的分割實驗表明，該算法不但能在含噪圖像上取得較為滿意的分割性能，而且適用于多種類型的含噪圖像。

圖像分割；多目標(biāo)進(jìn)化聚類；互補(bǔ)空間信息；局部空間信息

1 引言

在過去的幾十年中，學(xué)者們提出了很多圖像分割方法，主要包括閾值的方法[1,2]、聚類的方法[3,4]、區(qū)域的方法[5,6]等等。其中，基于聚類的圖像分割方法至今仍是國內(nèi)外研究的一個熱點?；诰垲惖膱D像分割算法一般是根據(jù)某一個聚類準(zhǔn)則來判別圖像中像素的歸屬，并將具有一致或相似屬性的像素聚為一類，因此獲得的圖像分割結(jié)果是在該準(zhǔn)則下最優(yōu)的或接近最優(yōu)的?；谶@一思想的經(jīng)典聚類算法包括K-均值聚類算法(HCM)和模糊c-均值聚類算法(FCM)等，該類算法簡單、快速而且有效，易被廣泛應(yīng)用于多個領(lǐng)域。然而這類方法也存在一些缺陷，例如對初始化條件比較敏感；容易陷入局部最優(yōu)；聚類數(shù)目需要人為指定等。此外，這類算法還具有對噪聲敏感和只適應(yīng)于發(fā)現(xiàn)球型聚類等局限性。

不同的聚類準(zhǔn)則函數(shù)具有不同的特性，可以滿足人們的不同需求。在實際應(yīng)用中，我們往往需要從多個角度來考慮圖像分割問題，也就是要在多個聚類準(zhǔn)則下取得一個均衡的結(jié)果。從數(shù)學(xué)的角度看，就是將圖像分割問題轉(zhuǎn)換為對多個目標(biāo)函數(shù)的最優(yōu)化問題。進(jìn)化算法作為一種群體智能搜索方法十分適合用來求解多目標(biāo)優(yōu)化問題。近年來，將基于多目標(biāo)進(jìn)化的聚類算法(多目標(biāo)進(jìn)化聚類)應(yīng)用于圖像分割問題已經(jīng)成為一個新的研究熱點[7,8]。該類算法可以同時優(yōu)化多個目標(biāo)函數(shù)，使得算法獲得的分割結(jié)果更能符合人們的預(yù)期。與基于單一聚類準(zhǔn)則的聚類算法相比，這類算法幾乎不再對初始化敏感且不易陷入局部最優(yōu)，此外，該類算法通過選取適當(dāng)?shù)娜旧w編碼策略和目標(biāo)函數(shù)可以實現(xiàn)分割數(shù)目的自動確定，減少了人為干預(yù)。

多目標(biāo)進(jìn)化聚類算法最初的工作是圍繞硬聚類算法展開的[9,10]。隨后，文獻(xiàn)[11]于2006年在模糊聚類算法的框架下，同時優(yōu)化總體偏差和連通性函數(shù)這兩個目標(biāo)函數(shù)。由于該算法是在模糊聚類算法的框架下提出的，因此可以處理重疊和含噪數(shù)據(jù)的聚類問題，例如圖像分割問題。同樣在模糊聚類的框架下，文獻(xiàn)[12,13]以FCM錯誤率函數(shù)Jm和Xie-Beni(XB)指數(shù)作為目標(biāo)函數(shù)也提出了相應(yīng)的多目標(biāo)進(jìn)化聚類算法。值得注意的是，這兩個聚類有效性函數(shù)不是完全獨立的。為此，文獻(xiàn)[14]在XB和Jm的基礎(chǔ)上引入PBM指標(biāo)[15]，同時優(yōu)化這3個聚類有效性函數(shù)，并通過對非支配解進(jìn)行集成獲得最終解。此外，2011年，文獻(xiàn)[16]采用模糊緊致性和模糊可分性這兩個完全獨立的模糊聚類有效性函數(shù)作為目標(biāo)函數(shù)進(jìn)行多目標(biāo)優(yōu)化，取得了不錯的聚類效果。這些多目標(biāo)進(jìn)化聚類算法已經(jīng)被成功應(yīng)用于圖像分割問題。

鑒于圖像是具有典型空間信息的數(shù)據(jù)，聚類算法用于圖像分割時，像素的空間信息對于像素聚類具有一定的指導(dǎo)作用。相關(guān)學(xué)者已經(jīng)把圖像的鄰域空間信息(又稱為局部空間信息)引入到模糊聚類算法[17,18]中，在一定程度上克服了噪聲對于圖像分割結(jié)果的影響。實際上，對于每一個像素而言，圖像中存在很多像素與它具有相似的鄰域結(jié)構(gòu)。與局部空間信息相比，利用和當(dāng)前像素具有相似鄰域結(jié)構(gòu)的像素來獲得空間信息顯然是更合理的，這種空間信息被稱之為非局部空間信息。我們在前期的工作[19,20]中已經(jīng)將圖像像素的非局部空間信息引入到模糊聚類算法中，該類算法不但可以克服圖像噪聲對于分割結(jié)果的影響，而且可以獲得更加準(zhǔn)確的圖像邊緣，獲得的分割效果要優(yōu)于結(jié)合局部空間信息的模糊聚類算法。然而，每種空間信息都有局限性。非局部空間信息是在加性噪聲模型下提取的，所以融合非局部空間信息的模糊聚類算法在被加性噪聲污染的圖像上能夠取得較好的分割效果，但在被椒鹽噪聲污染的圖像上的性能不是很理想。局部空間信息按照采用鄰域均值或鄰域中值又分為兩種，其中融合鄰域中值空間信息的模糊聚類算法能在被椒鹽噪聲污染的圖像上能夠取得較好的分割效果。然而，由于局部空間信息僅僅考慮了像素的局部鄰域，使得融合局部空間信息的模糊聚類算法在圖像邊緣保持上的性能不好。

現(xiàn)有的多目標(biāo)進(jìn)化聚類算法用于圖像分割時，采用的目標(biāo)函數(shù)都是模糊數(shù)學(xué)意義下的聚類有效性函數(shù)，并沒有考慮圖像的空間信息。鑒于局部空間信息和非局部空間信息的互補(bǔ)性，本文試圖將這兩種空間信息同時引入到模糊聚類有效性函數(shù)中，構(gòu)造了融合互補(bǔ)空間信息的目標(biāo)函數(shù)。然后基于該目標(biāo)函數(shù)，再結(jié)合其他的模糊聚類有效性函數(shù)構(gòu)成多個目標(biāo)函數(shù)，最后采用NSGA-II算法[21]作為多目標(biāo)框架來解決多個目標(biāo)函數(shù)的優(yōu)化問題，提出了應(yīng)用于圖像分割的多目標(biāo)進(jìn)化聚類算法。此外，為了減少人為干預(yù)，本文算法在進(jìn)化過程中采用染色體可變長編碼策略自動確定分割數(shù)目。實驗結(jié)果表明，本文算法不但可以克服傳統(tǒng)多目標(biāo)進(jìn)化聚類算法在含噪圖像上分割效果不理想的問題，而且適用于多種類型的含噪圖像。

2 基于互補(bǔ)空間信息的多目標(biāo)進(jìn)化聚類算法

2.1 染色體表示和種群初始化

本文算法對各個聚類中心進(jìn)行編碼，編碼方式采用十進(jìn)制編碼。如果一個染色體是由d維數(shù)據(jù)空間中的K個聚類中心所組成，那么該染色體的長度為d×K。例如，在3維數(shù)據(jù)空間中，染色體＜24.6 2.3 11.8 13.2 7.9 2.8 0.5 6.1 13.2＞表示3個聚類中心(24.6, 2.3, 11.8), (13.2, 7.9, 2.8)和(0.5, 6.1, 13.2)。

假設(shè)種群中的一個染色體i是由Ki個聚類中心組成，Ki=(rand( )mod(Kmax-1))+2，其中，rand( )是返回隨機(jī)整數(shù)的函數(shù)，Kmax是聚類數(shù)目的最大上界。因此，聚類的數(shù)目在2到Kmax之間取值。

2.2 適應(yīng)度函數(shù)計算

本文算法采用兩個適應(yīng)度函數(shù)，一個是融合空間信息的全局模糊緊致性函數(shù)Cs，另一個是模糊可分性函數(shù)S。假設(shè)X={x1,x2,…,xn}表示一幅具有n個像素的圖像，全局模糊緊致性函數(shù)Cs定義如下：

其中，δi和?i分別表示第i個像素的局部空間信息和非局部空間信息，β1和β2分別是控制這兩種空間信息作用的加權(quán)因子，v1, v2,…, vK是從給定染色體中抽取出來的K個聚類中心，uki表示第i個像素對第k類的隸屬度，采用式(2)計算：

在式(1)中，第i個像素的局部空間信息iδ是利用該像素的鄰域中值獲得的，即

其中，Si表示以第i個像素為中心的鄰域窗內(nèi)像素的集合。第i個像素的非局部空間信息i?采用式(4)計算：

其中，g(Ni)表示以第i個像素為中心、大小為s×s的相似窗Ni上的灰度向量，h是濾波程度參數(shù)，用來控制權(quán)值函數(shù)wij衰減程度，iz是歸一化常數(shù)，具體定義為從式(5)可以看出，在搜索窗內(nèi)，與第i個像素具有相似鄰域結(jié)構(gòu)的像素具有較大的權(quán)值。綜合式(4)和式(5)可以發(fā)現(xiàn)，第i個像素的非局部空間信息?i是對所有與其具有相似鄰域結(jié)構(gòu)的像素進(jìn)行加權(quán)平均獲得的。

模糊可分性函數(shù)S定義為

其中pqμ是聚類中心vq對于vp的隸屬程度，具體定義為

2.3 選擇、交叉和變異算子

選擇就是挑選染色體產(chǎn)生交配池的過程。本文采用擁擠二進(jìn)制錦標(biāo)賽選擇方法[21]產(chǎn)生染色體的交配池，需指出，該方法是由傳統(tǒng)的二進(jìn)制錦標(biāo)賽選擇方法與擁擠比較技術(shù)相結(jié)合得到的。

在染色體中，每個聚類中心都是不可分割的，所以交叉點只能位于兩個聚類中心之間。這里，以交叉概率pc對染色體進(jìn)行交叉操作[16]，并需要保證后代中聚類中心的數(shù)目至少為兩個。在本文中，如果一個后代染色體P的聚類數(shù)目大于Kmax，就采用K-均值聚類算法對染色體P的聚類中心進(jìn)行聚類，聚類數(shù)目是2到Kmax之間的一個隨機(jī)整數(shù)。

本文以變異概率pm對染色體進(jìn)行變異操作。如果要對某個染色體的第k個聚類中心vk進(jìn)行變異，那么vk的第p維的值將會變?yōu)関kp±10ξ，其中，ξ為一個[0, 1]上均勻分布的隨機(jī)數(shù)，‘+’或 ‘-’是等概率出現(xiàn)的。

2.4 精英策略

我們在前面已經(jīng)指出，本文采用NSGA-II算法作為多目標(biāo)框架來解決聚類問題。眾所周知，NSGA-II算法最具特色的部分就是它的精英操作。通過精英操作，父代和子代中的非支配解會遺傳到下一代種群中，因此，迄今為止發(fā)現(xiàn)的最優(yōu)解就會被保留下來。

2.5 最優(yōu)解的選擇

本文算法的最后一代將會獲得一個非支配解構(gòu)成的集合，從算法的角度來說，所有的非支配解都是同等重要的。然而，在實際應(yīng)用中，用戶往往只需要一個解。在文獻(xiàn)[7]中，作者采用聚類有效性指數(shù)I[22]從非支配解集合中選擇使得I值越大的解作為最終解。需要指出的是，由于聚類有效性指數(shù)I沒有考慮任何的圖像空間信息，所以它無法直接應(yīng)用于含噪圖像分割。為了解決這個問題，我們把局部空間信息和非局部空間信息同時引入到指數(shù)I中，提出融合互補(bǔ)空間信息的聚類有效性指數(shù)IS，用于從算法最終獲得的非支配解集合中選擇一個最優(yōu)解。指數(shù)IS定義為

其中，l=1，從式(10)可以發(fā)現(xiàn)，聚類有效性指數(shù)IS是由1/K, ES1/ESK和DSK3部分所構(gòu)成，其中，ES1對于給定的數(shù)據(jù)集來說是一個常數(shù)，ESK的定義為

式中隸屬度uki采用式(2)計算，iδ和i?分別表示第i個像素的局部空間信息和非局部空間信息，1β和2β分別是控制這兩種空間信息作用的加權(quán)因子。式(8)中DSK度量了所有可能的聚類對的最大可分性，其定義為

3 實驗結(jié)果與分析

3.1 實驗設(shè)置及說明

實驗中采用FCM，融合鄰域均值空間信息的模糊c-均值聚類算法(FCM-S1)[17]，融合鄰域中值空間信息的模糊c-均值聚類算法(FCM-S2)[17]，融合非局部空間信息的模糊c-均值聚類算法(FCM_NLS)[20]和多目標(biāo)可變長遺傳模糊聚類算法(MOVGA)[16]作為對比算法。鑒于這些算法都是聚類算法，采用聚類準(zhǔn)確率(CA)[23]作為算法分割性能的評價指標(biāo)。對各算法涉及的參數(shù)作如下說明：所有算法的模糊指數(shù)m=2；FCM, FCM-S1, FCM-S2和FCM-NLS算法的最大迭代次數(shù)T和算法結(jié)束閾值ε分別設(shè)置為300和10-5，本文算法和MOVGA算法的最大代數(shù)和種群規(guī)模分別設(shè)置為100和50，交叉和變異概率分別設(shè)置為0.9和0.1; FCM-S1, FCM-S2和 FCM-NLS算法的加權(quán)因子β設(shè)置為6；FCM-S1，F(xiàn)CM-S2和本文算法提取鄰域空間信息的鄰域窗大小設(shè)置為3×3, FCM-NLS和本文算法提取非局部空間信息的參數(shù)r, s和h分別設(shè)置為21, 7和30。需要指出的是，本文算法和MOVGA算法能自動確定聚類數(shù)目，其他算法的聚類數(shù)目是按照圖像的人工分割結(jié)果預(yù)先給定的。在實驗中，聚類數(shù)目的最大上界Kmax取值為10。

3.2 加權(quán)因子β1和β2的討論

從式(1)和式(11)可以看出，加權(quán)因子1β和2β控制了兩種空間信息作用的大小。直觀看來，1β取值大一點，會使得鄰域中值空間信息發(fā)揮較大的作用，從而使得算法對于被椒鹽噪聲污染的圖像的分割效果要好一些；2β取值大一點，會使得非局部空間信息發(fā)揮較大的作用，從而使得算法對于被高斯噪聲污染的圖像的分割效果要好一些。圖1(a)給出了一幅人工合成圖像，我們分別在這幅圖像上添加高斯噪聲((0, 0.02))、椒鹽噪聲((0, 0.03))以及由高斯和椒鹽混合而成的噪聲(高斯(0, 0.01) &椒鹽(0, 0.01))，噪聲圖像見圖1(b)～圖1(d)，試圖在不同類型的含噪圖像上考察1β和2β的取值策略。實驗中，我們在集合[0.5, 1, 1.5, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]上測試1β和2β，圖2給出了本文算法的聚類準(zhǔn)確率隨這兩個參數(shù)變化的曲面，其中，圖2(a)～圖2(c)分別為在高斯含噪圖像、椒鹽含噪圖像和混合含噪圖像上的性能曲面。從圖2(a)可以發(fā)現(xiàn)，對于高斯含噪圖像，當(dāng)2β取值比較大時，算法性能較好，此時1β的取值對算法性能影響不大；從圖2(b)中的曲面可以看出，對于椒鹽含噪圖像，當(dāng)1β取值比較大且2β的取值比較小時，算法性能較好；從圖2 (c)可以發(fā)現(xiàn)，對于混合含噪圖像，當(dāng)1β和2β取值都比較大時，算法性能較好。

3.3 Berkeley圖像對比實驗

本節(jié)采用多幅來自于Berkeley圖像庫的圖像進(jìn)行分割實驗。為了驗證本文算法及其對比算法對于不同類型含噪圖像的分割性能，我們在這些圖像上分別添加高斯噪聲、椒鹽噪聲以及由高斯和椒鹽混合而成的噪聲，表1給出了各個算法在含噪圖像上獲得的聚類準(zhǔn)確率。需要指出的是，根據(jù)3.2節(jié)給出的本文算法加權(quán)因子1β和2β的取值建議，對于高斯含噪圖像，這里我們把1β和2β分別賦值為6和16；對于椒鹽含噪圖像，1β和2β分別賦值為16和1；對于混合含噪圖像，1β和2β分別賦值為16和16。從表1可以看出，考慮了空間信息的各算法的分割性能一般都要優(yōu)于沒有考慮空間信息的算法，本文算法在絕大多數(shù)情況下的分割性能都是所有算法中最好的，適用于多種類型的含噪圖像。需指出，MOVGA算法的分割性能在多數(shù)情況下都不理想，這是因為該算法沒有利用任何的圖像空間信息，從而造成進(jìn)化獲得的分割數(shù)目不正確，這一點可以從下面將要展示的視覺分割結(jié)果中得到驗證。

圖1 人工合成圖像及其噪聲圖像

圖2 算法聚類準(zhǔn)確率隨1β和2β變化的曲面

表1 各個算法的性能比較

下面以一幅Berkeley圖像(#238011)為例展示一下本文算法及其對比算法的視覺分割效果。#238011圖像及其標(biāo)準(zhǔn)人工分割結(jié)果見圖3(a)和圖3(b)，該幅圖像的高斯、椒鹽以及由高斯和椒鹽混合而成的噪聲圖像分別如圖3(c)～圖3(e)所示。

圖3 #238011圖像

對于#238011圖像，圖4給出了本文算法及其對比算法在其高斯含噪圖像上的分割結(jié)果，圖5給出了這些算法在其椒鹽含噪圖像上的分割結(jié)果，圖6給出了這些算法在其混合含噪圖像上的分割結(jié)果。從結(jié)果可以看出，對于高斯和混合含噪圖像，本文算法獲得的視覺效果比較理想，獲得的分割圖像中含有較少的錯誤分割點，其它算法的視覺效果均不理想；對于椒鹽含噪圖像，本文算法獲得的視覺效果要明顯優(yōu)于其它算法，雖然MOVGA算法獲得了正確的分割數(shù)目，但是結(jié)果中仍殘留了大量的錯誤分割點。

圖4 #238011圖像的高斯含噪圖像的分割結(jié)果

圖5 #238011圖像的椒鹽含噪圖像的分割結(jié)果

圖6 #238011圖像的混合含噪圖像的分割結(jié)果

4 結(jié)束語

為了解決多目標(biāo)進(jìn)化聚類算法用于含噪圖像分割時性能不理想的問題，本文基于圖像的局部空間信息和非局部空間信息的互補(bǔ)性，同時將這兩種空間信息引入到模糊聚類有效性函數(shù)中，構(gòu)造了融合互補(bǔ)空間信息的目標(biāo)函數(shù)，提出了基于互補(bǔ)空間信息的多目標(biāo)進(jìn)化聚類圖像分割算法。圖像分割實驗表明，該算法能在含噪圖像上取得較為令人滿意的分割性能，而且適用于多種類型的含噪圖像。

本文算法需要給定控制互補(bǔ)的兩種空間信息作用的加權(quán)因子β1和β2。我們在實驗中考察了β1和β2的取值，討論了對于不同類型的含噪圖像這兩個參數(shù)的取值策略。需指出，如果能夠利用噪聲圖像的特點，自適應(yīng)地確定β1和β2將是一個有意義的研究內(nèi)容，我們會在未來開展這一工作。

[1] Dirami A, Hammouche K, Diaf M, et al.. Fast multilevel thresholding for image segmentation through a multiphase level set method[J]. Signal Processing, 2013, 93(1): 139-153.

[2] 范朝冬, 歐陽紅林, 張英杰. 基于小概率策略的Otsu圖像分割方法[J]. 電子與信息學(xué)報, 2013, 35(9): 2081-2087.

Fan Chao-dong, Ouyang Hong-lin, and Zhang Ying-jie. Small probability strategy based Otsu thresholding method for image segmentation[J]. Journal of Electronics & Information Technology, 2013, 35(9): 2081-2087.

[3] Gong Mao-guo, Liang Yan, Shi Jiao, et al.. Fuzzy c-means clustering with local information and kernel metric for image segmentation[J]. IEEE Transactions on Image Processing, 2013, 22(2): 573-584.

[4] Caldairoua B, Passata N, Habas P A, et al.. A non-local fuzzy segmentation method: application to brain MRI[J]. Pattern Recognition, 2011, 44(9): 1916-1927.

[5] Tarabalka Y, Chanussot J, and Benediktsson J A. Segmentation and classification of hyperspectral images using watershed transformation[J]. Pattern Recognition, 2010, 43(7): 2367-2379.

[6] 黃志堅, 黎湘, 徐帆江. 基于視覺復(fù)雜度的自適應(yīng)尺度遙感影像分割[J]. 電子與信息學(xué)報, 2013, 35(8): 1786-1792.

Huang Zhi-jian, Li Xiang, and Xu Fan-jiang. An adaptive scale segmentation for remote sensing image based-on visual complexity[J]. Journal of Electronics & Information Technology, 2013, 35(8): 1786-1792.

[7] Wei B C and Mandava R. Multiobjective optimization approaches in image segmentation–the directions and challenges[J]. International Journal of Advances in Soft Computing and Its Applications, 2010, 2(1): 40-65.

[8] Ooi W S and Lim C P. Multi-objective image segmentation with an interactive evolutionary computation approach[J]. Journal of Intelligent and Fuzzy Systems, 2013, 24(2): 239-249.

[9] Bandyopadhyay S and Maulik U. An evolutionary technique based on k-means algorithm for optimal clustering in RN[J]. Information Sciences, 2002, 146(1/2/3/4): 221-237.

[10] Caballero R, Laguna M, Marti R, et al.. Multiobjective clustering with metaheuristic optimization technology[R]. Technical Report of Leeds School of Business in the University of Colorado at Boulder, 2006.

[11] Handl J and Knowles J. An evolutionary approach to multiobjective clustering[J]. IEEE Transactions on Evolutionary Computation, 2006, 11(1): 56-76.

[12] Bandyopadhyay S, Maulik U, and Mukhopadhyay A. Multiobjective genetic clustering for pixel classification in remote sensing imagery[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(5): 1506-1511.

[13] Mukhopadhyay A, Bandyopadhyay S, and Maulik U. Clustering using multiobjective genetic algorithm and its application to image segmentation[C]. Proceedings of the International Conference on IEEE Systems, Man and Cybernetics, Taibei, 2006: 2678-2683.

[14] Mukhopadhyay A, Maulik U, and Bandyopadhyay S. Multiobjective genetic clustering with ensemble among Pareto front solutions: application to MRI brain image segmentation[C]. Proceedings of the International Conference on Advances in Pattern Recognition, Kolkata, India, 2009: 236-239.

[15] Pakhira M, Bandyopadhyay S, and Maulik U. Validity index for crisp and fuzzy clusters[J]. Pattern Recognition, 2004, 37(3): 487-501.

[16] Mukhopadhyay A and Maulik U. A multiobjective approach to MR brain image segmentation[J]. Applied Soft Computing, 2011, 11(1): 872-880.

[17] Chen S C and Zhang D Q. Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure[J]. IEEE Transactions on System, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(4): 1907-1916.

[18] Cai W L, Chen S C, and Zhang D Q. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J]. Pattern Recognition, 2007, 40(7): 825-838.

[19] Zhao F, Jiao L C, Liu H Q, et al.. A novel fuzzy clustering algorithm with non local adaptive spatial constraint for image segmentation[J]. Signal Processing, 2011, 91(4): 988-999.

[20] Zhao F, Jiao L C, and Liu H Q. Fuzzy c-means clustering with non local spatial information for noisy image segmentation[J]. Frontiers of Computer Science in China, 2011, 5(1): 45-56.

[21] Deb K, Agrawal S, Pratab A, et al.. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]. Proceedings of the Parallel Problem Solving from Nature VI Conference, Springer, Lecture Notes in Computer Science No.1917, Paris, France, 2000: 849-858.

[22] Maulik U and Bandyopadhyay S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12): 1650-1654.

[23] Wu M and Sch?lkopf B. A local learning approach for clustering[C]. Advances in Neural Information Processing Systems, Vancouver B.C., Canada, 2007: 1529-1536.

趙 鳳： 女，1980年生，副教授，研究方向為模式識別、圖像處理、模糊信息處理.

劉漢強(qiáng)： 男，1981年生，講師，研究方向為模式識別、圖像處理.

范九倫： 男，1964年生，教授，研究方向為模糊集理論、模式識別、信息安全.

Multi-objective Evolutionary Clustering with Complementary Spatial Information for Image Segmentation

Zhao Feng①Liu Han-qiang②Fan Jiu-lun①

①(School of Telecommunications and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710061, China)
②(School of Computer Science, Shaanxi Normal University, Xi’an 710062, China)

When existing multi-objective evolutionary clustering algorithms is applied to image segmentation, it can not obtain satisfactory segmentation performance on an image corrupted by noise due to no consideration of any spatial information derived from the image. Based on the complementarity of the local spatial information and the non local spatial information of the image, these two kinds of spatial information are introduced into a cluster validity function, and a novel objective function with complementary spatial information is constructed, and then a multi-objective evolutionary clustering algorithm with complementary spatial information for image segmentation is proposed. In order to reduce human intervention, the variable string length real coded technique is adopted to determine automatically the number of clusters during the evolving process. Natural image segmentation experiments show that the proposed method not only can obtain satisfactory segmentation performance on noisy images, but also can be suitable for many types of noisy images.

Image segmentation; Multi-objective evolutionary clustering; Complementary spatial information; Local spatial information

TP751

A

1009-5896(2015)03-0672-07

10.11999/JEIT140371

2014-03-19收到，2014-07-18改回

國家自然科學(xué)基金(61102095, 61202153, 61340040)，陜西省科技計劃(2014KJXX-72)和陜西省自然科學(xué)基礎(chǔ)研究計劃(2012JQ8045, 2014JQ8336, 2014JM8307, 2013JM3081) 資助課題

*通信作者：趙鳳 fzhao.xupt@gmail.com