Progressive Ziv-Lempel encoding of synthetic images

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. Both compressor and decompressor make use of earlier stages to significantly improve the compression of later stages of the progression. Our algorithm uses vector quantization to improve the distortion at the beginning of the progression, and adapts Ziv and Lempel's algorithm to make it efficient for progressive encoding. One principal motivation for this work is to address some significant shortcomings in using interlaced GIF for web browsing. First, the initial stages of a GIF progression are often hard to read (especially for text labels embedded in synthetic images). Our algorithm addresses this problem with a vector quantization design that uses a shifting metric to allow useful information, such as text, to appear early in the progression. Another shortcoming of interlaced GIF is that, because it does not take good advantage of the information transmitted in earlier stages, there is poor compression in later stages of the progression. We remedy this shortcoming with a data structure design which selectively codes only those portions of a LZ dictionary that are feasible matches, based on shared knowledge of the data already transmitted. Our test results are quite promising. For example, after the 2nd pass in a 4-pass transmission, our algorithm generates compressed file sizes (total of pass 1 & pass 2) that range from 21% to 81% of the corresponding GIF file sizes, in addition to showing superior image quality.