An alternative method of adaptive selection of Golomb power-of-two (GPO2) codes has been devised for use in efficient, lossless encoding of sequences of non-negative integers from discrete sources. The method is intended especially for use in compression of digital image data. This method is somewhat suboptimal, but offers the advantage in that it involves significantly less computation than does a prior method of adaptive selection of optimum codes through "brute force" application of all code options to every block of samples.

Upper and Lower Bounds on the optimum valueof the code parameter make it possible toreduce the number of code options that must beconsidered.

A rather lengthy discussion of background is necessary to give meaning to a brief summary of this innovation. For positive integer, m, the mth Golomb code defines a reversible, prefix-free mapping of non-negative integers to variable-length binary code words. Golomb codes are optimum for geometrically distributed sources (a model that frequently arises in image compression): In the case of a geometrically distributed random variable, δ, the appropriately selected Golomb code minimizes the expected code-word length over all possible lossless binary codes for δ.

In a GPO2 code, m = 2k, where k is a non-negative integer. Such a code makes the coding process particularly simple: The code word for the integer δ consists of the unary representation of ⎣δ/2k⎦ (that is, ⎣δ/2k⎦ zeros followed by a one) concatenated with the k least significant bits of the binary representation of δ. More specifically, the code is called a GPO2 code of parameter k.

The problem is to calculate or estimate the value of code parameter k that minimizes the expected bit rate (the average number of encoded bits per source symbol) for an image or other source. This problem arises in Rice coding, which is a coding method well known among experts in data compression. The Rice algorithm encodes a block of samples by use of the best code option for the block from among several candidate codes that consist mostly of different GPO2 codes. A fixed number of bits are used preceding the encoded block to indicate which code was selected. The Rice method does not specify how to find the best code option, and the most common approach is to exhaustively try every code option to pick the best one for each block. Information from previously coded blocks is not utilized. This concludes the background information.

In the present method, unlike in the Rice method, one utilizes the mean sample value in each block. The method is based partly on a theoretical derivation of bounds on the optimum value of k as functions of the mean sample value (see figure). These bounds are such that no more than three code choices can be optimum for a given mean sample value. For a given mean value, one of the three candidate codes is selected in a procedure that involves only integer arithmetic (without divisions) and table look-ups. It has been shown that the value of k selected in this relatively simple procedure is always within 1 of the optimum k value for the source, and that the cost added by the suboptimality of the selection is never more than 1/2 bit per sample and no more than about 13-percent inefficiency. In practical image compression experiments, the cost added by the suboptimality of the selection is negligible.

This work was done by Aaron Kiely of Caltech for NASA's Jet Propulsion Laboratory. 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-41336.

NASA Tech Briefs Magazine

This article first appeared in the November, 2007 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.