HP Labs Technical Reports

Lossless Compression for Sources with Two-Sided Geometric Distributions

Merhav, Neri; Seroussi, Gadiel; Weinberger, Marcelo J.

HPL-98-70

Keyword(s): lossless image compression; Huffman code; infinite alphabet; geometric distribution; exponential distribution; Golomb codes; prediction residual; universal coding; sequential coding; universal modeling

Abstract: Lossless compression is studied for a countably infinite alphabet source with an off-centered, two- sided geometric (TSG) distribution, which is a commonly used statistical model for image prediction residuals. In the first part of this paper, we demonstrate that arithmetic coding based on a simple strategy of model adaptation, essentially attains the theoretical lower bound to the universal coding redundancy associated with this model. In the second part, we focus on more practical codes for the TSG, that operate on a symbol-by-symbol basis. Specifically, we present a complete characterization of minimum expected-length prefix codes for TSG sources. The family of optimal codes introduced here is an extension of the Golomb codes, which are optimal for one-sided geometric distributions of nonnegative integers. As in the one-sided case, the resulting optimum Huffman tree has a structure that enables simple calculation of the codeword of every given source symbol. Our characterization avoids the heuristic approximations frequently used when modifying Golomb codes so as to apply to two-sided sources. Finally, we provide adaptation criteria for a further simplified, sub-optimal family of codes used in practice.

33 Pages

Back to Index