潘 欣,孫宏彬
(長(zhǎng)春工程學(xué)院計(jì)算機(jī)技術(shù)與工程學(xué)院,長(zhǎng)春130022)
并行的中心點(diǎn)優(yōu)化選取遙感影像聚類算法
潘 欣,孫宏彬
(長(zhǎng)春工程學(xué)院計(jì)算機(jī)技術(shù)與工程學(xué)院,長(zhǎng)春130022)
為了解決遙感影像聚類個(gè)數(shù)及中心點(diǎn)選取的問題,提出了一種并行的中心矢量?jī)?yōu)化選取的遙感影像聚類算法(PCVOS:Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)。該算法引入模糊評(píng)價(jià)目標(biāo)函數(shù)并給出了一種染色體評(píng)價(jià)機(jī)制,提高聚類染色體在類目、空間劃分的多樣性;同時(shí)引入MPI(Massage Passing Interface)多進(jìn)程并行技術(shù),加快了算法運(yùn)行速度。實(shí)驗(yàn)結(jié)果表明,相對(duì)于傳統(tǒng)的K-Means、ISODATA(Iterative Self Organizing Data Analysis Techniques Algorithm)和ACDE(Automatic Clustering Differential Evolution)算法,PCVOS不但可以獲得更好的聚類效果,而且可以充分利用并行資源加快算法運(yùn)行速度。
聚類;遙感影像;聚類個(gè)數(shù);并行計(jì)算;優(yōu)化選擇
遙感影像的聚類是一種根據(jù)影像光譜分布情況及像元點(diǎn)群特征,對(duì)影像進(jìn)行類目自動(dòng)劃分的方法。在不需要事先輸入樣本情況下僅需少量參數(shù)便可獲得分類結(jié)果,使該方法在遙感技術(shù)應(yīng)用領(lǐng)域發(fā)揮重要作用[1]。目前在遙感影像處理軟件中主要使用K均值算法(K-Means)和迭代自組織數(shù)據(jù)分析算法(ISODATA:Iterative Self Organizing Data Analysis Techniques Algorithm)進(jìn)行遙感的聚類分析。
為了改進(jìn)聚類質(zhì)量,很多學(xué)者提出了新的方法:文獻(xiàn)[2-4]引入模糊集理論改進(jìn)傳統(tǒng)算法應(yīng)對(duì)遙感影像中的不確定情況;文獻(xiàn)[5]提出了一種基于Markov模型關(guān)系的模糊影像聚類方法;文獻(xiàn)[6]針對(duì)SAR海冰影像多噪聲特點(diǎn)提出了一種模糊層次聚類方法;文獻(xiàn)[7]利用人工免疫技術(shù)引入?yún)?shù)提高了無監(jiān)督聚類質(zhì)量;文獻(xiàn)[8]使用通過遺傳算法改進(jìn)的模糊C均值聚類算法(FCM)算法進(jìn)行自動(dòng)影像聚類;文獻(xiàn)[9]通過元胞自動(dòng)機(jī)改進(jìn)并引入鄰域判斷改進(jìn)聚類質(zhì)量。
雖然以上成果改進(jìn)了遙感影像聚類質(zhì)量,算法實(shí)際運(yùn)用中仍會(huì)面臨以下問題:依賴初始化條件,類目個(gè)數(shù)需事先指定,且每個(gè)類目需對(duì)應(yīng)一個(gè)初始化的“中心點(diǎn)”,初始狀態(tài)對(duì)結(jié)果質(zhì)量有很大影響[10];易于陷入局部最優(yōu)解,算法難以在有限步驟內(nèi)收斂[11]。由于遙感影像數(shù)據(jù)量龐大、波段數(shù)較多,引起不同中心點(diǎn)個(gè)數(shù)、中心點(diǎn)位置的組合也難以窮舉,所以通過試錯(cuò)法(trial and error)往往達(dá)不到較優(yōu)的聚類效果。近年來,利用粒子群優(yōu)化無監(jiān)督分類計(jì)算過程在模式識(shí)別領(lǐng)域得到了關(guān)注,文獻(xiàn)[12]通過遺傳算法優(yōu)化了K-Means的計(jì)算結(jié)果,文獻(xiàn)[13]提出了差別進(jìn)化(DE:Differential Evolution)算法解決中心點(diǎn)位置選擇問題,文獻(xiàn)[14]通過優(yōu)化算法查找合理聚類個(gè)數(shù)。文獻(xiàn)[15]提出了自動(dòng)差別進(jìn)化算法(ACDE: Automatic Clustering DE)實(shí)現(xiàn)了自適應(yīng)的聚類中心點(diǎn)個(gè)數(shù)與位置選取,在ACDE染色體表達(dá)方式基礎(chǔ)上很多學(xué)者進(jìn)一步引入多種優(yōu)化方式實(shí)現(xiàn)無監(jiān)督分類[16,17]。雖然ACDE算法可以自主選擇聚類中心,但是,面對(duì)遙感影像此類算法會(huì)遇到以下問題:1)只有較多染色體才可獲得足夠的多樣性,而遙感影像波段數(shù)較多、數(shù)據(jù)量較大,分析過多染色體會(huì)帶來巨大計(jì)算負(fù)擔(dān);2)遙感影像中各種土地覆被/利用類型的面積大小不一致、邊界的模糊給染色體的合理評(píng)價(jià)帶來困難。
針對(duì)以上問題,筆者提出了一種并行的中心矢量?jī)?yōu)化選取的遙感影像聚類算法(PCVOS:Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)。該算法引入模糊評(píng)價(jià)目標(biāo)函數(shù)并給出了一種染色體評(píng)價(jià)機(jī)制,以提高聚類染色體在類目、空間劃分上的多樣性;同時(shí)引入MPI (Massage Passage Interface)多進(jìn)程并行技術(shù),加快了算法運(yùn)行速度。實(shí)驗(yàn)表明,相對(duì)于傳統(tǒng)的K-Means、ISODATA和ACDE算法,PCVOS不但可以獲得更好的聚類效果,而且可以充分利用并行資源,加快算法運(yùn)行速度。
1.1 遙感影像的聚類問題描述
一幅遙感影像可以表達(dá)為一個(gè)數(shù)據(jù)集Xn×d,其中n為像元數(shù),d為波段數(shù)。對(duì)影像進(jìn)行聚類的目標(biāo)是發(fā)現(xiàn)一個(gè)劃分C={C1,C2,…,Ck}將數(shù)據(jù)集劃分為K個(gè)類目使類目中的差異最小而類目間的差異最大,并且滿足3個(gè)關(guān)鍵屬性:
1)任意一個(gè)類目不為空;
2)任意兩個(gè)劃分的交集為空;
3)任意一個(gè)像元一定隸屬于一個(gè)類目。
尋找最佳的劃分C是個(gè)NP問題,目前遙感影像處理軟件中采取的辦法是預(yù)先輸入中心點(diǎn)個(gè)數(shù)范圍,隨機(jī)生成初始化中心點(diǎn)并不斷的迭代運(yùn)行,輸出較佳的聚類結(jié)果;在面對(duì)遙感影像數(shù)據(jù)量大、廣泛存在不確定不一致的處理對(duì)象時(shí),該方式可能會(huì)遺漏較好的劃分模式,并陷入局部最優(yōu),因此需要引入新方法,尋找較好的聚類劃分。
1.2 聚類質(zhì)量評(píng)價(jià)和PCVOS算法的染色體表達(dá)
PCVOS算法首先需要將遙感影像各個(gè)波段進(jìn)行歸一化,均衡各個(gè)波段的數(shù)據(jù)范圍。對(duì)于影像的第i像元的第j個(gè)波段的值Xi,j,利用公式
可以實(shí)現(xiàn)0到1之間的歸一化。其中
T為μj波段j的均值,而σj為波段j的標(biāo)準(zhǔn)差。通過式(1)可將95%總體數(shù)據(jù)[μ-2σ,μ+2σ]范圍內(nèi)的波段數(shù)據(jù)映射到[0,1]區(qū)間內(nèi),對(duì)于超出該范圍的5%的數(shù)據(jù),使用0或1極值作為結(jié)果。在歸一化基礎(chǔ)上PCVOS引入PBM-index作為衡量聚類質(zhì)量的評(píng)價(jià)指標(biāo)[18]
其中
K為劃分的類目數(shù),E1為將整個(gè)數(shù)據(jù)集作為一個(gè)類目時(shí)式(4)的計(jì)算結(jié)果,zk為對(duì)應(yīng)類目中心點(diǎn),Ukj為數(shù)據(jù)集中元素隸屬于某中心的模糊隸屬度。PCVOS算法使用染色體表達(dá)其對(duì)遙感聚類問題的解,染色的表達(dá)如圖1所示。
圖1 PCVOS對(duì)染色體的表達(dá)Fig.1 The chromosome representation of PCVOS
PCVOS通過PCVOSEvaluation算法可以定量地評(píng)價(jià)一個(gè)染色體影像的聚類結(jié)果,較高的得分對(duì)應(yīng)較高的評(píng)價(jià)質(zhì)量。
1.3 染色體的交叉進(jìn)化
PCVOS是對(duì)傳統(tǒng)ACDE遺傳算法的改進(jìn),每個(gè)染色體對(duì)應(yīng)一個(gè)聚類的解,在遺傳的第t代的第k個(gè)染色體可表示為,在第t+1代隨機(jī)選擇i和j兩個(gè)染色體可獲得計(jì)算公式[15]
其中Cr在(0,1)區(qū)間為交叉率,F(xiàn)=0.5(1+rand(0,1))為變化的尺度范圍。在此基礎(chǔ)上染色體進(jìn)化的算法如下。
通過該算法PCVOS的每一代均會(huì)試圖對(duì)每個(gè)染色體交叉計(jì)算,如果獲得較好的結(jié)果,則存儲(chǔ)新的染色體;否則,保留舊的染色體。
1.4 PCVOS算法總體流程
在PCVOS算法中每一次迭代均需要調(diào)用PCVONextGenetration進(jìn)行交叉計(jì)算,在計(jì)算過程中需要利用PCVOSEvaluation對(duì)染色體的聚類質(zhì)量進(jìn)行評(píng)價(jià),而對(duì)于評(píng)價(jià)式(3)需要對(duì)每個(gè)中心及每個(gè)像素進(jìn)行遍歷,該過程需要較長(zhǎng)的計(jì)算時(shí)間才可獲得結(jié)果,在染色體較多的情況下該過程將十分耗時(shí)。因此,需要引入并行化技術(shù),PCVOS進(jìn)行并行化聚類的流程如圖2所示。
圖2 PCVOS總體流程Fig.2 The overall flow of PCVOS
由圖2可見,在進(jìn)行 MPI并行化計(jì)算時(shí)系統(tǒng)啟動(dòng) Rank(0)~Rank(n-1)共 n個(gè)進(jìn)程。Rank(0)負(fù)責(zé)管理整個(gè)算法的計(jì)算流程,讀取遙感影像利用式(1)進(jìn)行預(yù)處理,將所有數(shù)據(jù)發(fā)送到1~(n-1)進(jìn)程。Rank(0)初始化一組染色體使PCVOS進(jìn)入迭代求優(yōu)階段,在該階段Rank(0)將所有染色體發(fā)送至每個(gè)進(jìn)程。每個(gè)進(jìn)程平均分配計(jì)算任務(wù)調(diào)用PCVONextGenetration算法,計(jì)算并產(chǎn)生下一代染色體并匯總回Rank(0)。Rank(0)對(duì)所有染色體進(jìn)行重新排序,為了保持聚類個(gè)數(shù)的多樣性采用如下算法。
如果達(dá)到迭代停止條件(如:達(dá)到最大迭代次數(shù)、多次迭代沒有獲得更好地染色體),則向其他進(jìn)程發(fā)送迭代結(jié)束命令停止其他進(jìn)程,最后輸出聚類結(jié)果;否則,繼續(xù)將所有染色體發(fā)送所有進(jìn)程繼續(xù)進(jìn)行迭代。在迭代求優(yōu)階段,每個(gè)進(jìn)程負(fù)責(zé)計(jì)算一組染色體的PCVONextGenetration算法結(jié)果,該計(jì)算過程是算法中最耗費(fèi)時(shí)間的部分,通過并行計(jì)算可以計(jì)算任務(wù)分配到各個(gè)進(jìn)程,以加快運(yùn)算流程。
實(shí)驗(yàn)影像來源為L(zhǎng)andsat-8,拍攝地位于吉林省向海國(guó)家級(jí)自然保護(hù)區(qū)北部,截取影像大小為1 024×1 024像素,拍攝時(shí)間為2013年8月9日,為該地區(qū)植物生長(zhǎng)季,影像共計(jì)11個(gè)波段,無云。該地區(qū)土地覆被類型主要涵蓋水域、鹽堿地、耕地、草地。影像如圖3所示。
本研究通過C++實(shí)現(xiàn)所有算法,實(shí)驗(yàn)環(huán)境為8核心AMD FX 8350+Linux+OpenMPI。為了測(cè)試PCVOS算法的并行加速效果,采用100個(gè)染色體,分別使用1,2,…,8個(gè)進(jìn)程進(jìn)行計(jì)算,指定求優(yōu)迭代次數(shù)為100次;整個(gè)迭代過程需要進(jìn)行100×100=1萬次PCVONextGenetration算法的調(diào)用。算法進(jìn)程數(shù)與運(yùn)行加速的關(guān)系表1所示。PCVOS算法進(jìn)程數(shù)與運(yùn)行時(shí)間的對(duì)比如圖4所示。
圖3 采用5,6,4假彩色合成研究區(qū)影像Fig.3 Study area image with composite of bands 5,6,4
表1 進(jìn)程數(shù)與運(yùn)行時(shí)間Tab.1 Processes number and run accelerate
圖4 PCVOS算法運(yùn)行時(shí)間與進(jìn)程的關(guān)系Fig.4 The relation between PCVOS run time and processes number
從表1和圖4可以看到,PCVOS算法可以利用多核心資源加快算法運(yùn)行。在1個(gè)進(jìn)程時(shí)算法需耗時(shí)3 023.21 s,隨著更多的進(jìn)程參與計(jì)算其運(yùn)行時(shí)間顯著減少,當(dāng)8個(gè)進(jìn)程參與計(jì)算時(shí)運(yùn)行時(shí)間達(dá)到了最低485.45 s時(shí),達(dá)到最高加速比6.23。由于實(shí)驗(yàn)計(jì)算機(jī)僅有8個(gè)核心,在并行時(shí)還需要設(shè)計(jì)進(jìn)程交互和同步問題,所以8進(jìn)程時(shí),并行效率為77.85%。
為驗(yàn)證PCVOS算法在聚類上的效果,筆者同K-Means算法、ISOData算法、傳統(tǒng)ACDE算法進(jìn)行了比較:
1)K-Means算法,測(cè)試聚類的類目數(shù)為2~10個(gè),采用式(3)作為聚類評(píng)價(jià)標(biāo)準(zhǔn),輸出評(píng)價(jià)指標(biāo)高的結(jié)果;
2)ACDE算法,指定最大類目個(gè)數(shù)為10個(gè),采用算法自帶的DB Index作為評(píng)價(jià)指標(biāo),引入20個(gè)染色體進(jìn)行查找最優(yōu)聚類結(jié)果;
3)ISOData算法,通過類目分層分割自動(dòng)決定類目數(shù)的聚類算法;
4)PCVOS算法,指定最大類目個(gè)數(shù)為10個(gè),引入100個(gè)染色體進(jìn)行查找最優(yōu)聚類結(jié)果。
4種算法的聚類效果如圖5所示。
圖5 聚類效果對(duì)比Fig.5 The remote sensing image cluster result comparison
K-Means算法共獲得5個(gè)聚束,從圖5a可以看出,大部分地物類型均被區(qū)分出來,水體由于數(shù)據(jù)分布情況的不同被細(xì)分為了水體1與水體2,但部分農(nóng)田被誤分為成為草地。ACDE算法共獲得4個(gè)中心點(diǎn),從圖5b可以看出,農(nóng)田被誤分的情況有所改善,但由于DB Index指標(biāo)對(duì)高維度及小團(tuán)塊支持不佳,所以大量的水體2被誤分,鹽堿地面積也有所擴(kuò)大。ISODATA算法共獲得7個(gè)聚束,從圖5c可以看出,新加入了草地2和耕地2解決過渡問題,但部分鹽堿地被誤分為了草地2,而且過多類目引起聚類效果交互混亂。圖5d對(duì)應(yīng)PCVOS算法,獲得了6個(gè)類目,較圖5a~圖5c中交替出現(xiàn)錯(cuò)誤的部分均得到了有效的修正,獲得了更為合理的聚類效果。筆者通過人工識(shí)別選取大量樣本,每種地物類型隨機(jī)選取500個(gè)樣本作為測(cè)試樣本,對(duì)于細(xì)分類目(如水體分為水體1和水體2)統(tǒng)一作為一種類目進(jìn)行精度分析。4種算法的分類精度對(duì)比如表2所示。
表2 4種算法的混淆矩陣和精度的對(duì)比Tab.2 The confusion matrix and accuracy of four algorithms
K-Mean算法耕地誤分現(xiàn)象較為嚴(yán)重;ACDE算法獲得了最低的聚類精度(80%),Kappa=73%,雖然其類目個(gè)數(shù)與目標(biāo)的類目個(gè)數(shù)一致,但相對(duì)較小的團(tuán)塊被大團(tuán)塊覆蓋,如水體2被鹽堿地覆蓋,引起部水體和鹽堿地樣本被錯(cuò)誤劃分,進(jìn)而降低的分類精度。ISODATA雖然聚類效果圖質(zhì)量較低,但受益于較多類目數(shù)使其獲得了第2高的分類精度,達(dá)到了精度為84.6%Kappa=79.5%;PCVOS算法達(dá)到了最高的精度為88.2%,Kappa為84.3%,從結(jié)果可以看出,在通過MCVOS算法查找優(yōu)化解的過程中,由于使用較多染色體可以獲得更加平衡的聚類效果。
針對(duì)遙感影像在聚類過程中所面臨的數(shù)據(jù)量大、計(jì)算量大、不確定不一致等問題,筆者提出了一種并行的中心矢量?jī)?yōu)化選取的遙感影像聚類算法(PCVOS)。該算法引入模糊評(píng)價(jià)目標(biāo)函數(shù)并給出了一種染色體評(píng)價(jià)機(jī)制,以提高聚類染色體在類目、空間劃分上的多樣性;同時(shí)引入MPI(Massage Passage Interface)多進(jìn)程并行技術(shù),加快了算法運(yùn)行速度。實(shí)驗(yàn)表明本算法可以充分利用多核心計(jì)算環(huán)境大大加快算法運(yùn)行速度,同時(shí)獲得較好的聚類質(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é)報(bào),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é)報(bào),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ìn)化的遙感影像自動(dòng)模糊聚類方法[J].測(cè)繪學(xué)報(bào),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
國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目(41101384);吉林省教育廳基金資助項(xiàng)目(2014327);吉林省科技廳基金資助項(xiàng)目(20130101179JC-23;20120332);吉林省發(fā)改委基金資助項(xiàng)目(2013C048);吉林省科技廳國(guó)際合作基金資助項(xiàng)目(20140105)
潘欣(1978— ),男,長(zhǎng)春人,長(zhǎng)春工程學(xué)院副教授,碩士生導(dǎo)師,主要從事遙感數(shù)據(jù)應(yīng)用研究,(Tel)86-13844908223 (E-mail)panxinpc@163.com。