Zhen Ye, Shihao Shi, Zhan Cao, Lin Bai, Cuiling Li, Tao Sun, Yongqiang Xi

Abstract: Hyperspectral image (HSI) contains a wealth of spectral information, which makes fine classification of ground objects possible. In the meanwhile, overly redundant information in HSI brings many challenges. Specifically, the lack of training samples and the high computational cost are the inevitable obstacles in the design of classifier. In order to solve these problems, dimensionality reduction is usually adopted. Recently, graph-based dimensionality reduction has become a hot topic. In this paper, the graph-based methods for HSI dimensionality reduction are summarized from the following aspects. 1) The traditional graph-based methods employ Euclidean distance to explore the local information of samples in spectral feature space. 2) The dimensionality-reduction methods based on sparse or collaborative representation regard the sparse or collaborative coefficients as graph weights to effectively reduce reconstruction errors and represent most important information of HSI in the dictionary. 3) Improved methods based on sparse or collaborative graph have made great progress by considering global low-rank information, local intra-class information and spatial information. In order to compare typical techniques, three real HSI datasets were used to carry out relevant experiments, and then the experimental results were analysed and discussed.Finally, the future development of this research field is prospected.

Keywords: hyperspectral image; dimensionality reduction; graph embedding; sparse representation;collaborative representation

1 Introduction

Hyperspectral images (HSI) are used in many fields due to their rich feature information, such as geological exploration, fine agriculture, ecological environment, urban remote sensing and other fields [1]. However, the redundant spectral information may lead to “Hughes” phenomenon,which makes the classification accuracy decrease[2−4]. Therefore, dimensionality reduction as an effective means to solve the problem has attracted more and more scholars’ attention. HSI dimensionality reduction can be categorized as band selection or spectral feature extraction [5].The former selects representative bands to represent the original data, while the latter retains the important information through mathematical transformation. As a hot topic, the latter is usually implemented by projecting HSI into a lower dimensional feature space. Principal component analysis (PCA) and Fisher’s linear discriminant analysis (LDA) are two traditional projection-based methods used for HSI dimensionality reduction [6−8]. PCA aims to find projections with a minimal reconstruction error of the global information, whereas LDA seeks to find projections that preserve the necessary information to separate the categories of targets[9−12]. In order to improve PCA and LDA, variant algorithms are proposed [13,14], such as kernel PCA [15], super PCA [6], super KPCA [16],hierarchical PCA [17], and so on.

As graph embedding framework was proposed [18,19], graph theory has been employed to develop dimensionality reduction methods that extract the statistical and geometric structural information in HSI by constructing an undirected weighted graph. The main idea of graphbased dimensionality reduction strategy is to derive a lower dimensional representation by constructing a graph weight matrix to solve a generalized eigenvalue problem [20,21]. Popular graphbased algorithms use Euclidean distance to describe the relationships between data, such as locality preserving projections (LPP) and locality preserving nonnegative factorization (LPNMF) [22,23]. As an unsupervised dimensionality reduction algorithm, LPP considers the manifold structure which is modelled by a nearest-neighbor graph to preserve the local structure of each class [24]. Based on LPP, LPNMF proposes to use nonnegative matrix factorization (NMF) to ensure that the eigenvalues are non-negative and use Kullback-Leibler divergence to explore the hidden similarity between data, thus ensuring the expected results after dimensionality reduction[25−28]. Above mentioned dimensionality reduction algorithm based on the class-condition distribution being a single Gaussian, which is not consistent with the fact that the class-condition distribution is multimodal [29−31]. Sugiyama proposed another graph-based dimensionality reduction method—local Fisher’s discriminant analysis (LFDA) to solve the multimodal problem [29].LFDA combines LDA with LPP to preserve the local structure in a low-dimensional manifold subspace and uses manifold learning to adapt to a multimodal structural environment. Then, The LFDA-related HSI classification algorithm was studied, such as, LFDA-GMM [32], LFDAGMM-MRF [33], 3DDWT-LFDA-GMM [34], unsupervised image-adapted LFDA [35], semi-supervised local fisher [36,37], genetic algorithm-LFDA [38], probability distribution LFDA [39], GFLFDA-RF [40], and kernel LFDA [41].

The traditional graph-based methods are sensitive to data noise and may result in suboptimal graph representation [42]. To address this problem, sparse representation was considered for HSI dimensionality reduction, since the sparse coefficients can be viewed as the graph weight to result in fewer reconstruction errors and can represent most of the important information in a dictionary. Although the regularization based onl0- norm has the desired sparse effect, its optimal solution is difficult to obtain due to the NP-hard problem [43,44]. A sparsity-preserving graph-embedding (SPGE) [45] was proposed to construct a graph whose edges are intended to be sparse exploring the sparsity structure of the data by anl1-norm optimization. To preserve the sparse relations in the graph, Ly et al. proposed sparse graph-based discriminant analysis (SGDA) [46].Different from traditional graph-based algorithms, SGDA uses Euclidean distance to measure the similarity between two points and constructs a sparse graph based onl1- norm regularization to preserve the sparse relationships in the original data [47−50]. Although SGDA can effectively find the neighborhood elements of the target elements, it lacks the constraint of global data and then cannot maintain the global geometric structure of HSI data, which affects the classification performance. To solve this problem,the sparse and low-rank graph-based discriminant analysis (SLGDA) [42] combines SGDA with low-rank representation [51] to effectively preserve the global information. He et al. argued that data localization is usually more important than data sparsity, so the weighted sparse graph based dimensionality reduction (WSGDR) [52]can obtain better classification performance by performing sparse coding in localization. In addition, Feng et al. argued that the Euclidean distance cannot measure the intrinsic spectral variation of an object and proposed graph-based discriminant analysis with spectral similarity(GDA-SS) [53]. GDA-SS uses the absolute difference between pairs of pixels to measure the similarity between spectra and sets a threshold to mitigate the effect of noise, effectively reflecting the intrinsic structures of HSI and achieving better classification results than SGDA.

Sparse graph-based strategies are superior to k-nearest-neighbor graphs (such as LPP) for dimensionality reduction of HSI, due to preserving the sparse connection in the manifold [46].However, sparse representation may not be accurate due to over-sparseness issue from profound within-class variation. Different from SGDA, the collaborative graph-based discriminant analysis (CGDA) usesl2- norm instead ofl1-norm to construct collaborative graphs, which means that the “collaborative” nature can be instead of“competitive” nature imposed by the sparsity constraints [54−56]. Therefore, CGDA has higher computation efficiency due to a close-form solution. Since the global structure of subgraphs are local to the overall data, block CGDA (BCGDA)maintains the local manifold structure of the data [57], significantly improving classification performance and reducing calculation cost.

In fact, collaborative representation usually results in a dense distribution of the representation coefficients, which may yield error discriminant results. To address the drawbacks of CGDA and BCGDA, a Laplacian regularization-based CGDA framework named Laplacian-CGDA(LapCGDA) was proposed [58] to preserve the flow structure in HSI data and exploit the intrinsic geometric information. In addition, Ye,et alproposed adaptive-CGDA (ACGDA) [59] for graph construction that reinforces the class-discriminant power and within-class representation,efficiently and adaptively, combining collaborative representation and distance-weighted Tikhonov regularization [60−62].

The above graph-based dimensionality reduction methods utilize the spectral information in HSI, but neglecting spatial information. In recent years, some scholars introduce spatial information into these methods in order to further improve the discriminant ability for HSI data[63−65]. Thereinto, Laplacian regularized spatialaware CGDA (LapSaCGDA) [66] uses regularization constraints to combine spatial information with spectra, tensor-SLGDA (TSLGDA) [67]treats HSI as a third-order tensor and extracts spatial information from a small block centered on the target element, and Nystrom-based kernel SLGDA (nKSLGDA) employs the Nystrom method to create a virtual kernel space dealing with nonlinear data [68]. Aiming at smallsamples-size (SSS) problem in HSI classification,some scholars have proposed to use pseudolabeled samples instead of real-labeled samples to classify HSI data [69,70]. At the same time, semisupervised and unsupervised graph-based approaches were also studied. Zhang proposed a semi-supervised approach to cope with the situation of insufficient labeled samples [71]. Gan et al. proposed an unsupervised method multi-structure manifold embedding (MSME), which obtains the optimal projection matrix by combining sparse graphs, sparse hypergraphs and local linearity properties [72]. An unsupervised approach, named collaboration-competition preserving graph embedding (CCPGE), constructs a“collaboration-competition” diagram, exploiting the relationship of inter-class and intra-class samples to effectively learn the global geometry and local manifold structure [73].

The remainder of this paper is organized as follows. In Section 2, we review the traditional graph-based dimensionality reduction methods,such as, LPP, LPNMF and LFDA. Section 3 presents sparse and collaborative graph-based dimensionality reduction methods, including SGDA, SLGDA, CGDA, BCGDA, ACGDA and CCPGE. In Section 4, we provide a description of the HSI datasets used for performance evaluation, as well as a detailed comparison with the traditional and state-of-the-art methods. Finally,we conclude the presented work.

2 Traditional Graph-Based Dimensionality Reduction

As a method that can be applied to multimodal environments, manifold learning aims to find lowdimensional stream structures of data that are in a high-dimensional space. Graph theory has been employed to develop methods that constructs graph by exploiting the geometric structure and preserving the similarity in his [74−77]. The main idea of graph-based DR strategy is to derive a lower dimensional representation by constructing a graph weight matrix to solve a generalized eigenvalue problem. Traditional graph-based methods mainly depend on pairwise Euclidean distance; for example, locality-preserving projection (LPP) [9], locality-preserving non-negative matrix factorization (LPNMF) [27] and local Fisher’s discriminant analysis (LFDA) [29].

2.1 Locality-Preserving Projection

To reduce redundant information in high-dimensional data spaces, dimensionality reduction is proposed as an essential pre-processing step that can reduce computational costs as well as potentially improve classification accuracy. Here, locality-preserving analysis explores the local relationships of the data while achieving dimensionality reduction. Locality-preserving projection (LPP),as an unsupervised and linear projection method for dimensionality reduction, preserves the local structure of data by constructing nearest neighbor graphs. How to optimally preserve the results of the original data neighbourhoods will be a problem for LPP. It is believed that when highdimensional data lie on a low-dimensional manifold embedded in the environment space, a locally preserved projection can be obtained by finding the optimal linear approximation of the eigenfunction of the Laplace operator on the manifold. Thus, the problem of solving the eigenmap is transformed into the problem of obtaining the generalized eigenvalue, which improves the computational efficiency effectively.

Obtain the eigenmaps by solving the eigenvectors and eigenvalues in the generalized eigenvalue problem

whereΛis the diagonal eigenvalue matrix,Wis the eigenvector matrix,L=D–Wis the Laplacian matrix, andDis a diagonal matrix with theithdiagonal element.

2.2 Locality-Preserving Non-Negative Matrix Factorization

whereY={yi,j}=UVT. Since the objective function is not a convex optimization problem when dealing withUandV, which makes solving the global minimum inOvery difficult, Li et al. proposed an iterative algorithm to solve this problem [25,26].

Although NMF is applied to the dimensionality reduction task of HSI, its failure to consider the intrinsic structure of the data makes the improvement of classification accuracy hindered.Therefore, Cai et al. proposed locality-preserving non-negative matrix factorization (LPNMF)combines LPP with NMF, which effectively improves the classification accuracy [27]. Different from traditional NMF, the objective function of the LPNMF can be defined as

whereλis the regularization parameter. The objective function of NMF is utilized in the left part of Eq. (4) to measure the Kullback-Leibler divergence betweenXandY. On the right-hand side of the equation,Ris the constraint used to preserve local geometric properties, denoted as

The local geometric structure can be obtained by modelling the nearest neighbour graph on a scatter graph, so that a graph can be considered as a document withNvertices and each point corresponds to a corpus. The edge-weight matrixWcan be defined as

whereNp(xs) represents the set ofPnearest neighbours ofxsused to measure the distance between points in the original data space,X.Similar to the theory of LPP, this matrix is able to preserve the intrinsic geometric structure in the data distribution. Thus, the minimization of the functionOand the estimation of the matricesUandVcan be expressed as

wherevqis theqthcolumn ofV,Iis theN×Nidentity matrix andLis the Laplacian matrix ofW. Limited by the spatial resolution of HSI,most of the spectrum of a single pixel is a mixture of multiple endmembers. LPNMF is able to preserve the intrinsic geometric structure in HSI by extracting the features of the endmembers.

2.3 Local Fisher's Discriminant Analysis

LFDA combines the properties of LDA and LPP,exploiting the advantages of each and preserving the neighbourhood relationships within the embedding by employing an “similarity or affinity”matrix [78].

The local Fisher’s discriminant analysis (LFDA), as a supervised method, combines LDA with LPP for dealing with multimodal, non-Gaussian distributed data [29]. Similar to LPP,LFDA uses the affinity matrix to preserve the neighbourhood relationships in the embedding graph. In addition, LFDA uses the same heat kernel approach as in Eq. (1). In the LFDA, the“local” inter-classS(lb)and intra-classS(lw)scatter matrices is scaled by the affinity matrix and defined as

where bothW(lb)andW(lw)areN×Nmatrices

The values of pairs of data within a class are weighted according to the affinity inS(lb)andS(lw), which are weakly dependent on the farpart, intra-class pair of elements. According to the nature of the local scatter matrix, the solution of the maximum Fisher ratio is expressed as

whereΛis the diagonal eigenvalue matrix andϕis the eigenvector matrix. Since the maximum Fisher ratio is defined by the local scatter matrix,thenTLFDAcan be calculated by

whereTis determined so that data pairs of different classes are apart and nearby data pairs of the same class are close. Since the far-apart data pairs of the same class are not assumed to be close, the LFDA can be viewed as a localized LDA. The modified Fisher’s ratio in the LFDA treats samples of a class within each mode independently so that it can estimate the dimensionality-reduction projection by these local scatter matrices and obtain good between-class separation while preserving local neighbourhoods. It is hence expected that the LFDA will be superior to the LDA when the distributions of input data are complex and even multi-modal.

3 Sparse and Collaborative Graph-Based Dimensionality Reduction

The traditional graph-based methods, whose structures depend on pairwise Euclidean distance,are sensitive to data noise and may result in suboptimal graph representation. As a key theory for graph-based methods, the graph embedding framework provides a unified template for subsequent dimensionality reduction algorithms. The core step in graph-based methods is the construction of the graph, and one of the more popular methods is to use sparse representation regularization or collaborative representation regularization to construct the graph. As popular graphbased representation methods, sparse graphbased discriminant analysis (SGDA) and the collaborative graph-based discriminant analysis(CGDA) have achieved good performance.However, both SGDA and CGDA have more obvious shortcomings due to their paradigm. For example, SGDA cannot preserve the global geometric structure of the data, while CGDA has poor performance in intra-class coefficients. To address these drawbacks, SLGDA, CCPGE and ACGDA as improved graph-based methods for HSI reduction methods.

3.1 Graph-Embedding Subspace Learning

In the graph embedding framework, graphbased dimensionality reduction methods are proposed, aiming to find a projection matrixPof sized×R(R≪d), which can generate a low-dimensional subspace by

In the above formula, certain statistical or geometric information in the dataset will be preserved. The objective function is defined as

which can be transformed into a generalized eigenvalue problem to solve

whereΛis a diagonal matrix ofRminimal nonzero eigenvalues with eigenvalues corresponding toRsmallest eigenvectors in the projectionP.

3.2 Sparse Graph-Based Discriminant Analysis(SGDA)

SGDA, as a supervised method, improves interclass separation by preserving sparse relationships in original data. To improve the NP-hard problem caused by the combinedl0-norm minimization, SGDA adopts thel1-norm minimization.For a single pixelxiin the dictionaryX, the sparse representation vector is obtained by solving the optimization problem for thel1-norm

wherewi=[wi1,wi2,···,wiN] is the sparse representation vector of size (N−1)×1 that corresponds toxiof sizeN×1, andXiis obtained by eliminatingxifromXandε>0 is a small tolerance. Therefore, the similarity (or affinity) matrixWis defined as

The generalized eigenvalue problem in Eq. (18) can be further expressed as

whereλis a Lagrange multiplier.

Sparse representation was considered for HSI dimensionality reduction, since the sparse coefficients can be viewed as the graph weight to result in fewer reconstruction errors and can represent most of the important information in a dictionary for HSI. In [19], the authors proposed a general formulation of graph-embedding (GE)and developed MFA-based methods to suppress the characteristics of the penalty graph and preserve the characteristics of the intrinsic graph.Later, a sparsity-preserving graph-embedding(SPGE) [45] was proposed to produce a graph whose edges are intended to be sparse and explore the sparsity structure of the data by anl1-norm optimization. In [46], the authors formulated a supervised version of SPGE that incorporates class-label information for supervised discriminant analysis, named sparse graph-based discriminant analysis (SGDA), which exploits the discriminant capability from sparse representation and has more class-discriminant power than SPGE.

3.3 Sparse and Low-Rank Graph-Based Discriminant Analysis (SLGDA)

In [42], sparse and low-rank graph-based discriminant analysis (SLGDA) combines the low-rank representation with SGDA to take advantage of the low-rank representation in maintaining the global structure, effectively compensating for the shortcomings of SGDA and achieving good classification results. Therefore, the objective function of SLGDA is expressed as

whereβandλare regularized parameter terms for the low-rank representation and the sparse representation, respectively.X(l)denotes the sample vector of thelthclass andl=[1,2,···,C].

According to the formula, the sparse criterion uses the sparse representation to preserve the local structure of the data, while the lowrank criterion is used to keep the highly correlated data in the same cluster, and the combination of the two criterions will effectively preserve the global and local information of the original data and further improve the reliability of dimensionality reduction.

3.4 Collaborative Graph-Based Discriminant Analysis (CGDA)

Sparse graph-based strategies are superior to that of traditionally used k-nearest-neighbor graphs(such as LPP) and other commonly used methods (such as LDA and LPP) for dimensionality reduction of HSI, due to preserving the sparse connection in the manifold [46]. However, sparse representation with few samples may not be accurate due to profound within-class variation(over-sparseness issue). The collaborative representation usesl2-norm minimization instead ofl1-norm minimization to construct the similarity matrix for the purpose of using other samples to jointly represent the target elements. The collaborative representation vectorxiis obtained by solving the optimization problem withl2-norm

whereXiis set the same as Eq. (19) andwi=[wi1,wi2,···,wiN] is the collaborative representation vector corresponding toxiof size(N−1)×1. In addition, the objective function of CGDA is further expressed as

whereλ, as the regularization parameter, plays the role of balancing the minimization regularization term with the residual part. In addition, the regularization part plays two main roles: stabilizing the least squares solution; and introducing sparsity to the constructed graph that is weaker than SGDA. By using the derivative, the collaborative representation vector can be calculated as

The similarity matrixW=[w1,w2,···,wN]of sizeN×Ncontains the weight coefficients of the constructed graph as well as its diagonal elements set to zero. In addition, Ly N et al. proposed a method called BCGDA, the training samples of CGDA are optimized and the intraclass element collaborative representation is used to construct the graph power matrix.

Estimation of the similarity matrix (or affinity) by imposingl1-norm minimization may lead to higher computational cost. On the other hand,collaborative graph-based discriminant analysis(CGDA) employs the similarity matrix by imposingl2-norm minimization instead ofl1-norm minimization, which means that the “collaborative” nature can be instead of “competitive”nature imposed by the sparsity constraint [79].Additionally, CGDA has higher computation efficiency due to a close-form solution. In [58], the authors proposed a Laplacian regularized CGDA framework, in which a Laplacian graph was introduced into CGDA for dimensionality reduction.

Since the bands in HSI are highly correlated,it may be inaccurate to use all labelled samples to measure the relationship between test pixels.Further, the non-zero coefficients in the weight matrix may be provided by inter-class samples,which can limit the effect of sparse representation and collaborative representation. As a solution, intra-class samples are used to jointly represent the target elements and construct the graph weight matrix. To enhance the inter-class discrimination, the weight matrixWis designed in the following form.

3.5 Adaptive Collaborative Graph-Based Discriminant Analysis (ACGDA)

SGDA uses sparse representation to preserve the sparse connections in the manifold, which effectively improves the class discrimination, but it brings the problems of over-sparsity and high computational cost at the same time. For the CGDA-based strategy, the collaboration constraint-based optimization has the computational efficiency and accuracy of the closed solution,but the collaborative representation also brings the problem of dense distribution of coefficients,which hinders the improvement of the classification accuracy. To address the drawbacks of CGDA and sparse graph-based strategies, ACGDA are proposed for graph construction that reinforces the class-discriminant power and withinclass representation, efficiently and adaptively,by combining the power of collaborative representation and distance-weighted Tikhonov regularization [60,62].

In ACGDA, an adaptive graph is constructed for dimensionality reduction of hyperspectral imagery. By adding weighted Tikhonov regularization, the proposed graph fully exploits the internal relationship among pixels, producing stronger ability of discrimination. The objective function of the proposed graph is optimized byl2-norm minimization with a closed-form solution and the graph weight matrix is designed in the form of a block-diagonal structure. Thus, the computational complexity of the proposed method is decreased.

where the collaborative representation vector corresponding toxliswl=[wl1,wl2,···,wlml],Γlis a biased Tikhonov matrix with respect tolthandλis the regularization parameter that serves to balance the minimization between regularization term and the residual part. Tikhonov matrix follows the norm of the Euclidean parametrization,and its regularized part is expressed in the following form

Based on CGDA, ACGDA introduces the distance-weighted Tikhonov matrix into the collaborative representation, which serves to adjust the collaborative representation vector. The presence of the Tikhonov matrix makes the elements more similar to the target elements assigned to larger weight coefficients, thus improving the distribution of intra-class coefficients in the weight matrix and enhancing the class discrimination ability.

Since ACGDA is a modification of CGDA, it can also be solved in closed form, i.e., the graph weights can be obtained by deriving the cost function

Then, by setting the value of Eq. (30) to zero,the minimumwlcan be obtained in the following form

In addition, the adaptive graph matrix in the block-diagonal form is constructed by Eq. (26)and the generalized eigenvalue problem can be solved by Eq. (18).

Fig.1 illustrates the graph weight matrixes for SGDA, CGDA and ACGDA using the threeclass synthetic data consistent with the labelled samples. All matrixes exhibit a block-diagonal structure (three blocks corresponding to three classes) described as Eq.(26), which means the three graph weights are capable of sample separation between different classes. As shown in Fig.1 (a) and (b), the distribution of weight coefficients of SGDA is significantly sparse, while the distribution of CGDA is more compact, which is determined by the properties of sparse representation and collaborative representation. As shown in Fig.1 (c), the sparsity of ACGDA is between the ones of SGDA and CGDA, which indicates that ACGDA coupled adaptive independent measure with collaborative representation can preserve the intrinsic structures, thus reinforcing discriminant power.

Fig.1 Visualization of the weight matrix of the two methods on three class of synthetic data: (a) SGDA; (b) CGDA;(c) ACGDA

3.6 Collaboration Competition Preserving Graph Embedding (CCPGE)

Since most graph-based dimensionality reduction algorithms explore only the spectral information and ignore the spatial information in HSI. Although the collaborative representation has high computational efficiency and good classification performance when solving as a closed solution, its performance in maintaining the local structure of the data is not satisfactory. To address the situation, an unsupervised algorithm was proposed,named CCPGE [73]. The collaborative representation and the competitive representation are fused by CCPGE, in which the competitive constraint is employed to enhance the weight of neighboring elements, further exploring the intrinsic structure of the data. CCPGE introduces competitive constraints into the objective function to improve the competitiveness of the neighboring elements of the target element, thereby realizing exploration of spectral and spatial information. The objective function of CCPGE is expressed as

4 Experimental Results and Analysis

In the experimental session, we mainly analyze traditional and sparse/collaborative graph-based methods, including LPP, LPNMF, LFDA, SGDA, LGDA, SLGDA, CGDA, BCGDA, ACGDA and CCPGE. To analyze the performance of the ten methods mentioned above, three real HSI datasets were employed in experiments.

1) Indian Pines

The Indian Pines dataset is a typical HSI dataset of size 145×145 collected with an AVIRIS sensor at the Indian Pines test site in northwestern Indiana. The dataset consists of 224 bands with a resolution of 20 m. After removing noise bands, the data contains 220 available bands. In the experiment, we extracted 150 samples in each class as a training set. The detailed information is indicated in Tab. 1.

Tab. 1 Class labels and train-test distribution of samples for the Indian Pines dataset

2) University of Pavia

The University of Pavia dataset is composed of part of the data taken by the Reflection Optical Spectral Imager (ROSI) in Pavia. The image size is 610×340, contains 115 bands, and the resolution is 1.3m. After removing noise bands, the data contains 103 available bands. In the experiments, we extract 200 samples from each class as a training set. The detailed information is provided in Tab. 2.

Tab. 2 Class labels and train-test distribution of samples for the University of Pavia dataset

3) Houston

The Houston dataset is composed of a dataset of size 349×1 905 collected in the Houston area using the ITRES CASI-1 500 sensor. The dataset consists of 144 bands in the hyperspectral range of 380 nm to 1 050 nm with a resolution of 2.5 m. In our experiments, we extract 100 samples from each class as the training set. The specific information is shown in Tab. 3.

Tab. 3 Class labels and train-test distribution of samples for the Houston dataset

Tab. 4 Classification accuracy (%) for the Indian Pines dataset

Tab. 5 Classification accuracy (%) for the University of Pavia dataset

Tab. 6 Classification accuracy (%) for the Houston dataset

In order to analyze the experimental results efficiently and conveniently, support vector machine (SVM) is a generalized linear classifier that classifies data in a supervised manner and has powerful capabilities to classify both linear and non-linear data. For further exploring the effect of parameters of the proposed methods, the following work utilizes a cross-validation strategy for parameter optimization and employs the overall classification accuracy (OA) and Kappa coefficient (KA) to evaluate the performance of each method.

For graph-based dimensionality reduction algorithms, the number of dimensions is a very important parameter, which plays a key role in the final classification performance. In Fig.2, we set the range of the parameterRfrom 2 to 40, and the interval is 3. For the Indian dataset, the parameterRis set to 8 for LFDA and 11 for LPP, while the seven sparse/collaborative graphbased algorithms achieve the optimal classification accuracy roughly at 17. For the University dataset, LGDA has the best classification accuracy when the parameter is taken as 8, the classification accuracy of SGDA and CCPGE tends to be stable when theRvalue tends to 40, while the other six algorithms have the best classification performance when theRvalue is taken as 11.Similarly, for the Houston dataset, parameter is set to 8 for LGDA and performance of CCPGE stabilized whenRis 20, while the other seven methods achieved optimal performance whenRis 11.

Fig.2 OA (%) versus reduced dimensionality R of extracted features for methods using the three experimental datasets: (a) Indian Pines; (b) University of Pavia; (c) Houston

From Tabs. 4–6, overall accuracy (OA) and Kappa coefficient (KA) are employed to evaluate the performance of the ten algorithms. To avoid any bias induced by random sampling, the classification results of all methods are averaged over 15 trials. First, the discriminant ability of traditional methods is generally weak, while sparse/collaborative graph-based methods yield more satisfactory performance. Based on SGDA,SLGDA explores the global structural information of the data species using low-rank representation, and thus can achieve better classification results than SGDA. Similarly, SLGDA will perform better relative to LGDA because it explores the local relationships in HSI. The results show that BCGDA has better classification results than CGDA, further demonstrating that the collaborative representation performs better in intra-class data than in inter-class data. In addition, ACGDA optimizes the collaborative representation using Tikhonov matrix, adaptively improves the distribution of intra-class coefficients,and has better classification performance compared to BCGDA. Based on CGDA, CCPGE is studied as an unsupervised method to combine spatial and spectral information using competitive constraints to achieve good performance.

Figs. 3–5 further illustrate the classification maps for the datasets corresponding to the methods as listed in Tabs. 4–6, respectively. According to the three figures, when compared with three traditional graph-based methods (i.e., LPP,LPNMF and LFDA), the sparse/collaborative graph-based methods (i.e. SGDA, LGDA, SLGDA, CGDA, BCGDA, ACGDA and CCPGE)provide obvious improvement of performance as well as smoother classification maps with fewer erroneous outliers.

Fig.3 Thematic maps resulting from classification for the Indian Pines dataset: (a) False-color image; (b) Ground-truth; (c) LDA:77.13%; (d) LPP: 75.97%; (e) LFDA: 80.01%; (f) SGDA: 71.19%; (g) LGDA: 84.81%; (h) SLGDA: 85.42%; (i) CGDA:80.63%; (j) BCGDA: 86.24%; (k) CCPGE: 83.56%; (l) ACGDA: 87.42%

In general, the number of tagged training samples is not sufficient to better predict the model for each class, so it is meaningful to detect how the dimension reduction algorithm performs at different numbers of training samples.Fig.6 represents the overall classification accuracy (OA) as a function of varying training samples for each class. As can be seen, we set the number of training samples per class for the Indian dataset and the University of Pavia dataset from 120 to 250, 50 to 100 for the Houston dataset. To avoid any bias induced by random sampling, the classification results of all methods are averaged over 20 trials. It is clear from the results that the classification results of each method increase as the sample size increases.However, the ACGDA method always works better than the other methods (even with a lower sample size), which indicates that the ACGDA method is able to further explore the hidden information in HSI data.

Fig.6 Classification accuracy as a function of sample size for different training samples per class: (a) Indian Pines; (b) University of Pavia; (c) Houston

Fig.4 Thematic maps resulting from classification for the University of Pavia dataset: (a) False-color image; (b) Ground-truth; (c)LDA: 80.95%; (d) LPP: 83.18%; (e) LFDA: 84.43%; (f) SGDA: 81.35%;(g) LGDA: 86.41%;(h) SLGDA: 87.91%; (i) CGDA:87.64%; (j) BCGDA: 89.00%; (k) CCPGE: 86.86%; (l) ACGDA: 90.26%

To visualize the computational complexity of the mentioned algorithms, we use the running time of a single program as a criterion for comparison. All experiments are carried out on MATLAB on a 3 GHz machine with 16 GB of RAM. As can be seen in Tab. 7, the computational efficiency of the traditional graph-based methods is significantly higher than that of the representation-based methods. This is because traditional graph-based methods only require the construction of similar graphs with simple structures. Due to the need to explore the hidden structural information in the data, the representation-based approaches require more computational cost when constructing graphs. In addition, since BCGDA and ACGDA use intra-class data as input to construct graphs, their computational efficiency is higher than that of methods(CGDA, SGDA, SLGDA) that construct graphs with inter-class data.

Tab. 7 Running time for the three datasets s

Fig.5 Thematic maps resulting from classification for the Houston dataset: (a) False-color image; (b) Ground-truth: (c) LDA:80.30%; (d) LPP: 76.69%; (e) LFDA: 82.20%; (f) SGDA: 78.93%; (g) LGDA: 86.73%; (h) SLGDA: 88.09%; (i) CGDA:83.28%; (j) BCGDA: 87.62%; (k) CCPGE: 89.94%; (l) ACGDA: 90.89%

According to the above experimental results and analysis, we have summarized some important points. First, traditional graph-based methods mainly depend on pairwise Euclidean distance. These methods are sensitive to data noise,and their graph structures are unstable with additive noise. The sparse (or collaborative) graphbased methods employ sparse (or collaborative)coefficients as the graph weight to represent most of the important information in a dictionary for HSI and result in fewer reconstruction errors.Second, only the local information is considered in SGDA, which may be ineffective in capturing the global structures of HSI data. Low-rank representation is considered for preserving global data structures in LGDA. Therefore, SLGDA,combining global geometrical structure with local prevalent structural information in HSI, has better classification performance than using one type of structural information of HSI data alone.Third, CGDA has shown success over SGDA and traditional methods by reinforcing discriminative power, but is limited in within-class representation and distribution of representation coefficients. Block-based methods withl2-norm minimization representation, such as BCGDA and ACGDA, preserve intrinsic geometrical structure of original data and improve the interpretability of the underlying graph through modeling the internal relationship among within-class pixels during graph construction. Fourth, although the collaborative representation has high computational efficiency and classification performance when solving as a closed solution, its performance in maintaining the local structure of the data is not satisfactory. To address the situation, CCPGE considers local spatial information by employing the competitive constraint to enhance the weight of neighboring elements and explore the intrinsic structure of HSI data.

5 Conclusion

Hyperspectral image (HSI) contains a wealth of spectral and radiation information. Therefore, it can be applied to accurately classify ground objects in geological exploration, fine agriculture,ecological environment, urban remote sensing,military target detection and other fields.However, there are many challenges and difficulties in classification applications, since HSI has the properties of a large dataset, multiple bands and strong band correlation. Specifically,the number of dimensionalities of HSI are often more than the number of available training samples. The lack of training samples and high computational cost are the inevitable obstacles in designing classifiers. In order to avoid “Hughes”phenomenon, dimensionality reduction (DR)technique has been developed rapidly. In this paper, we review graph-based DR methods, including traditional graph-based DR methods (e.g.LPP, LPNMF and LFDA), sparse/collaborative graph-based DR methods (e.g. SGDA, CGDA,SLGDA, BCGDA and ACGDA) and unsupervised graph-based methods (e.g. CCPGE).

Traditional graph-based DR methods are sensitive to data noise and may result in suboptimal graph representation. Sparse/collaborative graph-based DR methods can obtain better discriminant results, since the sparse/collaborative coefficients can be employed to construct the graph weight to result in fewer reconstruction errors and represent most of the important information in a dictionary for HSI. For sparse/collaborative graph-based DR methods, the key point is how to construct a more representative graph.According to the above experiments and analysis,it is clear that the graphs constructed by using various structural information in HSI data will have more advantages. However, some scholars point out that the current graph-based DR methods only use the shallow information in HSI, but lacks the mining of deep information. We also believe that how to combine the methods of graph embedding with graph deep learning is of research significance in future.