Modeling and low-complexity adaptive coding for image prediction residuals

This paper elaborates on the use of discrete, two-sided geometric distribution models for image prediction residuals. After providing achievable bounds for universal coding of a rich family of models, which includes traditional image models, we present a new family of practical prefix codes for adaptive image compression. This family is optimal for two-sided geometric distributions and is an extension of the Golomb (1966) codes. Our new family of codes allows for encoding of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the rough approximations used when a code designed for non-negative integers is matched to the encoding of any integer. We also provide adaptation criteria for a further simplified, sub-optimal family of codes used in practice.