Lossless Image Compression Using Pixel Reordering
Michael Ciavarella
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Alistair Moffat
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Status
Proc. 27th Australasian Computer Science Conference,
Dunedin, New Zealand, January 2004, pages 125-132.
Abstract
Lossless image compression techniques typically consider images to be
a sequence of pixels in row major order.
The processing of each pixel consists of two separate operations.
The first step forms a prediction as to the numeric value of the next
pixel.
Typical predictors involve a linear combination of neighboring pixel
values, possibly in conjunction with an edge detection heuristic.
In the second step, the difference between that prediction and the
actual value of the next pixel is coded.
In high-performance mechanisms such as JPEG-LS, the error
differential is coded in a conditioning context established by a
possibly-different set of neighboring pixels.
A per-context arithmetic, minimum-redundancy, or Rice coder completes the
processing of each pixel.
In this paper we explore pixel reordering as a way of reducing the
start-up (or learning) cost associated with each context.
By permuting the prediction errors into an order that reflects the
assessed volatility of the conditioning context, we are able to use a
single coding context, with the changing probability estimates
captured by local adaptation in the coder.
In this sense, our proposal has elements in common with the
Burrows-Wheeler text compression mechanism.
The result is a lossless compression implementation that achieves
excellent compression rates.