圖形模糊聚類算法初始化方式改進(jìn)

吳成茂， 何　晶

(西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121)

圖形模糊聚類算法初始化方式改進(jìn)

吳成茂， 何晶

(西安郵電大學(xué) 電子工程學(xué)院， 陜西 西安 710121)

摘要:為了降低初始化參數(shù)對(duì)圖形模糊聚類算法收斂性的影響，對(duì)圖形模糊聚類算法的初始化方法加以改進(jìn)。將隸屬度、中立度和拒絕度3個(gè)參量的隨機(jī)值先求平方，再按其平方和進(jìn)行歸一化處理，以代替原來(lái)的初始化方法。將改進(jìn)前后的算法用于Iris文本數(shù)據(jù)分類，以及基于1維或2維直方圖的人物、醫(yī)學(xué)和遙感的圖像分割，結(jié)果顯示，改進(jìn)算法用時(shí)短，收斂快。將改進(jìn)算法作用于含噪標(biāo)準(zhǔn)灰度圖像，分割結(jié)果的峰值信噪比更高。

關(guān)鍵詞:模糊聚類；圖形模糊集；初始化；收斂性

聚類算法可用于圖像分割[1-4]。結(jié)合分明集理論得出的聚類算法可實(shí)現(xiàn)圖像硬分割，但分割明晰，無(wú)法表示其屬于某一類的程度。引進(jìn)隸屬度概念，把模糊集理論[5]應(yīng)用于圖像分割，可得出模糊C均值算法(FuzzyC-meansclustering,FCM)[6-7]，實(shí)現(xiàn)圖像的軟分割，但模糊集僅用隸屬度表達(dá)一個(gè)元素屬于集合的肯定信息，無(wú)法表達(dá)一個(gè)元素不屬于集合的否定信息。結(jié)合直覺模糊集(Intuitionisticfuzzyclusteringalgorithm,IFCM)[8]得出的直覺模糊聚類算法[9-10]，既包含圖像的隸屬度，又包含非隸屬度，其表達(dá)更加充分，但如同既要有贊成票和反對(duì)票，還要有棄權(quán)票這種投票模型，前兩種理論都不能充分表達(dá)相關(guān)信息。圖形模糊聚類算法(Picturefuzzyclusteringalgorithm,FC-PFS)[11]將圖形模糊集理論[12]應(yīng)用于圖像分割，能有效解決這種多選擇性問題。

基于1維直方圖的圖形模糊聚類算法可降低聚類分割的時(shí)間開銷，但缺乏抗噪性。將統(tǒng)計(jì)像素與其鄰域像素均值所得的2維直方圖[13]引入圖形模糊聚類算法，可提高算法的抗噪性能，但其初始化參數(shù)的選取影響算法的收斂速度。鑒于此，本文擬對(duì)圖形模糊聚類算法的初始化方式加以改進(jìn)，以減少算法的運(yùn)行時(shí)間，提高算法收斂的可能性，并對(duì)標(biāo)準(zhǔn)灰度圖像添加噪聲,以驗(yàn)證改進(jìn)算法的性能。

1圖形模糊聚類算法

圖形模糊聚類算法是對(duì)模糊C均值算法和直覺模糊聚類算法的一種延拓，其目標(biāo)函數(shù)定義為

其中m的取值范圍為[1,+∞)，一般為2，稱為加權(quán)系數(shù)。該目標(biāo)函數(shù)的約束條件為

ukj+ηkj+ξkj≤1,

通過拉格朗日乘數(shù)法，進(jìn)行公式推導(dǎo)可以得出ukj、ηkj、ξkj和聚類中心vj的表達(dá)式分別為

(1)

(2)

ξkj=1-(ukj+ηkj)-

(3)

(4)

圖形模糊聚類算法可描述如下。

步驟1初始化聚類中心v(0),設(shè)定聚類類別數(shù)c，設(shè)置停止閾值ε，設(shè)置迭代計(jì)數(shù)器t=0，設(shè)置最大迭代步數(shù)為1 000，參數(shù)α的取值屬于區(qū)間(0，1)。

步驟2初始化ukj、ηkj和ξkj。產(chǎn)生(0,1)上的隨機(jī)值并賦值給變量ukj、ηkj和ξkj，并使它們的值滿足約束條件ukj+ηkj+ξkj≤1。

步驟3t=t+1。

步驟6重復(fù)步驟3、步驟4和步驟5,直到t超出最大迭代次數(shù)或

‖u(t))-u(t-1)‖+‖η(t)-η(t-1)‖+

‖ξ(t)-ξ(t-1)‖≤ε。

圖形模糊聚類算法對(duì)參數(shù)ukj、ηkj和ξkj進(jìn)行初始化時(shí)，采用產(chǎn)生(0,1)上隨機(jī)值的方式,不僅要求3個(gè)參數(shù)的取值在0和1之間，還要使其和不小于0且不超過1。這樣的初始化方式有一定缺陷：將此算法應(yīng)用于添加噪聲的2維圖像，會(huì)發(fā)現(xiàn)，α取某些數(shù)值時(shí)，算法不收斂，從而影響聚類性能。

2圖形模糊聚類改進(jìn)

針對(duì)圖形模糊聚類算法基于2維直方圖加噪圖像在有限次數(shù)內(nèi)不能保證收斂的問題，在此就其初始化方式給出一種改進(jìn)。

先產(chǎn)生(0，1)上的隨機(jī)值，并賦值給參量ukj、ηkj和ξkj，再對(duì)這3個(gè)參量隨機(jī)初始化，求平方和后再進(jìn)行歸一化。改進(jìn)后的初始化方式不僅滿足原算法的約束條件，而且能保障算法在有限迭代次數(shù)收斂，且耗時(shí)更短。將改進(jìn)算法應(yīng)用于2維加噪圖像，其收斂性能有顯著改善。

改進(jìn)的圖形模糊聚類算法可描述如下。

步驟1初始化聚類中心v(0),設(shè)定聚類類別數(shù)c，設(shè)置停止閾值ε，設(shè)置迭代計(jì)數(shù)器t=0，設(shè)置最大迭代步數(shù)為1 000,參數(shù)α的取值屬于區(qū)間(0，1)。

步驟2初始化ukj、ηkj和ξkj。先產(chǎn)生(0,1)上的隨機(jī)值并賦值給參量ukj、ηkj和ξkj，再對(duì)3個(gè)參量求平方和并進(jìn)行，即令

步驟3t=t+1。

步驟6重復(fù)步驟3、步驟4和步驟5,直到t超出最大迭代次數(shù)或

‖u(t))-u(t-1)‖+‖η(t)-η(t-1)‖+

‖ξ(t)-ξ(t-1)‖≤ε。

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

選取文本數(shù)據(jù)和圖片，驗(yàn)證改進(jìn)算法的有效性。固定參量加權(quán)系數(shù)m=2、閾值ε=10-3、最大迭代步數(shù)為1 000、聚類類別數(shù)c=2，并分別選取α=0.2, 0.4, 0.6和0.8。通過程序的輸出結(jié)果判斷改進(jìn)算法對(duì)Iris文本數(shù)據(jù)分類，以及對(duì)1維或2維直方圖聚類是否收斂。實(shí)驗(yàn)選取7幅灰度圖像進(jìn)行實(shí)驗(yàn)測(cè)試，如圖1所示。

圖1　原始圖像

(1) 對(duì)于Iris數(shù)據(jù)，對(duì)比改進(jìn)前后的圖形模糊聚類算法。第1次選擇初始聚類中心

(5.4， 3.4， 1.7， 0.2；

5.9， 3.2， 4.8， 1.8；

6.9， 3.2， 5.7， 2.3)，

第2次選擇聚類中心

(5.1， 3.5， 1.4， 0.2；

7.0， 3.2， 4.7， 1.4；

6.3， 3.3， 6.0， 2.5),

實(shí)驗(yàn)結(jié)果如表1和表2所示。

表1　第1類初始聚類中心對(duì)應(yīng)收斂次數(shù)

表2　第2類初始聚類中心對(duì)應(yīng)收斂次數(shù)

可見，改進(jìn)前后，算法對(duì)于Iris數(shù)據(jù)都是收斂的。

(2) 針對(duì)未加噪聲的小狗和蝴蝶圖片，采用1維直方圖下兩種不同初始化方式圖形模糊聚類分割法對(duì)其測(cè)試對(duì)比，實(shí)驗(yàn)結(jié)果如表3和表4所示。

表3　分割小狗圖的收斂次數(shù)

表4　分割蝴蝶圖的收斂次數(shù)

可見，改進(jìn)前后，算法對(duì)1維直方圖灰度級(jí)聚類是收斂的，其迭代次數(shù)相差很小。

(3) 針對(duì)未加噪聲的齒輪和CT圖片采用2維直方圖下兩種不同初始化方式圖形模糊聚類分割法對(duì)其測(cè)試對(duì)比，實(shí)驗(yàn)結(jié)果如表5和表6所示。

表5　分割齒輪圖的收斂次數(shù)

表6　分割CT圖的收斂次數(shù)

可見，改進(jìn)前后，算法對(duì)2維直方圖灰度級(jí)二元組聚類都是收斂的，其迭代結(jié)果相差很小，但改進(jìn)方法略好原圖形模糊聚類算法。

(4) 針對(duì)添加噪聲的蝴蝶和米粒圖片，采用2維直方圖下兩種不同初始化方式圖形模糊聚類分割法對(duì)其測(cè)試對(duì)比，實(shí)驗(yàn)結(jié)果如表7和表8所示。

表7　分割加噪蝴蝶圖的收斂次數(shù)

表8　分割加噪米粒圖的收斂次數(shù)

對(duì)于添加高斯噪聲的兩幅圖像的分割結(jié)果顯示，改進(jìn)算法經(jīng)過有限迭代次數(shù)后收斂，而原算法在設(shè)置最大迭代次數(shù)為1 000的情況下，對(duì)于不同的α取值，可能不收斂。這說(shuō)明改進(jìn)算法能提高圖形模糊聚類算法對(duì)于2維加噪圖像收斂的可能性。

(5) 對(duì)不加噪的攝影師圖、CT圖和遙感圖，各算法的分割效果如圖2至圖4所示。對(duì)其添加均值為0，均方差為81的高斯噪聲后，各算法的分割效果如圖圖5至圖7所示。

圖2　無(wú)噪攝影師圖的分割結(jié)果

圖3　無(wú)噪CT圖的分割結(jié)果

圖4　無(wú)噪遙感圖的分割結(jié)果

圖5　加噪攝影師圖的分割結(jié)果

圖6　加噪CT圖的分割結(jié)果

圖7　加噪遙感圖的分割結(jié)果

圖2至圖7顯示，改進(jìn)算法的去噪效果更好。不同分割算法所得分割結(jié)果圖像的峰值信噪比(PeakSignalToNoiseRatio,PSNR)如表9所示，從中可見，改進(jìn)算法的峰值信噪比均大于FCM算法和IFCM算法的的峰值信噪比。

表9　抗高斯噪聲分割算法性能PSNR比較

4結(jié)語(yǔ)

將圖形模糊聚類算法中隸屬度、中立度和拒絕度3個(gè)參量的隨機(jī)值先求平方，再按其平方和進(jìn)行歸一化處理，代替原圖形模糊聚類算法的初始化方法，可提高算法的分割性能和抗噪性。實(shí)驗(yàn)發(fā)現(xiàn)改進(jìn)算法對(duì)于2加噪圖像能在有限步數(shù)內(nèi)收斂，且運(yùn)行時(shí)間較短。通過對(duì)不同圖像添加噪聲進(jìn)行分割測(cè)試，結(jié)果表明，改進(jìn)算法具有較好的抗噪性能，能有效分割在噪聲干擾環(huán)境下捕獲的圖像。

參考文獻(xiàn)

[1]BORADJ,GUPTAKA.AComparativeStudyBetweenFuzzyClusteringAlgorithmandHardClusteringAlgorithm[J/OL].InternationalJournalofComputerTrendsandTechnology,2014,2(10):108-113[2015-10-20].http://www.ijcttjournal.org/archives/ijctt-v10p119.

[2]SHIVHAREP,GUPTAV.ReviewofImageSegmentationTechniquesIncludingPre&PostProcessingOperations[J/OL].InternationalJournalofEngineeringandAdvancedTechnology,2015,4(3)：153-157[2015-10-20].http://www.ijeat.org/attachments/File/v4i3/C3782024315.pdf.

[3]KANDWALR,KUMARA,BHARGAVAS.Review:ExistingImageSegmentationTechniques[J/OL].InternationalJournalofAdvancedResearchinComputerScienceandSoftwareEngineering,2014,4(4):153-156[2015-10-20].http://www.ijarcsse.com/docs/papers/Volume_4/4_April2014/V4I4-0130.pdf.

[4]HANLX,CHENGH.Afuzzyclusteringmethodofconstructionofontology-baseduserprofiles[J/OL].AdvancesinEngineeringSoftware,2009,7(40):535-540[2015-10-20].http://www.sciencedirect.com/science/artic-le/pii/S0965997808001762.DOI:10.1016/j.advengsoft.2008.10.006.

[5]ZADEHLA.Fuzzysets[J/OL].InformationandControl,1965,8(3):338-353[2015-10-20].http://www.sciencedirect.com/science/article/pii/S001999586590241.

[6]李琳,范九倫,趙鳳.模糊C-均值聚類圖像分割算法的一種改進(jìn)[J/OL].西安郵電大學(xué)學(xué)報(bào)2014,19(5):56-60[2015-10-20].http://www.doc88.com/p-8945397104718.html.DOI:10.13682/j.issn.2095-6533.2014.05.011.

[7]WANGZM,SONGQ,SOHYC,etal.Anadaptivespatialinformation-theoreticfuzzyclusteringalgorithmforimagesegmentation[J/OL].ComputerVisionandImageUnderstanding, 2013,117(10): 1412-1420[2015-10-20].http://www.sciencedirect.com/science/article/pii/S1077314213000957.DOI:10.1016/j.cviu.2013.05.001.

[8]ATANASSOVKT.Intuitionisticfuzzysets[J/OL].FuzzySetsandSystems,1986,20:87-96[2015-10-20].http://www.sciencedirect.com/science/article/pii/S0165011486800343.DOI:10.1016/SO165-0114(86)80034-3.

[9]LINKP.AnovelevolutionarykernelintuitionisticfuzzyC-meansclusteringalgorthm[J/OL].IEEETransactiononFuzzySystems,2014,22(5):1074-1087[2015-10-20].http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6587744.DOI:10.1109/TFUZZ.2013.2280141.

[10]PRABHJOTK,ANILS,ANJANAG.ArobustkernelizedintuitionisticfuzzyC-meansclusteringalgorithminsegmentationofnoisymedicalimages[J/OL].PatternRecognitionLetters,2013,34(2):163-175[2015-10-20].http://www.sciencedirect.com/science/article/pii/S0167865512003005.DOI:10.1016/j.patrec.2012.09.015.

[11]PHAMHT,LEHS.Picturefuzzyclustering:anewcomputationalintelligencemethod[EB/OL]. [2015-10-20].http://link.springer.com/article/10.1007%2Fs00500-015-1712-7# .

[12]CUONGBC.Picturefuzzysets[J/OL].ComputingScienceCybern,2014,30(4):409-420[2015-10-20].http://www.vjs.ac.vn/index.php/jcc/article/view/5032.DOI:10.15625/1813-9663/30/4/5032.

[13] 劉健莊,基于二維直方圖的圖像模糊聚類分割方法[J/OL].電子學(xué)報(bào),1992,20(9):41-46[2015-10-21].http://www.cnki.com.cn/Article/CJFD1992-DZXU199209008.htm.

[責(zé)任編輯:瑞金]

Animprovedinitializationofpicturefuzzyclusteringalgorithm

WUChengmao,HEJing

(SchoolofElectronicEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:To reduce th eeffects of initialization parameters on the convergence of picture fuzzy clustering algorithm, the initialization method of picture fuzzy clustering is improved. Different from the original one, after getting the random values of the three parameter, which are positive degree, neutral degree and refused degree, the new initialization method chose to normalize these parameters accordding to the sum of their squares. Classification experiment of Iris text data and segmentation experiment of people, medicine, and remote sensing images based on one dimensional or two dimensional histogram show that, the improved algorithm works shorter and converges faster. As be used on normal gray images with noise, the improved algorithm can get segmentations with higher peak signal to noise ratio in general.

Keywords:fuzzy clustering, picture fuzzy set, initialization, convergence

doi:10.13682/j.issn.2095-6533.2016.02.010

收稿日期：2015-11-23

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目(61136002)；陜西省自然科學(xué)基金資助項(xiàng)目 (2014JM8331,2014JQ5183,2014JM8307)；陜西省教育廳科學(xué)研究計(jì)劃資助項(xiàng)目(2015JK1654)

作者簡(jiǎn)介：吳成茂(1968-)，男，高級(jí)工程師，從事圖像處理與信息安全的研究。E-mail: wuchengmao123@sohu.com 何晶(1991-)，男，碩士研究生，研究方向?yàn)殡娐放c系統(tǒng)。E-mail:776248249@qq.com

中圖分類號(hào)：TP391.41

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-6533(2016)02-0052-05