Conclusions

For lossless encoding of images, we have demonstrated that it is possible to apply BWT/MTF directly to an image. 20-40% compression of the image can be achieved in this way. That is below the 40-50% achievable with a state-of-the-art encoder but we have hardly begun to explore the possibilities of combining BWT with other techniques in order to improve these results. For example, instead of performing a 2D to 1D transformation by zig-zag scan, we could try a Peano scan. Or we could follow a BWT by a predictive encoder. Or we could use wavelet transforms that map integers to integers and so are reversible. There are many possibilities.

We did not find any benefit in using predictive encoding followed by BWT, as suggested in a published paper.

For lossy encoding, we could not show any benefit in combining BWT with DCT.

Based on our experiments and published results [5], we are confident that BWT can be usefully employed to exploit the correlation between subbands evident in wavelet-transformed images. A promising avenue for further exploration would be the 2D to 1D scanning technique we must use before BWT. Instead of the zig-zag method we used here, we would like to try something similar to the zero-trees employed in EZT coding.

Aside from the purely technical question of whether it is possible to achieve good compression rates using BWT, we must also ask whether it is a practical technique. The biggest disadvantage of the BWT is that it operates on blocks of data, the larger the better. In the case of a compressed image, we would have to receive the entire set of data before being able to begin decompression.

Today, the state-of-the-art in lossy compression is the Said-Pearlman wavelet encoder. This encoder performs very well at eliminating redundancy from wavelet-encoded images. It is doubtful whether any BWT-based scheme could outperform such an encoder.

But Said-Pearlman has one very large advantage over BWT - it can progressively decode images. This means that the encoder can decompress the image to any resolution that is required without needing to process the entire compressed image data. This ability promises great flexibility in designing applications that access compressed image data - for example a mobile phone and a workstation could both access the same image file, the phone at a low resolution, the workstation at a much higher resolution.

In other words, it is difficult to compete in the lossy-compression arena against state-of-the-art algorithms that provide significant advantages other than high compression rates.

However, the application of BWT to lossless compression has not been well-explored. There might be applications where high compression is valued more than the ability to progressively decode (for example, in storing medical images).

The concept of sorting data before compression is a powerful one. Over the last six years, it has led to significant improvements in text compression. We feel it may well have an application in image compression too.