One of the most common algorithms used in computer graphics is the Lempel-Ziv-Welch, or LZW, compression scheme. This lossless method of data compression is found in several image file formats, such as GIF and TIFF, and is also part of the V.42bis modem compression standard and PostScript Level 2.
In 1977, Abraham Lempel and Jakob Ziv created the first of what we now call the LZ family of substitutional compressors. The LZ77 compression algorithms are commonly found in text compression and archiving programs, such as compress, zoo, lha, pkzip, and arj. The LZ78 compression algorithms are more commonly used to compress binary data, such as bitmaps.
In 1984, while working for Unisys, Terry Welch modified the LZ78 compressor for implementation in high-performance disk controllers. The result was the LZW algorithm that is commonly found today.
LZW is a general compression algorithm capable of working on almost any type of data. It is generally fast in both compressing and decompressing data and does not require the use of floating-point operations. Also, because LZW writes compressed data as bytes and not as words, LZW-encoded output can be identical on both big-endian and little-endian systems, although you may still encounter bit order and fill order problems. (See Chapter 6, Platform Dependencies, for a discussion of such systems.)
LZW is referred to as a substitutional or dictionary-based encoding algorithm. The algorithm builds a data dictionary (also called a translation table or string table) of data occurring in an uncompressed data stream. Patterns of data (substrings) are identified in the data stream and are matched to entries in the dictionary. If the substring is not present in the dictionary, a code phrase is created based on the data content of the substring, and it is stored in the dictionary. The phrase is then written to the compressed output stream.
When a reoccurrence of a substring is identified in the data, the phrase of the substring already stored in the dictionary is written to the output. Because the phrase value has a physical size that is smaller than the substring it represents, data compression is achieved.
Decoding LZW data is the reverse of encoding. The decompressor reads a code from the encoded data stream and adds the code to the data dictionary if it is not already there. The code is then translated into the string it represents and is written to the uncompressed output stream.
LZW goes beyond most dictionary-based compressors in that it is not necessary to preserve the dictionary to decode the LZW data stream. This can save quite a bit of space when storing the LZW-encoded data. When compressing text files, LZW initializes the first 256 entries of the dictionary with the 8-bit ASCII character set (values 00h through FFh) as phrases. These phrases represent all possible single-byte values that may occur in the data stream, and all substrings are in turn built from these phrases. Because both LZW encoders and decoders begin with dictionaries initialized to these values, a decoder need not have the original dictionary and instead will build a duplicate dictionary as it decodes.
TIFF, among other file formats, applies the same method for graphic files. In TIFF, the pixel data is packed into bytes before being presented to LZW, so an LZW source byte might be a pixel value, part of a pixel value, or several pixel values, depending on the image's bit depth and number of color channels.
GIF requires each LZW input symbol to be a pixel value. Because GIF allows 1- to 8-bit deep images, there are between 2 and 256 LZW input symbols in GIF, and the LZW dictionary is initialized accordingly. It is irrelevant how the pixels might have been packed into storage originally; LZW will deal with them as a sequence of symbols.
The TIFF approach does not work very well for odd-size pixels, because packing the pixels into bytes creates byte sequences that do not match the original pixel sequences, and any patterns in the pixels are obscured. If pixel boundaries and byte boundaries agree (e.g., two 4-bit pixels per byte, or one 16-bit pixel every two bytes), then TIFF's method works well.
The GIF approach works better for odd-size bit depths, but it is difficult to extend it to more than eight bits per pixel because the LZW dictionary must become very large to achieve useful compression on large input alphabets.
LZW does a very good job of compressing image data with a wide variety of pixel depths. 1-, 8-, and 24-bit images all compress at least as well as they do using RLE encoding schemes. Noisy images, however, can significantly degrade the compression effectiveness of LZW. Removing noise from an image, usually by zeroing out one or two of the least significant bit planes of the image, is recommended to increase compression efficiency. In other words, if your data does not compress well in its present form, transform it to a different form that does compress well.
One method that is used to make data more "compressible" by reducing the amount of extraneous information in an image is called differencing. The idea is that unrelated data may be easily converted by an invertible transform into a form that can be more efficiently compressed by an encoding algorithm. Differencing accomplishes this using the fact that adjacent pixels in many continuous-tone images vary only slightly in value. If we replace the value of a pixel with the difference between the pixel and the adjacent pixel, we will reduce the amount of information stored, without losing any data.
With 1-bit monochrome and 8-bit gray-scale images, the pixel values themselves are differenced. RGB pixels must have each of their color channels differenced separately, rather than the absolute value of the RGB pixels' differences (difference red from red, green from green, and blue from blue).
Differencing is usually applied in a horizontal plane across scan lines. In the following code example, the algorithm starts at the last pixel on the first scan line of the bitmap. The difference between the last two pixels in the line is calculated, and the last pixel is set to this value. The algorithm then moves to the next to last pixel and continues up the scan line and down the bitmap until finished, as shown in the following pseudo-code:
/* Horizontally difference a bitmap */
for (Line = 0; Line < NumberOfLines; Line++)
for (Pixel = NumberOfPixelsPerLine - 1; Pixel >= 1; Pixel--)
Bitmap[Line][Pixel] -= Bitmap[Line][Pixel-1];
Vertical and 2D differencing may also be accomplished in the same way. The type of differencing used will have varied effectiveness depending upon the content of the image. And, regardless of the method used, differenced images compress much more efficiently using LZW.
Several variations of the LZW algorithm increase its efficiency in some applications. One common variation uses index pointers that vary in length, usually starting at 9 bits and growing upward to 12 or 13 bits. When an index pointer of a particular length has been used up, another bit is tacked on to increase precision.
Another popular variation in LZW compressors involves constantly monitoring the compression process for any drop in efficiency. If a drop is noted, the least recently used (LRU) phrases in the dictionary are discarded to make room for new phrases, or the entire dictionary is discarded and rebuilt.
The LZMW variant on the LZW compression method builds phrases by concatenating two phrases together, rather than by concatenating the current phrase and the next character of data. This causes a quicker buildup of longer strings at the cost of a more complex data dictionary.
LZW is a simple algorithm that is difficult to implement efficiently. Deciding when to discard phrases from the dictionary and even how to search the data dictionary during encoding (using a hashing or tree-based scheme) is necessary to improve efficiency and speed.
Variations on the standard LZW algorithm are more common than a programmer may realize. For example, the TIFF and GIF formats use the standard features of the LZW algorithm, such as a Clear code (the indication to discard the string table), EOF code (end of file), and a 12-bit limit on encoded symbol width. However, GIF treats each pixel value as a separate input symbol. Therefore, the size of the input alphabet, the starting compressed-symbol width, and the values of the Clear and EOF codes will vary depending on the pixel depth of the image being compressed.
GIF also stores compressed codes with the least significant bit first, regardless of the native bit order of the machine on which the algorithm is implemented. When two codes appear in the same byte, the first code is in the lower bits. When a code crosses a byte boundary, its least significant bits appear in the earlier bytes.
TIFF's LZW variation always reads 8-bit input symbols from the uncompressed data regardless of the pixel depth. Each symbol may therefore contain one pixel, more than one pixel, or only part of a pixel, depending upon the depth of the pixels in the image. TIFF always stores compressed codes with the most significant bit first, the opposite of GIF. (Don't confuse the byte-order indicator in the TIFF header, or the value of the FillOrder tag, with the bit order of the LZW compressed data. In a TIFF file, LZW-compressed data is always stored most significant bit first.)
TIFF LZW also contains a bit of a kludge. Compressed code widths are required to be incremented one code sooner than is really necessary. For example, the compressor changes from 9-bit to 10-bit codes after adding code 511 to its table rather than waiting until code 512 is added, thus wasting one bit.
We understand that the explanation for this practice is that the LZW implementation supplied by Aldus in Revision 5.0 of the TIFF Developer's Toolkit contained this bug, although the TIFF 5.0 specification itself specified the LZW algorithm correctly. By the time the problem was identified (by Sam Leffler, the head of the TIFF Advisory Committee), too many applications existed that used the erroneous implementation, and there was no way to identify incorrectly encoded LZW data. The solution was simply to change the TIFF specification to require this "variation" in the TIFF algorithm, rather than to change the code, break all existing TIFF LZW applications, and regard all previously created TIFF 5.0 LZW images as incorrect and useless.
On December 22, 1994, CompuServe Information Service announced that it had entered into a license agreement with Unisys Corporation for the use of the LZW compression/decompression method in CompuServe's GIF file format.
NOTE:This section attempts to provide information that will help you understand the legalities you may face when using the LZW compresion/decompression algorithms. We've used the most accurate information available to us as we went to press. However, we are not lawyers, nor are we employees of Unisys. Therefore, this text should not in any way be considered as a publication of Unisys Corporation, or as being approved by Unisys, or in any way obligating Unisys to enter into a license agreement based upon the terms, interpretations, and/or answers to questions provided in this text. Note that Unisys advises that Unisys licensing policies have been revised to reflect changes in the use of LZW and the needs of its existing and future licensees.
CompuServe also announced that all developers creating or modifying hardware or software technology that accessed the CompuServe Information Service and that used GIF should obtain a licensing agreement directly from CompuServe and pay a royalty on each copy of their product sold. CompuServe's agreement covered only the use of GIF on CompuServe; since Unisys owned the LZW patent, Unisys claimed that any software that used GIF was subject to licensing.
The graphics and online community reacted with anger and panic. They had been misled by CompuServe to assume that the GIF file format had been freely available for unrestricted use since its invention in 1987. By 1994, GIF had risen to replace PCX as the most used file format for 8-bit color graphics. All graphics editing and display packages, including online browsers, supported the GIF format. And now, it seemed that the GIF format was not in the public domain. What was going on?
CompuServe explained that they had been approached by Unisys Corporation, which owned the patent on the LZW compression/decompression algorithm. Apparently, CompuServe had not done its homework when it included the patented LZW algorithms in the GIF file format. The result was that CompuServe had to take a license from Unisys for the use of LZW in GIF. CompuServe decided to extend a licensing requirement to everyone who was developing any GIF-using products that interfaced to CompuServe's networks. All money collected by CompuServe would essentially go to pay CompuServe's own licensing agreement with Unisys. It looked as if CompuServe was asking GIF software developers to pay for the Unisys license that CompuServe had to take because of its failure to check out whether GIF was free of patent liability.
Some people were suspicious about the timing of the CompuServe announcement. It had been known for many years in the programming community that GIF used LZW and that LZW was patented by Unisys. Yet CompuServe continued to promote the use of GIF. Unisys claimed that the company had only recently discovered that GIF used LZW. It was also a fact that the World Wide Web industry was exploding and that GIF was an integral interchange medium for transferring low-resolution graphics across the Internet.
After the smoke cleared, Unisys' LZW patent and licensing agreements held fast. Unisys softened the burden on GIF software developers by substantially reducing the license fees it had charged prior to 1995, thus offering very reasonable license fees. In addition, Unisys announced that it would not seek license fees for inadvertent infringement by GIF software products delivered prior to 1995. (However, license fees are required for updates delivered after 1995.)
People realized, upon closer examination, that it is not illegal to own, transmit, or receive GIF files (provided that no unlicensed compression and/or decompression of the files occurs). It was, in fact, the implementation of the LZW algorithm that was under licensing restriction. However, because every GIF file contains LZW-encoded data, this didn't make people feel much better. Many developers swore off using GIF, while still others started grass-roots projects aimed at developing a file format to one day replace GIF. However, wide GIF usage remains and is not likely to go away any time soon, if ever.
To better understand what the Unisys LZW licensing agreement may mean to you, let's first go back a little further in history.
Since 1990 hundreds of companies have entered into LZW licensing agreements with Unisys.
Many books on data compression contain information on the LZ and LZW compression algorithms. The first reference below is the definitive source for a very general explanation about the LZW algorithm itself and does not focus specifically on bitmap image data:
Welch, T. A., "A Technique for High Performance Data Compression," IEEE Computer, vol. 17, no. 6, June 1984.
The TIFF specification (both revisions 5.0 and 6.0) contains an explanation of the TIFF variation on LZW compression. Refer to the "For Further Information" section of the TIFF article for information and see the CD-ROM for the specification itself.
The following articles and manuscripts are also specifically related to LZW:
Bell, Timothy C., "Better OPM/L Text Compression," IEEE Transactions on Communications, vol. 34, no. 12, December 1986, 1176-1182.
Bernstein, Daniel J., Y coding, Draft 4b, March 19, 1991, manuscript part of the Yabba Y Coding package.
Blackstock, Steve, LZW and GIF Explained, manuscript in the public domain, 1987.
Montgomery, Bob, LZW Compression Used to Encode/Decode a GIF File, manuscript in the public domain, 1988.
Nelson, Mark R., "LZW Data Compression," Dr. Dobbs Journal, October 1989, pp. 29-36.
Phillips, Dwayne, "LZW Data Compression," The Computer Applications Journal, Circuit Cellar Ink, vol. 27, June/July 1992, pp. 36-48.
Rodriguez, Karen, "Graphics file format patent Unisys seeks royalties from GIF developers," InfoWorld, vol. 17, January 9, 1995, p. 3.
Thomborson, Clark, "The V.42bis standard for data-compressing modems," IEEE Micro, October 1992, pp. 41-53.
Ziv, J., and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, vol. 23, no. 3, 1977, pp. 337-343.
Ziv, J., and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Transactions on Information Theory, vol. 24, no. 5, September 1978.
You can get additional information about LZW, and find out about licensing of LZW, by contacting Unisys:
Welch Patent Licensing Department
Unisys Corporation
Mail Stop C1SW19
P.O. Box 500
Blue Bell, PA 19424 USA
FAX: 215-986-3090
Email: lzw_info@unisys.com
General licensing information may also be obtained from the homepage of the Unisys Web server:
http://www.unisys.com
In particular, see:
http://www.unisys.com/LeadStory/lzwterms.htm
http://www.unisys.com/LeadStory/lzwfaq.htm
The comp.graphics.misc and comp.compression USENET newsgroups contain frequent discussions of LZW technical issues and some discussions of the patent issues. The official newsgroup where much discussion takes place is alt.gif-agreement. You might also find information on the misc.legal.computing, misc.int-property, and comp.patents newsgroups.
Be sure to check out the compression and graphics file formats FAQs as well. Both contain a substantial amount of information about LZW and the patent issues.
You can get a copy of the actual LZW patent from the U.S. Patent Office. The patent is also available at many Internet sites, including:
ftp://cs.columbia.edu/archives/mirror2/world-info/obi/USPatents/lzw-patent.gz
ftp://ftp.std.com/obi/USPatents/lzw-patent.Z
ftp://ftp.uu.net/doc/literary/obi/USPatents/lzw-patent.Z
ftp://gatekeeper.dec.com/.8/misc/lzw-patent.Z
Copyright © 1996, 1994 O'Reilly & Associates, Inc. All Rights Reserved.
