基于超像素錨圖二重降維的高光譜聚類算法

賴星錦，鄭致遠，杜曉顏，徐莎*，楊曉君

基于超像素錨圖二重降維的高光譜聚類算法

賴星錦1，鄭致遠2，杜曉顏3，徐莎1*，楊曉君1

（1.廣東工業(yè)大學 信息工程學院，廣州 510006； 2.火箭軍工程大學 第五大隊，西安 710025； 3.96962部隊，北京 102206）（ ? 通信作者電子郵箱sally.xu@gdut.edu.cn）

針對傳統(tǒng)譜聚類算法難以應用于大規(guī)模高光譜圖像，以及現(xiàn)有的改進譜聚類算法對大規(guī)模高光譜圖像的處理效果不佳的問題，為降低聚類數(shù)據(jù)的復雜度，以降低聚類過程的計算成本從而多方面提升聚類性能，提出一種基于超像素錨圖二重降維的高光譜聚類算法。首先，對高光譜數(shù)據(jù)進行主成分分析（PCA）處理，并針對高光譜圖像的區(qū)域特性對其進行基于超像素切割的降維；其次，通過構(gòu)造錨圖的思想對上一步所得數(shù)據(jù)進行錨點的選取，并構(gòu)建鄰接錨圖來實現(xiàn)二重降維，從而進行譜聚類；同時，為去除算法運行中人為調(diào)節(jié)參數(shù)的環(huán)節(jié)，在構(gòu)建錨圖時采用一種去除高斯核的無核錨圖構(gòu)造方式以實現(xiàn)自動構(gòu)圖。在Indian Pines數(shù)據(jù)集和Salinas數(shù)據(jù)集上的實驗結(jié)果表明所提算法在保證可用性與低耗時的前提下可提高聚類的整體效果，從而驗證了所提算法能提高聚類的質(zhì)量與性能。

高光譜圖像；超像素切割；錨圖；譜聚類；降維

0 引言

高光譜遙感技術(shù)可以在得到地表物體遙感圖像的同時獲取目標幾十個甚至幾百個連續(xù)譜段，提供豐富信息用于地面物體精準識別與分類，在國防安全、農(nóng)業(yè)調(diào)查、環(huán)境監(jiān)測等方面發(fā)揮重要作用，這令高光譜圖像研究成為21世紀遙感領域最重要的研究方向之一［1-4］。

高光譜圖像擁有豐富信息的同時具有大量冗余信息，給高光譜圖像后續(xù)特征信息判別帶來了一些困難［5］，因此，對高光譜數(shù)據(jù)集的降維預處理尤為重要。無監(jiān)督降維技術(shù)中，最廣泛應用的手段之一是主成分分析（Principal Component Analysis， PCA），PCA傾向于尋找正交變換來最大化投影數(shù)據(jù)的總方差。然而，高光譜圖像中不同區(qū)域具有不同的變換向量，僅對其進行PCA的后果是樣本之間的相關(guān)性可能會丟失，對高光譜圖像的降維效果并不理想。對此，針對降維算法在高光譜圖像上的應用，許多學者進行了廣泛的研究：文獻［6］針對高光譜不同區(qū)域具有不同光譜特征的特點，提出了一種簡單有效的超像素降維方法用于提取高光譜圖像的特征；文獻［7］通過帶分組技術(shù)改進方法，為擴展形態(tài)輪廓的生成提供了合適的基礎圖像；文獻［8］將基于多尺度顯著性檢測的視覺注意機制引入到高光譜影像的噪聲去除和圖像增強處理中，并基于分層聚類算法，提出一種結(jié)合聚類降維和視覺注意機制的高光譜影像分類方法。

為進一步提高譜聚類算法在高光譜聚類應用上的性能與精度，本文提出一種基于超像素錨圖二重降維的高光譜聚類（Super-pixel Dimension-reduction Anchor Spectral Clustering， SDASC）算法。該算法創(chuàng)新性地將基于超像素降維的方法與構(gòu)建鄰接錨圖進行融合處理。針對高光譜圖像各區(qū)域特征不同的特點，首先基于超像素降維對高光譜圖像進行初步處理；隨后對超像素降維得到的數(shù)據(jù)集進行錨點選??；在此基礎上去除熱核參數(shù)，避免人工調(diào)節(jié)參數(shù)，構(gòu)造基于錨點的無核關(guān)系圖進行譜聚類分析并獲得聚類結(jié)果。通過Indian Pines數(shù)據(jù)集和Salinas數(shù)據(jù)集的仿真，驗證了SDASC算法能夠有效地處理大規(guī)模高光譜數(shù)據(jù)。

1 相關(guān)原理

1.1　PCA降維

1.2　熵率超像素分割

1.3　多尺度分割

1.4　譜聚類分析

譜聚類的目標函數(shù)為：

2 本文方法

2.1　SDASC算法

文獻［9-11］中的實驗結(jié)果表明，基于錨圖構(gòu)建的譜聚類算法在高光譜應用上雖然能加快聚類速度，但是精度依舊不高，原因一方面是譜聚類本身適合處理小樣本、各簇分布較為均勻、類別數(shù)較少的數(shù)據(jù)集，大部分高光譜數(shù)據(jù)集并沒有這種特點；另一方面是錨點的選取有較強的隨機性和樣本整體性，錨點選取的結(jié)果間接影響了聚類結(jié)果，在高光譜圖像中，由于圖像各區(qū)域?qū)煌矬w且區(qū)域劃分大小不一致，所以單純對圖像數(shù)據(jù)集進行整體錨點的選取是不合適的，易出現(xiàn)數(shù)據(jù)相關(guān)性丟失、數(shù)據(jù)無法較好保留等問題。針對此問題，本文結(jié)合對高光譜降維效果較佳的超像素降維與基于錨點構(gòu)圖的思想，提出一種運行時間與聚類精度兼顧的基于超像素錨圖二重降維的高光譜聚類算法。算法流程如圖1所示。

圖1　SDASC算法流程

本算法步驟描述如下：

步驟一 針對高光譜圖像信息量過大、數(shù)據(jù)量冗余的缺點對高光譜圖像進行初步PCA降維，從而達到去除噪聲干擾、提取主要信息、方便后續(xù)處理高光譜圖像的目的。

步驟三 對上一步所得數(shù)據(jù)矩陣進行錨圖的選點，在本文算法中采用的是隨機選點法，由于經(jīng)過兩次降維，所以隨機選點法得到的錨圖矩陣在后續(xù)參與聚類中既保證精度不會太差也保證較高的聚類速度。其中，在構(gòu)建錨圖時為避免人工調(diào)節(jié)額外的高斯參數(shù)，引入了無核自適應構(gòu)建錨圖的方法，進一步提升了聚類的速度。

步驟四 譜聚類分析，最終得到聚類后的結(jié)果。

2.2　多尺度降維融合

針對每一個通過超像素切割切分好的區(qū)域，進行PCA降維處理，隨后將各個區(qū)域提取出來的主成分組合起來，形成降維后的數(shù)據(jù)集，利用基于多數(shù)投票的決策融合策略對圖像不同尺度分割后不同的分類結(jié)果進行融合：

2.3　錨圖去核自適應構(gòu)圖方法

Using above boundary conditions, the coefficients are obtained as

SDASC算法具體如下。

算法1 SDASC算法。

2.4　時間復雜度分析

3 實驗結(jié)果與分析

3.1　數(shù)據(jù)集介紹

為驗證SDASC算法在高光譜圖像上的聚類性能，本文所用高光譜數(shù)據(jù)集為Indian Pines數(shù)據(jù)集和Salinas數(shù)據(jù)集。Indian Pines數(shù)據(jù)集是AVIRIS設備于美國印第安納州西北部獲取的印度松高光譜圖像數(shù)據(jù)，圖像成像大小為145×145，物體標簽個數(shù)為16，光譜帶數(shù)量為220；去除部分噪聲帶后，用于實驗研究的為21 025個總樣本數(shù)與200個光譜帶。Salinas數(shù)據(jù)集是AVIRIS設備在加利福尼亞州薩利納斯山谷采集的高光譜圖像，圖像大小為512×217，地物共有16類，光譜帶有224個；去除部分噪聲帶后，用于實驗研究的光譜帶為204個，圖像像素總數(shù)為111 104。

3.2　實驗指標

本實驗的對照方法包括-means、譜聚類（Spectral Clustering， SC）兩種傳統(tǒng)聚類算法與文獻［9］提出的SCAG算法、文獻［20］提出的加入非負松弛項的改進譜聚類（Scalable Graph-based Clustering with Nonnegative Relaxation， SGCNR）算法、文獻［21］提出的基于結(jié)構(gòu)圖學習的快速譜嵌入聚類（Fast Spectral Embedded Clustering based on Structured Graph Learning， FSECSGL）算法。同時，為測試SDASC算法在原基礎上對數(shù)據(jù)集降維處理的效果，將SDASC算法的聚類效果與超像素降維結(jié)合譜聚類（Spectral Clustering based on Super-pixel Principal Component Analysis， SPCA-SC）的效果進行對比實驗。

表1　實驗環(huán)境

本文采用總準確度（Overall Accuracy， OA）、平均準確度（Average Accuracy， AA）、一致性系數(shù)Kappa、運行時間Time和聚類結(jié)果圖作為實驗評估指標。表2為各個算法的計算時間復雜度對比。

表2　各個算法的計算時間復雜度對比

3.3　Indian Pines數(shù)據(jù)集上的實驗分析

表3為本文算法與其他算法在Indian Pines數(shù)據(jù)集的實驗結(jié)果對比，表中對最佳的結(jié)果進行加粗標記。就評價指標而言，SDASC算法的AA、OA、Kappa分別達到60.46%、34.65%、和28.69%。與-means算法相比，SDASC算法的AA、OA、Kappa分別提高了24.13個百分點、0.44個百分點、1.80個百分點，耗時降低了86.67%；SC算法運行時間最長，聚類精度不高，驗證了譜聚類算法在高光譜上應用效果不佳的特點；與SCAG算法、SGCNR算法、SPCA-SC算法、FSECSGL算法等改進譜聚類算法相比，SDASC的運行時間最少，并有大幅提升，相較于耗時第二少的1.7 s運行耗時少了76.47%；平均準確度AA最高，較次高數(shù)值提升41.16%；總準確度OA指標排名第二，比SPCA-SC的OA低0.33個百分點；Kappa系數(shù)排名第一，較第二提高0.16個百分點。

表3　SDASC與其他算法在Indian Pines數(shù)據(jù)集上的比較

從圖2可見，SDASC算法得到的聚類圖錯分點與噪聲點更少，地物分布平滑，噪聲點聚類的視覺效果得到顯著的改善。因此可以看出，在Indian Pines數(shù)據(jù)集聚類中，使用SDASC算法聚類是有益的。SDASC算法充分利用高光譜圖像的空間信息進行有效降維，并與錨圖的思想結(jié)合，達到二次降維的效果，既有效保存圖像的主要信息又大幅提升了運行速度，進一步提高了算法聚類性能。

圖2　在Indian Pines數(shù)據(jù)集上不同算法的聚類效果

3.4　Salinas數(shù)據(jù)集上的實驗分析

表4為本文算法與其他算法在Salinas數(shù)據(jù)集的實驗結(jié)果對比，表中對最佳的結(jié)果進行加粗標記。SDASC算法的AA、OA、Kappa數(shù)值分別達到81.50%、57.84%、54.42%。由表4可知，SC、SPCA-SC算法已經(jīng)因為內(nèi)存溢出（Out of Memory， OM），無法應用在Salinas數(shù)據(jù)集上。與-means算法相比，SDASC算法的AA提升了26%，OA降低了1.8%，Kappa系數(shù)提升了1.1%，時間降低了51%；與基于錨點選取的SCAG算法比較，SDASC算法的AA提升了20%，OA提升了28%，Kappa系數(shù)提升了36%，運行時間減少了5%；與SGCNR算法比較，SDASC算法的AA提升了約25%，OA提升了21%，Kappa系數(shù)提升了27%，運行時間減少了86%；與FSECSGL相比，運行時間上減少了99%左右，而AA、OA、Kappa三個指標分別提升了67%、82%、139%。

表4　SDASC與其他算法在Salinas數(shù)據(jù)集上的比較

與Indian Pines數(shù)據(jù)集上的實驗類似，SDASC處理Salinas高光譜圖像可以進一步提高聚類精度。由于高光譜地物復雜且具有不同的數(shù)據(jù)結(jié)構(gòu)，-means算法在聚類過程中無法確保每一個指標的數(shù)值都為最佳，基于SC的改進算法容易出現(xiàn)精度不高、耗時長、堆內(nèi)存溢出（OM）等問題，而SDASC算法在對數(shù)據(jù)集進行超像素降維與錨點選取后，性能指標在AA和 Kappa 上都是最高的，OA與最高值也相差不大。由圖3可知，相較于其他算法的處理效果，SDASC的聚類圖像噪聲點、錯分點更少，區(qū)域邊界分明，視覺上的體驗更好。

圖3　在Salinas數(shù)據(jù)集上不同算法聚類效果

3.5　實驗結(jié)論

綜上可看出，本文提出的SDASC算法可以有效降低譜聚類算法在高光譜圖像處理中的計算耗時，并提高聚類精度。

4 結(jié)語

針對傳統(tǒng)譜聚類算法應用在高光譜圖像上容易內(nèi)存溢出，改進譜聚類算法在高光譜圖像應用上聚類精度低、耗時長的問題，提出了一種基于超像素錨圖二重降維的快速高光譜圖像聚類方法。SDASC算法創(chuàng)新性地將PCA、超像素降維、構(gòu)建錨圖、無核去參的方法與譜聚類融合并應用于高光譜圖像中。該算法首先對高光譜圖像進行降維處理，考慮了高光譜圖像多區(qū)域特征不同的特性，對其進行了超像素降維處理，有效去除冗余信息，隨后進行錨點提取，在構(gòu)建錨圖的過程中進行了去除高斯核優(yōu)化。為驗證本文算法的優(yōu)越性，分別在Indian Pines與Salinas高光譜數(shù)據(jù)集上進行了實驗，將算法的聚類指標AA、OA、Kappa與運行耗時和其他算法進行了對比，實驗結(jié)果說明，SDASC算法能夠有效處理高光譜圖像，在降低計算耗時的同時提升聚類精度。

[1] 杜培軍，夏俊士，薛朝輝，等. 高光譜遙感影像分類研究進展［J］. 遙感學報， 2016， 20（2）：236-256.（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.）

[2] 王相海，王順，謝釋鋮，等. 高光譜圖像光譜維結(jié)構(gòu)相關(guān)性及稀疏重建模型［J］. 中國科學：信息科學， 2021， 51（3）：449-467.（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.）

[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.（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.）

[5] 許裕雄，楊曉君，蔡湧達，等. 基于二叉樹錨點的高光譜快速聚類算法［J］. 激光與光電子學進展， 2021， 58（2）： No.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.）

[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.

[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.

[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] 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.

[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.

[12] 趙薔. 主成分分析方法綜述［J］. 軟件工程， 2016， 19（6）：1-3.（ZHAO Q. A review of principal component analysis［J］. Software Engineering， 2016， 19（6）： 1-3.）

[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.

[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.

[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.

[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.

[17] 陳永，盧晨濤. 基于超像素分割和暗亮通道結(jié)合的單幅圖像去霧［J］. 激光與光電子學進展， 2020， 57（16）： No.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.）

[18] NIE F P， ZHU W， LI X L. Unsupervised large graph embedding based on balanced and hierarchical-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.

[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.

[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.

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.

XU Sha， born in 1988， Ph. D.， lecturer. Her research interests include data mining.

YANG Xiaojun， born in 1983， Ph. D.， associate professor. His research interests include clustering algorithm， intelligent information processing.

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

LAI Xingjin1， ZHENG Zhiyuan2， DU Xiaoyan3， XU Sha1*， YANG Xiaojun1

（1，，510006，；2，，’710025，；396962，102206，）

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.

hyperspectral image; super-pixel segmentation; anchor graph; spectral clustering; dimension-reduction

This work is partially supported by Research and Development Program in Key Areas of Guangdong Province （2018B010115001）， Natural Science Foundation of Guangdong Province （2021A1515011141）.

TP751

A

1001-9081（2022）07-2088-06

10.11772/j.issn.1001-9081.2021050825

2021?05?19；

2021?09?23；

2021?09?28。

廣東省重點領域研發(fā)計劃項目（2018B010115001）；廣東省自然科學基金資助項目（2021A1515011141）。

賴星錦（1998—），男，廣東揭陽人，碩士研究生，主要研究方向：聚類算法； 鄭致遠（2000—），男，廣東廣州人，主要研究方向：降維算法； 杜曉顏（1980—），女，河南方城人，工程師，主要研究方向：數(shù)據(jù)挖掘； 徐莎（1988—），女，湖北武漢人，講師，博士，主要研究方向：數(shù)據(jù)挖掘； 楊曉君（1983—），男，安徽潁上人，副教授，博士，主要研究方向：聚類算法、智能信息處理。