PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Clustering Framework for Hyperspectral Band Selection

Qi Wang, Fahong Zhang, Xuelong Li

arXiv:1904.13036v1eess.IVcs.LGstat.ML

TL;DR

Existing unsupervised band-selection methods often provide only approximate solutions, especially for clustering-based searches over large solution spaces. The paper proposes OCF for constrained optimal clustering, RCS for selecting representative bands, and an automatic band-number estimator; experiments on four datasets show the resulting methods are robust and effective.

  • Problem

    Existing unsupervised band-selection methods generally obtain approximate solutions, while clustering-based selection has a very large solution space that makes optimal search difficult.

  • Method

    OCF searches for optimal clustering under a reasonable constraint, RCS ranks bands within clusters, and a correlation-reduced band-power ratio estimates the required band number.

  • Results

    Experiments on four datasets demonstrate that OCF- and RCS-based algorithm versions are robust and effective.

  • Takeaways & Limitations

    The framework combines optimal constrained clustering with within-cluster ranking and automatic band-number estimation for hyperspectral band selection.

Abstract

from arXiv · show

Band selection, by choosing a set of representative bands in hyperspectral image (HSI), 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 (OCF), which can obtain the optimal clustering result for a particular form of objective function under a reasonable constraint. 2) A rank on clusters strategy (RCS), which provides an effective criterion to select bands on existing clustering structure. 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 to some state-of-the-art competitors. According to the experimental results, the proposed algorithm is robust and significantly outperform the other methods on various data sets.

I. INTRODUCTION

Hyperspectral images contain highly correlated, high-dimensional band data, motivating unsupervised band selection that preserves physically interpretable information. The paper addresses the difficulty of finding globally optimal clustering-based selections by introducing OCF, RCS, and automatic band-number estimation.

  • HSIs contain hundreds of two-dimensional wavelength images, whose correlations and dependencies increase computational complexity and contribute to the Hughes phenomenon.
  • Band selection chooses discriminative original bands without modification, preserving information in a physically interpretable form compared with feature extraction.
  • The paper focuses on unsupervised methods because obtaining labeled samples for supervised and semi-supervised selection is difficult in real applications.
  • Existing greedy and evolutionary methods generally obtain approximate rather than globally optimal solutions, often because their searches are iterative, random, or trapped in local optima.
  • OCF searches for optimal clustering under a reasonable constraint and supports multiple objective functions sharing the same procedure when they satisfy a specific form.
  • RCS ranks bands within the achieved clusters, while automatic band-number estimation evaluates distinctive information produced by different numbers of bands.

II. RELATED WORK

Unsupervised band-selection methods use ranking, clustering, greedy, or evolutionary search strategies, each balancing discriminative selection, redundancy reduction, efficiency, and sensitivity to noise or initialization.

  • Ranking-based methods: Ranking-based methods select top-ranked bands and can discover discriminative bands, but the selected bands may remain highly correlated.
  • Ranking-based methods: MVPCA prioritizes bands by variance, but noisy bands can receive high priority and the selected bands can contain substantial redundancy.
  • Ranking-based methods: CBS minimizes band correlation and is less sensitive to noisy bands, yet it neglects interactions among selected bands, allowing correlated bands to remain.
  • Clustering-based methods: Clustering-based methods reduce correlation by partitioning bands and selecting representatives, while WaLuMI and WaLuDi can form noise-driven single-band clusters.
  • Clustering-based methods: E-FDPC combines local density and inter-cluster distance, but these quantities are difficult to measure exactly.
  • Greedy-based methods: Greedy methods optimize an objective at each iteration but cannot obtain the optimal solution; VGBS can select noisy bands, while SFS is sensitive to initialization.

D. Evolutionary-based methods

The paper motivates efficient optimal clustering by exploiting dynamic-programming structure and a contiguous-band constraint grounded in hyperspectral spectral smoothness. This constraint sharply reduces the clustering search space and enables more efficient optimization.

  • Evolutionary-based methods: Evolutionary methods randomly initialize band subsets and update them with evolutionary algorithms toward nearly optimal solutions.
  • Evolutionary-based methods: MTSP uses a compressive band descriptor, a multi-task criterion, and immune clonal search to seek effective band combinations.
  • Evolutionary-based methods: MOBS jointly optimizes information entropy and band count, but summed entropy may not capture interrelationships among bands.
  • Optimal clustering framework: Dynamic programming repeatedly decomposes a complex problem into reusable subproblems and combines their solutions to solve the original problem.
  • Contiguous Band Indexes Constraint: Nearby wavelengths generally produce similar reflectances, so adjacent spectral bands tend to have stronger correlations and support contiguous clustering constraints.
  • Contiguous Band Indexes Constraint: For L = 200 and K = 15, the constrained search space is about 10^21, compared with approximately 10^23 without the constraint.
  • Optimal clustering framework: The constraint converts clustering into finding critical bands that divide the full band sequence into intervals, enabling more efficient optimal-solution search.

C. OCF Formulization

OCF formulates clustering as optimizing contributions from contiguous band intervals and solves the resulting problem through decomposition and combination under critical band-index constraints.

  • Problem formulation: OCF represents a clustering by critical band indexes that partition the ordered bands into K contiguous subsets.The critical indexes mark each cluster’s last band, with s0 = 0 and sK = L.
  • Problem formulation: The objective sums a mapping f over the contributions of the K band intervals.Each interval’s contribution is evaluated through f, and the resulting objective Ds is optimized.
  • Problem decomposition: OCF decomposes the full optimization into simpler subproblems over the first l bands and k intervals.The subproblem solution M^k_l represents the optimum for partitioning the first l bands into k intervals.
  • Subproblem combination: Overlapping subproblems expose an optimal-substructure property that enables efficient subproblem combination.The framework computes M^k_l values in sequence and then recovers the critical band-index vector from stored maximizers.
  • Algorithm: The recovered critical band indexes are output as the clustering structure produced by OCF.Algorithm 1 initializes and updates subproblem values, then backtracks from k = K to recover the indexes.

D. Extended-OCF

Extended-OCF generalizes the objective by replacing addition with an arbitrary binary operator, while retaining the same optimization procedure when the required form is satisfied.

  • Extended objective: Extended-OCF replaces the sum of interval contributions with an arbitrary binary operator ⊕: R^2 → R.The objective is defined through a tuple (⊕, f), where f evaluates each band interval.
  • Extended objective: The optimization procedure remains nearly identical, requiring only replacement of the addition operator in the recurrence.Thus, objectives defined by a compatible tuple (⊕, f) can be solved through OCF.

E. Rank on Clusters Strategy

RCS selects representative bands by combining an existing ranking with the achieved clustering structure, choosing one high-ranked band per cluster.

  • Motivation: Conventional cluster-wise selection can miss bands that are discriminative relative to the complete band set.The most discriminative band within an individual cluster need not be most discriminative with respect to all bands.
  • RCS procedure: RCS ranks bands globally while enforcing the constraint that exactly one band is selected from each cluster.This combines band discrimination with the diversity imposed by the clustering structure.
  • RCS procedure: The RCS solution selects the band with the highest rank value in every cluster.The selected bands form the desired subset under the achieved clustering.

IV. IMPLEMENTATION OF OCF

The implementation uses normalized cut and top-rank cut objectives with OCF, constructs band similarities by local scaling, and imposes contiguous-band clustering to make optimization tractable.

  • Objective functions: The implementation evaluates OCF with normalized cut (NC) and top-rank cut (TRC) objective functions.NC is a graph-based criterion, while TRC is designed around ranked bands and interval contributions.
  • Normalized cut: NC favors partitions with high within-group correlation and low between-group correlation, and can be optimized through normalized association.Minimizing NC is equivalent to maximizing normalized association (NA).
  • Similarity construction: A local-scaling similarity matrix is constructed from neighboring-band distances before applying the objectives.The local scaling parameter uses the distance to the m-th neighbor, with m set to 7 according to the cited method.
  • Top-rank cut: TRC addresses noisy or weak intervals by maximizing the minimum contribution and prioritizing the highest-ranked bands used by RCS.TRC selects the highest-ranked band in each cluster, scores its similarities to bands outside that cluster, and minimizes the maximum cluster score.

B. Ranking Methods for RCS

RCS evaluates bands with ranking criteria that prioritize distinctive, representative, or informative bands, while accounting for noise sensitivity and inter-band correlation. The proposed algorithm names each objective-function and ranking-method combination explicitly.

  • Ranking criteria: MVPCA ranks bands by variance because larger variance generally indicates more distinctive information for separating ground objects.However, noisy bands can also have large variances, making MVPCA noise-sensitive.
  • Ranking criteria: E-FDPC identifies cluster-center bands using high local density and distance from bands with higher local densities.These criteria suppress noisy bands and reduce correlation among selected bands.
  • Ranking criteria: Information entropy measures information hidden in a stochastic variable and is applied to each band using its gray-level histogram.The paper defines entropy over the gray-scale color space Ω with probabilities derived from histogram counts.
  • Algorithm naming: The algorithm names each implementation as “objective function”-OC-“ranking method,” such as TRC-OC-FDPC.This notation identifies which clustering objective and ranking criterion are combined.

C. Analysis of Computational Complexity

The framework computes mappings, optimizes an objective function for clustering, and ranks bands for selection. Its overall O(L^2N) cost is acceptable in many applications, but preprocessing and ranking constrain time-critical use.

  • Framework stages: The proposed algorithm has preprocessing, clustering, and selection steps, with computational complexity analyzed separately for each stage.These stages respectively prepare objective-function mappings, obtain the optimal clustering result, and rank bands through RCS.
  • Preprocessing: Preprocessing costs O(L^2N) to form similarity matrices and O(L^3) to calculate mappings for NC and TRC.TRC additionally aligns each band with ranking values, whose cost depends on the ranking method.
  • Band-number determination: The proposed band-number measure replaces variance-only power accounting because high-variance HSI bands may remain strongly correlated.The correlation-reduced ratio instead estimates distinctive power from low-correlated bands selected through clustering.
  • Band-number determination: Given R*, the required band count K* is the smallest threshold crossing satisfying Rcrvar(K*-1) ≤ R* < Rcrvar(K*).The method first sets an upper bound M = λL and computes the ratio from the variances of selected bands; under K < L ≪ N, total cost is O(L^2N).

V. EXPERIMENT

Experiments evaluate four proposed variants against established band-selection methods on four real-world HSI datasets using classification accuracy and automatically determined band counts. With R* = 0.8, the required counts are 14, 17, 11, and 10 across the datasets.

  • Datasets: Experiments use four real-world HSI datasets captured by two image systems: Indian Pines, Pavia University, Salinas, and Kennedy Space Center.The datasets differ in spatial dimensions, spectral bands, and land-cover classes.
  • Comparison methods: The proposed algorithms are compared with WaLuDi, UBS, VGBS, E-FDPC, and MTSP as state-of-the-art competitors.WaLuDi, UBS, VGBS, and E-FDPC are parameter-free apart from setting K, whereas MTSP parameters are tuned on Indian Pines.
  • Classification setting: Classification uses KNN, LDA, SVM, and EPF, training on 10% of each class and testing on the remaining samples.Results are averaged over 10 runs to reduce instability from random training-sample selection.

B. Result Analysis

Across four HSI data sets, the proposed OCF-based algorithms generally deliver robust and competitive OA performance across classifiers and selected-band counts. Their band-number estimator tracks diminishing OA gains and relative dataset requirements, but underestimates K on noisy KSC data.

  • Experimental design: The experiments evaluate OA curves, average OA across selected-band counts, and OA at automatically determined band numbers using four OCF-based variants.The comparisons use different classifiers and four real HSI data sets.
  • Indian Pines Scene: On Indian Pines, TRC-OC-FDPC and NC-OC-IE achieve stable, high OA across band counts and classifiers, with higher average OA and superiority at 14 bands.The reported indicators are shown in Figs. 5–7.
  • Pavia University Scene: On Pavia University, NC-OC-MVPCA and UBS achieve the best averaged performance when 17 bands are selected, although results vary by classifier and band count.NC-OC-MVPCA slightly leads the average-OA comparison, while E-FDPC performs better with KNN at 17 bands.
  • Salinas Scene: On Salinas, TRC-OC-FDPC is generally superior, NC-OC-IE is comparatively robust across classifiers, and the proposed algorithms outperform competitors in most average-OA cases.At 11 bands, VGBS exceeds the proposed methods with EPF, while the proposed methods remain superior with other classifiers.
  • Kennedy Space Center: On KSC, NC-OC-IE and TRC-OC-FDPC perform strongly across classifiers, while NC-OC-MVPCA and VGBS perform poorly under severe salt noise.The KSC results therefore distinguish methods that are more resistant to noisy bands from variance- or geometry-sensitive approaches.
  • Band number determination: The automatic estimator identifies slowing OA growth near the estimated band counts and captures that Pavia University requires more bands than Salinas, but underestimates KSC's requirement.The reported estimates are 17 bands for Pavia University and 11 for Salinas; noisy bands receive excessive power from MVPCA on KSC.

C. Comparison of Computational Time

The methods were timed on four HSI data sets using MATLAB on a specified desktop system while selecting 15 bands. The proposed algorithms required moderate, computationally acceptable processing time while maintaining superior performance.

  • Experimental setup: 15 bands were selected on each of four HSI data sets to compare the processing times of different band-selection methods.Experiments used an Intel Core i5-4590 3.30-GHz CPU, 16-GB RAM, and MATLAB R2016b.
  • Computational comparison: The proposed algorithm versions required moderate computational time across the evaluated data sets.The comparison included the MTSP and WaLuDi data sets.
  • Proposed methods: The proposed framework combines OCF, RCS, and a correlation-reduced band-power ratio across several algorithm versions.Different objective functions and ranking methods are used to devise the algorithm versions.
Loading 1904.13036v1…