基于超像素锚图二重降维的高光谱聚类算法

doi:10.11772/j.issn.1001-9081.2021050825

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (7): 2088-2093.DOI: 10.11772/j.issn.1001-9081.2021050825

基于超像素锚图二重降维的高光谱聚类算法

赖星锦¹, 郑致远², 杜晓颜³, 徐莎¹(), 杨晓君¹

^1.广东工业大学信息工程学院, 广州 510006
^2.火箭军工程大学第五大队, 西安 710025
^3.96962部队, 北京 102206

收稿日期:2021-05-19 修回日期:2021-09-23 接受日期:2021-09-28 发布日期:2021-09-23 出版日期:2022-07-10
通讯作者: 徐莎
作者简介:赖星锦（1998—），男，广东揭阳人，硕士研究生，主要研究方向：聚类算法
郑致远（2000—），男，广东广州人，主要研究方向：降维算法
杜晓颜（1980—），女，河南方城人，工程师，主要研究方向：数据挖掘
杨晓君（1983—），男，安徽颍上人，副教授，博士，主要研究方向：聚类算法、智能信息处理。
基金资助:
广东省重点领域研发计划项目(2018B010115001);广东省自然科学基金资助项目(2021A1515011141)

Hyperspectral clustering algorithm by double dimension-reduction based on super-pixel and anchor graph

Xingjin LAI¹, Zhiyuan ZHENG², Xiaoyan DU³, Sha XU¹(), Xiaojun YANG¹

^1.School of Information Engineering，Guangdong University of Technology，Guangzhou Guangdong 510006，China
^2.The Fifth Battalion，Rocket Force Engineering University，Xi’an Shaanxi 710025，China
^3.96962 Troops，Beijing 102206，China

Received:2021-05-19 Revised:2021-09-23 Accepted:2021-09-28 Online:2021-09-23 Published:2022-07-10
Contact: Sha XU
About author:LAI Xingjin， born in 1998， M. S. candidate. His research interests include clustering algorithm.
ZHENG Zhiyuan， born in 2000. His research interests include dimension reduction algorithm.
DU Xiaoyan， born in 1980， engineer. Her research interests include data mining.
YANG Xiaojun， born in 1983， Ph. D.， associate professor. His research interests include clustering algorithm， intelligent information processing.
Supported by:
Research and Development Program in Key Areas of Guangdong Province(2018B010115001);Natural Science Foundation of Guangdong Province(2021A1515011141)

摘要/Abstract

摘要：

针对传统谱聚类算法难以应用于大规模高光谱图像，以及现有的改进谱聚类算法对大规模高光谱图像的处理效果不佳的问题，为降低聚类数据的复杂度，以降低聚类过程的计算成本从而多方面提升聚类性能，提出一种基于超像素锚图二重降维的高光谱聚类算法。首先，对高光谱数据进行主成分分析（PCA）处理，并针对高光谱图像的区域特性对其进行基于超像素切割的降维；其次，通过构造锚图的思想对上一步所得数据进行锚点的选取，并构建邻接锚图来实现二重降维，从而进行谱聚类；同时，为去除算法运行中人为调节参数的环节，在构建锚图时采用一种去除高斯核的无核锚图构造方式以实现自动构图。在Indian Pines数据集和Salinas数据集上的实验结果表明所提算法在保证可用性与低耗时的前提下可提高聚类的整体效果，从而验证了所提算法能提高聚类的质量与性能。

关键词: 高光谱图像, 超像素切割, 锚图, 谱聚类, 降维

Abstract:

Traditional spectral clustering algorithms are difficult to be applied to large-scale hyperspectral images， and the existing improved spectral clustering algorithms are not effective in processing large-scale hyperspectral images. To address these problems， a hyperspectral clustering algorithm based on double dimension-reduction of super-pixel and anchor graph was proposed to reduce the complexity of clustering data that is to reduce the computational cost of clustering process， thereby improving the clustering performance in many aspects. Firstly， Principal Component Analysis （PCA） was performed to the hyperspectral image data， and dimension-reduction was carried out to the data based on super-pixel segmentation according to the regional characteristics of hyperspectral image. Then， the anchor points of the data obtained in previous step were selected with the idea of constructing anchor graph. And the adjacent anchor graph was constructed to achieve double dimension-reduction for spectral clustering. At the same time， in order to remove the artificial adjustment of parameters in the operation of the algorithm， a kernel-free anchor graph construction method with the Gaussian kernel removed was used in the construction of anchor graph to achieve automatic graph construction. Experimental results on Indian Pines dataset and Salinas dataset show that the proposed algorithm can improve the overall effects of clustering with guaranteeing availability and low time consumption， thus verifying that the proposed algorithm can improve the quality and performance of clustering.

Key words: hyperspectral image, super-pixel segmentation, anchor graph, spectral clustering, dimension-reduction

中图分类号:

TP751

赖星锦, 郑致远, 杜晓颜, 徐莎, 杨晓君. 基于超像素锚图二重降维的高光谱聚类算法[J]. 计算机应用, 2022, 42(7): 2088-2093.

Xingjin LAI, Zhiyuan ZHENG, Xiaoyan DU, Sha XU, Xiaojun YANG. Hyperspectral clustering algorithm by double dimension-reduction based on super-pixel and anchor graph[J]. Journal of Computer Applications, 2022, 42(7): 2088-2093.

图/表 7

图1 SDASC算法流程

Fig. 1 Flow of SDASC algorithm

表1 实验环境

Tab. 1 Experimental environment

项目	参数
运行内存	125 GB
操作系统版本	CentOS Linux release 7.2.1511 （Core）
运行环境	Matlab R2017a

表2 各个算法的计算时间复杂度对比

Tab. 2 Computing time complexity comparison of various algorithms

算法名称	时间复杂度
K-means	$O (n k d)$
SC	$O (n 2 d + n 2 v)$
SCAG	$O (n d m)$
SGCNR	$O (n d m)$
FSECSGL	$O (n d m)$
SPCA-SC	$O (n 2 p + n 2 v)$
SDASC	$O (n p 2)$

表2 各个算法的计算时间复杂度对比

Tab. 2 Computing time complexity comparison of various algorithms

算法名称	时间复杂度
K-means	$O (n k d)$
SC	$O (n 2 d + n 2 v)$
SCAG	$O (n d m)$
SGCNR	$O (n d m)$
FSECSGL	$O (n d m)$
SPCA-SC	$O (n 2 p + n 2 v)$
SDASC	$O (n p 2)$

表3 SDASC与其他算法在Indian Pines数据集上的比较

Tab. 3 Comparison of SDASC and other algorithms on Indian Pines dataset

算法	AA/%	OA/%	Kappa/%	Time/s
K-means	36.33	34.21	26.89	3.0
SC	30.66	33.45	27.54	54.3
SCAG	39.45	33.56	28.53	1.7
SGCNR	31.79	26.42	18.71	6.8
FSECSGL	42.83	26.06	17.72	178.8
SPCA-SC	33.85	34.98	27.23	19.7
SDASC	60.46	34.65	28.69	0.4

图2 在Indian Pines数据集上不同算法的聚类效果

Fig. 2 Clustering effects of different algorithms on Indian Pines dataset

表4 SDASC与其他算法在Salinas数据集上的比较

Tab. 4 Comparison of SDASC and other algorithms on Salinas dataset

算法	AA/%	OA/%	Kappa/%	Time/s
K-means	64.57	58.95	53.80	15.2
SC	OM	OM	OM	OM
SCAG	67.65	45.06	39.37	7.8
SGCNR	65.46	47.73	42.68	54.4
FSECSGL	48.87	31.70	22.76	898.8
SPCA-SC	OM	OM	OM	OM
SDASC	81.50	57.84	54.42	7.4

图3 在Salinas数据集上不同算法聚类效果

Fig. 3 Clustering effects of different algorithms on Salinas dataset

参考文献 21

1	杜培军，夏俊士，薛朝辉，等. 高光谱遥感影像分类研究进展［J］. 遥感学报， 2016， 20（2）：236-256. 10.11834/jrs.20155022
	DU P J， XIA J S， XUE Z H， et al. Review of hyperspectral remote sensing image classification［J］. Journal of Remote Sensing， 2016， 20（2）： 236-256. 10.11834/jrs.20155022
2	王相海，王顺，谢释铖，等. 高光谱图像光谱维结构相关性及稀疏重建模型［J］. 中国科学：信息科学， 2021， 51（3）：449-467. 10.1360/ssi-2019-0229
	WANG X H， WANG S， XIE S C， et al. Spectral dimensional structure correlation and sparse reconstruction model of hyperspectral images［J］. SCIENTIA SINICA Informationis， 2021， 51（3）： 449-467. 10.1360/ssi-2019-0229
3	王姗姗. 高光谱图像特征提取和分类算法研究［D］. 大连：辽宁师范大学， 2020：1473-1519.
	WANG S S. Research on hyperspectral image feature extraction and classification algorithm［D］. Dalian： Liaoning Normal University， 2020：1473-1519.
4	杨随心，耿修瑞，杨炜暾，等. 一种基于谱聚类算法的高光谱遥感图像分类方法［J］. 中国科学院大学学报， 2019， 36（2）：267-274. 10.7523/j.issn.2095-6134.2019.02.015
	YANG S X， GENG X R， YANG W T， et al. A method of hyperspectral remote sensing image classification based on spectral clustering［J］. Journal of University of Chinese Academy of Sciences， 2019， 36（2）： 267-274. 10.7523/j.issn.2095-6134.2019.02.015
5	许裕雄，杨晓君，蔡湧达，等. 基于二叉树锚点的高光谱快速聚类算法［J］. 激光与光电子学进展， 2021， 58（2）： No.0210021. 10.3788/lop202158.0210021
	XU Y X， YANG X J， CAI Y D， et al. Hyperspectral fast clustering algorithm based on binary tree anchor points［J］. Laser and Optoelectronics Progress， 2021， 58（2）： No.0210021. 10.3788/lop202158.0210021
6	JIANG J J， MA J Y， CHEN C， et al. SuperPCA： a superpixelwise PCA approach for unsupervised feature extraction of hyperspectral imagery［J］. IEEE Transactions on Geoscience and Remote Sensing， 2018， 56（8）：4581-4593. 10.1109/tgrs.2018.2828029
7	BEIRAMI B A， MOKHTARZADE M. Band grouping SuperPCA for feature extraction and extended morphological profile production from hyperspectral images［J］. IEEE Geoscience and Remote Sensing Letters， 2020， 17（11）： 1953-1957. 10.1109/lgrs.2019.2958833
8	雷存款. 高光谱影像降维与谱-空分类方法研究［D］. 大连：辽宁师范大学， 2020：1216-1278.
	LEI C K. Research on dimensionality reduction and spectral-spatial classification methods for hyperspectral image［D］. Dalian： Liaoning Normal University， 2020：1216-1278.
9	WANG R， NIE F P， YU W Z. Fast spectral clustering with anchor graph for large hyperspectral images［J］. IEEE Geoscience and Remote Sensing Letters， 2017， 14（11）：2003-2007. 10.1109/lgrs.2017.2746625
10	ZHU W， NIE F P， LI X L. Fast spectral clustering with efficient large graph construction［C］// Proceedings of the 2017 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2017： 2492-2496. 10.1109/icassp.2017.7952605
11	YANG X J， YU W Z， WANG R， et al. Fast spectral clustering learning with hierarchical bipartite graph for large-scale data［J］. Pattern Recognition Letters， 2020， 130：345-352. 10.1016/j.patrec.2018.06.024
12	赵蔷. 主成分分析方法综述［J］. 软件工程， 2016， 19（6）：1-3. 10.3969/j.issn.1008-0775.2016.06.001
	ZHAO Q. A review of principal component analysis［J］. Software Engineering， 2016， 19（6）： 1-3. 10.3969/j.issn.1008-0775.2016.06.001
13	LUO M， BORS A G. Principal component analysis of spectral coefficients for mesh watermarking［C］// Proceedings of the 15th IEEE International Conference on Image Processing. Piscataway： IEEE， 2008： 441-444. 10.1109/icip.2008.4711786
14	LI J Y， ZHANG H Y， ZHANG L P. Efficient superpixel-level multitask joint sparse representation for hyperspectral image classification［J］. IEEE Transactions on Geoscience and Remote Sensing， 2015， 53（10）： 5338-5351. 10.1109/tgrs.2015.2421638
15	MA J Y， LI C， MA Y， et al. Hyperspectral image denoising based on low-rank representation and superpixel segmentation［C］// Proceedings of the 2016 IEEE International Conference on Image Processing. Piscataway： IEEE， 2016： 3086-3090. 10.1109/icip.2016.7532927
16	TANG Y W， ZHAO L Y， REN L. Different versions of entropy rate superpixel segmentation for hyperspectral image［C］// Proceedings of the IEEE 4th International Conference on Signal and Image Processing. Piscataway： IEEE， 2019： 1050-1054. 10.1109/siprocess.2019.8868344
17	陈永，卢晨涛. 基于超像素分割和暗亮通道结合的单幅图像去雾［J］. 激光与光电子学进展， 2020， 57（16）： No.161023. 10.3788/lop57.161023
	CHEN Y， LU C T. Single image dehazing based on superpixel segmentation combined with dark-bright channels［J］. Laser and Optoelectronics Progress， 2020， 57（16）： No.161023. 10.3788/lop57.161023
18	NIE F P， ZHU W， LI X L. Unsupervised large graph embedding based on balanced and hierarchical K-means［J］. IEEE Transactions on Knowledge and Data Engineering， 2022， 34（4）：2008-2019.
19	NIE F P， WANG X Q， JORDAN M I， et al. The constrained Laplacian rank algorithm for graph-based clustering［C］// Proceedings of the 30th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2016：1969-1976. 10.1609/aaai.v30i1.10302
20	WANG R， NIE F P， WANG Z， et al. Scalable graph-based clustering with nonnegative relaxation for large hyperspectral image［J］. IEEE Transactions on Geoscience and Remote Sensing， 2019， 57（10）：7352-7364. 10.1109/tgrs.2019.2913004
21	YANG X J， LIN G Q， LIU Y J， et al. Fast spectral embedded clustering based on structured graph learning for large-scale hyperspectral image［J］. IEEE Geoscience and Remote Sensing Letters， 2022， 19： No.5501705. 10.1109/lgrs.2020.3035677

[1]	丁雨, 张瀚霖, 罗荣, 孟华. 基于信念子簇切割的模糊聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1128-1138.
[2]	孟圣洁, 于万钧, 陈颖. 最大相关和最大差异的高维数据特征选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 767-771.
[3]	唐海涛, 王红军, 李天瑞. 判别多维标度特征学习[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1323-1329.
[4]	马志峰, 于俊洋, 王龙葛. 多样性表示的深度子空间聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 407-412.
[5]	李文博, 刘波, 陶玲玲, 罗棻, 张航. L1正则化的深度谱聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3662-3667.
[6]	张琦, 郑伯川, 张征, 周欢欢. 基于随机分块的稀疏子空间聚类方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1148-1154.
[7]	翟东昌, 陈红梅. 基于邻域熵的高光谱波段选择算法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 485-492.
[8]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[9]	王基厚, 林培光, 周佳倩, 李庆涛, 张燕, 蹇木伟. 结合公司财务报表数据的股票指数预测方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3632-3636.
[10]	高冉, 陈花竹. 改进的基于谱聚类的子空间聚类模型[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3645-3651.
[11]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[12]	李杏峰, 黄玉清, 任珍文. 联合低秩稀疏的多核子空间聚类算法[J]. 计算机应用, 2020, 40(6): 1648-1653.
[13]	王锦凯, 贾旭. 基于加权正交约束非负矩阵分解的车脸识别算法[J]. 计算机应用, 2020, 40(4): 1050-1055.
[14]	张凯琳, 阎庆, 夏懿, 章军, 丁云. 基于焦点损失的半监督高光谱图像分类[J]. 计算机应用, 2020, 40(4): 1030-1037.
[15]	李东博, 黄铝文. 重加权稀疏主成分分析算法及其在人脸识别中的应用[J]. 计算机应用, 2020, 40(3): 717-722.

基于超像素锚图二重降维的高光谱聚类算法

Hyperspectral clustering algorithm by double dimension-reduction based on super-pixel and anchor graph

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 21

相关文章 15

编辑推荐

Metrics