Site-wide links

Center For Applied and Computational Mathematics

Hyperspectral Image Segmentation

Hyperspectral Image Segmentation
Faculty:  Anthony Harkin
  William Basener

Background:

Hyperspectral images are digital images, often taken either from an airplane or satellite, in which each pixel has not just the usual three visible bands of light (red at 650nm, green at 550nm, and blue at 450nm), but on the order of hundreds of wavelengths so that spectroscopy can be conducted on the materials on the ground. The user is then able to identify, for instance, the species of trees and other vegetation, crop health, mineral and soil composition, moisture content of soils and vegetation, and pollution quantities. In images over water, it is possible to identify and quantify water particulates, chlorophyll levels, erosion patterns, and in some cases water depth. The technology also has clear military and intelligence applications, as it enables the identification of man-made materials such as buildings and vehicles, even with attempts to camouflage. It is also possible to detect and identify gas plumes such as those arising from leaks even when the gasses are invisible to the human eye. In fact, hyperspectral imaging was used following the attack on the twin towers and the hurricane Katrina disaster to identify dangerous gas leaks, providing guidance and protection to rescuers. Hyperspectral sensors are flown on aerial platforms by several private companies, and NASA runs a hyperspectral sensor called Hyperion on their EOS-1 satellite.

Although this technology has incredible potential, its utility is currently limited because of the enormous quantity and complexity of the data it gathers. A single image can consist of millions of pixels, each with hundreds of bands, and can require tens of gigabytes of memory to store. The standard data analysis algorithms for spectral and multispectral imaging, which use linear methods and multivariate statistics, break down on complex scenes and are unable to extract information from the nonlinear structures embedded in hyperspectral data sets. It has recently been demonstrated, by researchers at RIT and others, that topological tools along with ideas from the theory of networks are well suited to successfully handle hyperspectral data sets.

The goal of image segmentation for a hyperspectral image is to devise an unsupervised algorithm that partitions the image by placing each pixel into one of several clusters, or spectral classes. One of the most well known methods for data clustering is the K-means algorithm, which assigns a pixel to a cluster by minimizing the variance between the pixel and the cluster center. Although K-means is fast, it suffers two major drawbacks when applied to hyperspectral images. The number of clusters, K, must be specified in advance and the quality of the solution depends on the initial set of cluster centers. Other classical methods for processing data sets, such as principal components analysis and manifold embeddings, also suffer drawbacks and have not been able to capture many of the complex nonlinear structures in HSI data.

Community Detection Algorithms

Hyperspectral Image Segmentation

Summary:

It has recently been demonstrated that topological tools, along with ideas from the theory of networks, are well suited to successfully identify complex nonlinear structures in HSI data sets and perform image segmentation. The new paradigm offered by these ideas points to significant progress and enhanced utility of hyperspectral imaging technology. The main idea is simple and elegant, that the high dimensionality and nonlinearity of a hyperspectral data set can be better handled by imposing a network structure on it. The problem of image segmentation then maps to the problem of detecting community structure on networks. To convert the image into a network, each pixel becomes a node. Since each pixel has N numbers associated with it, one for each frequency band, it can be thought of as a point in N-dimensional space. Two nodes are then connected by an edge if the distance between them is sufficiently small. Once the network is constructed, a community detection algorithm can be employed to partition it.

Collaborators:

Ryan Lewis (student)

Gradient Flow Method

Hyperspectral Image Segmentation

Summary:

In the gradient flow method, a graph is also constructed, as with the community detection approach algorithm – each pixel in the image is represented by a node and an edge connects two nodes if their distance is less than some threshold. The density of data near each node is computed and a (discretization of a) differential equation is constructed on the edges of the graph pointing in the direction of increasing density. The regions of high density in the data are sinks for this differential equation and the basins of attraction for the clusters. The gradient flow algorithm produces nonlinear decision surfaces between classes that outperform the corresponding results from the standard K-means algorithm.