Simpler Adaptive Selection of Golomb Power-of-Two Codes

NASA’s Jet Propulsion Laboratory, Pasadena, California

Thursday, November 01 2007 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.