The classical computational approaches of dealing with hyperspectral data tend to analyze it using best fitting algorithms scanning the data pixel wise.
Abstract
The classical computational approaches of dealing with hyperspectral data tend to analyze it using best fitting algorithms scanning the data pixel wise, thus taking advantage of only one dimension of the 3 available by the hypercube. The main consequence of this is high computational complexity of the analysis process and the need for professional human intervention in the analysis process. In this project we propose an original approach to solving the hyperspectral analysis problem, incorporating new and more efficient ICA paradigms as the Sparse Decomposition and Relative Newton algorithm with new spatial approach to the hyperspectral data. The spatial approach addresses the images of the hypercube as linear mixtures of the pure mineral abundance maps. This enables the extraction of the pure abundance maps using the various ICA algorithms. These abundance maps enable us to reach the thematic mineral mapping of the photographed scene by performing spectral analysis of only handful of carefully chosen pixels, and thus reduce substantially the computational efficiency of the process. For the implementation of this combined scheme, a multi-stage algorithm has been devised, which takes advantage of all 3 dimensions of the hyperspectral data in order to reach thematic mineral mapping of the scene. The algorithm has been tested on synthetically created hyperspectral data benchmark, and has demonstrated high performance in reconstructing the mineral map of the modeled scene, and has also presented computational time abilities that are similar to those of other commercial software, using specially designated hyperspectral analysis algorithms.
The problem
In this project we use hyperspectral data, collected over an examined area, in order to estimate its mineralogical ground composition. We explore the possibility of combining classical Blind Source Separation in an original framework based on a spatial approach to the Hyperspectral data to solve the problem.
The solution
Short Introduction
Figure 1 – Schematic description of the hyperspectral data structure
Figure 2 – Hyperspectral data models : (a) classical spectral model (b) spatial model
Hyperspectral imagers
Hyperspectral Imagers, also called imaging spectrometers, are specialized cameras used for high precision remote sensing. “Imager” means that it takes 2-D pictures rather than spot data, and “hyperspectral” means that it does this in hundreds of colour bands. The output datacube (see Fig. 1) contains a spectroscopic signature for each image pixel, and this gives the chemical composition of the materials in the picture. Hyperspectral images are spectrally overdetermined, which means that they provide ample spectral information to identify and distinguish spectrally unique materials. Regional geological mapping and mineral exploration are among the main applications benefiting from this technology.
The Hyperspectral Data Structure
In reflected-light spectroscopy the fundamental property that we want to obtain is spectral reflectance: the ratio of reflected energy to incident energy as a function of wavelength. Reflectance varies with wavelength for most materials because energy at certain wavelengths is scattered or absorbed to different degrees. By sampling the reflectance of the same area in many wavelengths(bands) a spectral reflectance curve can be built. The more narrow the bands are, the smoother and more continuous the curve becomes. Using airborne imagers large areas can be partitioned into “pixels” and sampled to obtain a reflectance image in every wavelength. Stacking the images one behind another band wise gives us a reflectance curve for each pixel, see Fig 1. The stacked image structure is the common format used to contain hyperspectral data and has been given the name hypercube. As the bands become narrower the reflectance variations are evident when we compare spectral reflectance curves (plots of reflectance versus wavelength) for different materials. Pronounced downward deflections of the spectral curves mark the wavelength ranges for which the material selectively absorbs the incident energy. These features are commonly called absorption bands. The overall shape of a spectral curve and the position and strength of absorption bands in many cases can be used to identify and discriminate different materials.
Hyper spectral data models and the BSS problem
The mathematical linear mixing model of the hyperspectral data is the most useful model for hyperspectral data classical and modern analysis techniques. In this project we approached the mixing model from two viewpoints, that are, in fact, two ways to observe the model.
Spectral approach – the common way to view the hyperspectral data is to represent the individual pixel spectra of the hyperspectral data set (also called hypercube) as linear mixtures of pure minerals (usually referred to as endmembers). The mixing coefficients of the pure mineral spectra are the relative abundances of the individual minerals the examined area (included in one pixel). This approach can be viewed schematically in Fig. 2(a). Let us view one particular pixel of the hypercube. Here we denote the pure mineral spectra si, i=1,…,N, were N denotes the number of pure minerals present in area covered by pixel k. xk denotes the pixel k spectrum and vector contains the relative abundances of the pure minerals si present in the scene. As we can see, vector xk be viewed as linear combination of the pure mineral spectra. We can write this model mathematically in the following fashion:
where M stands for the number of spectral bands in the hyperspectral data. In the same fashion the spectral curve of all the other pixels of the hypercube can be written as a linear combination of the pure mineral spectral curves, with the relative abundances as the mixing coefficients.
Spatial approach – The mixing model can also be schematically viewed as described in Fig. 2(b). Each spectral band picture can be viewed as a linear combination of the pure mineral abundance maps, and the mixing coefficients are the radiance amplitudes of the pure mineral spectra. Mathematically this can be written, as before, in a matrix notation, as follows:
where N, as before, denotes the number of pure minerals present at the examined scene, while L and W stand for the dimensions of the images in the hypercube (length and width respectively). In a similar manner each of the band images in the hypercube can be shown to be linear combination of pure mineral abundance maps. This approach allows us to extract information about the spatial information encrypted in the hypercube as a natural consequence of the mixing model.
Blind Source Separation (BSS) – The basic model of the blind source separation problem involves two main features: (1) the examined signals are linear mixtures of arbitrary source signals, and (2) the sources themselves are statistically independent of each other. These two assumptions facilitate in the construction of blind separation algorithms, as the ICA algorithm. This basic mixing model is quite similar to the hyperspectral data structure, described above. Thus a natural step is to combine these two approaches and view the hyperspectral data as a specific example of the blind source separation problem.
The Algorithm
Traditional uses of Blind Source Separation techniques in hyperspectral data analysis have focused only on the spectral side of the data and did not make any use of its spatial features. We have seen two equivalent ways of modeling the hyperspectral data, one as a linear mixture of source spectra, and the other as a linear mixture of source abundance maps. Using the second model, the algorithm utilizes both spatial and spectral information and combines them to produce a thematic mineral mapping of the scanned area. . The algorithm consists of two main parts: the first part (see Fig. 2(Right) ) extracts relevant spatial information from the hyperspectral data. The second (see Fig. 2(Left) ) uses this information to extract the minimal spectral data needed for unmixing using BSS ICA technique and enables the completion of the thematic mineral map. Making use of spatial data reduces the amount of spectral data examined during the algorithms run, and therefore increases efficiency.
Basic concept
Since every pixel in the hypercube represents an approximate area of 20X20 meters of ground, it is usually the case that every pixel holds a mixture of minerals. the resulting spectral curve in that pixel is therefore a combination of a number of pure mineral spectral curves. Previous work have shown that using BSS techniques, this mixture can be unmixed to it’s components, and that way the pure mineral spectral curves in each pixel can be found. Systematic application of this technique on a pixel basis can in principle be used to produce a complete thematic mineral map. However, this method is highly inefficient since it has to loop through the entire image, considering only one pixel at a time. In order to increase efficiency, we need to narrow the number of pixels we loop through. When using BSS techniques on the hyperspectral images rather than the spectral curves, our sources become the mineral abundance maps. By combining the abundance maps data with spatialy localized spectral BSS analysis, we can produce the thematic mineral map without having to go over the image pixel by pixel.
Using the abundance maps we can locate two pixels in the image composed of the same mineral ingredients . Likewise we are able to locate two pixels differing by only one mineral component. In addition we are able to say which of the found abundance maps is associated with this mineral component. Having identified such pixels, then it is possible using BSS techniques to find the pure minerals in each pixel. Since the pixels differ by one mineral, by matching between the pure minerals retrieved for each pixel, we can isolate the differentiating mineral curve and identify it based on a mineral spectra library.
Figure 3 – the algorithm scheme: (Right) the scheme of the first part (Left) the scheme of second part
Short stage description
In the first stage we used PCA along with 2D-ICA in order to retrieve the mineral abundance maps from the hypercube data. In the second stage we used the information contained in the abundance maps to create a matrix Joint, which tells us the “mineral composition” in every pixel of the studied region. We have also devised lists A1&A2 containing the coordinates of pixels whose “mineral composition” differ only by one mineral, which is associated with a known abundance map A_coupled.In the third stage we have performed 1D-ICA on the spectral content of the pixels listed in A1&A2 in order to deduce the mineral spectral curve belonging to A_coupled. By this time we have associated the abundance map A_coupled with a mineral spectral curve. In the final stage a matching sequence was used to find the mineral spectra in the USGS library, which is closest to the mineral spectra, associated with abundance map A_coupled. This enabled us, finally, to give this mineral a name. We know everything we wanted to know about one of the mineral components in the studied region, both it’s identity and where it’s abundance map have been found. After the looping is finished we have performed the algorithm for each abundance map. We have identified the mineral components in the studied region, and are able to build a thematic mineral map describing their location. An extra feature we earned using this algorithm is the knowledge on the relative abundance of each of the minerals in the entire scene.
Tools
The algorithm is implemented on Matlab 6.5 platform, and comes with a graphical user friendly interface (GUI). The algorithm was run on a Pentium IV PC workstation, running with windows 2000 operating system.
Results
An example of the final algorithms results is shown here. On the left is the real thematic mineral map of the area, and listed on top are the real minerals existing in this area. On the right is the estimated mineral map, and listed above it are the three most probable mineral estimates.
The algorithm was tested on randomly generated synthetic data containing 5 minerals. The performance was measured by map closeness and by correct mineral name estimation (up to single mineral groupings). Results of running the algorithm 100 times showed near perfect map recovery and complete recovery of all 5 minerals in 70% of the cases. If we loose the demands a bit, and demand recovery of only 4 out of 5 minerals, the performance jumps to 94%.
Computation time of the algorithm is on the order of 5-30 minutes depending on the image size and the number of minerals in it. The computation time increases with the increase of mineral number and of image size.
Conclusions
In this work we have presented a novel algorithm for the analysis of hyperspectral data. The algorithm combines Blind Source Separation techniques with a newly developed spatial approach to automatically produce a thematic mineral map of a studied area. It is up to our knowledge, the first fully functional hyperspectral data analysis tool to be using Blind Source Separation techniques. Unlike other approaches, utilizing only the spectral features of the data, on an individual pixel basis, this algorithm also takes advantage of the spatial features already inherited in the data structure by performing operations on complete images. This rids the algorithm from looping over the entire image, which can easily reach a million pixels, one pixel at a time, and therefore makes it much more efficient. The algorithm is innovative in two aspects: first, in the way it approaches the problem as a blind source separation problem, with the sources being the abundance maps, and second, in the way it uses the abundance maps information to find the mineral names. The obtained results, thus far on synthetic data, confirm the effectiveness of the idea and have shown high performance of the algorithm for noise free data. As for noise, the algorithm is in general sensitive to noise, mainly due to it being based on a BSS technique, which does not cope well with noise. Future work should include further testing on real data. In addition the following enhancements of the algorithm might be of special interest:
1. Adding a noise removal stage prior to running the algorithm. This stage should include processing of the band images to detect and remove noisy bands, and also detection and tagging of local corrupted areas in generally uncorrupted bands.
2. Further improving the two matching sequences, for better matching results.
3. Further research into exploiting the high redundancy of the algorithm.
4. Larger library mineral families must be found in order to simplify the mineral to library matching.
Acknowledgment
We would like to thank our supervisor, Michael Bronstein, for his help during the course of the project. We would especially like to thank Johanan Erez, Eli Appelboim, Alex Bronstein and the entire VISL laboratory stuff for their ongoing support and technical aid. We are also grateful to the Ollendorff Minerva Center Fund for supporting this project.