chapter 7, Lossless Predictive Coding

Excerpt

For typical images, the values of adjacent pixels are highly correlated; that is, a great deal of information about a pixel value can be obtained by inspecting its neighboring pixel values. This property is exploited in predictive coding techniques where an attempt is made to predict the value of a given pixel based on the values of the surrounding pixels. We first describe a general, but impractical, predictive coding scheme and then discuss modifications that yield a practical scheme.

Consider an image modeled as an mth-order Markov source, where each pixel is represented by k bits and can thus take any one of K( = 2^k) possible values. In this model, the value of a given pixel x_m depends only on the values of the m previous pixels, x₀,x₁,…,x_m−1. The number of possible combinations of the m previous pixel values is K^m, and each combination defines a state of the Markov source. For each state, there is an associated set of K conditional probabilities for the value of the pixel x_m, i.e., p(x_m∣x_m−1,…,x₀), for x_m = 0,…,K−1. If these conditional probabilities, along with the stationary state probabilities, are known, the entropy of the mth-order Markov source can be calculated according to Eq. (2.5).

In theory, a lossless predictive coding scheme is capable of encoding an image at a bit rate close to this entropy by employing the following strategy. Given the m previous pixel values, the state of the Markov source is defined and the conditional probabilities for the current pixel value p(x_m∣x_m−1,…,x₀) for x_m = 0,…,K−1 are known. The numbers 0 through K − 1 form a set of K predictions (estimates) for the value of x_m given the current state. The prediction that matches the actual value x_m is identified and encoded using a variable-length code optimized for the set of conditional probabilities within that state. Since the decoder also has access to the m previous pixels, it can track the state of the Markov source and hence the corresponding codebook. This allows the decoder to decode the encoded information and identify the actual pixel value x_m.