Asymmetric lossless image compression

Asymmetric Lossless Image Compression Nasir D. Memon Dept. of Computer Science Northern Illinois University

Khalid Sayood Dept. of Electrical Eng. University of Nebraska-Lincoln

Lossless image compression is often required in situations where compression is done once and decompression is to be performed a multiple number of times. Since compression is to be performed only once, time taken for compression is not a critical factor while selecting an appropriate compression scheme. What is more critical is the amount of time and memory needNed for decompression and also the compression ratio obtained. Compression schemes that satisfy the above constraints are called asymmetric techniques. While there exist many asymmetric techniques for the lossy compression of image data, most techniques reported for lossless compression of image data have been symmetric. In this paper we present a new lossless compression technique that is well suited for asymmetric applications. It gives superior performance compared to standard lossless compression techniques by exploiting ‘global’ correlations By ‘global’ correlations we mean similar patterns of pixels that re-occur within the image, not necessarily at close proximity. The developed technique can also potentially be adapted for use in symmetric applications that require high compression ratios. The scheme is based on the notion of a prediction pattern which is simply a k x k array with each of its elements representing an index of a prediction scheme from a given set F of predictors. To encode a given image, we first choose a set of prediction schemes F,and then construct a codebook of prediction patterns that is optimal for the image under consideration. For each block in the image, we then identify the best prediction pattern from within the codebook by an exhaustive search. The index of this prediction pattern is then transmitted along with an encoding of the prediction residuals obtained by using i,his prediction pattern on the image block. The entire codebook of prediction patterns is also explicitly transmitted to the receiver as additional overhead. The problem is to construct an optimal codebook of specified size for the given image (or class of images). We develop algorithms for codebook design using LBG like clustering of image blocks. For the sake of a preliminary investigation, codebooks of various sizes were constructed using different block sizes and using the 8 JPEG predictors as the set of prediction schemes. To encode the prediction residuals efficiently, we use a composite source model with a forward adaptive switching scheme. We look at a few different heuristics for classifying pixel blocks into one of k different sub-sources and transmitting the label of the sub-source as side information. Each sub-source is encoded by using an adaptive arithmetic code. The final bit rates achieved with preliminary implementations represent a significant improvement over some standard symmetric techniques reported in the literature.

1068-0314/95$4.00 0 1995 IEEE

457