并行的中心点优化选取遥感影像聚类算法

潘 欣，孙宏彬

(长春工程学院计算机技术与工程学院，长春130022)

并行的中心点优化选取遥感影像聚类算法

潘 欣，孙宏彬

(长春工程学院计算机技术与工程学院，长春130022)

为了解决遥感影像聚类个数及中心点选取的问题，提出了一种并行的中心矢量优化选取的遥感影像聚类算法(PCVOS:Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)。该算法引入模糊评价目标函数并给出了一种染色体评价机制，提高聚类染色体在类目、空间划分的多样性;同时引入MPI(Massage Passing Interface)多进程并行技术，加快了算法运行速度。实验结果表明，相对于传统的K-Means、ISODATA(Iterative Self Organizing Data Analysis Techniques Algorithm)和ACDE(Automatic Clustering Differential Evolution)算法，PCVOS不但可以获得更好的聚类效果，而且可以充分利用并行资源加快算法运行速度。

聚类;遥感影像;聚类个数;并行计算;优化选择

0 引 言

遥感影像的聚类是一种根据影像光谱分布情况及像元点群特征，对影像进行类目自动划分的方法。在不需要事先输入样本情况下仅需少量参数便可获得分类结果，使该方法在遥感技术应用领域发挥重要作用［1］。目前在遥感影像处理软件中主要使用K均值算法(K-Means)和迭代自组织数据分析算法(ISODATA:Iterative Self Organizing Data Analysis Techniques Algorithm)进行遥感的聚类分析。

为了改进聚类质量，很多学者提出了新的方法:文献［2-4］引入模糊集理论改进传统算法应对遥感影像中的不确定情况;文献［5］提出了一种基于Markov模型关系的模糊影像聚类方法;文献［6］针对SAR海冰影像多噪声特点提出了一种模糊层次聚类方法;文献［7］利用人工免疫技术引入参数提高了无监督聚类质量;文献［8］使用通过遗传算法改进的模糊C均值聚类算法(FCM)算法进行自动影像聚类;文献［9］通过元胞自动机改进并引入邻域判断改进聚类质量。

虽然以上成果改进了遥感影像聚类质量，算法实际运用中仍会面临以下问题:依赖初始化条件，类目个数需事先指定，且每个类目需对应一个初始化的“中心点”，初始状态对结果质量有很大影响［10］;易于陷入局部最优解，算法难以在有限步骤内收敛［11］。由于遥感影像数据量庞大、波段数较多，引起不同中心点个数、中心点位置的组合也难以穷举，所以通过试错法(trial and error)往往达不到较优的聚类效果。近年来，利用粒子群优化无监督分类计算过程在模式识别领域得到了关注，文献［12］通过遗传算法优化了K-Means的计算结果，文献［13］提出了差别进化(DE:Differential Evolution)算法解决中心点位置选择问题，文献［14］通过优化算法查找合理聚类个数。文献［15］提出了自动差别进化算法(ACDE: Automatic Clustering DE)实现了自适应的聚类中心点个数与位置选取，在ACDE染色体表达方式基础上很多学者进一步引入多种优化方式实现无监督分类［16，17］。虽然ACDE算法可以自主选择聚类中心，但是，面对遥感影像此类算法会遇到以下问题:1)只有较多染色体才可获得足够的多样性，而遥感影像波段数较多、数据量较大，分析过多染色体会带来巨大计算负担;2)遥感影像中各种土地覆被/利用类型的面积大小不一致、边界的模糊给染色体的合理评价带来困难。

针对以上问题，笔者提出了一种并行的中心矢量优化选取的遥感影像聚类算法(PCVOS:Parallelized Center Vector Optimized Selection Algorithm for Remote Sensing Image Cluster)。该算法引入模糊评价目标函数并给出了一种染色体评价机制，以提高聚类染色体在类目、空间划分上的多样性;同时引入MPI (Massage Passage Interface)多进程并行技术，加快了算法运行速度。实验表明，相对于传统的K-Means、ISODATA和ACDE算法，PCVOS不但可以获得更好的聚类效果，而且可以充分利用并行资源，加快算法运行速度。

1 算法原理

1.1 遥感影像的聚类问题描述

一幅遥感影像可以表达为一个数据集Xn×d，其中n为像元数，d为波段数。对影像进行聚类的目标是发现一个划分C={C1，C2，…，Ck}将数据集划分为K个类目使类目中的差异最小而类目间的差异最大，并且满足3个关键属性:

1)任意一个类目不为空;

2)任意两个划分的交集为空;

3)任意一个像元一定隶属于一个类目。

寻找最佳的划分C是个NP问题，目前遥感影像处理软件中采取的办法是预先输入中心点个数范围，随机生成初始化中心点并不断的迭代运行，输出较佳的聚类结果;在面对遥感影像数据量大、广泛存在不确定不一致的处理对象时，该方式可能会遗漏较好的划分模式，并陷入局部最优，因此需要引入新方法，寻找较好的聚类划分。

1.2 聚类质量评价和PCVOS算法的染色体表达

PCVOS算法首先需要将遥感影像各个波段进行归一化，均衡各个波段的数据范围。对于影像的第i像元的第j个波段的值Xi，j，利用公式

可以实现0到1之间的归一化。其中

T为μj波段j的均值，而σj为波段j的标准差。通过式(1)可将95%总体数据［μ-2σ，μ+2σ］范围内的波段数据映射到［0，1］区间内，对于超出该范围的5%的数据，使用0或1极值作为结果。在归一化基础上PCVOS引入PBM-index作为衡量聚类质量的评价指标［18］

其中

K为划分的类目数，E1为将整个数据集作为一个类目时式(4)的计算结果，zk为对应类目中心点，Ukj为数据集中元素隶属于某中心的模糊隶属度。PCVOS算法使用染色体表达其对遥感聚类问题的解，染色的表达如图1所示。

图1 PCVOS对染色体的表达Fig.1 The chromosome representation of PCVOS

PCVOS通过PCVOSEvaluation算法可以定量地评价一个染色体影像的聚类结果，较高的得分对应较高的评价质量。

1.3 染色体的交叉进化

PCVOS是对传统ACDE遗传算法的改进，每个染色体对应一个聚类的解，在遗传的第t代的第k个染色体可表示为，在第t+1代随机选择i和j两个染色体可获得计算公式［15］

其中Cr在(0，1)区间为交叉率，F=0．5(1+rand(0，1))为变化的尺度范围。在此基础上染色体进化的算法如下。

通过该算法PCVOS的每一代均会试图对每个染色体交叉计算，如果获得较好的结果，则存储新的染色体;否则，保留旧的染色体。

1.4 PCVOS算法总体流程

在PCVOS算法中每一次迭代均需要调用PCVONextGenetration进行交叉计算，在计算过程中需要利用PCVOSEvaluation对染色体的聚类质量进行评价，而对于评价式(3)需要对每个中心及每个像素进行遍历，该过程需要较长的计算时间才可获得结果，在染色体较多的情况下该过程将十分耗时。因此，需要引入并行化技术，PCVOS进行并行化聚类的流程如图2所示。

图2 PCVOS总体流程Fig.2 The overall flow of PCVOS

由图2可见，在进行 MPI并行化计算时系统启动 Rank(0)～Rank(n-1)共 n个进程。Rank(0)负责管理整个算法的计算流程，读取遥感影像利用式(1)进行预处理，将所有数据发送到1～(n-1)进程。Rank(0)初始化一组染色体使PCVOS进入迭代求优阶段，在该阶段Rank(0)将所有染色体发送至每个进程。每个进程平均分配计算任务调用PCVONextGenetration算法，计算并产生下一代染色体并汇总回Rank(0)。Rank(0)对所有染色体进行重新排序，为了保持聚类个数的多样性采用如下算法。

如果达到迭代停止条件(如:达到最大迭代次数、多次迭代没有获得更好地染色体)，则向其他进程发送迭代结束命令停止其他进程，最后输出聚类结果;否则，继续将所有染色体发送所有进程继续进行迭代。在迭代求优阶段，每个进程负责计算一组染色体的PCVONextGenetration算法结果，该计算过程是算法中最耗费时间的部分，通过并行计算可以计算任务分配到各个进程，以加快运算流程。

3 实验与分析

实验影像来源为Landsat-8，拍摄地位于吉林省向海国家级自然保护区北部，截取影像大小为1 024×1 024像素，拍摄时间为2013年8月9日，为该地区植物生长季，影像共计11个波段，无云。该地区土地覆被类型主要涵盖水域、盐碱地、耕地、草地。影像如图3所示。

本研究通过C++实现所有算法，实验环境为8核心AMD FX 8350+Linux+OpenMPI。为了测试PCVOS算法的并行加速效果，采用100个染色体，分别使用1，2，…，8个进程进行计算，指定求优迭代次数为100次;整个迭代过程需要进行100×100=1万次PCVONextGenetration算法的调用。算法进程数与运行加速的关系表1所示。PCVOS算法进程数与运行时间的对比如图4所示。

图3 采用5，6，4假彩色合成研究区影像Fig.3 Study area image with composite of bands 5，6，4

表1 进程数与运行时间Tab.1 Processes number and run accelerate

图4 PCVOS算法运行时间与进程的关系Fig.4 The relation between PCVOS run time and processes number

从表1和图4可以看到，PCVOS算法可以利用多核心资源加快算法运行。在1个进程时算法需耗时3 023.21 s，随着更多的进程参与计算其运行时间显著减少，当8个进程参与计算时运行时间达到了最低485.45 s时，达到最高加速比6.23。由于实验计算机仅有8个核心，在并行时还需要设计进程交互和同步问题，所以8进程时，并行效率为77.85%。

为验证PCVOS算法在聚类上的效果，笔者同K-Means算法、ISOData算法、传统ACDE算法进行了比较:

1)K-Means算法，测试聚类的类目数为2～10个，采用式(3)作为聚类评价标准，输出评价指标高的结果;

2)ACDE算法，指定最大类目个数为10个，采用算法自带的DB Index作为评价指标，引入20个染色体进行查找最优聚类结果;

3)ISOData算法，通过类目分层分割自动决定类目数的聚类算法;

4)PCVOS算法，指定最大类目个数为10个，引入100个染色体进行查找最优聚类结果。

4种算法的聚类效果如图5所示。

图5 聚类效果对比Fig.5 The remote sensing image cluster result comparison

K-Means算法共获得5个聚束，从图5a可以看出，大部分地物类型均被区分出来，水体由于数据分布情况的不同被细分为了水体1与水体2，但部分农田被误分为成为草地。ACDE算法共获得4个中心点，从图5b可以看出，农田被误分的情况有所改善，但由于DB Index指标对高维度及小团块支持不佳，所以大量的水体2被误分，盐碱地面积也有所扩大。ISODATA算法共获得7个聚束，从图5c可以看出，新加入了草地2和耕地2解决过渡问题，但部分盐碱地被误分为了草地2，而且过多类目引起聚类效果交互混乱。图5d对应PCVOS算法，获得了6个类目，较图5a～图5c中交替出现错误的部分均得到了有效的修正，获得了更为合理的聚类效果。笔者通过人工识别选取大量样本，每种地物类型随机选取500个样本作为测试样本，对于细分类目(如水体分为水体1和水体2)统一作为一种类目进行精度分析。4种算法的分类精度对比如表2所示。

表2 4种算法的混淆矩阵和精度的对比Tab.2 The confusion matrix and accuracy of four algorithms

K-Mean算法耕地误分现象较为严重;ACDE算法获得了最低的聚类精度(80%)，Kappa=73%，虽然其类目个数与目标的类目个数一致，但相对较小的团块被大团块覆盖，如水体2被盐碱地覆盖，引起部水体和盐碱地样本被错误划分，进而降低的分类精度。ISODATA虽然聚类效果图质量较低，但受益于较多类目数使其获得了第2高的分类精度，达到了精度为84.6%Kappa=79.5%;PCVOS算法达到了最高的精度为88.2%，Kappa为84.3%，从结果可以看出，在通过MCVOS算法查找优化解的过程中，由于使用较多染色体可以获得更加平衡的聚类效果。

4 结 语

针对遥感影像在聚类过程中所面临的数据量大、计算量大、不确定不一致等问题，笔者提出了一种并行的中心矢量优化选取的遥感影像聚类算法(PCVOS)。该算法引入模糊评价目标函数并给出了一种染色体评价机制，以提高聚类染色体在类目、空间划分上的多样性;同时引入MPI(Massage Passage Interface)多进程并行技术，加快了算法运行速度。实验表明本算法可以充分利用多核心计算环境大大加快算法运行速度，同时获得较好的聚类质量。

［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］.遥感学报，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］于波，孟俊敏，张晰，等.结合凝聚层次聚类的极化SAR海冰分割［J］.遥感学报，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］张帅，钟燕飞，张良培.自适应差分进化的遥感影像自动模糊聚类方法［J］.测绘学报，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.

(责任编辑:刘东亮)

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

国家自然科学基金青年基金资助项目(41101384);吉林省教育厅基金资助项目(2014327);吉林省科技厅基金资助项目(20130101179JC-23;20120332);吉林省发改委基金资助项目(2013C048);吉林省科技厅国际合作基金资助项目(20140105)

潘欣(1978— )，男，长春人，长春工程学院副教授，硕士生导师，主要从事遥感数据应用研究，(Tel)86-13844908223 (E-mail)panxinpc@163.com。