Burrows-Wheeler Transform in image compression

Markus Gaertner, David Havelin

In 1994, Burrows and Wheeler proposed a new lossless compression algorithm.
The heart of the algorithm is a reversible block sort which increases the
compressibility of the input data. As described in the original paper, this
algorithm is only applicable to text data. It cannot be applied directly to
image data.

It is possible, however, to encode or transform the image data before using
the Burrows-Wheeler Transform (BWT). This project will investigate various
methods of transforming the image data, including DCT and DWT, to make it
suitable for use with the BWT. Initially, we shall compare the performance of a
lossless compression scheme incorporating the BWT with a high-performance modern
compression standard, e.g. JPEG-LS. Then we shall investigate the usefulness of
the BWT as part of a lossy compression scheme.

Our goal is to develop a compression algorithm incorporating first an appropriate 
transform of the image data, followed by the BWT, then finally an encoding scheme
that together are competitive with the best modern methods of lossless and lossy 
compression.

Further goals include the modification of the BWT to make it more suitable 
for 2-dimensional image data.

References:
1. M. Burrows, D.J. Wheeler. A block-sorting lossless data compression
algorithm. Technical Report SRC-124, Digital System Research Center, Palo
Alto, May 1994.
2. Guo Haitao, C.S. Burrus. Waveform and image compression using the
Burrows Wheeler transform and the wavelet transform. In Proceedings of the
International Conference on Image Processing, pages 65-68, volume 1 , 1997.