An analysis of some common scanning techniques for lossless image coding

Though most image coding techniques use a raster scan to order pixels prior to coding, Hilbert and other scans have been proposed as having better performance due to their superior locality preserving properties. However, a general understanding of the merits of various scans has been lacking. This paper develops an approach for quantitatively analyzing the effect of pixel scan order for context-based, predictive lossless image compression and uses it to compare raster, Hilbert, random and hierarchical scans. Specifically, for a quantized-Gaussian image model and a given scan order, it shows how the encoding rate can be estimated from the frequencies with which various pixel configurations are available as previously scanned contexts, and from the corresponding conditional differential entropies. Formulas are derived for such context frequencies and entropies. Assuming an isotropic image model and contexts consisting of previously scanned adjacent pixels, it is found that the raster scan is better than the Hilbert scan which is often used in compression applications due to its locality preserving properties. The hierarchical scan is better still, though it is based on nonadjacent contexts. The random scan is the worst of the four considered. Extensions and implications of the results to lossy coding are also discussed.