融合增強(qiáng)型模糊聚類遺傳算法與ISODATA算法的遙感影像分類

郭云開(kāi)1，曾　繁2

(1. 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410076； 2. 湖南交通職業(yè)技術(shù)學(xué)院

路橋工程學(xué)院，湖南 長(zhǎng)沙 410132)

Remote Sensing Classification of Combined Enhanced Fuzzy Clustering Genetic

Algorithm with ISODATA Algorithm

GUO Yunkai，ZENG Fan

?

融合增強(qiáng)型模糊聚類遺傳算法與ISODATA算法的遙感影像分類

郭云開(kāi)1，曾繁2

(1. 長(zhǎng)沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410076； 2. 湖南交通職業(yè)技術(shù)學(xué)院

路橋工程學(xué)院，湖南 長(zhǎng)沙 410132)

RemoteSensingClassificationofCombinedEnhancedFuzzyClusteringGenetic

AlgorithmwithISODATAAlgorithm

GUOYunkai，ZENGFan

摘要：針對(duì)ISODATA算法預(yù)設(shè)參數(shù)較多，其聚類中心與最優(yōu)迭代數(shù)目很難預(yù)先準(zhǔn)確設(shè)定，且在聚類時(shí)沒(méi)有將影像自身特點(diǎn)充分考慮，對(duì)個(gè)體適應(yīng)度函數(shù)重視不夠的問(wèn)題，本文提出一種融合增強(qiáng)型模糊聚類GA與ISODATA的聚類方法，對(duì)聚類原型矩陣進(jìn)行編碼，構(gòu)造隸屬度矩陣，解求個(gè)體適應(yīng)度函數(shù)值，在影像特征空間中搜索得到樣本全局收斂極值點(diǎn)。通過(guò)試驗(yàn)證明，該方法能避開(kāi)隨機(jī)初選值的敏感問(wèn)題，避免聚類過(guò)程的隨機(jī)性，使分類結(jié)果與實(shí)際情況更為接近，該算法精度優(yōu)于傳統(tǒng)的ISODATA算法與模糊聚類GA算法，提高了分類的精度，整體效果較好。

關(guān)鍵詞：ISODATA；增強(qiáng)型模糊聚類GA；適應(yīng)度函數(shù)；遙感影像分類

一、引言

聚類是把具有相似性質(zhì)的事物區(qū)分開(kāi)并加以分類[1-3]，所謂物以類聚。迭代自組織數(shù)據(jù)分析技術(shù)算法(iterativeself-organizingdataanalysistechniquesalgorithm，ISODATA)是人們熟悉的非監(jiān)督聚類算法之一，可自動(dòng)執(zhí)行類別合并與分裂，是成批樣本修正法[2]。但這種硬分類算法沒(méi)有充分考慮圖像本身的特點(diǎn)，最優(yōu)迭代次數(shù)很難設(shè)定[3]。李前進(jìn)等提出了基于直覺(jué)模糊的ISODATA算法[4]，改進(jìn)了隸屬度函數(shù)，提高了算法速度；沈照慶等[5]在模糊ISODATA算法的基礎(chǔ)上改進(jìn)了隸屬度的計(jì)算公式，使算法在實(shí)際應(yīng)用中更易實(shí)現(xiàn)。盡管如此，該算法仍需面對(duì)隨機(jī)初選值的敏感問(wèn)題，在一定程度上受人為的事先干預(yù)。

遺傳算法(geneticalgorithm，GA)屬于進(jìn)化計(jì)算之一，許多聚類分析領(lǐng)域內(nèi)的學(xué)者利用進(jìn)化計(jì)算來(lái)降低傳統(tǒng)聚類算法對(duì)初始化的要求。早在20世紀(jì)90年代，Bezdek等就提出用遺傳算法指導(dǎo)聚類的思路[6]。由于聚類分析僅憑自然聚類的特性進(jìn)行盲目分類，在結(jié)合遺傳算法后能增大真正達(dá)到物以類聚的可能性，增強(qiáng)型模糊聚類遺傳算法將遺傳算法與傳統(tǒng)的模糊聚類算法有機(jī)結(jié)合起來(lái)，收斂速度遠(yuǎn)大于之前[7]。即便如此，遺傳算子的搜索能力仍不夠全面，該算法的操作參數(shù)與聚類分析性能可以進(jìn)一步提高[7]。

本研究提出將增強(qiáng)型模糊聚類遺傳算法與ISODATA算法融合，能避開(kāi)隨機(jī)初選值的敏感問(wèn)題，減少人為事先干預(yù)，避免聚類過(guò)程的隨機(jī)性，比單純應(yīng)用傳統(tǒng)ISODATA和模糊聚類分析方法得到的聚類結(jié)果更符合實(shí)際。

二、融合增強(qiáng)型模糊聚類GA與ISODATA的聚類分析算法

1. 普通ISODATA算法

ISODATA算法是一種基于統(tǒng)計(jì)模式識(shí)別的非監(jiān)督學(xué)習(xí)動(dòng)態(tài)聚類算法。其實(shí)質(zhì)是用將輸入的模式樣本生成初始類別作為種子，依據(jù)最小距離準(zhǔn)則進(jìn)行自動(dòng)迭代聚類的過(guò)程。ISODATA算法是個(gè)循環(huán)過(guò)程，其步驟如下：

1) 預(yù)設(shè)聚類分析可調(diào)參數(shù)，讀入N個(gè)模式樣本{Xi，i=1,2,3，…，N}。一般需要先定義最大聚類中心數(shù)Nmax，能作為獨(dú)立聚類的最少樣本數(shù)θN，一集群中樣本的距離標(biāo)準(zhǔn)差θS，兩聚類中心間的最小距離θC，能一次合并的最多聚類中心對(duì)數(shù)L，最大迭代次數(shù)I。

2) 初始分類，根據(jù)式(1)按距離最小原則將模式樣本分給最近的聚類Sj，依照式(2)、式(3)分別修正與計(jì)算各聚類中心值和各聚類中心間的距離均值

(1)

(2)

(3)

式(1)—式(3)中，Nc為預(yù)選的初始聚類中心數(shù)，Nc可≠Nmax；Nj為Sj類中的樣本數(shù)。

3) 根據(jù)預(yù)設(shè)參數(shù)，將已獲取的聚類集進(jìn)行分裂、合并處理，得到新的聚類中心，依據(jù)式(4)計(jì)算全部聚類中心的距離

(4)

4) 反復(fù)進(jìn)行迭代運(yùn)算，判別聚類結(jié)果是否符合要求，如有需要可修改輸入?yún)?shù)，直到獲得理想的聚類結(jié)果。

2. 增強(qiáng)型模糊聚類遺傳算法

遺傳算法的基本原理是1962年由J.H.Holland提出的，在一定條件下，遺傳算法可以在搜索空間中收斂到全局最優(yōu)解。模糊聚類需要將原始數(shù)據(jù)矩陣進(jìn)行無(wú)量綱化處理，使每一指標(biāo)值統(tǒng)一在某一共同的數(shù)據(jù)特性范圍內(nèi)[10-11]。增強(qiáng)型模糊聚類GA需要將聚類問(wèn)題的解進(jìn)行編碼，構(gòu)造衡量各個(gè)體碼鏈對(duì)聚類問(wèn)題適應(yīng)程度的適應(yīng)度函數(shù)；并選擇遺傳算子，自適應(yīng)選取操作參數(shù)，如選種概率Pi、交叉率Pc及浮動(dòng)區(qū)間中心點(diǎn)等[7]。

聚類的最終目標(biāo)是獲得樣本集X的模糊劃分矩陣U和聚類原型P，兩者是相關(guān)的，求其一便知其二[12]。該增強(qiáng)型模糊聚類遺傳算法對(duì)聚類原型矩陣P編碼，把n組表示聚類原型的參數(shù)連接起來(lái)，根據(jù)各自的取值范圍，根據(jù)式(5)將其量化值用二進(jìn)制串表示，式(6)定義適應(yīng)度函數(shù)，并將進(jìn)化結(jié)束的準(zhǔn)則改為范數(shù)準(zhǔn)則。

(5)

(6)

式中，ζ為一給定的常數(shù)；D(xk，pi)為相似性測(cè)度函數(shù)。

3. 融合增強(qiáng)型模糊聚類GA與ISODATA算法

(1) 適應(yīng)度函數(shù)

模糊聚類問(wèn)題可由一目標(biāo)函數(shù)Tn(U，P)表示，其最優(yōu)聚類結(jié)果則對(duì)應(yīng)于目標(biāo)函數(shù)的極小值[10]。本文提出的融合算法需要計(jì)算個(gè)體適應(yīng)度函數(shù)的值。

D2(xk,Pi)=(xk-pi)T(xk-pi)-(〈xi-pi,di〉)2

(7)

(8)

(2) 融合遺傳算子

該融合算法需要借助融合遺傳算子找到待優(yōu)化問(wèn)題的解，其中包括：

1) 選種算子Ts(·)：根據(jù)樣本中個(gè)體的適應(yīng)度值Fi在聚類中心附近選取雙親的過(guò)程。Fi越大，則賦予更大的選種概率Pi。

(9)

3) 梯度算子Tg(·)：此算子將適應(yīng)度值最高的字符串對(duì)應(yīng)的解作為初始點(diǎn)作梯度優(yōu)化獲得極值點(diǎn)，保證每次迭代都能至少搜索到極值點(diǎn)。

4) 解釋算子Te(·)：是解碼算子的擴(kuò)展，將解碼得到的實(shí)數(shù)轉(zhuǎn)換為編碼區(qū)間所對(duì)應(yīng)的值

(10)

式中，Ai為Si對(duì)應(yīng)的實(shí)數(shù)編碼區(qū)間中心點(diǎn)；B為編碼區(qū)間大??；C為L(zhǎng)比特位的二進(jìn)制碼的全1串所表示的實(shí)數(shù)值。

(3) 算法步驟

1) 讀入影像數(shù)據(jù)區(qū)域樣本，用Gray碼進(jìn)行編碼，得到二進(jìn)制的一組數(shù)列。

2) 預(yù)設(shè)聚類間最小距離為3，結(jié)合樣本個(gè)體適應(yīng)度值與傳統(tǒng)ISODATA距離最小原則進(jìn)行初始分類。

3) 設(shè)置進(jìn)化停止的允許誤差為0.02，借助融合遺傳算子自適應(yīng)選取操作參數(shù)，將已有聚類域與領(lǐng)域像元對(duì)比分析，對(duì)聚類結(jié)果進(jìn)行分裂、重組等必要的優(yōu)化。

4) 更新適應(yīng)度函數(shù)與聚類中心，反復(fù)迭代，直到獲得滿意的聚類結(jié)果(全部聚類中心平均變化量小于所設(shè)閾值)。

三、試驗(yàn)研究分析

分類對(duì)比試驗(yàn)前需要先完成影像裁減、幾何糾正、大氣糾正等預(yù)處理工作[12]，本文采用2010年11月2日長(zhǎng)株潭部分地區(qū)的SPOT-5 1A影像作為試驗(yàn)數(shù)據(jù)，影像空間分辨率為10m，共4個(gè)波段(綠、紅、近紅外、短波紅外)，如圖1所示。

圖1　原圖

圖2是用ISODATA算法得到的聚類結(jié)果，本次試驗(yàn)按照影像區(qū)域內(nèi)主要地物統(tǒng)一劃分為水體、林地、草地、耕地、道路及房屋5大類(影像中道路與房屋的反射率接近，單借助光譜分類法很難區(qū)分，故兩者作為一個(gè)大類表示)。圖2中的河流能被完全搜索提取出來(lái)，但將與水體挨很近的部分房屋道路也誤判成水體大類，總水體面積占總區(qū)域面積7.683%(見(jiàn)表1)，與實(shí)際不符；此外由于11月份的農(nóng)田大都處于收割狀態(tài)，耕地表層覆蓋有干稻草，ISODATA算法不能將其與他類準(zhǔn)確區(qū)分，在河流的西北部把耕地誤判成道路房屋大類、河流南部將耕地誤判成林地和草地的結(jié)果較嚴(yán)重，而本身屬于道路房屋大類的區(qū)域沒(méi)有準(zhǔn)確提取，總體精度不高。

圖2　ISODATA分類圖

圖3　模糊聚類GA分類圖

圖4　融合法分類圖

圖4是經(jīng)過(guò)將融合增強(qiáng)型模糊聚類GA與ISODATA的算法應(yīng)用到遙感影像分類得到的聚類結(jié)果，所設(shè)參數(shù)包括最小類間距離為5，變化閾值3%。從圖3、圖4中都可看出河流中部的橫跨橋梁，且沒(méi)有將部分房屋道路誤判成水體，耕地也能被很好地提取出來(lái)，與道路房屋大類有鮮明區(qū)分。表1為3種分類方法得到的各地物所占圖像百分比對(duì)比表，據(jù)統(tǒng)計(jì)，后兩者總水體面積都少于圖2，耕地面積大于圖2。當(dāng)然，圖4中對(duì)水體、道路房屋的提取相比圖3更為完全，可以反映出道路的連貫性與房屋群的成片特點(diǎn)通過(guò)，對(duì)比能夠明顯看出該圖的分類結(jié)果與實(shí)際情況更為符合。

表1　分類結(jié)果統(tǒng)計(jì)　(%)

通過(guò)目視判斷，從原始影像中隨機(jī)選取水體、林地、耕地、草地、道路房屋這5大類的樣本點(diǎn)，建立混淆矩陣，進(jìn)而分別求得傳統(tǒng)ISODATA、模糊聚類GA與融合算法的分類精度和Kappa系數(shù)[11]，表2是3種分類方法的精度對(duì)比表，可以看出本文提出的融合方法提高了分類精度，整體效果良好。

表2　分類精度

四、結(jié)論

本文提出融合增強(qiáng)型模糊聚類GA與ISODATA算法應(yīng)用于遙感影像分類，以SPOT-5影像為試驗(yàn)數(shù)據(jù)，且分析比較了傳統(tǒng)ISODATA、模糊聚類GA與該融合方法的分類結(jié)果。總體可以得出以下結(jié)論：

1) 本文提出的融合算法顯示了很好的分類精度，特別是在區(qū)分水體、耕地、道路房屋大類時(shí)，能有效避免誤判現(xiàn)象，總體分類精度達(dá)83%，優(yōu)于另外兩種方法。

2) 從算法上分析，融合增強(qiáng)型模糊聚類遺傳算法與迭代自組織分析算法緩和了傳統(tǒng)ISODATA的“硬”與模糊聚類的“軟”，在分類過(guò)程中簡(jiǎn)化了參數(shù)的預(yù)設(shè)選取，能根據(jù)融合遺傳算子自適應(yīng)調(diào)整操作參數(shù)，減少人為事先干預(yù)，并對(duì)聚類原型矩陣進(jìn)行編碼，計(jì)算個(gè)體適應(yīng)度函數(shù)值，能在特征空間中搜索得到其收斂極值點(diǎn)，使聚類結(jié)果與實(shí)際情況更為接近，提高了算法的智能化。

綜上所述，該融合算法能改善中等分辨率影像的非監(jiān)督分類精度，但是否對(duì)于高分辨率影像同樣適用有待進(jìn)一步研究。

參考文獻(xiàn)：

[1]趙英時(shí)．遙感應(yīng)用分析原理與方法[M]．北京：科學(xué)出版社，2003：194-201．

[2]王新洲，史文中，王樹(shù)良．模糊空間信息處理[M]．武漢：武漢大學(xué)出版社，2003：59-63．

[3]吳孔江，曾永年，勒文憑，等．改進(jìn)利用蟻群規(guī)則挖掘算法進(jìn)行遙感影像分類[J]．測(cè)繪學(xué)報(bào)，2013，2(42)：59-66．

[4]李前進(jìn)，王寅龍，李志祥，等．基于直覺(jué)模糊的ISODATA[J]．計(jì)算機(jī)工程與應(yīng)用，2012，48(9)：176-177．

[5]沈照慶，舒寧，龔衍，等．基于改進(jìn)模糊ISODATA算法的遙感影像非監(jiān)督聚類研究[J]．遙感信息，2008(5)：28-32．

[6]BEZDEK J C．A Convergence Theoren for the Fuzzy ISODATA Clustering Algorithm[J]．IEEE Trans．PAMI，1980，1(2)：1-8．

[7]高新波．模糊聚類分析及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2004．

[8]郭云開(kāi)，張起森．基于廣義夾角的遙感圖像計(jì)算機(jī)分類方法[J]，中國(guó)公路學(xué)報(bào)，2002，15(2):28-30．

[9]楊紅磊，彭軍還．基于馬爾可夫隨機(jī)場(chǎng)的模糊c-均值遙感影像分類[J]．測(cè)繪學(xué)報(bào)，2012,41(2)：214-218．

[10]ISHIBUCHI H，NOZAKI N，YAMAMOTO N．Selecting Fuzzy If-then Rules for Classification Problems Using Genetic Algorithms[J].IEEE Trans．FS，1995，3(3)：260-270．

[11]尹淑玲，舒寧，劉新華．基于自適應(yīng)遺傳算法和改進(jìn)BP算法的遙感影像分類[J]．武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2007，32(3)：201-204．

[12]郭云開(kāi)，曾繁．基于FLAASH與QUAC模型的SPOT5影像大氣校正比較[J]．測(cè)繪通報(bào)，2012(11)：21-23，41．

[13]張儷文 ,汪云甲,王行風(fēng). 仿射傳播聚類在室內(nèi)定位指紋庫(kù)中的應(yīng)用研究[J].測(cè)繪通報(bào),2014(12): 36-39.

作者簡(jiǎn)介：郭云開(kāi)(1958—)，男，博士，教授，主要研究方向?yàn)榈缆翻h(huán)境遙感評(píng)價(jià)等。E-mail：guoyunkai226@163.com

基金項(xiàng)目：國(guó)家自科科學(xué)基金(41471421)；國(guó)家自然科學(xué)基金(41171397)；貴州省交通科技計(jì)劃項(xiàng)目(2014-121-039)

收稿日期：2015-03-20；修回日期： 2015-10-15

中圖分類號(hào)：P237

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

文章編號(hào)：0494-0911(2015)12-0023-04

引文格式： 郭云開(kāi)，曾繁. 融合增強(qiáng)型模糊聚類遺傳算法與ISODATA算法的遙感影像分類[J].測(cè)繪通報(bào)，2015(12)：23-26.DOI:10.13474/j.cnki.11-2246.2015.369