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

郭云開1，曾　繁2

(1. 長沙理工大學交通運輸工程學院，湖南 長沙 410076； 2. 湖南交通職業技術學院

路橋工程學院，湖南 長沙 410132)

Remote Sensing Classification of Combined Enhanced Fuzzy Clustering Genetic

Algorithm with ISODATA Algorithm

GUO Yunkai，ZENG Fan

?

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

郭云開1，曾繁2

(1. 長沙理工大學交通運輸工程學院，湖南 長沙 410076； 2. 湖南交通職業技術學院

路橋工程學院，湖南 長沙 410132)

RemoteSensingClassificationofCombinedEnhancedFuzzyClusteringGenetic

AlgorithmwithISODATAAlgorithm

GUOYunkai，ZENGFan

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

關鍵詞：ISODATA；增強型模糊聚類GA；適應度函數；遙感影像分類

一、引言

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

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

本研究提出將增強型模糊聚類遺傳算法與ISODATA算法融合，能避開隨機初選值的敏感問題，減少人為事先干預，避免聚類過程的隨機性，比單純應用傳統ISODATA和模糊聚類分析方法得到的聚類結果更符合實際。

二、融合增強型模糊聚類GA與ISODATA的聚類分析算法

1. 普通ISODATA算法

ISODATA算法是一種基于統計模式識別的非監督學習動態聚類算法。其實質是用將輸入的模式樣本生成初始類別作為種子，依據最小距離準則進行自動迭代聚類的過程。ISODATA算法是個循環過程，其步驟如下：

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

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

(1)

(2)

(3)

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

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

(4)

4) 反復進行迭代運算，判別聚類結果是否符合要求，如有需要可修改輸入參數，直到獲得理想的聚類結果。

2. 增強型模糊聚類遺傳算法

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

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

(5)

(6)

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

3. 融合增強型模糊聚類GA與ISODATA算法

(1) 適應度函數

模糊聚類問題可由一目標函數Tn(U，P)表示，其最優聚類結果則對應于目標函數的極小值[10]。本文提出的融合算法需要計算個體適應度函數的值。

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

(7)

(8)

(2) 融合遺傳算子

該融合算法需要借助融合遺傳算子找到待優化問題的解，其中包括：

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

(9)

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

4) 解釋算子Te(·)：是解碼算子的擴展，將解碼得到的實數轉換為編碼區間所對應的值

(10)

式中，Ai為Si對應的實數編碼區間中心點；B為編碼區間大小；C為L比特位的二進制碼的全1串所表示的實數值。

(3) 算法步驟

1) 讀入影像數據區域樣本，用Gray碼進行編碼，得到二進制的一組數列。

2) 預設聚類間最小距離為3，結合樣本個體適應度值與傳統ISODATA距離最小原則進行初始分類。

3) 設置進化停止的允許誤差為0.02，借助融合遺傳算子自適應選取操作參數，將已有聚類域與領域像元對比分析，對聚類結果進行分裂、重組等必要的優化。

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

三、試驗研究分析

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

圖1　原圖

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

圖2　ISODATA分類圖

圖3　模糊聚類GA分類圖

圖4　融合法分類圖

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

表1　分類結果統計　(%)

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

表2　分類精度

四、結論

本文提出融合增強型模糊聚類GA與ISODATA算法應用于遙感影像分類，以SPOT-5影像為試驗數據，且分析比較了傳統ISODATA、模糊聚類GA與該融合方法的分類結果。總體可以得出以下結論：

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

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

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

參考文獻：

[1]趙英時．遙感應用分析原理與方法[M]．北京：科學出版社，2003：194-201．

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

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

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

[5]沈照慶，舒寧，龔衍，等．基于改進模糊ISODATA算法的遙感影像非監督聚類研究[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]高新波．模糊聚類分析及其應用[M].西安：西安電子科技大學出版社，2004．

[8]郭云開，張起森．基于廣義夾角的遙感圖像計算機分類方法[J]，中國公路學報，2002，15(2):28-30．

[9]楊紅磊，彭軍還．基于馬爾可夫隨機場的模糊c-均值遙感影像分類[J]．測繪學報，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]尹淑玲，舒寧，劉新華．基于自適應遺傳算法和改進BP算法的遙感影像分類[J]．武漢大學學報：信息科學版，2007，32(3)：201-204．

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

[13]張儷文 ,汪云甲,王行風. 仿射傳播聚類在室內定位指紋庫中的應用研究[J].測繪通報,2014(12): 36-39.

作者簡介：郭云開(1958—)，男，博士，教授，主要研究方向為道路環境遙感評價等。E-mail：guoyunkai226@163.com

基金項目：國家自科科學基金(41471421)；國家自然科學基金(41171397)；貴州省交通科技計劃項目(2014-121-039)

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

中圖分類號：P237

文獻標識碼：B

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

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