A progressive Ziv-Lempel algorithm for image compression

We describe an algorithm that gives a progression of compressed versions of a single image. Each stage of the progression is a lossy compression of the image, with the distortion decreasing in each stage, until the last image is losslessly compressed. Progressive encodings are useful in applications such as Web browsing and multicast, where the best rate/distortion tradeoff often is not known in advance. With progressive encoding, the system can respond dynamically: for example, a low-quality version of an image is sufficient when a user wishes to browse quickly, or when a slow link is encountered in a multicast. Our algorithm assumes an initial vector quantization step which maps important information of an image, such as intensity values, into higher-order bits. The bit planes are then sent successively using a progressive Ziv-Lempel (1978) algorithm. We propose data structuring techniques for selectively coding only those entries in a Ziv-Lempel dictionary that are feasible matches, based on shared knowledge of the data transmitted in earlier stages. Our technique, when applied to sample images on the Web, gives significant improvements over interlaced GIF in both image quality and compression rate. Our progressive LZ algorithm runs in amortized linear time