Parallel Lossless Image Compression Using Huffman and Arithmetic Coding

P. G. Howard and J. S. Vitter. ``Parallel Lossless Image Compression Using Huffman and Arithmetic Coding,'' Information Processing Letters, 59, 1996, 65-73. A shortened version appears in Proceedings of the 1992 IEEE Data Compression Conference (DCC '92), Snowbird, UT, March 1992, 299-308.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

We show that high-resolution images can be encoded and decoded efficiently in parallel. We present an algorithm based on the hierarchical MLP method, used either with Huffman coding or with a new variant of arithmetic coding called quasi-arithmetic coding. The coding step can be parallelized, even though the codes for different pixels are of different lengths; parallelization of the prediction and error modeling components is straightforward.