基于互補空間信息的多目標進化聚類圖像分割

趙 鳳劉漢強范九倫

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

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

基于互補空間信息的多目標進化聚類圖像分割

趙 鳳*①劉漢強②范九倫①

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

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

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

圖像分割；多目標進化聚類；互補空間信息；局部空間信息

1 引言

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

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

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

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

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

2 基于互補空間信息的多目標進化聚類算法

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

本文算法對各個聚類中心進行編碼，編碼方式采用十進制編碼。如果一個染色體是由d維數據空間中的K個聚類中心所組成，那么該染色體的長度為d×K。例如，在3維數據空間中，染色體＜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)。

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

2.2 適應度函數計算

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

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

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

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

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

模糊可分性函數S定義為

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

2.3 選擇、交叉和變異算子

選擇就是挑選染色體產生交配池的過程。本文采用擁擠二進制錦標賽選擇方法[21]產生染色體的交配池，需指出，該方法是由傳統的二進制錦標賽選擇方法與擁擠比較技術相結合得到的。

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

本文以變異概率pm對染色體進行變異操作。如果要對某個染色體的第k個聚類中心vk進行變異，那么vk的第p維的值將會變為vkp±10ξ，其中，ξ為一個[0, 1]上均勻分布的隨機數，‘+’或 ‘-’是等概率出現的。

2.4 精英策略

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

2.5 最優解的選擇

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

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

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

3 實驗結果與分析

3.1 實驗設置及說明

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

3.2 加權因子β1和β2的討論

從式(1)和式(11)可以看出，加權因子1β和2β控制了兩種空間信息作用的大小。直觀看來，1β取值大一點，會使得鄰域中值空間信息發揮較大的作用，從而使得算法對于被椒鹽噪聲污染的圖像的分割效果要好一些；2β取值大一點，會使得非局部空間信息發揮較大的作用，從而使得算法對于被高斯噪聲污染的圖像的分割效果要好一些。圖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給出了本文算法的聚類準確率隨這兩個參數變化的曲面，其中，圖2(a)～圖2(c)分別為在高斯含噪圖像、椒鹽含噪圖像和混合含噪圖像上的性能曲面。從圖2(a)可以發現，對于高斯含噪圖像，當2β取值比較大時，算法性能較好，此時1β的取值對算法性能影響不大；從圖2(b)中的曲面可以看出，對于椒鹽含噪圖像，當1β取值比較大且2β的取值比較小時，算法性能較好；從圖2 (c)可以發現，對于混合含噪圖像，當1β和2β取值都比較大時，算法性能較好。

3.3 Berkeley圖像對比實驗

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

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

圖2 算法聚類準確率隨1β和2β變化的曲面

表1 各個算法的性能比較

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

圖3 #238011圖像

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

圖4 #238011圖像的高斯含噪圖像的分割結果

圖5 #238011圖像的椒鹽含噪圖像的分割結果

圖6 #238011圖像的混合含噪圖像的分割結果

4 結束語

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

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

[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]. 電子與信息學報, 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] 黃志堅, 黎湘, 徐帆江. 基于視覺復雜度的自適應尺度遙感影像分割[J]. 電子與信息學報, 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年生，副教授，研究方向為模式識別、圖像處理、模糊信息處理.

劉漢強： 男，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改回

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

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