An Optimizing Lossy Generalization of LZW

We present a lossy generalization of Welch's LZW algorithm [Welch84]. We rst discuss tw o lossy generalizations of LZW,G-LZW [Pigeon95] and LLZW [Chiang98] that do not optimize an y speci c objective function. We present an algorithm, also lossy, that optimizes compression according to an objective function supplied by the user. This enables him to balance betw een compression ratio and image quality. The algorithm in [Pigeon95] uses a trie as its data structure. Instead of looking for an exact match in the trie with the current input, algorithm G-LZW greedily matches with the pixel in the trie having the less di erence with the corresponding pixel in the input. This greedy strategy maximizes image quality but preven ts the algorithm from nding longer matches because of a locally bad match. The algorithm in [Chiang98] nds the longuest string in the dictionary that does not exceed a certain error threshold. This only maximize compression. The proprosed algorithm searches its dictionary to nd a string that maximizes (or minimizes) some error function that takes into account both compression ratio and image quality. This algorithm, P-LLZW, optimizes in linear time over the trie a separable objective function (parameterized by , as in the table, the maximum instantaneous error). Our implementation of the algorithm as a GIF optimizer has the particularity that it is decode compatible with GIF readers, meaning that the program creates les that can be read b y web browsers and le viewers without having to recourse to a plug-in, even if the compressor tak es di erent decisions during compression. The table sho ws results for les from the DJVU corpus. P-LLZW 8 BPP File Ra w Size Gif Size K Gif BPP Size in K BPP SNR NY Cargo 1.1M 766.8 5.7 20 275 2.0 27 dB Jupiter 7.9M 4542 4.6 20 3436 3.4 25 dB Laga e 8.5M 5064 4.8 20 3495 2.4 26 dB New River 16.7M 8402 4.1 20 6164 3.0 29 dB P-Boxes 7.4M 3410 3.7 2