在聚类分析的过程中,不需要样本标签,可以自动实现图像分割但是许多情况下需要通过部分样本设置初始参数,此时又可看做是一种半监督的分割方法。目前通过聚类算法的面向对象图像分割存在集群中心的初始化问题,中心的初始化会影响性能和精度[14]。本文基于多种典型的降维和聚类算法,采用主成分分析法(Principal Component Analysis, PCA)降维为K-means算法产生聚类中心,消除随机中心造成结果的不确定性,在UC Merced Land Use Dataset场景数据库[15]和人工GF-2遥感影像数据库[16]上与现有的图像分割方法进行研究对比,提出一种基于多源数据库、联合降维和聚类算法的面向对象多尺度分割优化,以提高分割精度。
1 研究方法与原理 1.1 技术路线 针对K-means初始聚类中心不确定性对聚类结果稳定性的影响,本文将降维分析引入聚类算法中,基于典型的PCA降维和K-means算法的组合,提出一种新的基于PCA的面对对象图像分割优化算法。算法流程如图 1所示,采用UC Merced Land Use Dataset场景数据库[15]和人工GF-2遥感影像数据库[16]在ASUS FX50J Intel(R) Core(TM) i7-4710HQ CPU@2.50 GHz, 12 GB内存硬件平台, Windows 8.1, MatlabR2017a, eCognition developer9平台下通过机器学习中的PCA对多波段的遥感影像进行降维,为聚类算法产生初始聚类中心,从而消除随机的初始聚类中心对聚类结果稳定性的影响。本文将评价经典降维和聚类算法并于现有的eCognition图像分割软件中成熟的图像分割算法如棋盘分割(Chessboard Segmentation)、四叉树分割(Quadtree based Segmentation)、对比度分割(Contrast Split Segmentation)、多尺度分割(Multiresolution Segmentation)、光谱差异分割(Spectral Difference Segmentation)通过目视和定量评价指标跟降维与聚类融合的面向对象多尺度分割优化算法进行对比分析。
图 1 本文技术路线 Fig. 1 Technical route of this paper |
图选项 |
1.2 无监督降维基本原理 机器学习中的降维算法将高维度数据从“维度灾”中解救出来[17],用较少的新变量代替原来较多的变量,而这些新变量能够尽量保持原始数据中包含所有信息。在此引入PCA[18]。
PCA是一种无监督的线性降维方法,假定一组有m个样本数据,有N个变量的标准化数据:X∈Rm×N为
(1) |
计算相关系数矩阵R为
(2) |
式中:rij(i=1, 2, …, m;j=1, 2, …, N)为xi与xj的相关系数。求解特征方程|λE-R|=0(E为单位矩阵),得到特征值λj(j=1, 2, …, N)且λ1≥λ2≥…≥λN≥0,对应特征值λj的特征向量ej(j=1, 2, …, N)。经过特征向量变换下的主成分累计贡献率达到较高的百分数时,就对应为这p(p≤N)个主成分。本文实现对数据的降维过程如图 2所示。
图 2 图像分割PCA过程简图 Fig. 2 A brief diagram of PCA process in image segmentation |
图选项 |
1.3 K-means算法基本原理 聚类分析在任何涉及多元数据分析的学科中都是普遍存在的。其是为了将一组点、模式或对象自然分组[19]。本文针对K-means[20]进行改进并运用于遥感图像面向对象多尺度分割之中。
假设样本数据集Y={yi}, i=1, 2, …, n, 包含n个样本,每个样本是d维特征向量,K-means算法将n个对象分为K个簇,C={Ck}, k=1, 2, …, K。这个聚类簇C满足最小化平方误差。假设μk为Ck的质心,就是簇Ck的均值向量,即
(3) |
μk与Ck其间的平方误差可以定义为
(4) |
K-means的目标是最小化所有K个簇的平方误差之和,即
(5) |
传统的K-means算法从数据集Y随机选取K个样本作为初始的质心向量{μ1, μ2, …, μK},并将簇初始化为C={Ck}, k=1, 2, …, K,通过不断迭代,计算每个簇内样本点与对应质心的距离,并不断更新簇,直至K个质心向量μk不再发生变化,输出K个簇,C={Ck}, k=1, 2, …, K。
K-means算法的聚类结果,很大程度受到初始聚类中心的影响,从而导致图像分割结果的优劣,改进初始聚类中心的随机性,有利于增加聚类结果的准确性。
1.4 基于PCA的K-means算法 K-means算法将n个对象分为K个簇,C={Ck}, k=1, 2, …, K,这个聚类簇C满足最小化平方误差。假设Z={zj}, j=1, 2, …, n, 为原变量Y={yi}, i=1, 2, …, n, 的第一主成分且采用升序排列的一维向量,则初始μk定义为
(6) |
式中:
图 3 基于PCA的K-means算法聚类中心选择 Fig. 3 Clustering center selection of K-means algorithm based on PCA |
图选项 |
图 3中,“栈”中的数据为第一主成分升序排列后形成,假设聚类簇
(7) |
式(7)选定K-means算法的初始聚类中心,避免了初始聚类中心的随机性,增加了聚类结果的稳定度。
K-means算法的另一个核心参数是聚类簇K。本文通过“D-K”曲线选取较优K值,如图 4所示。
图 4 K-means聚类K值的选择 Fig. 4 Selecting parameter K in K-means clustering |
图选项 |
图 4中,D为类内平均距离与类间平均距离的比值,根据曲线中变化较为明显的“拐点”,得到较优参数K值。
1.5 评价指标 本文评价指标分为2个方面:①针对聚类算法的评价指标,分别为内部评价指标和外部评价指标,内部评价指标包括:误差平方和(Sum of theSquared Error, SSE)[21]、均方根标准差(Root-Mean-Square Standard Deviation, RMSSTD)[22]、戴维森堡丁(Davies-Bouldin, DB)指标[23];外部评价指标有:准确率、F度量值、熵和纯度。②对于分割结果的评价:分割精度[10]、欠分割率[10]、过分割率[10]及混淆矩阵[1]。
针对聚类算法内部和外部评价指标如下。
SSE作为聚类的目标函数,同时也可以衡量不同聚类结果好坏的指标:
(8) |
式中:K为簇的个数,并将簇初始化为C={Ck}, k=1, 2, …, K,μk为Ck的质心。簇内样本点xi与其对应的聚类中心相异度计算常常会采用欧氏距离度量。
RMSSTD指标是数据集中所有变量的综合标准差,RMSSTD越小,表明簇内个体对象相似程度越高,聚类效果越好。
(9) |
DB指标的表达式为
(10) |
式中:
(11) |
(12) |
DB指标表示类内的松散程度,其值越小表示簇内越紧密,簇间差异度越大,聚类效果越好。
外部评价指标中,纯度方法和熵值都在0~1之间,完全错误的聚类算法值为0,完全正确的方法值为1。
分割结果的评价指标原理如下。
分割精度是指图像分割对象的面积占原始图像中对象面积的比率,即
(13) |
式中:SA为分割精度;Rs为真实图像原始的面积;Ts为原始图像分割后的分割影像面积。|Rs-Ts|为错分割的面积。
欠分割率OS表示为
(14) |
式中:Os为实际不在分割图像中,却被分割在分割结果中的像素点个数。OS∈[0, 1],当OS=0时,分割效果最佳,当OS=1时表示未分割,即Os越小分割效果越好。
过分割率US表示为
(15) |
式中:Us为实际不在分割图像中,但本应该在分割图像中的像素点的个数。US∈[0, 1],当US=0时,分割效果最佳,当US=1时表示未分割,即与Os一样,Us值越小,分割效果越好。
基于机器学习的遥感图像分类中,通常把分类结果的精度显示在一个混淆矩阵中, 即
(16) |
2 实验结果与分析 2.1 数据描述 本文采用UC Merced Land Use Dataset场景数据库[15]和真实地表数据GF-2遥感影像数据库[16]作为面向对象图像分割的数据源。各个数据库影像如图 5和图 6所示。
图 5 UC Merced Land Use Dataset场景影像 Fig. 5 UC Merced Land Use Dataset scene images |
图选项 |
图 6 GF-2遥感影像 Fig. 6 GF-2 remote sensing images |
图选项 |
图 5中场景数据库图像来源于加州大学美熹德分校(UC Merced),提取自美国地质调查局(USGS)国家地图城市区域图像集,像素大小为256×256,分辨率为1 ft(1 ft=304.8 mm),共包含21类场景图像,该数据库常用于遥感图像分类中[24]。
图 6中GF-2遥感影像时相为2015-09-02,景号为:GF2_PMS1_E116.3_N39.7_201509-02_L1A0001015327,作为本文图像分割初始数据源,各波段参数如表 1所示。
表 1 GF-2卫星有效载荷技术参数 Table 1 Technical parameters of GF-2 satellite payload
波段序号 | 波长范围/μm | 波段名称 | 空间分辨率/m |
Band 1 | 0.45~0.52 | Blue | 4 |
Band 2 | 0.52~0.59 | Green | 4 |
Band 3 | 0.63~0.69 | Red | 4 |
Band 4 | 0.77~0.89 | NIR | 4 |
PAN | 0.45~0.90 | Panchromatic | 1 |
注:数据来源于中国资源卫星应用中心 |
表选项
2.2 遥感数据预处理与分析 本文GF-2遥感影像处理包括辐射定标、大气校正、几何校正、图像融合以及感兴趣区域(Region of Interest, ROI)裁剪等步骤,如图 7所示。
图 7 遥感影像ROI提取流程 Fig. 7 ROI extraction process of remote sensing image |
图选项 |
图 7中,辐射定标需要GF-2卫星的绝对辐射定标系数如表 2所示,PMS为金色多光谱相机。多光谱遥感影像经过大气校正与全色影像正射校正和几何配准后进行图像融合。融合后的影像作为提取模拟影像中的地物所用。
表 2 GF-2卫星绝对辐射定标系数 Table 2 Absolute radiometric calibration coefficient of GF-2 satellite
波段序号 | 定标系数 | GF-2 PMS 1 | GF-2 PMS 2 |
PAN | Gain | 0.1503 | 0.1679 |
Bias | 0 | 0 | |
Band 1 | Gain | 0.1193 | 0.1434 |
Bias | 0 | 0 | |
Band 2 | Gain | 0.1530 | 0.1595 |
Bias | 0 | 0 | |
Band 3 | Gain | 0.1424 | 0.1511 |
Bias | 0 | 0 | |
Band 4 | Gain | 0.1569 | 0.1685 |
Bias | 0 | 0 | |
注:Le=Gain·DN+Bias,Le为卫星载荷通道入瞳处等效辐射亮度, Gain和Bias分别为定标系数增益和偏移量,单位均为W/(m 2·sr·μm), DN(Digital Number)为卫星载荷观测值,无单位。 |
表选项
构建的人工数据集,采用经过预处理的GF-2遥感影像的ROI数据集包括:不同材质及纹理屋顶的建筑、草地、林地、耕地和水体等土地利用类型, 如图 8所示。
图 8 人工影像数据集 Fig. 8 Artificial image data sets |
图选项 |
2.3 结果与分析 1) 传统的影像分割技术
图 9所示为ESP(Estimation of Scale Parameter)分割及尺度选择。由图中可以看出,传统影像分割在形状因子和紧致度因子分别为0.5和0.6的情况下,计算影像对象同质性的局部方差(Local Variance, LV),利用局部方差的变化率ROC-LV(Rate of Change of LV),并通过目视解译选择出最优分割尺度参数。
图 9 ESP分割及尺度选择 Fig. 9 ESP segmentation and scale selection |
图选项 |
UC Merced Land Use Dataset场景影像中6类场景数据库在eCognition developer9平台上采用5种方法包括:棋盘分割、四叉树分割、对比度分割、多尺度分割、光谱差异分割,分割结果如图 10~图 14所示。
图 10 棋盘分割结果 Fig. 10 Chessboard segmentation results |
图选项 |
图 11 四叉树分割结果 Fig. 11 Quadtree based segmentation results |
图选项 |
图 12 对比度分割结果 Fig. 12 Contrast split segmentation results |
图选项 |
图 13 多尺度分割结果 Fig. 13 Multiresolution segmentation results |
图选项 |
图 14 光谱差异分割结果 Fig. 14 Spectral difference segmentation results |
图选项 |
图 10中棋盘法简单地将地物分割成若干网格,网格的尺寸可人为设置,但棋盘分割结果缺失地物特征,不能较好地反映地物特征,针对不同地物多尺度分割意义不大。
图 11中,利用四叉树分割对飞机、建筑、河流的分割效果较差,当分割尺度较小时,分割单元数量较大。
对比度分割首先采用棋盘法将对象分割为若干个正方形,再利用设定的阈值进行对比,划分对象。该算法优于简单的棋盘分割,能够较好地分割出某些地物特征,但是对于图中机场和棒球场的分割效果较弱。
图 13多尺度分割和图 14光谱差异分割中,均需设定初始参数,图 13中在形状因子0.1下,各类场景分割效果不明显,传统的多尺度分割需要设置尺度和形状因子,存在主观经验的影响。图 14中,进行光谱差异分割时,通过设定的光谱差异阈值,将同质区合并,异质区分割,图 14为在最大光谱差异阈值10的条件下,图像分割结果能较好的区分河流和高尔夫球场。不同阈值下,分割结果不同。
2) 本文面向对象分割方法
图 15~图 16为本文多尺度分割优化算法,图 15中,通过PCA降维提取主成分,并利用排序算法将产生图 16中K-means的初始聚类中心,通过目视解译,可以看出经过PCA降维的K-means算法能较好地分割出飞机场、高尔夫球场、河流和跑道4个对象。
图 15 PCA降维结果 Fig. 15 PCA dimension reduction results |
图选项 |
图 16 联合PCA-K-means分割结果 Fig. 16 Segmentation results of combining PCA-K-means |
图选项 |
2.4 指标评价 对高分影像的分割结果进行评价是GEOBIA(Geographic Object-Based Image Analysis)技术领域的难点之一,也是分割流程自动化必不可少的一项关键技术。陈扬洋等[25]对常用分割评价方法进行了系统总结。目前最常用的分割评价方法依旧是主观评价法。本文采用主客观相结合的评价体系,研究各分割结果的优劣。评价指标如表 3所示,由表中可以看到,当聚类簇数目较大时,K-means随机产生的聚类中心得到的聚类结果SSE较大,经过PCA降维处理后的K-means聚类簇内SSE较小,聚类结果较为稳定。
表 3 误差平方和 Table 3 Index of sum of the squared error
数据集 | SSE | 簇 | |
PCA- K-means | K-means | ||
飞机场 | 3130471.24 | 3154435.88 | 7 |
棒球场 | 4087335.06 | 4163850.17 | 8 |
建筑 | 8363422.52 | 8385022.59 | 4 |
高尔夫球场 | 11631195.71 | 11631195.71 | 3 |
河流 | 39832127.26 | 39832127.26 | 2 |
跑道 | 7319143.02 | 7319143.02 | 4 |
表选项
如图 17所示,在内部评价指标RMSSTD和DB指标中,经过PCA降维后结合K-means的聚类算法在簇内紧密度、相似度和簇间差异度方面有所提高,聚类效果较好。
图 17 K-means随机聚类与PCA-K-means评价 Fig. 17 Evaluation of K-means random clustering and PCA-K-means |
图选项 |
图 18中,经过PCA降维后的K-means聚类纯度评价均较高,对于不同场景中,熵评价方法各有差异。
图 18 PCA-K-means外部指标评价 Fig. 18 External index evaluation of PCA-K-means |
图选项 |
由图 19可见,飞机场场景中第4类和河流第2类分割精度高达0.99以上,高尔夫球场达到0.98以上,以及跑道的各类精度都较高,近似完美分割。而在棒球场、建筑的场景中,由于棒球场地、建筑和水泥地地物类型较为冗余,因此分割效果较弱。
图 19 分割结果评价 Fig. 19 Evaluation of segmentation results |
图选项 |
3 结论 本文针对面向对象多尺度分割中分割尺度选择的主观试验性及聚类算法中K-means等算法的初始聚类中心不确定性造成的结果不稳定2个方面,提出一种基于PCA的面向对象多尺度分割优化算法,并利用多源数据库进行分析,得到:
1) 面向对象的遥感图像分割效果主要受到分割尺度的影响,本文联合降维和聚类的分割算法实现无监督分割,此方法不受主观经验因素的影响,不依赖于多尺度的分割经验。
2) 联合降维技术与聚类算法,如K-means结合PCA,解决了K-means聚类算法初始聚类随机性的问题,增加了聚类算法产生聚类结果稳定性。
3) 通过聚类评价指标计算,经过PCA变换后进行的聚类,提高了聚类结果的精度。
本文采用的多光谱遥感影像,维度较低、信息量较小,随着高分航空、航天遥感数据获取能力的不断提高,可利用的多源数据不断增加,对于高维度遥感数据集,本文算法是否适用有待进一步研究分析,后续将针对此方面尤其是高光谱遥感影像等高维度数据集,在降维、聚类算法上继续开展相关研究。
参考文献
[1] | 邓书斌. ENVI遥感图像处理方法[M]. 2版. 北京: 高等教育出版社, 2014. DENG S B. ENVI remote sensing image processing methods[M]. 2nd ed. Beijing: Higher Education Press, 2014. (in Chinese) |
[2] | JOZDANI S E, MOMENI M, JOHNSON B A, et al. A regression modelling approach for optimizing segmentation scale parameters to extract buildings of different sizes[J]. International Journal of Remote Sensing, 2018, 39(3): 684-703. |
[3] | HU Z W, ZHANG Q, ZOU Q, et al. Stepwise evolution analysis of the region-merging segmentation for scale parameterization[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2018, 11(7): 2461-2472. |
[4] | 高仁强, 欧阳建, 陈亮雄, 等.面向对象的鹤地水库高分辨率影像分类研究[J/OL].测绘科学: 1-14(2018-11-19)[2019-07-02].http://kns.cnki.net/kcms/detail/11.4415.P.20181115.1629.002.html. GAO R Q, OU Y J, CHEN L X, et al.Research on high resolution image classification of Hedi reservoir based on object-oriented method[J/OL].Science of Surveying and Mapping: 1-14(2018-11-19)[2019-07-02].http://kns.cnki.net/kcms/detail/11.4415.P.20181115.1629.002.html(in Chinese). |
[5] | HU L, CHAN K C C. Fuzzy clustering in a complex network based on content relevance and link structures[J]. IEEE Transactions on Fuzzy Systems, 2016, 24(2): 456-470. |
[6] | ZHANG H, SHI W Z, HAO M, et al. An adaptive spatially constrained fuzzy c-means algorithm for multispectral remotely sensed imagery clustering[J]. International Journal of Remote Sensing, 2018, 39(8): 2207-2237. |
[7] | FAN J C, WANG J. A two-phase fuzzy clustering algorithm based on neurodynamic optimization with its application for PolSAR image segmentation[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(1): 72-83. |
[8] | 王慧贤, 靳惠佳, 王娇龙, 等. k均值聚类引导的遥感影像多尺度分割优化方法[J]. 测绘学报, 2015, 44(5): 526-532. WANG H X, JIN H J, WANG J L, et al. Optimization approach for multi-scale segmentation of remotely sensed imagery under k-means clustering guidance[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(5): 526-532. (in Chinese) |
[9] | SIDDIQUI F U, ISA N A M. Enhanced moving K-means (EMKM) algorithm for image segmentation[J]. IEEE Transactions on Consumer Electronics, 2011, 57(2): 833-841. |
[10] | 姜文斌, 刘丽萍, 孙学宏. 基于自适应权重法的K-means模型对遥感图像分割[J]. 计算机应用与软件, 2019, 36(5): 231-234. JIANG W B, LIU L P, SUN X H. K-means model based on adaptive weight method for remote sensing image segmentation[J]. Computer Applications and Software, 2019, 36(5): 231-234. (in Chinese) |
[11] | CHEN S Y, SUN T L, YANG F Q, et al. An improved optimum-path forest clustering algorithm for remote sensing image segmentation[J]. Computers & Geosciences, 2018, 112: 38-46. |
[12] | 马彩虹, 戴芹, 刘士彬. 一种融合PSO和Isodata的遥感图像分割新方法[J]. 武汉大学学报(信息科学版), 2012, 37(1): 35-38. MA C H, DAI Q, LIU S B. A new method of remote sensing image segmentation based on PSO and Isodata[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1): 35-38. (in Chinese) |
[13] | CHEN J Y, ZHENG H B, LIN X, et al. A novel image segmentation method based on fast density clustering algorithm[J]. Engineering Applications of Artificial Intelligence, 2018, 73: 92-110. |
[14] | FAN J C, HAN M, WANG J. Single point iterative weighted fuzzy C-means clustering algorithm for remote sensing image segmentation[J]. Pattern Recognition, 2009, 42(11): 2527-2540. |
[15] | YANG Y, NEWSAM S.Bag-of-visual-words and spatial extensions for land-use classification[C]//ACM Press the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems(ACM GIS).New York: ACM, 2010: 270. |
[16] | 中国资源卫星应用中心.数据服务平台[EB/OL].(2015-09-02)[2019-07-02].http://www.cresda.com/. China Centre for Resources Satellite Data and Application.Data service platform[EB/OL].(2015-09-02)[2019-07-02].http://www.cresda.com/(in Chinese). |
[17] | 杉山将.图解机器学习[M].许永伟, 译.北京: 人民邮电大学出版社, 2015: 143. SUGIYAMA M.Graphic machine learning[M].XU Y W, translated.Beijing: People's University of Posts and Telecommunications Press, 2015: 143(in Chinese). |
[18] | JIANG Q C, YAN X F. Parallel PCA-KPCA for nonlinear process monitoring[J]. Control Engineering Practice, 2018, 80: 17-25. |
[19] | JAIN A K. Data clustering:50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666. |
[20] | HARTIGAN J A, WONG M A. Algorithm AS 136:A K-means clustering algorithm[J]. Journal of the Royal Statistical Society, 1979, 28(1): 100-108. |
[21] | 周本金, 陶以政, 纪斌, 等. 最小化误差平方和k-means初始聚类中心优化方法[J]. 计算机工程与应用, 2018, 54(15): 48-52. ZHOU B J, TAO Y Z, JI B, et al. Optimizing k-means initial clustering centers by minimizing sum of squared error[J]. Computer Engineering and Applications, 2018, 54(15): 48-52. (in Chinese) |
[22] | 傅立伟, 武森. 基于属性值集中度的分类数据聚类有效性内部评价指标[J]. 工程科学学报, 2019, 41(5): 682-693. FU L W, WU S. A new internal clustering validation index for categorical data based on concentration of attribute values[J]. Chinese Journal of Engineering, 2019, 41(5): 682-693. (in Chinese) |
[23] | DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224-227. |
[24] | LI M, DE BEURS K M, STEIN A, et al. Incorporating open source data for Bayesian classification of urban land use from vhr stereo images[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2017, 10(11): 4930-4943. |
[25] | CHEN Y Y, MING D P, XU L, et al. An overview of quantitative experimental methods for segmentation evaluation of high spatial remote sensing images[J]. Journal of Geo-information Science, 2017, 19(6): 818-830. |