LOSSLESS COMPRESSION ALGORITHM FOR HYPERSPECTRAL DATA

• US 20090018801A1
• Filed: 07/09/2007
• Published: 01/15/2009
• Est. Priority Date: 07/09/2007
• Status: Active Grant

• Current Assignee: The United States of America As Represented By The Secretary of Commerce
• Original Assignee: The United States of America As Represented By The Secretary of Commerce
• Inventors: Gladkova, Irina, Grossberg, Michael, Roytman, Leonid
• Granted Patent: US 7,907,784 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/34 Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• CPC Class Codes: H04N 19/463 by compressing encoding parameters before transmission
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Lossless compression techniques provide efficient compression of hyperspectral satellite data. The present invention combines the advantages of a clustering with linear modeling. A number of visualizations are presented, which help clarify why the approach of the present invention is particularly effective on this dataset. At each stage, the algorithm achieves an efficient grouping of the data points around a relatively small number of lines in a very large dimensional data space. The parametrization of these lines is very efficient, which leads to efficient descriptions of data points. The method of the present invention yields compression ratios that compare favorably with what is currently achievable by other approaches.

Claims

1. A method of compressing a stream of input data elements to produce an output data stream, the method comprising the steps of:

(a) selecting at least one model, from a set of predetermined mathematical models, each mathematical model parameterizing a space with a set of model specific coordinates, the coordinates represented by a tuple of at least one coordinate values, and outputting for each selected model parameters comprising a map, from a tuple of coordinate values in the model space to an approximating set of data values for at least one subportion of the data elements,

(b) determining, for at least one subportion of the data elements, a label indicating a selected model, and the values of a tuple of model coordinates which map to a tuple of data values which, according to some measure of merit, best approximate the subportion of the data elements, and

(c) outputting at least the model coordinates as at least a portion of an output data stream.

2. The method of claim 1, further comprising the step of:

(d) computing differences between model representations for a selected mathematical model and the corresponding subportion of data elements as residuals and outputting the residuals as a portion of the output data stream.

3. The method of claim 2, further comprising the step of:

(e) compressing at least one of the model parameters, model coefficients, and residuals prior to outputting the mathematical model, model coefficients, and residuals as a portion of the output data stream.

4. The method of claim 1, wherein the step of selecting at least one model comprises the step of:

selecting at least two models by first clustering into groups, a set of tuples of data values, wherein each tuple of values corresponds to a subportion of the data elements.

5. The method of claim 2, wherein the steps (a)-(d) are performed using a lossless model to insure integrity of reconstructed data from the output data stream.

6. The method of claim 2, further comprising the step of

iteratively processing the residuals through steps (a)-(d) to further compress the input data and produce new residuals.

7. The method of claim 6, further comprising the step of:

applying a transformation to the input data before applying step (a).

8. The method of claim 1, further comprising the step of:

applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters.

9. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using a mean the sum of squared errors to quantify the fit between the input data elements and the piecewise model parameters.

10. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using mean sum of absolute distances to quantify the fit between the data and the piecewise model parameters.

11. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using mean entropy of the residuals to quantify the fit between the data and the piecewise model parameters.

12. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using a non-linear optimization of the model coefficients to quantify the fit between the data and the piecewise model parameters to minimize the objective function.

13. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using a randomized search of the optimal model coefficients to quantify the fit between the data and the piecewise model parameters to minimize the objective function.

14. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using a brute force search for the optimal model coefficients to quantify the fit between the data and the piecewise model parameters to minimize the objective function.

15. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using a gradient decent search to quantify the fit between the data and the piecewise model parameters for the optimal parameters of the objective function.

16. The method of claim 8, wherein the step of applying an objective function (measure of merit) to quantify a fit between the input data elements and the piecewise model parameters comprises the step of:

using a linear least squares minimization between the data and the model to quantify the fit between the data and the piecewise model parameters.

17. The method of claim 4, wherein the stream of input data elements comprises remotely sensed hyperspectral data, and the step of the clustering the input data elements into groups of data elements so that each subportion of data elements can be represented compactly by one of a set of predetermined mathematical models comprises the step of clustering the hyperspectral data into a hyperspectral data cube.

18. The method of claim 1, wherein the step of compressing at least one of the model parameters, model coefficients, and residuals prior to outputting the mathematical model, model coefficients, and residuals as a portion of the output data stream comprises the step of:

independently encoding the model parameters, model coefficients, and residuals by channel encoding.

19. The method of claim 18, wherein the step of channel coding comprises forward error-correction coding.

20. The method of claim 19, wherein the model parameters are channel encoded using a first, very strong level of forward error-correction to provide robustness from error with a negligible effect on compression.

21. The method of claim 20, wherein the model coefficients are channel encoded using a second, strong level of forward error-correction, less strong than the first, very strong level of error correction to provide robustness from error with a negligible effect on compression.

22. The method of claim 20, wherein the residuals are channel encoded using a third, weak level of forward error-correction, less strong than the second, strong level of error correction, as error in the final residuals has a negligible effect on a reconstructed data stream.