Optimal Clustering Framework for Hyperspectral Band Selection

Qi Wang, Fahong Zhang, Xuelong Li

This paper presents a significant step forward in Hyperspectral Image (HSI) processing by moving from "good enough" heuristic searches to mathematically optimal solutions for band selection.

TL;DR

The authors introduce the Optimal Clustering Framework (OCF), which uses dynamic programming to find the globally optimal band partition for hyperspectral images. By leveraging the physical reality that adjacent spectral bands are highly correlated, they reduce a computationally "impossible" search problem into one that can be solved efficiently and accurately.

What Problem Does This Paper Address?

Hyperspectral sensors capture hundreds of narrow spectral bands, providing a "data cube" rich in detail but plagued by massive redundancy. This leads to the "Hughes Phenomenon": as the number of features (bands) increases, the accuracy of a classifier actually decreases unless the amount of training data grows exponentially.

To fix this, researchers use Band Selection to pick a small subset of representative bands. Most existing methods use "greedy" searches (picking the best band one-by-one) or "evolutionary" algorithms (randomized searches). These are prone to getting stuck in local optima—they find a good solution, but rarely the best one. The challenge is that the total number of ways to cluster 200 bands into 15 groups is roughly $10^{223}$, making a brute-force search impossible.

Methods

The paper introduces three core innovations:

  1. Contiguous Band Indexes Constraint (CBIC): The authors observe that bands with similar wavelengths are naturally more correlated. They propose that an optimal cluster should only contain contiguous bands. This physical constraint drastically shrinks the search space.
  2. Optimal Clustering Framework (OCF): Because of the contiguous constraint, the problem now has an "optimal substructure." The authors apply Dynamic Programming to break the problem into smaller sub-problems (e.g., "What is the best way to partition the first $l$ bands into $k$ clusters?"). This allows them to find the global maximum of an objective function (like Normalized Cut) in $O(L^2K)$ time.
  3. Rank on Clusters Strategy (RCS): Instead of just picking the center band of a cluster, they rank all bands based on their importance (using variance or information entropy) and then select the highest-ranked band within each optimal cluster.

Datasets

The framework was evaluated on four classic hyperspectral benchmarks:

  • Indian Pines: 200 bands, agricultural land cover.
  • Pavia University: 103 bands, urban environment.
  • Salinas Scene: 204 bands, California farmland.
  • Kennedy Space Center (KSC): 176 bands, wetland/space center environment (notable for having significant "salt noise").

Key Insights and Ideas

  • Physics informs Math: The "aha moment" is realizing that the smooth curve of spectral reflectance (Fig. 2 in the paper) justifies the contiguous constraint. This physical property is what makes the dynamic programming approach viable.
  • Global vs. Local: Most clustering methods (like k-means) are sensitive to initialization and often fail to find the global optimum. OCF guarantees the optimal result for the chosen objective function.
  • Robustness to Noise: The authors proposed a new objective function called Top-Rank Cut (TRC). Unlike standard methods that can be "tricked" by noisy bands with high variance, TRC focuses on maximizing the contribution of the most discriminative bands, making it much more stable on noisy datasets like KSC.

Key Results

  • Superior Accuracy: Across all four datasets, the OCF-based methods consistently outperformed state-of-the-art competitors (like E-FDPC and MTSP) in classification accuracy.
  • Stability: The method showed high "stability against classifiers." Whether using K-Nearest Neighbors (KNN), SVM, or Linear Discriminant Analysis (LDA), the bands selected by OCF provided consistently high performance.
  • Efficiency: While more complex than simple ranking, the $O(L^2N)$ complexity is well within the limits of modern workstations, taking only a few seconds to process datasets that previously required much longer for evolutionary searches.

Limitations and Future Work

The authors acknowledge a few areas for improvement:

  • Pre-processing Bottleneck: The efficiency of the framework is currently limited by the initial step of calculating similarity matrices and band rankings.
  • Manifold Learning: Future work aims to incorporate "low-dimensional manifold" information—essentially trying to understand the underlying geometric structure of the data to create even better similarity measures between bands.
  • Objective Function Diversity: While they tested Normalized Cut and Top-Rank Cut, the framework is general; finding even more powerful objective functions remains an open research goal.

Summary updated

Abstract

Band selection, by choosing a set of representative bands in a hyperspectral image, is an effective method to reduce the redundant information without compromising the original contents. Recently, various unsupervised band selection methods have been proposed, but most of them are based on approximation algorithms which can only obtain suboptimal solutions toward a specific objective function. This paper focuses on clustering-based band selection and proposes a new framework to solve the above dilemma, claiming the following contributions: 1) an optimal clustering framework, which can obtain the optimal clustering result for a particular form of objective function under a reasonable constraint; 2) a rank on clusters strategy, which provides an effective criterion to select bands on existing clustering structure; and 3) an automatic method to determine the number of the required bands, which can better evaluate the distinctive information produced by certain number of bands. In experiments, the proposed algorithm is compared with some state-of-the-art competitors. According to the experimental results, the proposed algorithm is robust and significantly outperforms the other methods on various data sets.
BibTeX
@article{wang2018optimal,
  author = {Qi Wang and Fahong Zhang and Xuelong Li},
  title = {{Optimal Clustering Framework for Hyperspectral Band Selection}},
  journal = {IEEE Trans. Geosci. Remote. Sens.},
  year = {2018},
  url = {https://openreview.net/forum?id=zRVTYNOHIe},
}

Loading related content...

Figure