Image Ownership -- Jamie Alexander <jamie_alexander@ccmgate.ihsenv.com> asked me why I didn't mention compression algorithm patent and licensing issues in the graphic file formats article in NetBITS-007. I didn't because in this case intellectual property ownership doesn't result in costs to those who create and view images. The costs come when you buy (or develop) software that reads or writes formats which have licensing deals behind them.

To clarify, GIF (and the popular prepress format TIFF, which has no bearing on the Internet) uses the LZW, or Lempel-Ziv-Welch, compression algorithm; Unisys owns the underlying patents for implementations of LZW compression. This algorithm involves finding patterns (called phrases) throughout a file and replacing them with tokens that correspond to the patterns as entries in a table. For example, if you had a text file with the word "hellzapoppin" in it 50 times, the word might be replaced with a one-byte value of 137. In the phrase table, an entry matches the value 137 with "hellzapoppin."

All the major image editing developers, like Adobe, Corel, Macromedia, and others, pay licensing fees to Unisys to use LZW with TIFF, GIF, and other formats; Adobe also uses LZW in PostScript. This issue rose to consciousness because even though Unisys had patented LZW in the late 1980s, they didn't bother to discover its use in the GIF format until several years after it was in wide use. (They had already made deals to license it for other file formats, like TIFF.)

PNG uses the zlib library, which is based on very similar ideas - using variations on an older set of Lempel-Ziv algorithms - but is implemented in such a way as to avoid licensing fees or patent violation. Zlib is the basis of the Unix gzip compression program, and it's available as a choice (ZIP) in Adobe Acrobat Distiller for compressing black-and-white bitmaps.

JPEG uses Discrete Cosine Transformation (DCT) and Huffman Encoding as two of the five steps it goes through to compress image data, and as far as my reading and understanding goes, these two algorithms aren't patented.

The bottom line: any commercial software you buy has to license LZW anyway, in order to deal with multiple file formats besides GIF. The author of every shareware package you use that displays or creates GIFs pays a minimal licensing fee. Although some people have advocated abandoning GIF because Unisys charges fees for a previously "free" format, don't avoid GIF just because someone owns part of its soul. Information may want to be free, and you can help contribute to that cause; but as an author I know that creativity must be rewarded even if a corporation is the one that ultimately cashes that check. [GF]

<http://www.unisys.com/LeadStory/lzwfaq.html>