2.1.

Search Algorithms

The aim of the feature (channel) selection methods is to select the best combination of $n$ out of $N$ variables on the basis of a predefined metric of performance. In the supervised FS for DR of hyperspectral images, finding a truly optimal combination is very challenging due to the dimensionality of data. The selection of a limited number of channels, e.g., 10, from an original hyperspectral image, with, e.g., 224 channels, requires the evaluation of a huge number of combinations, i.e., $7.15\times {10}^{16}$, which makes the evaluation of all of them impossible. This problem is known to be NP-hard.^36,37 Therefore, instead of an exhaustive search, a greedy algorithm, which solves the problem heuristically to find a near optimal solution, is usually apply.³⁸

There are several search strategies to select $n$ out of $N$ spectral channels of an original hyperspectral dataset. Here, we briefly explain three frequently used search algorithms, which later will be compared with the SRS method.

2.2.

Separability Metrics

The separability distance shows how well the given classes are separated in the feature space, which provides guidance for the actual classification of images. Swain and Davis defined the separability analysis as a performance assessment based on the training data to estimate the expected error in the classification for various feature combinations.²²

There are several separability metrics, with the simplest ones only taking into account the interclass distances, while most consider both interclass distance and intraclass diameter. Figure 1 schematically shows two normally distributed classes [$N({\mu }_a,{\sigma }_a^2),N({\mu }_b,{\sigma }_b^2)$] in one-dimensional feature space. The distance obtained from the mean values $({\mu }_a-{\mu }_b)$ gives the interclass distance, and the variances of the classes (${\sigma }^2$) indicate the intraclass diameters.

Fig. 1

Two hypothetical classes with normal distribution in one-dimensional feature space.

We applied six separability metrics in this study for FS. The equations of the metrics are given in this review, and more details on them can be found in Refs. 18, 22, 24, and 43. Let $a$ and $b$ be two given classes, $\mu =\{{\mu }_1,{\mu }_2,\dots ,{\mu }_n\}$ and $\mathrm{\Sigma }$ be the mean vector and covariance matrix of a class in an $n$-dimensional feature space, respectively, and ${\sigma }_i$ be the variance of a class in the $i$’th dimension. The six separability metrics are as follows:

All of the mentioned separability metrics compute the distance between two classes. In multiclass cases, a common solution is to calculate the average distance over all class pairs⁴³

3.1.

Spectral Region Splitting

In the SRS method, the spectrum is split into spectral bands with different spectral widths. This method is an iterative top-down algorithm, and, therefore, a termination point must be chosen to stop the iterations. We use the term “bands” to refer to the spectral regions, either narrow or wide, obtained by the SRS algorithm and the term “channels” to refer to the narrow spectral channels in the original hyperspectral image data.

Let $R$ be an original hyperspectral image with $N_c$ channels and $N_p$ pixels: $R=\{R_{ij}|1\le i\le N_c,1\le j\le N_p\}$, and $R_{ij}$ is the $i$’th signal value in the $j$’th pixel. Assume that a reduced spectral band configuration ($A$) with $k$ bands, $k\in {\mathbb{Z}}^{+}$ and $k\le N_c$, is $A=\{A_{tj}|1\le t\le k,1\le j\le N_p\}$, and $A_{tj}$ is the value of the $t$’th band in the $j$’th pixel. The number of splits is $k-1$, with $N_c-1$ possible spectral locations. The set $S=\{s_1,s_2,\dots ,s_{k-1}\}$ gives the split locations sorted with respect to their wavelength, so $s_1<s_2<\dots <s_{k-1}$. Determining the splits does not necessarily occur in the same order, e.g., the first split found can be any $s\in S$. By defining $s_0$ and $s_k$ as the beginning and the end of the spectrum in $S$, then $S=\{s_0,s_1,\dots ,s_{k-1},s_k\}$, and $A$ is defined by

If one band is required, there will be no split and the signal per pixel in this band will be the mean value of all spectral channels. It has no spectral detail whatsoever. If the measurements in the individual channels are noisy due to the narrow spectral bandwidth of the spectrometer, the wide band will have a much better signal to noise ratio than the individual channels. Therefore, an advantage of the broadband over the narrow channels is that at least the radiance is computed with less random noise. However, the loss of all spectral details is the disadvantage.

If $k>1$, then the algorithm will search for the location of the first split. The location is determined based on the predefined criterion. The critical point is to translate the criterion into a score that gives a value depending on the split location for the entire spectrum. Thus, by scanning all possible locations of the split, the maximum or the minimum score determines the best location of the split in that iteration. The new band configuration is generated using Eq. (8) for every location of the split and then calculates the score. Finally, the best location of the split at that iteration will be found; then the subsequent locations of splits are determined sequentially, and at each iteration, a new split is placed in the spectrum. After each iteration, the termination point must be checked. In conclusion, the algorithm yields a continuous bandset comprising several narrow and wide bands, identified by the spectral locations of the splits. The SRS procedure is described schematically in Table 1.

Table 1

SRS algorithm (pseudocode).

The search is based on the given objective and corresponding metric, which in this paper is the class discrimination. The first two spectral regions give the maximum separability on average of the classes defined in the scene. Next, the algorithm searches for the second spectral location giving the highest separability, taking into account the location of the first split. This process continues iteratively until either the average separability [Eq. (7)] achieved with the selected bands or the number of spectral regions reaches the predefined termination point. Finally, we have a set of continuous bands with different widths covering the entire spectrum.

3.2.

Spectral Region Splitting with the Class Separability Metric

The channel selection methods operate keeping the original channel width.^18,19 Such methods search in the original hyperspectral space consisting of hundreds of narrow channels and select the channels that provide the optimal value of the given metric. If the target application is classification, this metric is usually a separability metric, which is calculated based on the known classes in the scene. In each channel, the class attributes, such as mean or variance, are constant, and the search algorithm finds the best channel combination maximizing separability.

In the SRS algorithm, in addition to the possibility of selecting narrow channels, there is also the freedom to average the narrow channels and construct wider spectral regions with new class means and variances. The algorithm can average the channels to yield a better class discrimination than the selection of individual channels. By averaging the channels, two situations may cause a better discrimination among the classes: (1) a larger distance between the class means (i.e., an increase in the interclass distance) and (2) a smaller class variance (i.e., a reduction in the intraclass distance).

Here, we prove that the intraclass distance becomes smaller in the new feature space. Let $X=\{X_1,X_2,\dots ,X_n\}$ be a class in a hyperspectral dataset having $n$ independent spectral channels with $m$ sample pixels per channel. The class variance is a vector given as ${\sigma }^2=\{{\sigma }_1^2,{\sigma }_2^2,\dots ,{\sigma }_n^2\}$. The variance of the linear combination $Y={\sum }_{i=1}^n{a}_i{X}_i$, where $a_1,a_2,\dots .a_3$ are real constants ($a_i\in R$), is

3.3.

Spectral Region Splitting Iterations

SRS, likewise most search algorithms, detects a suboptimal feature subset based on the selected criterion, to avoid an exhaustive search for all possible combinations. The total number of subsets of size $n$ out of $N$ possible elements, $n<N$, is $C_n^N=\frac{N!}{(N-n)!n!}$. In the case of hyperspectral images, the number of combinations is very large, e.g., the number of possible selections of 10 out of 200 channels is $2.25\times {10}^{16}$. Whitney³³ proposed the SFS method to reduce the number of subsets evaluated and obtain a suboptimal subset. This iterative process selects a single element (like a channel) that appears to be the best when combined with a previously selected subset of elements. SRS follows the same rule as well. Since SRS searches for the location of the split to divide the spectrum, the number of possible locations is $N-1$ at each iteration, where $N$ is the number of channels. Therefore, the number of subsets searched to find a subset of $n$ bands from an original dataset ($2\le n\le N$) is given by

Thus, the previous example of selecting 10 bands out of 200 channels requires evaluating 1755 band sets, i.e., 13 orders of magnitude (${10}^{13}$) less than the number of bandsets searched by an exhaustive search strategy.

5.1.

Spectral Region Splitting Versus Best-Selected Channels

In the first experiment, we compared the spectral configuration constructed by SRS with the best channels giving the maximum separability selected by the BB search algorithm. As mentioned, BB selects the best $n$ features with the highest value of the given metric out of an $N$-feature dataset. All other channel selection methods would choose $n$ channels giving a lower or at best equal value of the metric than the channel set selected by BB. However, BB is costly when applied to large datasets.³⁴ Therefore, we used smaller datasets with 20 channels in this experiment.

The 20-channel datasets were chosen from two spectral regions of the Indian Pines scene: (1) visible (VIS) spectral region: 400 to 637 nm and (2) near-infrared (NIR) spectral region: 647 to 822 nm. The two common separability measures, Mh and JM, were applied as separability metrics with the SRS and BB algorithms. We also applied the two other search algorithms to select channels: SFS and SFFS. These two algorithms do not select the channels having a better result than BB since they select a suboptimal channel set (see Sec. 2.1). We used them in this experiment to benchmark their performance against BB, prior to applying them to the entire scene in the second experiment.

The first experiment shows that the SRS method can provide a better class discrimination than the best selection of spectral channels (Fig. 6). When the number of bands is small (in the worst case, it was three), SRS may not give a better class separability than channel selection. After a few iterations, however, the SRS method has a rapid improvement and creates spectral regions providing better separability. This means that the spectral regions identified by SRS would discriminate the classes better than the same number of selected spectral channels by BB. This result was obtained in all cases, regardless of whether Mh or JM was used. Table 2 also gives the value of JM on the NIR subset for more clarification.

Fig. 6

The mean class separability versus the number of features obtained by applying the (a) Mh and (b) JM distances and the four algorithms described in the text; the datasets used are two spectral subsets with 20 channels of the Indian Pines scene from VIS and NIR spectral regions.

Table 2

Mean JM distance between the class pairs using the bands and channels obtained by different algorithms over the NIR dataset.

The performance with both SFS and SFFS is almost as good as the BB selection in most cases. SFFS sometimes gave a lower separability than SFS, e.g., when Mh is used over NIR spectral regions. The result of the final selection, i.e., 20 features, was the same for all the algorithms since all available features were applied to determine separability with all the algorithms.

Overall, a spectral configuration determined by SRS identifies features that give better class separability than the other search algorithms used for channel selection in this study. The widely used search methods, SFS and SFFS, result in channel sets providing lower class separability than the channels selected by BB to maximize separability, although the differences are rather small.

5.2.

Spectral Region Splitting Versus Conventional Channel Selection Methods

The second experiment compares the SRS with SFS and SFFS by applying them to the complete datasets. The BB algorithm is not applicable for a large dataset (see Sec. 2.1). We used the six separability measures mentioned in Sec. 2.2, and both the Indian Pines and Salinas datasets were used. Figures 7 and 8 show the general trends in mean separability versus the number of features for the two different hyperspectral scenes, with the number of features being from two to a maximum of 30.

Fig. 7

The mean separability distance of the features obtained with different algorithms for the Indian Pines dataset.

Fig. 8

The mean separability distance of the features obtained with different algorithms for the Salinas dataset.

Overall, SRS yields a better separability with a higher number of bands in all cases except when Euclidean distance was applied. The main difference between the Euclidean distance and the other metrics is the class variance that is not taken into account by the Euclidean distance, which only accounts for interclass distance. This means that a new feature space is generated by SRS, but, if based on the class mean only, it gives a worse discrimination. On the other hand, when other separability metrics are used, SRS achieves a better class discrimination than SFS and SFFS. These metrics consider both the class mean and the class variance, which contribute to improving the separability. Initial selections usually give better performance with individual channels than with wider spectral bands. The number of wider bands needed for higher separability than with spectral channels is different from case to case, but at some points SRS always provides a better separability. For example, even with two bands, SRS gave a better result than channel selection methods when Bhattacharyya or divergence metrics were applied with the Indian Pines dataset. In the worst case, at least seven bands were needed to achieve a better SRS performance for the Salinas scene, when the TD metric is applied.

Sometimes SFFS does not select the number of channels predefined by the termination point since SFFS remains in a local loop during the search and cannot determine the required number of features. This occurs during the “conditional exclusion” of the features already selected in the backward process of the algorithm (see Ref. 34 for the details).

We developed a hypothetical example of the steps in a run of the SFFS algorithm since, in the practical cases of this experiment, the number of steps is too large to reveal this issue. Let $k$ be the number of features in the set $S_k$ and $J(S_k)$ be the criterion function for the given set. Then the example is as follows (Table 3):

Table 3

A hypothetical example of the steps in a run of the SFFS algorithm remaining in a local loop.

At step 2, the features are {1,2}, which are again obtained 10 steps later, at step 12. When the iteration continues, the same loop will be repeated, and the other features of the original dataset will not be selected. This situation is more likely to occur when the number of features is large. In these cases, we considered the maximum number of channels provided by SFFS.

Using the Euclidean distance, the results of SFS and SFFS were the same. Furthermore, SFFS does not always provide a higher separability than SFS,³⁹ and the results with the two methods were almost the same, whereas the SRS results were better. Table 4 also gives more details about the spectral location of the channels and the splits selected by the two algorithms using the JM metric.

Table 4

The spectral locations (nm) of the channels and splits selected by SFS-JM and SRS-JM, respectively, for the Indian Pines dataset in the order of selection.

5.3.

Separability with Wider Spectral Bands

The second experiment suggests that the class variance (intraclass distance) is the major determinant of the better separability achieved by SRS since we obtained the worst result by SRS when the Euclidean distance was used. We evaluated in detail the role of the class variance (intraclass distance) in determining class separability by analyzing the variations of both intra- and interclass distances. This evaluation was performed by averaging all the intra- and interclass distances for the Indian Pines dataset using the features identified by SRS and SFS at each iteration. There are 13 intraclasses (class variances) per feature and 78 interclass distances per feature set. The number of features in a set increases in each iteration. Therefore, for a given feature set with $k$ bands or channels, we calculated the mean value of $k\times 13$ intraclass and 78 interclass distances. We consider the results of the two most comprehensive separability measures: JM and TD.

As expected (see Sec. 3.2), the mean intraclass distance (class variance) obtained with the spectral bands is smaller than with individual channels in most cases [Fig. 9(a)], i.e., the mean intraclass distance becomes smaller when the channel signals are averaged. The difference increases with the number of bands. Analyzing the interclass distances [Fig. 10(b)] reveals that none of the methods performs better than the other ones since each method sometimes gives a higher mean interclass distance (distance between the class centroids).

Fig. 9

The mean (a) intraclass and (b) interclass distance of 13 classes for the Indian Pines dataset with a different number of features when JM and TD measures are applied with the SRS and SFS search algorithms.

Fig. 10

The classification accuracy obtained with the classifiers MLC and SVM applied to the bands and channels identified by SRS, SFS, and SFFS using the JM and TD separability metrics; (a) and (b) Indian Pines and (c) and (d) Salinas scenes.

From the three experiments, it can be concluded that a bandset created by SRS with the proper number of bands gives a better class separability than the other channel selection methods with the same criterion, and this is mainly due to the reduction of the intraclass distances because of averaging the channel signals. The SRS separability is lower in the initial iterations because the initial SRS bands are usually very broad. In this case, the class variances of the constitutive channels are not usually equal, and an individual channel having a small class variance may yield a better class separability. For example, a vegetation class has a larger NIR than VIS variance, so a narrow VIS channel is likely to give a smaller variance than the average of all the variances across the spectrum. After the first iterations, however, the newly formed spectral bands comprise channels with comparable variances, and averaging the channels in every band yields a better separability of the classes in a scene.

5.4.

Classification Accuracy

Finally, we applied two classifiers to the selected bands and channels and computed the accuracy of classification to evaluate and compare performance. In this experiment, maximum likelihood classifier (MLC) and SVM were applied to the final channels and bands identified by SFS, SFFS, and SRS using the JM and TD metrics. The classification accuracies are shown in Fig. 10 for the two scenes. Table 5 also gives the accuracy of six instances of feature sets determined by SFS-JM and SRS-JM.

Table 5

The classification accuracy of two DR methods (SFS-JM and SRS-JM) based on the filter approach and one method (SVM-RFE) based on the wrapper approach.

The classification accuracy obtained with the spectral bands identified by SRS was higher than the accuracy obtained with the channel selection methods. When the number of features was small, SFS and SFFS might give better results. On the other hand, with a maximum of four spectral features, SRS gave higher accuracy than both SFS and SFFS for the Indian Pines scene when MLC was used as the classifier. For the Salinas scene, there were larger fluctuations in the classification accuracy, i.e., sometimes the channel selection methods gave better results when the number of bands was low, while with higher number of bands SRS had better accuracy. MLC gave a larger improvement in classification accuracy with the bandset created by SRS than with SVM. On average, the improvements were about 3.24% and 0.96% when MLC and SVM were used, respectively. This is due to the reduction in class variances having a larger impact on a parametric classifier like MLC that considers the distributions of class attributes explicitly.

5.5.

Comparison with a Wrapper Approach

The last results revealed that the band configurations identified by SRS gave a noticeable improvement in classification accuracy compared with the channel selected by SFS and SFFS, especially when the MLC was used. Although our focus was on FS based on the filter approach, we compared the results of classification with an algorithm based on the wrapper models^35,47,48 as well. In the wrapper models, features (channels) are usually selected given the classifier based on the accuracy of classification. It is usually assumed that the wrapper approaches achieve better classification accuracy than the filter approaches since they identify features that better suit the classification algorithm regarding the performance.^49–51 The wrapper approaches, on the other hand, are computationally more expensive than the filter approaches.^52,53 We examined a well-known wrapper algorithm for channel selection on the basis of classification accuracy in comparison with a method giving a better classification result in our experiments: SRS-JM combined with MLC. Infact, SRS-JM identifies features based on maximizing class separability, to be applied with a classification algorithm, whereas a wrapper algorithm selects features to maximize classification accuracy.

We used SVM-RFE (recursive feature elimination) as a wrapper algorithm^{50,51,54–56} in this study. In RFE, the decision function of the SVM, i.e., finding an optimal hyperplane that maximizes the marginal distance between two classes, is used as the criterion to select features in a backward elimination approach. It computes ranking weights based on the training samples for all the features and sorts the features according to weight vectors.^51,56

For the SVM-RFE algorithm implemented in this experiment, we considered the commonly used “one-against-all’ strategy.^43,54 The “one-against-all” strategy converts the problem of $k$ classes ($k>2$) into $k$ dual-class problems. The radial basis function^46,52,53 is utilized as the kernel function to map the original feature space into the higher dimensional space. For the kernel width factor ($\gamma$) and regularization parameter ($C$), we applied different values suggested in the literature and chose the ones giving the best classification performance, i.e., $\gamma =0.1$ and $C=2000$ proposed by Ref. 54

In this experiment, we investigated which combination of features and classifiers would give a higher classification accuracy. Thus, the accuracy achieved with the spectral configuration constructed by SRS-JM, combined with MLC, was compared with the accuracy obtained by SVM-RFE for each dataset (Fig. 11). Table 5 also gives the accuracy obtained with six feature sets determined by SVM-RFE in comparison with SRS-JM.

Fig. 11

The classification accuracy obtained by a filter approach, i.e., features identified by SRS-JM and the classification with MLC and one wrapper approach (SVM-RFE) for two datasets. The legend gives in each row the feature identification algorithm, the classification method, and the dataset used, respectively.

It was observed in this experiment that the combination of the features identified by SRS-JM and MLC gave a better or comparable classification accuracy than the wrapper method. The SVM-RFE combination starts with a classification accuracy of about 70% for the Salinas scene, increases gradually, and reaches the accuracy of SRS-JM with MLC when the number of features is about 25. For the Indian Pines dataset, SVM-RFE had a lower accuracy than SRS-JM in all cases, whereas the difference became less by increasing the number of features. The SRS-JM-MLC gave about 3% higher classification accuracy with 30 features.

In comparison with the SVM-RFE algorithm, the spectral configuration determined by SRS gave a better or comparable classification accuracy when MLC was used as the classifier and the number of features was less than 30.

5.6.

Discussion

We compared SRS with three search strategies used in channel selection: BB, SFS, and SFFS, by applying different separability metrics: Euclidean, Mh, Bhattacharyya, divergence, TD, and JM.

In the first experiment, the comparison between SRS and BB indicated that SRS gives better results than the best-selected channels over small datasets with the same criterion. Then, SRS was compared with search algorithms widely used in channel selection, i.e., SFS and SFFS, using different separability metrics over complete hyperspectral datasets. The second experiment had a very similar outcome, i.e., better class discrimination by SRS with a higher number of bands. On average, at least four spectral bands are needed to have better separability than by selecting narrow channels.

The third experiment analyzed the effect of the broader spectral regions formed by SRS on two main factors of class discrimination: interclass and intraclass distances. The results of this experiment and the second one revealed that the main reason that SRS provides a better class separability is the reduction of intraclass distances due to the broader spectral bands identified by SRS. Having a better separability between the classes in a scene leads to a higher classification accuracy in a filter-based approach and, finally, a better identification of observed targets, as shown by the fourth experiment. Comparison with a wrapper approach, in the fifth experiment, revealed that the combination of SRS and MLC gave a better or comparable accuracy of classification.