Predictors in Image Coding

This is a short one. I'm talking about heuristics for predicting the value of a pixel based on its neighbours, for the purposes of generating residuals with less entropy than the input pixels, and which are thus more compressible. Read the PNG specification or an introductory text on image coding, or the prediction + residual coding strategy more generally, if you have no idea what i'm on about.

I'm going to define the predictors in terms of pixels called N, W and NW, being the pixels lying to the north, west and northwest of the target, respectively. I'll call the predicted value P.

PNG defines five predictors:

• None: P = 0
• Sub, aka West: P = W
• Up, aka North: P = N
• Average: P = (N + W) / 2
• Paeth: Q = N + W - NW; dN = |N - Q|; dW = |W - Q|; dNW = |NW - Q|; P = (if dN < dW, dNW) N, (if dW < dN, dNW) W, (if dNW < dN, dW) NW. In English, compute a meta-predictor, Q, as N + W - NW (which corresponds to the value P would have if there was a constant gradient of colour in this part of the image), then pick the neighbouring pixel whose value is closest to the meta-predictor to use as a predictor.

Paeth is a weird one; i would have thought the meta-predictor would itself make quite a good predictor! I think the point is that sticking to an already-used value makes more sense in images like drawings, where there are big blocks of constant colour.

A popular new predictor is:

• Median Adaptive: P = (if NW > max(N, W)) min(N, W), (if NW < min(N, W)) max(N, W), (else) N + W - NW

Basically, this is applying the Paeth meta-predictor, but clamping the value to the range [min(N, W), max(N, W)].