聶 敏, 劉鵬飛, 吳成茂, 劉曉慧

(1. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121; 2. 西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121)

雙邊加權(quán)直方圖模糊C-均值聚類分割算法

聶 敏1, 劉鵬飛2, 吳成茂2, 劉曉慧2

(1. 西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121; 2. 西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121)

針對小目標(biāo)圖像分割的問題，提出一種雙邊加權(quán)直方圖模糊C-均值聚類分割算法。該算法將樣本信息和幾何結(jié)構(gòu)信息作為權(quán)值，對傳統(tǒng)模糊C-均值聚類分割算法進(jìn)行雙邊加權(quán)。并對加權(quán)聚類分割目標(biāo)函數(shù)進(jìn)行最優(yōu)化推導(dǎo)，獲得迭代求解的隸屬度、聚類中心和聚類幾何信息權(quán)表達(dá)式。對比實驗表明，該分割算法能得到較好的分割效果。

圖像分割；模糊C-均值聚類；樣本加權(quán)；結(jié)構(gòu)加權(quán)；分割精度

遙感圖像中地物對象的分割是遙感圖像理解地物識別的基礎(chǔ)，其分割的關(guān)鍵在于獲取符合地物內(nèi)在尺度的分割。目前，針對小目標(biāo)研究方面，基于馬爾科夫隨機(jī)場[1]、閾值分割[2]、局部均值[3]等分割方法都是針對紅外小目標(biāo)圖像所提出的。由于衛(wèi)星遙感圖像與紅外圖像存在較大差異，如遙感圖像信息量大、邊界模糊、灰度值集中等特點(diǎn)，導(dǎo)致現(xiàn)有紅外小目標(biāo)檢測方法并不完全適合衛(wèi)星遙感小目標(biāo)提取的問題[4-5]。因此，小目標(biāo)遙感圖像分割，已成為遙感圖像理解地物識別的瓶頸。

考慮到衛(wèi)星遙感地物圖像本身具有模糊性，將模糊技術(shù)方法引入遙感圖像分割[6-12]，其中基于目標(biāo)函數(shù)的非監(jiān)督模糊聚類方法[6-7]成為了主要關(guān)注點(diǎn)。模糊C-均值聚類(Fuzzy C-means Clustering, FCM)算法[6]就是一種典型的模糊聚類算法。由于傳統(tǒng)FCM算法本身存在對數(shù)據(jù)集等劃分趨勢的不足。因此，需通過加權(quán)模糊C-均值聚類方法進(jìn)行改進(jìn)，其方式主要包括樣本加權(quán)模糊C-均值聚類和屬性加權(quán)模糊C-均值聚類兩大類，其中樣本加權(quán)包括樣本疏密程度信息加權(quán)[8-10]和聚類幾何結(jié)構(gòu)偏差信息加權(quán)[11-12]。由于樣本疏密程度加權(quán)不能反映聚類幾何結(jié)構(gòu)信息，容易產(chǎn)生誤分割現(xiàn)象，而利用聚類幾何結(jié)構(gòu)偏差信息加權(quán)，只能對于聚類中心調(diào)整，不能按照樣本原有信息自適應(yīng)調(diào)整，導(dǎo)致聚類速度較慢，因此文獻(xiàn)[13]將兩種加權(quán)方式結(jié)合，提出了一種抗噪性強(qiáng)的雙邊加權(quán)模糊C-均值聚類算法，改善了聚類結(jié)果。如何將上述這種加權(quán)思想應(yīng)用于遙感圖像處理領(lǐng)域[14-17]成為了解決遙感圖像分割的關(guān)鍵。文獻(xiàn)[14]通過在目標(biāo)函數(shù)中添加空間信息權(quán)使聚類更加合理，提高分割算法的魯棒性；文獻(xiàn)[15]將每個像素點(diǎn)的空間鄰域信息考慮在內(nèi)對傳統(tǒng)FCM算法進(jìn)行加權(quán)處理，用以提高分割算法的抗噪性，在遙感圖像處理方面得到了較理想的應(yīng)用[16-17]。但是，由于單一的樣本信息或者聚類集合結(jié)構(gòu)信息都不能很好的反映聚類分布情況，尤其是在處理目標(biāo)和背景相差懸殊的遙感圖像處理時，不能達(dá)到理想的分割結(jié)果。因此，本文將樣本信息加權(quán)和聚類幾何結(jié)構(gòu)信息權(quán)相結(jié)合的FCM聚類算法用于遙感圖像分割。由于圖像分割的本質(zhì)是不同像素的聚類問題，可將其轉(zhuǎn)化為直方圖上不同灰度級的聚類問題，其中不同灰度級樣本信息權(quán)源于該灰度級在圖像中所出現(xiàn)的頻次，而聚類幾何結(jié)構(gòu)信息權(quán)利用灰度級與不同聚類中心之間的偏差信息確定，這兩種權(quán)值的合理選取保證了本算法能夠在目標(biāo)和背景所占圖像比例相差懸殊的遙感圖像中準(zhǔn)確地提取出目標(biāo)。

1 模糊C-均值聚類

1.1 經(jīng)典FCM方法

給定大小為N的樣本集

X={x1,x2,…,xN}，

假定將其劃分為c類，且2≤c

(1)

其中uki約束條件為

(ⅰ) 0≤uki≤1 (1≤i≤N,1≤k≤c);

隸屬度矩陣和聚類中心矩陣分別表示為

U=(uki)c×N,V=(vk)c×1,

利用拉格朗日乘子法可獲得該優(yōu)化問題的迭代逼近最優(yōu)解所對應(yīng)的隸屬度uki和聚類中心vk表達(dá)式[6]為

(2)

(3)

根據(jù)上述式(2)和式(3)可構(gòu)造FCM聚類算法對數(shù)據(jù)集聚類，并通過最大隸屬度準(zhǔn)則實現(xiàn)樣本的分類。

1.2 加權(quán)FCM方法

針對傳統(tǒng)FCM聚類主要適合類內(nèi)樣本相差不懸殊且呈團(tuán)狀數(shù)據(jù)的分類，樣本加權(quán)FCM聚類算法[10]就是通過在FCM算法基礎(chǔ)上添加樣本權(quán)的方式改善這種等趨勢劃分的不足，其目標(biāo)函數(shù)為

(4)

其中權(quán)值pi是根據(jù)樣本之間的疏密程度確定的，且權(quán)系數(shù)pi滿足的約束條件為

(5)

選取該樣本權(quán)的典型方法為

(6)

一般而言，選取α=2.0。

針對傳統(tǒng)FCM聚類未充分利用數(shù)據(jù)聚類時所對應(yīng)的聚類幾何結(jié)構(gòu)信息，而導(dǎo)致的抗噪性差的問題,正則化加權(quán)FCM算法[12](Sample - Weighted Fuzzy Clustering with regularizations, SW-GFCR)就是通過引入聚類幾何結(jié)構(gòu)信息權(quán)以增強(qiáng)算法的抗噪性，其聚類目標(biāo)函數(shù)為

(7)

其中權(quán)系數(shù)wi滿足約束條件為

(8)

該種權(quán)wi與聚類結(jié)構(gòu)緊密相關(guān)，隨聚類迭代過程而發(fā)生變化。這種正則化加權(quán)極大地提高聚類算法抗干擾能力，已被廣泛應(yīng)用于奇異數(shù)據(jù)的聚類分析和研究。

因此，雙邊加權(quán)FCM聚類算法[13]通過將這兩種加權(quán)方式進(jìn)行結(jié)合，從而使其在對奇異噪聲數(shù)據(jù)分類時，表現(xiàn)出良好的魯棒性和抗噪性，其聚類目標(biāo)函數(shù)為

(9)

其中權(quán)系數(shù)wi和pi分別滿足約束條件(8)和約束條件(5)。

通過拉格朗日乘子法計算出該聚類算法所對應(yīng)的權(quán)wi、隸屬度uki和聚類中心vk的迭代表達(dá)式為[13]

(10)

(11)

(12)

其中pi選取如式(6)。正則化參數(shù)ξ=σ2，σ2表示數(shù)據(jù)集中所有數(shù)據(jù)中離散度的統(tǒng)計量即方差。在數(shù)據(jù)集中可表示為

該雙邊加權(quán)FCM算法充分利用樣本分布特性和樣本聚類幾何結(jié)構(gòu)信息，對奇異噪聲數(shù)據(jù)表現(xiàn)出良好的魯棒性和抗噪性。因此，本文將這種雙邊加權(quán)的思想引入小目標(biāo)遙感圖像的分割處理中。

2 雙邊加權(quán)直方圖模糊C-均值聚類分割方法

假設(shè)大小為m1×n1的灰度圖像

G={g(x,y):1≤x≤m1,1≤y≤n1},

其中不同灰度級所出現(xiàn)次數(shù)記為h(i)(i=0,1,…,L-1)(L-1表示最大灰度級)。將FCM聚類應(yīng)用灰度圖像G進(jìn)行不同灰度級聚類時所對應(yīng)的目標(biāo)函數(shù)為

該聚類目標(biāo)函數(shù)等價的直方圖FCM聚類所對應(yīng)的目標(biāo)函數(shù)為

為了提高該直方圖聚類算法的有效性，將傳統(tǒng)樣本加權(quán)FCM推廣至直方圖模糊C-均值聚類，便獲得加權(quán)直方圖FCM聚類，其聚類目標(biāo)函數(shù)為

其中樣本權(quán)pi應(yīng)滿足約束條件為

為了進(jìn)一步提高樣本加權(quán)FCM聚類算法的魯棒性，將灰度級聚類幾何結(jié)構(gòu)權(quán)融入加權(quán)直方圖FCM聚類，便獲得如下聚類目標(biāo)函數(shù)

(13)

其中灰度級聚類幾何結(jié)構(gòu)權(quán)wi的約束條件為

針對直方圖上灰度級聚類的雙邊加權(quán)FCM聚類目標(biāo)函數(shù)式(13)，采用拉格朗日乘子法獲得幾何結(jié)構(gòu)權(quán)、隸屬度和聚類中心所對應(yīng)的迭代表達(dá)式

(14)

(15)

(16)

其中樣本權(quán)值pi是根據(jù)灰度圖像中各灰度級i出現(xiàn)的概率確定的，本文構(gòu)造樣本權(quán)的方式可表示為

正則化參數(shù)ξ=σ2，σ2表示圖像中所有灰度級的方差，即

將式(14)、式(15)和式(16)三式分別作為聚類幾何信息權(quán)wi、聚類中心vk和隸屬度uki迭代表達(dá)式，來構(gòu)造雙邊加權(quán)直方圖模糊C-均值聚類分割算法，其詳細(xì)步驟如下。

步驟1 目標(biāo)函數(shù)中參數(shù)的選取，包括最大迭代次數(shù)Tm、聚類因子m、聚類分類個數(shù)c、最大類中心誤差ε；

步驟2 對聚類中心vk和隸屬度uki用FCM算法進(jìn)行初始化；

步驟3 設(shè)置循環(huán)次數(shù)count=0；

步驟4 根據(jù)迭代表達(dá)式計算變權(quán)值wi、聚類中心vk和隸屬度uki；

步驟5 更新隸屬度矩陣U，聚類中心矩陣V和結(jié)構(gòu)信息權(quán)值矩陣W；

步驟6 若|Vnew-Vold|<ε或count≥Tm，則結(jié)束循環(huán)，根據(jù)最大隸屬度，分割圖像，并輸出分割結(jié)果。否則，設(shè)定count=count+1，然后返回步驟4重復(fù)操作。

針對該聚類算法中的聚類中心表達(dá)式(16)的探討如下。

(17)

其中參數(shù)ω選取值對分割效果具有較大影響。一般而言，常選取該值為0.001附近有利于分割需要。若過大或過小將導(dǎo)致分割效果難以令人滿意。

3 實驗及其結(jié)果分析

為了驗證算法的有效性，在Matlab 2010b平臺上測試，參數(shù)選取模糊因子m=2,分類個數(shù)c=2，迭代誤差ε=0.01,最大迭代次數(shù)Tm=500。對復(fù)雜遙感圖像進(jìn)行分割。

3.1 分割有效性測試

選取3幅不同的遙感圖像，如圖1所示，原圖像對應(yīng)灰度圖像的直方圖如圖2所示。分別用傳統(tǒng)FCM算法、樣本加權(quán)(SWFCM)算法[10]、正則化加權(quán)(SW-GFCR)算法[12]和本文算法4種算法進(jìn)行對比測試，實驗結(jié)果如圖3～圖5所示，其中參數(shù)ω選取為0.001。

(a) 河流

(b) 巴黎

(c) 洞庭湖

(a) 河流 (b) 巴黎 (c) 洞庭湖

圖2 灰度直方圖

圖3為河流遙感圖像的分割結(jié)果，原圖像屬于目標(biāo)背景不均勻的遙感圖像。由分割結(jié)果可以看出，在圖3(a)和圖3(c)中，不能有效地將目標(biāo)分割出來，圖3(b)中，能夠得到較為理想的分割效果。而在圖3(d)中，本文算法能夠有效地將目標(biāo)從背景中分割出來，輪廓清晰且噪聲較小。

(a) FCM算法(b) SWFCM算法 (c) SW-GFCR算法(d)本文算法

圖3 河流遙感圖像的分割結(jié)果

圖4為巴黎遙感圖像分割結(jié)果，原圖像是典型的小目標(biāo)遙感圖像。由分割結(jié)果可以看出，在圖4(a)、圖4(b)和圖4(c)中,目標(biāo)都沒有從背景中被分割出來，而在圖4(d)中，BWFCM算法能夠有效地將目標(biāo)從背景中分割出來。所以，本文算法在小目標(biāo)圖像分割時能獲得較理想的分割結(jié)果。

(a) FCM算法(b) SWFCM算法 (c) SW-GFCR算法(d)本文算法

圖4 巴黎遙感圖像的分割結(jié)果

(a) FCM算法(b) SWFCM算法 (c) SW-GFCR算法(d)本文算法

圖5 洞庭湖遙感圖像的分割結(jié)果

圖5為洞庭湖遙感圖像分割結(jié)果，原圖像為標(biāo)準(zhǔn)的遙感圖像。從分割結(jié)果中可以看出，采用4種聚類算法都能將目標(biāo)從背景中分離出來，但是通過比較分割效果表明本文算法具有較強(qiáng)的抗噪能力和魯棒性。

3.2 分割性能分析

為了測試算法的準(zhǔn)確率，給出3幅圖像進(jìn)行理想閾值分割結(jié)果，如圖6所示。

(a) 河流(b) 巴黎 (c) 洞庭湖

圖6 理想分割

假設(shè)圖像的大小為m1×n1，將理想分割圖像與不同算法分割圖像比較，計算二者之間相同位置處分割結(jié)果相同的像素個數(shù)并記為n，則獲得不同算法分割結(jié)果的準(zhǔn)確率η為

(18)

獲得FCM算法、SWFCM算法、SW-FCR算法、本文算法對河流圖像、巴黎遙感圖像、洞庭湖圖像分割結(jié)果的準(zhǔn)確率，詳細(xì)情況如表1所示。

表1 不同算法的準(zhǔn)確率

綜合圖1～圖5以及表1的數(shù)據(jù)可以看出，權(quán)值的選擇對聚類有很大的影響，不同權(quán)重可導(dǎo)致圖像分割效果存在顯著差異。

若只考慮樣本加權(quán)和正則化加權(quán)的一種權(quán)值對圖像進(jìn)行分割的時不具有普適性,將兩種權(quán)值都考慮在內(nèi)時，本文算法不論是在處理一般圖像，還是小目標(biāo)圖像上都能達(dá)到較好的分割效果。綜上所述可以表明，本文算法對遙感圖像的分割是有效的。

3.3 分割時間復(fù)雜性分析

算法的時間復(fù)雜度可以用迭代次數(shù)和運(yùn)行來衡量，用4種算法對每個圖像各運(yùn)行50次取平均值作為實驗結(jié)果，如表2所示。

表2 對不同圖像不同算法的時間復(fù)雜度

通過對表2中的數(shù)據(jù)進(jìn)行對比可知，本文算法、傳統(tǒng)FCM算法和SWFCM算法的時間復(fù)雜度相當(dāng)，然而由于SW-GFCR算法收斂速度慢，導(dǎo)致分割時間開銷相對較多，不利于實時場合廣泛應(yīng)用。

然而，本文算法不僅利用了樣本加權(quán)，而且也考慮聚類幾何結(jié)構(gòu)權(quán)，由于兩種權(quán)相結(jié)合的方式改善了聚類算法的收斂速度，極大地降低算法的時間開銷。

3.4 參數(shù)敏感性測試

為了驗證本文算法中參數(shù)選取的問題，將式(16)中參數(shù)ω選取不同值時對分割效果的影響進(jìn)行了測試，其詳細(xì)情況如表3所示。

從表3所示的測試結(jié)果來看，參數(shù)ω的不同導(dǎo)致分割效果有較大差異。與文中的分析相符。一般而言，選取參數(shù)ω為0.001就能獲得滿意的分割效果，如圖3～圖5中的子圖(d)所示。

表3 參數(shù)ω對分割效果的影響

4 結(jié)束語

將樣本權(quán)和聚類幾何結(jié)構(gòu)權(quán)相結(jié)合引入傳統(tǒng)模糊C-均值聚類，用以改善聚類分割算法，以提高聚類算法的普適性。通過直觀判斷、準(zhǔn)確度分析和時間復(fù)雜度分析3方面的分析結(jié)果表明，雙邊加權(quán)直方圖模糊C-均值聚類分割算法與現(xiàn)有的加權(quán)聚類分割算法相比，有更好的分割性能，并且具有更好的普適性。

[1] Wang Peng, Tian Jinwen, Gao chenqiang. Infrared small target detection using directional highpass filters based on LS-SVM[J]. Electronics letters, 2009, 45(3): 156-158.

[2] 吳一全, 吳加明, 占必超. 一種可有效分割小目標(biāo)圖像的閾值選取方法[J]. 兵工學(xué)報, 2011, 32(4): 469-475.

[3] 劉運(yùn)龍, 薛雨麗, 袁素真, 等. 基于局部均值的紅外小目標(biāo)檢測算法[J]. 紅外與激光工程, 2013, 42(3): 814-822.

[4] Bai Xiangzhi, Zhou Fugen. Analysis of new top-hat transformation and the application for infrared dim small target detection[J]. Pattern Recognition, 2010, 43(6): 2145-2156.

[5] Wang L, Yung N H C. Extraction of moving objects from their background based on multiple adaptive thresholds and boundary evaluation[J]. IEEE Transactions on Intelligent Transportation Systems, 2010, 11(1): 40-51.

[6] Bezdek J C. Pattern recognition with fuzzy objective function algorithms[M]. Kluwer Academic Publishers, 1981:145-154.

[7] 支曉斌, 許朝暉. 改進(jìn)型特征權(quán)重自調(diào)節(jié) K-均值聚類算法[J]. 西安郵電大學(xué)學(xué)報, 2014, 19(6): 26-31.

[8] 李琳, 范九倫, 趙鳳. 模糊 C-均值聚類圖像分割算法的一種改進(jìn)[J]. 西安郵電大學(xué)學(xué)報, 2014, 19(5): 56-60.

[9] 李金秀, 高新波, 高玉娥, 等. 基于特征加權(quán)的模糊聚類算法研究[J]. 北京電子科技學(xué)院學(xué)報, 2007, 15(2): 74-76.

[10] 范九倫. 模糊聚類新算法與聚類有效性問題研究[D]. 西安：西安電子科技大學(xué), 1998: 40-52.

[11] Yu J, Yang M S, Lee E S. Sample-weighted clustering methods[J]. Computers and Mathematics with Applications, 2011, 62(5): 2200-2208.

[12] Yang M S, Pan Y S. Sample-weighted fuzzy clustering with regularizations[J]. International Journal of Computer, Information, Systems and Control Engineering, 2013, 7(7): 407-410.

[13] Hadjahmadi A H, Homayounpour M M, Ahadi S M. Bilateral weighted fuzzy C-means clustering[J]. Iranian Journal of Electrical and Electronic Engineering, 2012, 8(2): 108-121.

[14] 翁文田, 趙曙光. 圖像分割的改進(jìn)的加權(quán)模糊聚類算法[J]. 計算機(jī)工程與應(yīng)用, 2010, 46(33): 182-184.

[15] Gong M G, Shi J, Ma W P, et al. Fuzzy c-means clustering with local in formation and kernel metric for image segmentation[J].IEEE Transactions On Image Processing, 2013, 22(2): 573-584.

[16] Hasanzadeh M, Kasaei S. A multispectral image segmentation method using size-weighted fuzzy clustering and membership connectedness[J]. IEEE Geoscience and Remote Sensing Letters, 2010, 7(3): 520-524.

[17] Hung C C, Kulkarni S, Kuo B C. A new weighted fuzzy c-means clustering algorithm for remotely sensed image classification[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5(3): 543-553.

[責(zé)任編輯:祝劍]

Bilateral weighted fuzzy C-means clustering segmentation algorithm on histogram

NIE Min1, LIU Pengfei2, WU Chengmao2, LIU Xiaohui2

(1.School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.School of Electronic Engineering,Xi’an University of Posts and telecommunications, Xi’an 710121,China)

A bilateral weighted fuzzy C-means clustering segmentation algorithm on histogram is proposed in this paper for small target image segmentation. In this algorithm, the sample and structure information weights are combined to bilateral weight for the traditional fuzzy C- means clustering segmentation. The iterative expression of degree of membership, clustering centre and the weight of structure information coefficient is obtained through strict mathematical derivation by the weighted clustering segmentation objective function. This proposed algorithm is more effective and universal on image segmentation compared with the existing weighted fuzzy C- means clustering segmentation algorithm.

image segmentation, fuzzy C-means clustering, sample weighted, structure weighted, accuracy of segmentation

2015-01-07

國家自然科學(xué)基金重大項目(61136002),國家自然科學(xué)基金資助項目(61172071, 61201194),陜西省自然科學(xué)基金資助項目(2014JM8331,2014JQ5138),陜西省教育廳專項科研計劃資助項目(2014JK1663)

聶 敏 (1989-)， 男， 博士后，教授，從事圖像處理和量子通信方向研究。E-mail: niemin@xupt.edu.cn 劉鵬飛 (1990-)，男，碩士研究生，研究方向數(shù)字圖像處理。E-mail: 915156234@qq.com

10.13682/j.issn.2095-6533.2015.03.009

TP391.41

A

2095-6533(2015)03-0053-08