An algorithm that effects fast lossless compression of multispectral-image data is based on low-complexity, proven adaptive filtering algorithms. This algorithm is intended for use in compressing multispectral-image data aboard spacecraft for transmission to Earth stations. Variants of this algorithm could be useful for lossless compression of three-dimensional medical imagery and, perhaps, for compressing image data in general.

The main adaptive-filtering algorithm on which the present algorithm is based is the sign algorithm (also known as the sign error algorithm and as the binary reinforcement algorithm). The sign algorithm is related to the least-mean-square (LMS) algorithm. Both algorithms are briefly described in the following two paragraphs.

Consider a sequence of image data (or any other data) that one seeks to compress. The sequence is specified in terms of a sequentially increasing index (*k*) and the value (*d _{k}*) of the kth sample. An estimated value of the kth sample,

*k*, is calculated by the equation

,

where *w _{k}* is a filter-weight vector at index

*k*and

*u*is an input vector that can be defined in any of a number of different ways, depending on the specific application. Once the estimate

_{k}*k*has been calculated, the error between the estimate and the exact value is calculated as

When the LMS algorithm or sign algorithm is used as part of a predictive compression scheme, the sequence of *e _{k}* values is encoded in the compressed bitstream.

The error value is also used to update the filter weights in either of two ways, depending on which algorithm is in use. In the LMS algorithm, the update equation is

In the sign algorithm, the update equation is

.

In both update equations, *µ* is a positive, scalar step-size parameter that controls the trade-off between convergence speed and average steady-state error. A smaller value of *µ* results in better steady state performance but slower convergence. In some variants of these algorithms, the value of *µ* changes over time.

In the present algorithm, the index *k* is taken as an abstract representation of three indices *(x,y,z) *that are the coordinates of the sample in the multispectral dataset. Specifically, *x* and *y *are the spatial coordinates and *z* denotes the spectral band. The signal level (equivalently, the sample value) for that location is represented by *d _{k} = s(x,y,z)*.

For purposes of compression, an image represented by a stream of data to be compressed is partitioned spatially into conveniently sized, fixed regions. The data are compressed in the order in which they are received, maintaining separate statistics for each band and switching among the bands as necessary. The data from each region are compressed independently of those from other regions. Performing independent compression calculations for each region limits the adverse effect of loss of data.

The input vector uk chosen for this algorithm contains values from a six sample prediction neighborhood of a sample of interest: three values from adjacent samples in the same spectral band and one sample each from the same location in each of three preceding spectral bands. Specifically, where *(x,y,z)* is a mean value of previous samples in the vicinity of *x,y* in spectral band *z*. The stream of *e _{k}* values calculated by use of this

*u*is further compressed by use of Golomb codes.

_{k}In tests, the compression effectiveness of this algorithm was shown to be competitive with that of the best previously reported data-compression algorithms of similar complexity. The table presents results from one series of tests performed on multispectral imagery acquired by NASA’s airborne visible/infrared imaging spectrometer (AVIRIS).

This work was done by Matthew Klimesh of Caltech for NASA’s Jet Propulsion Laboratory.

*For further information, access the Technical Support Package (TSP) free online at www.techbriefs.com/tsp under the Information Sciences category. *

*The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-42517.*