A lossless image-compression algorithm that can be executed entirely in electronic hardware has been developed. This algorithm yields about 15 percent more compression than does the Rice algorithm, which is a lossless-compression algorithm commonly used for transmitting images from spacecraft to Earth. A prototype of the hardware (see figure), consisting mainly of a field-programmable gate array (FPGA) and a small random-access memory, has been built and verified to function as intended.

The present algorithm is called “FPGA LOCO” because of the FPGA implementation and because it is a modified version of a prior lossless image-compression algorithm called “Low Complexity Lossless Compression for Images” (LOCO-I). The purpose and effect of the modifications were to reduce the complexity of implementation in hardware and, especially, implementation in an FPGA.

The FPGA LOCO algorithm accepts, as input, a stream of 8- bit data that represent the brightnesses of pixels in a rectangular image. The output of the algorithm is a sequence of bits from which the original image data can be reconstructed.

The FPGA LOCO algorithm is based on the concept of predictive compression. During compression, the pixel data are processed in raster-scan order: Scanning starts at the upper left corner of each image, and pixel positions are incremented along each row before dropping down to the next row. The first two pixels in the first row are simply put into the output bit stream uncoded. For all other pixels of the image, the processing can be considered to be divided into the following steps:

1. Classify the current pixel into one of several contexts according to the values of a small number (usually 5) of previously encoded nearby pixels.

2. Estimate the value for the current pixel by extrapolation from a small number (usually 3) of previously encoded nearby pixels and add a correction (called the bias) that depends on the context.

3. Map the difference between the estimated and actual values of the current pixel to a nonnegative integer, and encode this integer by use of a Golomb code (Golomb codes are relatively simple, variable-length entropy codes that are well suited for encoding quantities with distributions that are approximately geometric).

4. Update the statistics for the context on the basis of the value for the current pixel.

The prototype hardware (see figure) includes a commercial FPGA installed on a commercial circuit board that features a PC/104 interface [PC/104 is an industry standard for compact, stackable modules that are fully compatible (in architecture, hardware, and software) with personal-computer data- and power-bus circuitry]. An optional 256K × 18 zero-bus-turn-around (ZBT) static random-access memory (SRAM) is installed on the board with the FPGA. An adaptor card is used as an additional interface between the PC/104 interface and the Industry Standard Architecture (ISA) interface of the computer in which the prototype hardware is installed. To enable simultaneous access to all the data for a context, a second, identical SRAM was installed on a daughter card that is connected to the board via two ribbon cables.

The Prototype Image-Compression Hardware is installed in a computer that supplies the input image data and accepts the output (compressed) image data.

In tests at a clock speed of 12 MHz, the prototype hardware was found to process image data at a rate of 260 kilopixels per second. However, most of the processing time was spent waiting for transfers of data to and from the computer. The throughput rate of the prototype hardware by itself is about 1.33 megapixels per second.

This work was done by Matthew Klimesh, Valerie Stanton, and David Watola of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free online at www.nasatech.com/tsp under the Electronic Components and Systems category.

In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to

Intellectual Property group
JPL
Mail Stop 202-233
4800 Oak Grove Drive
Pasadena, CA 91109
(818) 354-2240

Refer to NPO-21238, volume and number of this NASA Tech Briefs issue, and the page number.


This Brief includes a Technical Support Package (TSP).
Lossless Image-Compression Algorithm Implemented in an FPGA

(reference NPO-21238) is currently available for download from the TSP library.

Don't have an account? Sign up here.



NASA Tech Briefs Magazine

This article first appeared in the January, 2002 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.