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.

Topics:
Architecture Computer software and hardware Electronics & Computers Hardware Imaging and visualization Mathematical models Optics Parts Photonics Simulation and modeling
This Brief includes a Technical Support Package (TSP).
Document cover
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?

Magazine cover
NASA Tech Briefs Magazine

This article first appeared in the January, 2002 issue of NASA Tech Briefs Magazine (Vol. 26 No. 1).

Read more articles from the archives here.

Overview

The document discusses the development and implementation of a novel lossless image-compression algorithm designed for use in electronic hardware, specifically utilizing a field-programmable gate array (FPGA). This algorithm, referred to as "FPGA LOCO," achieves approximately 15% better compression than the commonly used Rice algorithm, which is employed for transmitting images from spacecraft to Earth.

The hardware prototype consists of a commercially available FPGA board, the APS-V240, which features a Xilinx Virtex XCV50 FPGA. The board is interfaced with a computer via a PC/104 interface and an Industry Standard Architecture (ISA) adaptor card. To enhance data processing capabilities, the system includes an optional 256K×18 zero-bus-turn-around (ZBT) static random-access memory (SRAM) and a second identical SRAM on a daughter card, allowing simultaneous access to data.

The document outlines the physical setup of the FPGA LOCO system, detailing how the FPGA processes image data at a rate of 260 kilopixels per second, although the overall throughput is limited to about 1.33 megapixels per second due to data transfer delays with the computer. The implementation avoids complex features like run-length encoding, which could complicate hardware execution, focusing instead on efficient compression of natural images.

The motivation behind this work stems from the need for a hardware implementation of a lossless image compression algorithm that can effectively handle natural images, as previous hardware implementations yielded inferior compression results. The solution involved modifying a state-of-the-art algorithm to reduce implementation complexity, making it suitable for hardware execution.

The document also emphasizes the novelty of the work, highlighting its improvements over prior art in terms of compression efficiency and hardware suitability. It notes that the research was conducted at NASA's Jet Propulsion Laboratory under a contract with the National Aeronautics and Space Administration (NASA), and it includes a disclaimer regarding the endorsement of specific commercial products.

In summary, the document presents a significant advancement in image compression technology, showcasing a hardware-optimized algorithm that enhances the efficiency of image transmission, particularly in the context of space exploration.