The manipulation of digital images is becoming more and more commonplace in todayŐs business environment. Scanners, desk-top publishing and web browsers involve the creation, manipulation storage, and transmission of large amounts of information.

In order to make these tasks more manageable, data compression is used to reduce the amount of information that must be handled in some of these processes. One particular method of data compression became quite popular, until users were hit by the torpedo of a "submarine patent." The story is informative as an example of what can happen if you are not aware of a relevant patent when you are developing software. It is also informative as to how bad feelings may result in a backlash due to poor handling of discovered infringements.

In 1984, Terry Welch published a paper presenting a compression algorithm known as LZW (named for Lempel-Ziv-Welch, the three people who developed and expanded aspects of the data compression algorithm described in the paper). There was no mention in the paper of a patent in the algorithm owned by (what is now) Unisys Corporation. (A copy of the patent can be found on the Internet at http://www.clark.net/pub/muddy/GIF_Patent/.) The data compression algorithm proved so useful that CompuServe employed it in its Graphic Interchange Format (GIF) design. It has also been used in other graphic formats, such as TIFF (Tagged Interchange File Format) which many scanners use to compress scanned images. Certain PostScript applications, which are used in printers and portable document creation software, among other uses, also use the LZW data compression algorithm. The algorithm is even used in some data transmission protocols utilized to speed up modem traffic. While other methods of compressing data are available, LZW has been one of the most widely used and accepted-- for instance, a majority of graphics on the World Wide Web are GIFs whose creation and display invoke the LZW patent.

CompuServe released the GIF standard as a "free and open" specification in 1987. As the GIF standard was promoted, most developers did not know that the GIF specification contained the LZW algorithm, or even if the developers did know about the algorithm, they did not know that it was patented. Unisys was also unaware of the GIF standard and that it contained the patented LZW algorithm.

When software developers began to become aware of the patent issue (including at least one GIF software developer in 1990-91), and tried to contact Unisys for a license, the developers had to convince Unisys that it owned the patent and should be providing licenses.

In 1992, it appears that Unisys became aware of use of the LZW patent in the CompuServe GIF specification, at which point Unisys contacted CompuServe. Unfortunately, discussions then continued quietly between the parties without anyone informing software developers-- who continued to build GIF support into their programs, unaware that there was an unresolved patent issue.

In December of 1994, Unisys announced that it intended to pursue licensing arrangements with GIF developers. To put this into perspective, this was a time when the Internet and on-line services were starting to explode in popularity-- in large part because of the ability to display graphical information. NCSA Mosaic, the first graphical web browser, was released in 1993. In June of 1993, there were only about 150 web server sites on the Internet. By September of 1995, it is estimated that there were about 8,750,000 web pages available on the Internet.

A web browser can only display certain file formats. Most modern web browsers can display a variety of graphic formats. In initial versions, however, Mosaic only supported GIF as an image format; thus, there was a tremendous desire to produce software to create, manipulate and display images using the GIF format.

To Unisys' credit, it initially acknowledged some of this development and stated that it did not intend to pursue licenses with software creators who had marketed products prior to 1995, or with developers of GIF-based applications who were distributing their software for free-- only commercial products introduced in 1995 or earlier products that were enhanced in 1995 would require a license.

Unfortunately for Unisys, this announcement came after the rumor mill started about an impending "GIF tax." The outcry was substantial. Some people were even under the impression that there would be a fee charged for distributing GIFs, not just for the creation of encoders and decoders that contained the LZW algorithm. In response, a number of developers, such as CompuServe (see its press release at http://www.w3.org/pub/WWW/Graphics/PNG/CS-950117.html), began work on developing an alternate to the GIF standard.

Even more unfortunate was that Unisys continued to revise its definition of who would require a license to use the LZW algorithm. Alternative means of decompressing GIFs without use of the LZW algorithm were immediately created, but they did not escape the Unisys patent. Support for alternative graphic formats, such as JPEG (Joint Photographic Experts Group) were added to web browsers.

By the end of 1996, CompuServeŐs efforts to produce a new data compression standard had been combined with others to produce the PNG standard (for Portable Network Graphics-- or PNG is Not GIF, if you prefer). The PNG standard was officially announced as a recommended standard by the World Wide Web Consortium in October of 1996. There are now a number of web browsers that support the PNG standard (for a list, see http://www.wco.com/~png/pngapbr.html).

What does this mean for Unisys? There will still be uses for Unisys' LZW patent. GIF will be used for some time to come. Other formats which also use the LZW algorithm, such as PostScript and TIFF, will also be used for some time to come. The GIF standard may have a limited life-span as an Internet graphics format-- better formats have developed, and would have likely developed in time regardless of Unisys' actions. However, Unisys angered many of the people who are potential licensees of its patents. The potential licensees were angry enough that they worked to develop replacement technology for those patents-- as a result of what they considered to be inadequate public notice on the part of the patent holder, as well as inconsistent but worsening statements of the patent holderŐs licensing intentions.

The GIF specification is well enough entrenched that it is not likely to be replaced completely anytime soon, but part of this entrenchment is because the use of the LZW patent in the GIF specification is riding on the crest of the development of the World Wide Web-- the fastest growing medium of communication that has ever been created on this planet. Other patent holders who are not more careful or responsive may not be as lucky as Unisys, and may watch their products be cast aside and their royalties dry up-- which, of course, will be facilitated by the ability of patent licensees to communicate with other licensees over the Internet which the Unisys patent helped encourage along... .

(For more information on the history and controversy, see http://www.xmission.com:80/~mgm/gif/ and http://www.cloanato.com/users/19950127giflzw.html.)