February Fourier Talks 2011

Jeffrey Bowles


Nearest-neighbor Search in High Dimensional Spectral Data


There are a number of situations where it is desired to determine which spectrum in a hyperspectral image, or library, is closest (in some metric) to another spectrum.
For example, it is often useful to reduce a given image by choosing some subset of the scene spectra (known as the exemplars) that can represent the image with sufficient accuracy to support follow-on processing.  Empirical evidence has shown that the number of exemplars can be as little as 1% of the size of the represented scene depending on what the next step in the processing chain is.  The challenge is to identify the 'interesting pixels' in very large scenes in a reasonable amount of time.  To this end, NRL has developed a series of algorithms that can quickly identify the exemplars for a given image.  The basic idea is to run through an image and classify each pixel as either 'new' (not already in the exemplar set), or 'redundant' (already present, and thus can be ignored).  In order to do this quickly, spectra are projected down into a much lower-dimensional subspace, and we then use Cauchy-Schwartz and some basic geometry to test whether a given spectra could possibly be a new exemplar. More recently, the NRL has applied this technology to searching very large spectral libraries.  Here, the libraries may have several million spectra each having up to 90 spectral bands, which must be searched for millions of pixels in a given image.  The same algorithms developed for the exemplar selection problem above have proven to be useful in this search.  Recent results will be discussed.
This is joint work with David Gillis.