潘 欣，孫宏彬

(長春工程學(xué)院計算機技術(shù)與工程學(xué)院，長春130022)

并行的中心點優(yōu)化選取遙感影像聚類算法

潘 欣，孫宏彬

(長春工程學(xué)院計算機技術(shù)與工程學(xué)院，長春130022)

為了解決遙感影像聚類個數(shù)及中心點選取的問題，提出了一種并行的中心矢量優(yōu)化選取的遙感影像聚類算法(PCVOS:Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)。該算法引入模糊評價目標函數(shù)并給出了一種染色體評價機制，提高聚類染色體在類目、空間劃分的多樣性;同時引入MPI(Massage Passing Interface)多進程并行技術(shù)，加快了算法運行速度。實驗結(jié)果表明，相對于傳統(tǒng)的K-Means、ISODATA(Iterative Self Organizing Data Analysis Techniques Algorithm)和ACDE(Automatic Clustering Differential Evolution)算法，PCVOS不但可以獲得更好的聚類效果，而且可以充分利用并行資源加快算法運行速度。

聚類;遙感影像;聚類個數(shù);并行計算;優(yōu)化選擇

0 引 言

遙感影像的聚類是一種根據(jù)影像光譜分布情況及像元點群特征，對影像進行類目自動劃分的方法。在不需要事先輸入樣本情況下僅需少量參數(shù)便可獲得分類結(jié)果，使該方法在遙感技術(shù)應(yīng)用領(lǐng)域發(fā)揮重要作用［1］。目前在遙感影像處理軟件中主要使用K均值算法(K-Means)和迭代自組織數(shù)據(jù)分析算法(ISODATA:Iterative Self Organizing Data Analysis Techniques Algorithm)進行遙感的聚類分析。

為了改進聚類質(zhì)量，很多學(xué)者提出了新的方法:文獻［2-4］引入模糊集理論改進傳統(tǒng)算法應(yīng)對遙感影像中的不確定情況;文獻［5］提出了一種基于Markov模型關(guān)系的模糊影像聚類方法;文獻［6］針對SAR海冰影像多噪聲特點提出了一種模糊層次聚類方法;文獻［7］利用人工免疫技術(shù)引入?yún)?shù)提高了無監(jiān)督聚類質(zhì)量;文獻［8］使用通過遺傳算法改進的模糊C均值聚類算法(FCM)算法進行自動影像聚類;文獻［9］通過元胞自動機改進并引入鄰域判斷改進聚類質(zhì)量。

雖然以上成果改進了遙感影像聚類質(zhì)量，算法實際運用中仍會面臨以下問題:依賴初始化條件，類目個數(shù)需事先指定，且每個類目需對應(yīng)一個初始化的“中心點”，初始狀態(tài)對結(jié)果質(zhì)量有很大影響［10］;易于陷入局部最優(yōu)解，算法難以在有限步驟內(nèi)收斂［11］。由于遙感影像數(shù)據(jù)量龐大、波段數(shù)較多，引起不同中心點個數(shù)、中心點位置的組合也難以窮舉，所以通過試錯法(trial and error)往往達不到較優(yōu)的聚類效果。近年來，利用粒子群優(yōu)化無監(jiān)督分類計算過程在模式識別領(lǐng)域得到了關(guān)注，文獻［12］通過遺傳算法優(yōu)化了K-Means的計算結(jié)果，文獻［13］提出了差別進化(DE:Differential Evolution)算法解決中心點位置選擇問題，文獻［14］通過優(yōu)化算法查找合理聚類個數(shù)。文獻［15］提出了自動差別進化算法(ACDE: Automatic Clustering DE)實現(xiàn)了自適應(yīng)的聚類中心點個數(shù)與位置選取，在ACDE染色體表達方式基礎(chǔ)上很多學(xué)者進一步引入多種優(yōu)化方式實現(xiàn)無監(jiān)督分類［16，17］。雖然ACDE算法可以自主選擇聚類中心，但是，面對遙感影像此類算法會遇到以下問題:1)只有較多染色體才可獲得足夠的多樣性，而遙感影像波段數(shù)較多、數(shù)據(jù)量較大，分析過多染色體會帶來巨大計算負擔(dān);2)遙感影像中各種土地覆被/利用類型的面積大小不一致、邊界的模糊給染色體的合理評價帶來困難。

針對以上問題，筆者提出了一種并行的中心矢量優(yōu)化選取的遙感影像聚類算法(PCVOS:Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)。該算法引入模糊評價目標函數(shù)并給出了一種染色體評價機制，以提高聚類染色體在類目、空間劃分上的多樣性;同時引入MPI (Massage Passage Interface)多進程并行技術(shù)，加快了算法運行速度。實驗表明，相對于傳統(tǒng)的K-Means、ISODATA和ACDE算法，PCVOS不但可以獲得更好的聚類效果，而且可以充分利用并行資源，加快算法運行速度。

1 算法原理

1.1 遙感影像的聚類問題描述

一幅遙感影像可以表達為一個數(shù)據(jù)集Xn×d，其中n為像元數(shù)，d為波段數(shù)。對影像進行聚類的目標是發(fā)現(xiàn)一個劃分C={C1，C2，…，Ck}將數(shù)據(jù)集劃分為K個類目使類目中的差異最小而類目間的差異最大，并且滿足3個關(guān)鍵屬性:

1)任意一個類目不為空;

2)任意兩個劃分的交集為空;

3)任意一個像元一定隸屬于一個類目。

尋找最佳的劃分C是個NP問題，目前遙感影像處理軟件中采取的辦法是預(yù)先輸入中心點個數(shù)范圍，隨機生成初始化中心點并不斷的迭代運行，輸出較佳的聚類結(jié)果;在面對遙感影像數(shù)據(jù)量大、廣泛存在不確定不一致的處理對象時，該方式可能會遺漏較好的劃分模式，并陷入局部最優(yōu)，因此需要引入新方法，尋找較好的聚類劃分。

1.2 聚類質(zhì)量評價和PCVOS算法的染色體表達

PCVOS算法首先需要將遙感影像各個波段進行歸一化，均衡各個波段的數(shù)據(jù)范圍。對于影像的第i像元的第j個波段的值Xi，j，利用公式

可以實現(xiàn)0到1之間的歸一化。其中

T為μj波段j的均值，而σj為波段j的標準差。通過式(1)可將95%總體數(shù)據(jù)［μ-2σ，μ+2σ］范圍內(nèi)的波段數(shù)據(jù)映射到［0，1］區(qū)間內(nèi)，對于超出該范圍的5%的數(shù)據(jù)，使用0或1極值作為結(jié)果。在歸一化基礎(chǔ)上PCVOS引入PBM-index作為衡量聚類質(zhì)量的評價指標［18］

其中

K為劃分的類目數(shù)，E1為將整個數(shù)據(jù)集作為一個類目時式(4)的計算結(jié)果，zk為對應(yīng)類目中心點，Ukj為數(shù)據(jù)集中元素隸屬于某中心的模糊隸屬度。PCVOS算法使用染色體表達其對遙感聚類問題的解，染色的表達如圖1所示。

圖1 PCVOS對染色體的表達Fig.1 The chromosome representation of PCVOS

PCVOS通過PCVOSEvaluation算法可以定量地評價一個染色體影像的聚類結(jié)果，較高的得分對應(yīng)較高的評價質(zhì)量。

1.3 染色體的交叉進化

PCVOS是對傳統(tǒng)ACDE遺傳算法的改進，每個染色體對應(yīng)一個聚類的解，在遺傳的第t代的第k個染色體可表示為，在第t+1代隨機選擇i和j兩個染色體可獲得計算公式［15］

其中Cr在(0，1)區(qū)間為交叉率，F(xiàn)=0．5(1+rand(0，1))為變化的尺度范圍。在此基礎(chǔ)上染色體進化的算法如下。

通過該算法PCVOS的每一代均會試圖對每個染色體交叉計算，如果獲得較好的結(jié)果，則存儲新的染色體;否則，保留舊的染色體。

1.4 PCVOS算法總體流程

在PCVOS算法中每一次迭代均需要調(diào)用PCVONextGenetration進行交叉計算，在計算過程中需要利用PCVOSEvaluation對染色體的聚類質(zhì)量進行評價，而對于評價式(3)需要對每個中心及每個像素進行遍歷，該過程需要較長的計算時間才可獲得結(jié)果，在染色體較多的情況下該過程將十分耗時。因此，需要引入并行化技術(shù)，PCVOS進行并行化聚類的流程如圖2所示。

圖2 PCVOS總體流程Fig.2 The overall flow of PCVOS

由圖2可見，在進行 MPI并行化計算時系統(tǒng)啟動 Rank(0)～Rank(n-1)共 n個進程。Rank(0)負責(zé)管理整個算法的計算流程，讀取遙感影像利用式(1)進行預(yù)處理，將所有數(shù)據(jù)發(fā)送到1～(n-1)進程。Rank(0)初始化一組染色體使PCVOS進入迭代求優(yōu)階段，在該階段Rank(0)將所有染色體發(fā)送至每個進程。每個進程平均分配計算任務(wù)調(diào)用PCVONextGenetration算法，計算并產(chǎn)生下一代染色體并匯總回Rank(0)。Rank(0)對所有染色體進行重新排序，為了保持聚類個數(shù)的多樣性采用如下算法。

如果達到迭代停止條件(如:達到最大迭代次數(shù)、多次迭代沒有獲得更好地染色體)，則向其他進程發(fā)送迭代結(jié)束命令停止其他進程，最后輸出聚類結(jié)果;否則，繼續(xù)將所有染色體發(fā)送所有進程繼續(xù)進行迭代。在迭代求優(yōu)階段，每個進程負責(zé)計算一組染色體的PCVONextGenetration算法結(jié)果，該計算過程是算法中最耗費時間的部分，通過并行計算可以計算任務(wù)分配到各個進程，以加快運算流程。

3 實驗與分析

實驗影像來源為Landsat-8，拍攝地位于吉林省向海國家級自然保護區(qū)北部，截取影像大小為1 024×1 024像素，拍攝時間為2013年8月9日，為該地區(qū)植物生長季，影像共計11個波段，無云。該地區(qū)土地覆被類型主要涵蓋水域、鹽堿地、耕地、草地。影像如圖3所示。

本研究通過C++實現(xiàn)所有算法，實驗環(huán)境為8核心AMD FX 8350+Linux+OpenMPI。為了測試PCVOS算法的并行加速效果，采用100個染色體，分別使用1，2，…，8個進程進行計算，指定求優(yōu)迭代次數(shù)為100次;整個迭代過程需要進行100×100=1萬次PCVONextGenetration算法的調(diào)用。算法進程數(shù)與運行加速的關(guān)系表1所示。PCVOS算法進程數(shù)與運行時間的對比如圖4所示。

圖3 采用5，6，4假彩色合成研究區(qū)影像Fig.3 Study area image with composite of bands 5，6，4

表1 進程數(shù)與運行時間Tab.1 Processes number and run accelerate

圖4 PCVOS算法運行時間與進程的關(guān)系Fig.4 The relation between PCVOS run time and processes number

從表1和圖4可以看到，PCVOS算法可以利用多核心資源加快算法運行。在1個進程時算法需耗時3 023.21 s，隨著更多的進程參與計算其運行時間顯著減少，當(dāng)8個進程參與計算時運行時間達到了最低485.45 s時，達到最高加速比6.23。由于實驗計算機僅有8個核心，在并行時還需要設(shè)計進程交互和同步問題，所以8進程時，并行效率為77.85%。

為驗證PCVOS算法在聚類上的效果，筆者同K-Means算法、ISOData算法、傳統(tǒng)ACDE算法進行了比較:

1)K-Means算法，測試聚類的類目數(shù)為2～10個，采用式(3)作為聚類評價標準，輸出評價指標高的結(jié)果;

2)ACDE算法，指定最大類目個數(shù)為10個，采用算法自帶的DB Index作為評價指標，引入20個染色體進行查找最優(yōu)聚類結(jié)果;

3)ISOData算法，通過類目分層分割自動決定類目數(shù)的聚類算法;

4)PCVOS算法，指定最大類目個數(shù)為10個，引入100個染色體進行查找最優(yōu)聚類結(jié)果。

4種算法的聚類效果如圖5所示。

圖5 聚類效果對比Fig.5 The remote sensing image cluster result comparison

K-Means算法共獲得5個聚束，從圖5a可以看出，大部分地物類型均被區(qū)分出來，水體由于數(shù)據(jù)分布情況的不同被細分為了水體1與水體2，但部分農(nóng)田被誤分為成為草地。ACDE算法共獲得4個中心點，從圖5b可以看出，農(nóng)田被誤分的情況有所改善，但由于DB Index指標對高維度及小團塊支持不佳，所以大量的水體2被誤分，鹽堿地面積也有所擴大。ISODATA算法共獲得7個聚束，從圖5c可以看出，新加入了草地2和耕地2解決過渡問題，但部分鹽堿地被誤分為了草地2，而且過多類目引起聚類效果交互混亂。圖5d對應(yīng)PCVOS算法，獲得了6個類目，較圖5a～圖5c中交替出現(xiàn)錯誤的部分均得到了有效的修正，獲得了更為合理的聚類效果。筆者通過人工識別選取大量樣本，每種地物類型隨機選取500個樣本作為測試樣本，對于細分類目(如水體分為水體1和水體2)統(tǒng)一作為一種類目進行精度分析。4種算法的分類精度對比如表2所示。

表2 4種算法的混淆矩陣和精度的對比Tab.2 The confusion matrix and accuracy of four algorithms

K-Mean算法耕地誤分現(xiàn)象較為嚴重;ACDE算法獲得了最低的聚類精度(80%)，Kappa=73%，雖然其類目個數(shù)與目標的類目個數(shù)一致，但相對較小的團塊被大團塊覆蓋，如水體2被鹽堿地覆蓋，引起部水體和鹽堿地樣本被錯誤劃分，進而降低的分類精度。ISODATA雖然聚類效果圖質(zhì)量較低，但受益于較多類目數(shù)使其獲得了第2高的分類精度，達到了精度為84.6%Kappa=79.5%;PCVOS算法達到了最高的精度為88.2%，Kappa為84.3%，從結(jié)果可以看出，在通過MCVOS算法查找優(yōu)化解的過程中，由于使用較多染色體可以獲得更加平衡的聚類效果。

4 結(jié) 語

針對遙感影像在聚類過程中所面臨的數(shù)據(jù)量大、計算量大、不確定不一致等問題，筆者提出了一種并行的中心矢量優(yōu)化選取的遙感影像聚類算法(PCVOS)。該算法引入模糊評價目標函數(shù)并給出了一種染色體評價機制，以提高聚類染色體在類目、空間劃分上的多樣性;同時引入MPI(Massage Passage Interface)多進程并行技術(shù)，加快了算法運行速度。實驗表明本算法可以充分利用多核心計算環(huán)境大大加快算法運行速度，同時獲得較好的聚類質(zhì)量。

［1］JENSEN JR.Introductory Digital Image Processing，a Remote Sensing Perspective［M］.Upper Saddle River:Prentice Hall，2004.

［2］ZHONG Y，ZHANG L，HUANG B，et al.An Unsupervised Artificial Immune Classifier for Multi/Hyperspectral Remote Sensing Imagery［J］.IEEE Transactions on Geoscience and Remote Sensing，2006，44(1):420-431.

［3］YU J，GUO P，CHEN P，et al.Remote Sensing Image Classification Based on Improved Fuzzy C-Means［J］.Geo-Spatial Information Science，2008，11(1):2-10.

［4］JIAO L，GONG M，WANG S，et al.Natural and Remote Sensing Image Segmentation Using Memetic Computing［J］.IEEE Computational Intelligence Magazine，2010，5(1):78-91.

［5］張路，廖明生.一種顧及上下文的遙感影像模糊聚類［J］.遙感學(xué)報，2006，10(1):58-65.ZHANG Lu，LIAOMingsheng.Contextual Fuzzy Clustering of Remote Sensing Imagery［J］.Journalof Remote Sensing，2006，10(1):58-65.

［6］于波，孟俊敏，張晰，等.結(jié)合凝聚層次聚類的極化SAR海冰分割［J］.遙感學(xué)報，2013，17(4):887-904. YU Bo，MENG Junmin，ZHANG Xi，et al.Segmentation Method for Agglomerative Hierarchical-Based Sea Ice Types Using Polarimetric SAR Data［J］.Journal of Remote Sensing，2013，17(4):887-904.

［7］ZHONG Y，ZHANG L，GONGW.Unsupervised Remote Sensing Image Classification Using an Artificial Immune Network［J］.International Journal of Remote Sensing，2011，32(19):5461-5483.

［8］張帥，鐘燕飛，張良培.自適應(yīng)差分進化的遙感影像自動模糊聚類方法［J］.測繪學(xué)報，2013，42(2):239-246. ZHANG Shuai，ZHONG Yanfei，ZHANG Liangpei.An Automatic Fuzzy Clustering Algorithm Based on Self Adaptive Differential Evolution for Remote Sensing Image［J］.Acta Geodaetica et Cartographica Sinica，2013，42(2):239-246.

［9］HE Q，DAI L，ZHANGW，WANG H，et al.An Unsupervised Classifier for Remote-Sensing Imagery Based on Improved Cellular Automata［J］.International Journal of Remote Sensing，2013，34(21):7821-7837.

［10］HALKIDI M，BATISTAKIS Y，VAZIRGIANNIS M.On Clustering Validation Technique［J］.Journal of Intelligent Information Systems，2001，17(2):107-145.

［11］GHOSH A，MISHRA N S，GHOSH S.Fuzzy Clustering Algorithms for Unsupervised Change Detection in Remote Sensing Images［J］.Information Sciences，2011，181(6):699-715.

［12］KRISHNA K，MURTY M N.Genetic K-Means Algorithm［J］.IEEE Transactions on Systems，1999，29(3):433-439.

［13］STORN R，PRICE K.Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces［J］.Journal of Global Optimization，1997，11(4):341-359.

［14］ROSENBERGER C，CHEHDI K.Unsupervised Clustering Method with Optimal Estimation of the Number of Clusters: Application to Image Segmentation［C］∥Process of International Conference on Pattern Recognition(ICPR).Barcelona: IEEE Press，2000，1:656-659.

［15］DASS，ABRAHAM A，KONAR A.Automatic Clustering Using an Improved Differential Evolution Algorithm［J］.IEEE Transactions on Systems，2008，38(1):218-237.

［16］RASHEDI E，NEZAMABADI-POUR H，SARYAZDI SAEID.GSA:A Gravitational Search Algorithm［J］.Information Sciences，2009，179(1):2232-2248.

［17］LIU R，CHEN Y，JIAO L，et al.A Particle Swarm Optimization Based Simultaneous Learning Framework for Clustering and Classification［J］.Pattern Recognition，2014，47(6):2143-2152.

［18］PAKHIRA M K，BANDYOPADHYAY S，MAULIK U.Validity Index for Crisp and Fuzzy Clusters［J］.Pattern Recognition，2004，37(3):487-501.

(責(zé)任編輯:劉東亮)

Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster

PAN Xin，SUN Hongbin

(School of Computer Project＆Technology，Changchun Institute of Technology，Changchun 130022，China)

In order to solve the problem of selecting the clustering number of remote sensing images and positions of center points，Proposed a PCVOS(Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)which introduces fuzzy evaluation of the objective function and put forward an evaluation mechanism of chromosomes to improve the diversity of category and space division of clustering chromosomes is proposed.The MPImulti-process parallel technology is simultaneously introduced to speed up the running speed of the algorithm.The experiment shows that compared with the traditional K-Means，ISODATA(Iterative Self Organizing Data Analysis Techniques Algorithm)and ACDE(Automatic Clustering Differential Evolution) algorithm，PCVOS can obtain a better clustering effect，and make full use of parallel resources to speed up the running speed of the algorithm.

cluster;remote sensing image;category number;parallel computing;optimized selection

TP751

A

1671-5896(2015)04-0441-08

2014-12-01

國家自然科學(xué)基金青年基金資助項目(41101384);吉林省教育廳基金資助項目(2014327);吉林省科技廳基金資助項目(20130101179JC-23;20120332);吉林省發(fā)改委基金資助項目(2013C048);吉林省科技廳國際合作基金資助項目(20140105)

潘欣(1978— )，男，長春人，長春工程學(xué)院副教授，碩士生導(dǎo)師，主要從事遙感數(shù)據(jù)應(yīng)用研究，(Tel)86-13844908223 (E-mail)panxinpc@163.com。