Efficient imagery exploitation employing wavelet-based feature indices

• US 7,805,005 B2
• Filed: 07/12/2006
• Issued: 09/28/2010
• Est. Priority Date: 08/02/2005
• Status: Expired due to Fees

• Current Assignee: US Army Corps of Engineers (U.S. Department Of Defense)
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: Bosch, Edward H., Simental, Edmundo, Rand, Robert S.
• Primary Examiner(s): Werner; Brian P
• Assistant Examiner(s): DRENNAN, BARRY T
• Application Number:
  US11/484,559
• Publication Number:
  US 20070031042A1
• Time in Patent Office: 1,539 Days
• Field of Search: 382/191, 702/2, 702/5
• US Class Current: 382/191
• CPC Class Codes: G06V 10/52 Scale-space analysis, e.g. wavelet analysis multi-scale boundary representations G06V10/42
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

A wavelet-based band difference-sum ratio method reduces the computation cost of classification and feature extraction (identification) tasks. A Generalized Difference Feature Index (GDFI), computed using wavelets such as Daubechies wavelets, is employed in a method to automatically generate a large sequence of generalized band ratio images. In select embodiments of the present invention, judicious data mining of the large set of GDFI bands produces a small subset of GDFI bands suitable to identify specific Terrain Category/Classification (TERCAT) features. Other wavelets, such as Vaidyanathan, Coiflet, Beylkin, and Symmlet and the like may be employed in select embodiments. The classification and feature extraction (identification) performance of the band ratio method of the present invention is comparable to that obtained with the same or similar data sets using much more sophisticated methods such as discriminants, neural net classification, endmember Gibbs-based partitioning, and genetic algorithms.

Claims

1. An efficient method of data mining to facilitate ready identification of desired features within imagery data dispersed among multiple spectral bands, comprising:

(a) selecting a wavelet type for use in said efficient method of data mining;

(b) providing means for manipulating said data, said means at least further capable of implementing the algorithm,

$G<br><br><br><br>D<br><br><br><br>F<br><br><br><br>I_{2<br><br>n}<br><br>\left(i,t\right)=\frac{h_o<br><br>z_i+h_1<br><br>z_{i+t}+\mathrm{\dots <br><br>}<br><br>+h_{\left(2<br><br>n-1\right)}<br><br>z_{i+\left(2<br><br>n-1\right)<br><br>t}}{g_o<br><br>z_i+g_1<br><br>z_{i+t}+\mathrm{\dots <br><br>}<br><br>+g_{\left(2<br><br>n-1\right)<br><br>t}<br><br>z_{i+\left(2<br><br>n-1\right)<br><br>t}},$

 

where

GDFI_2n(i, t) is a wavelet-based generalized difference feature index,

i refers to wavelength band i of a data collector,

t is a specified lag between wavelength bands,

h₀, h₁ . . . h<sub>2n−

1</sub> are high frequency coefficients

g₀, g₁ . . . g<sub>2n−

1</sub> are low frequency coefficients,

wherein, a number of said high and low frequency coefficients is determined upon establishing an order of a wavelet of said selected wavelet type,

n is a specified number of vanishing moments of said selected wavelet type, and

z_i, z_i+t. . . z<sub>i +(2n−

1)t</sub> are data necessary to yield at least one said wavelet-based generalized difference feature index from a spectral signature of an image;

(c) establishing a set of wavelet-based generalized difference feature indices that may be generated later in said efficient method of data mining;

(d) initiating at least one said means for manipulating data by setting a maximum wavelet order limit, selecting wavelength bands and setting K=0 and setting T=1, where

K is a specified wavelet array index, and

T is an incremented specified lag, defined as a specified number of said wavelength bands skipped between ones of said selected wavelength bands;

(e) setting a lag limit defined as

$1\le <br><br>t\le <br><br>\left(\mathrm{integer}<br><br>\left(\frac{m-1}{2<br><br>n-1}\right)\right),$

 

where m is a specified number of wavelength bands in a specified dataset;

(f) reading at least one said data set comprising said wavelength in said specified dataset bands into said means for manipulating;

(g) identifying and discarding said specified wavelength bands having compromised data;

(h) incrementing said K;

(i) incrementing said T by 1;

(j) computing a reduced set of difference-sum wavelength band ratios;

(k) generating at least one said established wavelet-based generalized difference feature index;

(l) generating a cube of each said established wavelet-based generalized difference feature index;

(m) selecting at least one of said established wavelet-based generalized difference feature indices;

(n) thresholding said selected pre-specified established wavelet-based generalized difference feature indices,

wherein said thresholding results in only said selected pre-specified established wavelet-based generalized difference feature indices being used henceforth;

(o) saving said thresholded selected pre-specified established wavelet-based generalized difference feature indices;

(p) determining if said lag limit has been met;

(q) if said lag limit has been met, determining if said maximum wavelet order limit has been met;

(r) if said lag limit has not been met, performing another iteration of steps (h) through (r) until said lag limit has been met;

(s) if said maximum wavelet order limit has been met, stopping; and

(t) if said maximum wavelet order limit has not been met, setting said T=1 and performing another iteration of steps (h) through (t) until said maximum wavelet order limit has been met,

wherein, if both said lag limit and said maximum wavelet order limit have been met, said efficient method of data mining is ended, resulting in an efficient identification of said desired features in said imagery data.

2. The method of claim 1 said imagery data comprising hyperspectral data.

3. The method of claim 2 said hyperspectral data comprising wavelengths in the spectra from about 300 to about 900 nanometers.

4. The method of claim 2 said hyperspectral data comprising wavelengths in the spectrum of visible light.

5. The method of claim 1 said means for manipulating said data comprising software running on at least one specially programmed computer.

6. The method of claim 1 wherein, in the step of setting said maximum wavelet order limit, said maximum wavelet order limit is set at sixteen (16).

7. The method of claim 1 selecting said wavelet type from the group consisting of Daubechies, Vaidyanathan, Coiflet, Beylkin, and Symmlet Wavelets.

8. The method of claim 7 selecting said Daubechies Wavelet as said wavelet type.

9. An efficient method of data mining to facilitate ready identification of desired features within a multi-band data set, comprising:

(a) selecting a wavelet type for use in said efficient method of data mining;

(b) providing means for manipulating said data, said means configured to perform the algorithm,

$G<br><br><br><br>D<br><br><br><br>F<br><br><br><br>I_{2<br><br>n}<br><br>\left(i,t\right)=\frac{h_o<br><br>z_i+h_1<br><br>z_{i+t}+\mathrm{\dots <br><br>}+h_{\left(2<br><br>n-1\right)}<br><br>z_{i+\left(2<br><br>n-1\right)<br><br>t}}{g_o<br><br>z_i+g_1<br><br>z_{i+t}+\mathrm{\dots <br><br>}+g_{\left(2<br><br>n-1\right)<br><br>t}<br><br>z_{i+\left(2<br><br>n-1\right)<br><br>t}},$

 

where

GDFI_2n(i, t) is a wavelet-based generalized difference feature index,

i refers to band i of a data collector,

t is a specified lag between bands,

h₀, h₁. . . h<sub>2n−

1</sub> are high frequency coefficients

g₀, g₁. . . g<sub>2n−

1</sub> are low frequency coefficients,

wherein, a number of said high and low frequency coefficients is determined upon establishing an order of a wavelet of said selected wavelet type,

n is a specified number of vanishing moments of said selected wavelet, and

z_i, z_i+t. . . z<sub>i+(2n−

1)t</sub> are data necessary to yield at least one said wavelet-based generalized difference feature index from a spectral signature;

(c) establishing a set of wavelet-based generalized difference feature indices that may be generated later in said efficient method of data mining;

(d) initiating at least one said means for manipulating data by setting a maximum wavelet order limit, selecting bands and setting K=0 and setting T=1, where

K is a specified wavelet array index, and

T is an incremented a specified lag, defined as a specified number of said bands skipped between ones of said selected bands;

(e) setting a lag limit defined as

$1\le <br><br>t\le <br><br>\left(\mathrm{integer}<br><br>\left(\frac{m-1}{2<br><br><br><br>n-1}\right)\right),$

 

where m is a specified number of bands in a specified dataset;

(f) reading at least one said data set comprising said bands in said specified dataset into said means for manipulating;

(g) identifying and discarding said specified bands having compromised data;

(h) incrementing said K;

(i) incrementing said T by 1;

(j) computing a reduced set of difference-sum band ratios;

(k) generating at least one said established wavelet-based generalized difference feature index;

(l) generating a cube of each said established wavelet-based generalized difference feature index;

(m) selecting at least one of said established wavelet-based generalized difference feature indices;

(n) thresholding said selected pre-specified established wavelet-based generalized difference feature indices,

wherein said thresholding results in only said selected pre-specified established wavelet-based generalized difference feature indices being used henceforth;

(o) saving said thresholded selected pre-specified established wavelet-based generalized difference feature indices;

(p) determining if said lag limit has been met;

(q) if said lag limit has been met, determining if said maximum wavelet order limit has been met;

(r) if said lag limit has not been met, performing another iteration of steps (h) through (r) until said lag limit has been met;

(s) if said maximum wavelet order limit has been met, stopping; and

(t) if said maximum wavelet order limit has not been met, setting said T=1 and performing another iteration of steps (h) through (t) until said maximum wavelet order limit has been met,

wherein, if both said lag limit and said maximum wavelet order limit have been met, said efficient method of data mining is ended, resulting in an efficient identification of said desired features in said multi-band data set.

10. An efficient method of data mining to facilitate ready categorization of a data set dispersed over multiple bands, comprising:

selecting at least one wavelet type for use in said method,

wherein said wavelet is selected to achieve optimum computational efficiency;

providing software for at least implementing an algorithm to calculate at least one wavelet-based generalized difference feature index (GDFI);

specifying a set of generalized difference feature indices to be calculated using said efficient method of data mining;

providing a software routine to select and process a reduced set of bands of said data set dispersed over multiple bands;

iterating a sub-routine of said routine while applying a lag limit and a maximum wavelet order limit to establish a number of iterations, said sub-routine to at least;

compute a reduced set of difference-sum band ratios;

calculate said generalized difference feature indices;

generate the cube of each said calculated generalized difference feature index;

select pre-specified ones of said calculated generalized difference feature indices;

threshold said selected calculated generalized difference feature indices,

wherein said thresholding results in only said selected calculated generalized difference feature indices being used henceforth; and

save said thresholded selected calculated generalized difference feature indices;

wherein, if both said lag limit and said maximum wavelet order limit have been met, said efficient method of data mining to facilitate ready categorization of a data set dispersed over multiple bands is ended, resulting in an efficient identification of said desired features in said data set.

11. A method that samples all band ratio combinations in hyperspectral data for use with rapid combinatorial computations that integrate wavelet and wavelet-variogram techniques for improved data anomaly filtering, detection and classification of imagery, comprising:

selecting at least one wavelet type for use in said method,

wherein said at least one wavelet type is selected to achieve optimum computational efficiency; and

providing software that displays results in a form that facilitates classification and feature extraction tasks while employing a least-ordered said wavelet that enables select features to be readily identified,

wherein executing said software yields band ratios that provide useful information in support of said classification and feature extraction tasks, and

wherein said method yields select said imagery with specific features highlighted by employing at least one generalized difference feature index (GDFI) band ratio and multiplying said generalized difference feature index (GDFI) band ratio by constants associated with coefficients of said at least one wavelet type, said GDFI band ratio defined by;

$G<br><br><br><br>D<br><br><br><br>F<br><br><br><br>I_{2<br><br>n}<br><br>\left(i,t\right)=\frac{h_o<br><br>z_i+h_1<br><br>z_{i+t}+\mathrm{\dots <br><br>}+h_{\left(2<br><br>n-1\right)}<br><br>z_{i+\left(2<br><br>n-1\right)<br><br>t}}{g_o<br><br>z_i+g_1<br><br>z_{i+t}+\mathrm{\dots <br><br>}+g_{\left(2<br><br>n-1\right)<br><br>t}<br><br>z_{i+\left(2<br><br>n-1\right)<br><br>t}},$

where

GDFI_2n(i, t) is a wavelet-based generalized difference feature index,

i refers to band i of a data collector,

t is a lag between bands,

h₀, h₁. . . h<sub>2n−

1</sub> are high frequency coefficients

g₀, g₁. . . g<sub>2n−

1</sub> are low frequency coefficients,

wherein, the number of said high and low frequency coefficients is determined upon establishing the order of said wavelet type,

n is the number of vanishing moments of said selected wavelet type, and

z_i, z_i+t . . . z<sub>i+(2n−

1)t</sub> are data used to yield at least one said generalized difference feature index; and

wherein at least one said feature appears in a resultant display as a distinct color or shade lighter than the remainder of said imagery.