
HP Labs Technical Reports
Click here for full text:
Lossless Compression for Sources with TwoSided Geometric Distributions
Merhav, Neri; Seroussi, Gadiel; Weinberger, Marcelo J.
HPL9870
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 offcentered, 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 symbolbysymbol basis. Specifically, we present a complete characterization of minimum expectedlength prefix codes for TSG sources. The family of optimal codes introduced here is an extension of the Golomb codes, which are optimal for onesided geometric distributions of nonnegative integers. As in the onesided 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 twosided sources. Finally, we provide adaptation criteria for a further simplified, suboptimal family of codes used in practice.
33 Pages
Back to Index
