Internet GIF tax,
PNG to the rescue!
 Alternatively, ``Unisys bombshell, / Christmas 1994. / PNG to the rescue!''
The Portable Network Graphics image format, or PNG for short, is the first general-purpose image format to achieve wide, cross-platform acceptance since JPEG/JFIF arrived in the early 1990s. Almost every major feature in PNG exists in other general-purpose formats--specifically, GIF, JPEG, and TIFF--yet in January 1995, a group of strangers felt compelled to band together and design another image format from scratch. To understand why, it is necessary to delve even further into history.
 The choice of adjectives is intentional: there are other widely accepted formats, such as Windows BMPs, but they're not cross-platform, and there are cross-platform formats such as PostScript or the astronomical FITS format, but they're not general-purpose.
In 1977 and 1978, Israeli researchers Jacob Ziv and Abraham Lempel published a pair of papers on a new class of lossless data-compression algorithms in the journal IEEE Transactions on Information Theory. These algorithms, now collectively referred to as ``LZ77'' and ``LZ78,'' formed the basis for an entire industry of software, hardware, and subsequent research papers. One of the follow-up papers was by Terry Welch and was published in the June 1984 issue of IEEE Computer. Entitled ``A Technique for High-Performance Data Compression,'' it described his research at Sperry into a fast, efficient implementation of LZ78 called LZW.
By 1987, when CompuServe's Bob Berry was busy designing the GIF image format, LZW was well established in the Unix world in the form of the compress command, and in the PC world in the form of SEA's ARC. As a fast algorithm with good compression and relatively low memory requirements, LZW was ideally suited to the PCs of the day, and it became Berry's choice for a GIF compression method, too. In turn, GIF became the image format of choice on the Internet, particularly on the worldwide discussion forum known as Usenet.
And so things remained largely unchanged until 1994. The introduction (from a practical standpoint) of JPEG around 1992 or 1993 may have slowed GIF's rising star slightly, but computational requirements and the limitations of then-current graphics cards limited JPEG's acceptance for several years. With the advent of graphical browsers for the World Wide Web in 1992 and 1993, GIF's popularity only increased: simple graphics with few colors were the norm, and those were ideally suited to GIF's palette-based format. With the release of Netscape Navigator 1.0 in 1994, progressive rendering of images as they downloaded suddenly became widespread, and GIF's interlacing scheme worked in its favor once more.
 Progressive capability had for quite some time been part of the JPEG specification, too, but since the Independent JPEG Group's free library didn't support the progressive mode until August 1995, neither did any applications--including web browsers.
Then, three days after Christmas 1994, CompuServe quietly dropped a small bombshell on an unsuspecting world: henceforth, all GIF-supporting software would require royalties. In fact, the announcement was apparently the culmination of more than a year of legal wrangling with Unisys, which had inherited the Welch LZW patent in the 1986 merger of Sperry and Burroughs, and which had by 1993 become considerably more aggressive about enforcing its patent in software-only applications.
In any case, shortly after the holidays ended, word of the announcement reached the Internet--specifically, the ever-volatile Usenet community. As one might expect, the results were spectacular: within days, a full-fledged conflagration of bluster, whining, flaming, vitriol, and general-purpose noise had engulfed several of the Usenet newsgroups, among them comp.compression and comp.graphics. But mixed in with the noise was the genesis of an informal Internet working group led by Thomas Boutell. Its purpose was to design not only a replacement for the GIF format, but also a successor to it: better, smaller, more extensible, and free.
What would become known as the ``PNG Group'' or ``PNG Development Group'' began as many such groups do--as a collection of participants in a Usenet newsgroup. When the discussion became both more detailed and considerably more verbose, it became a mailing list with an associated CompuServe forum. Tom Boutell posted the very first PNG draft--then known as ``PBF,'' for Portable Bitmap Format--to comp.graphics, comp.compression, and comp.infosystems.www.providers on Wednesday, 4 January 1995. It had a 3-byte signature, chunk numbers rather than chunk names, a maximum pixel depth of 8 bits, and no specified compression method, but even at that stage it had more in common with today's PNG than with any other existing format.
Within one week, most of the major features of PNG had been proposed, though by no means yet accepted: delta filtering for improved compression (Scott Elliott and Mark Adler), deflate compression (Tom Lane, the Info-ZIP Group and many others), 24-bit support (many folks), the PNG name itself (Oliver Fromme), internal CRCs (Greg Roelofs), gamma chunk (Paul Haeberli), and 48- and 64-bit support (Jonathan Shekter). That week also saw the first proto-PNG mailing list set up, Tom Boutell's release of the second draft of the specification, and Greg's posting of some test results that showed a 10% improvement in compression if GIF's LZW method were simply replaced with the deflate (LZ77) algorithm.
One of the real strengths of the PNG group was its ability to weigh the pros and cons of various issues in a (mostly) rational manner, reach some sort of consensus, and then move on to the next issue without prolonging discussion on ``dead'' topics indefinitely. In part this was probably due to the fact that the group was relatively small, yet possessed of a sufficiently broad range of graphics and compression expertise that no one felt unduly shut out when a decision went against him. In part it was also due to a frequently updated ``scorecard,'' which listed the accepted and rejected features and summarized any issues that were still undecided.
 All of the PNG authors were male. Most of them still are. No doubt there's a dissertation in there somewhere.
But the most important factor in the group's progress was the position of Benevolent Dictator, held by Tom Boutell. As with the very successful Linux development model, in which Linus Torvalds is trusted with the final say on anything having to do with the Linux kernel, so Tom, as the initiating force behind the PNG project, was granted this power. When consensus was impossible, Tom would make a decision, and that would settle the matter. On one or two rare occasions he might later have been persuaded to reverse the decision, but this generally happened only if new information came to light.
In any case, the development model worked: by the beginning of February 1995, seven drafts had been produced, and the PNG format was settling down. (The PNG name was adopted in Draft 5, after a great deal of fuss; GIF's indeterminate pronunciation was the prime motivating factor, but the allure of an unofficial recursive acronym--PNG's Not GIF--was what decided the matter.) The next month was mainly spent working out the details: chunk-naming conventions, CRC size and placement, choice of filter types, palette ordering, specific flavors of transparency and alpha-channel support, interlace method, and so on. CompuServe was impressed enough by the design that on February 7, 1995, they announced support for PNG as the designated successor to GIF, supplanting what they had initially referred to as the GIF24 development project. By the beginning of March, PNG Draft 9 was released and the specification was officially frozen--just over two months from its inception. Although further drafts followed, they merely added clarifications, some recommended behaviors for encoders and decoders, and a tutorial or two. Indeed, Glenn Randers-Pehrson has kept some so-called ``paleo PNGs'' that were created at the time of Draft 9; they are still readable by any PNG decoder today.
Table 7-1 is a time line listing many of the major events in PNG's history.
|Table 7-1. PNG Time Line|
Perhaps equally interesting are some of the proposed features and design suggestions that ultimately were not accepted: the Amiga IFF format; uncompressed bitmaps, either gzip'd or stored inside zipfiles; thumbnail images and/or generic multi-image support; ``little-endian'' byte order; Unicode UTF-8 character set for text; YUV and other lossy (nonlossless) image-encoding schemes; vector graphics; and so forth. Many of these topics produced an amazing amount of discussion--in fact, the main proponent of the zipfile idea was still arguing about it more than two years later.
 The name stems from a reference in Gulliver's Travels to opposing factions of silly people, some of whom (Lilliputians) broke their eggs at the little end before eating them and some of whom (Blefuscudians) broke them at the big end. The argument over PNG's byte order was almost equally silly, but in the end (so to speak) big-endian was chosen for two reasons: it's easier for humans to read and debug in a ``hex dump'' (a textual rendering of a binary file), and it's the same as ``network byte order,'' which is something of an Internet standard.
A frozen spec opens the door to implementations, and many people set about writing PNG encoders and decoders as soon as Draft 9 appeared. The real glory, however, is reserved for the handful of people who took it upon themselves to write the free programming libraries supporting PNG: Jean-loup Gailly and Mark Adler, both of Info-ZIP and gzip fame, who rewrote the deflate compression engine in a form suitable for general-purpose use and released it as zlib; and Guy Eric Schalnat of Group 42, who almost single-handedly wrote the initial version of libpng (then known as pnglib). The first truly usable versions of the libraries were released two months after Draft 9, on May 1, 1995. Although both libraries were missing some features required for full implementation, they were sufficiently complete to be used in various freeware applications. Draft 10 of the specification was released at the same time, with clarifications and corrections resulting from these first implementations.
The pace of development slowed at that point, at least to outward appearances. Partly this was due to the fact that, after four straight months of intense development and many megabytes of email, everyone was exhausted; partly it was due to the fact that Guy controlled the development of libpng, and he became busy with other things at work. Often overlooked is the fact that, while writing the spec was a very focused effort and writing the reference implementation was only slightly less so, once the library had been released in a usable form there were literally hundreds of potential applications pulling at developers' interests. And finally, there was the simple perception that PNG was basically done--a point that was emphasized by a CompuServe press release to that effect in June 1995.
Nevertheless, progress continued. June saw the genesis of the PNG web site, which has now grown to more than two dozen pages, and Kevin Mitchell officially registered the ``PNGf'' Macintosh file ID with Apple Computer. In August 1995, Alexander Lehmann and Willem van Schaik released a fine pair of additions to the NetPBM image-manipulation suite: pnmtopng and pngtopnm version 2.0. And in December, at the Fourth International World Wide Web Conference, the World Wide Web Consortium (W3C) released the PNG Specification version 0.92 as an official standards-track Working Draft.
February 1996 saw the release of version 0.95 as an Internet Draft by the Internet Engineering Task Force (IETF), followed in July by the Internet Engineering Steering Group's (IESG) approval of version 1.0 as an official Informational RFC. (It was finally released by the IETF as RFC 2083 in January 1997.) In early August, the Virtual Reality Modeling Language (VRML) Architecture Group adopted PNG as one of the two required image formats for minimal VRML 2.0 conformance. Meanwhile, the W3C promoted the spec to Proposed Recommendation status in July and then to full Recommendation status on the first of October. Finally, in mid-October 1996, the Internet Assigned Numbers Authority (IANA) formally approved ``image/png'' as an official Internet Media Type, joining image/gif and image/jpeg as non-experimental image formats for the Web. Much of this standardization would not have happened nearly as quickly without the tireless efforts of Tom Lane and Glenn Randers-Pehrson, who took over editing duties of the spec from Thomas Boutell.
Also in 1996 came the revival of efforts to produce a multiple-image variant of PNG suitable for slide shows, animations, and very efficient storage of certain simple kinds of images. Multi-image support had been left out of the PNG specification for several reasons: multi-image capability in GIF was supported by virtually no one; multi-image GIFs were indistinguishable from single-image GIFs (i.e., they had the same filename extension); including multi-image support in PNG would have delayed both its development and its acceptance in the marketplace, due to the burden of extra complexity, and creating a separate, PNG-based multi-image format not only would be a logical extension of PNG but also would be more appropriate to a group with backgrounds in animation and multimedia. As it happened, however, this latter group never materialized, and with the early-1996 release of Netscape Navigator 2.0 with support for GIF animations, it became clear that the PNG Group needed to produce some sort of response.
 Alas, Netscape's support of GIF animations probably did more to ensure the format's longevity than any other event in GIF's history.
Unfortunately there was a fairly fundamental disagreement within the group over whether the new format should be a very thin layer on top of PNG, capable of duplicating GIF animations but not much more, or whether it should be a full-fledged multimedia format capable of synchronizing images, sound, and possibly video. Although the former would have been trivial (and fast) to design and implement, proponents of the latter design held sway during the early discussions in the summer of 1996. In the end, however, something of a compromise was created--though possibly due more to attrition than consensus. Called Multiple-image Network Graphics, the MNG format design was largely shaped by Glenn Randers-Pehrson and included simple but general operations to manipulate sections of images, but no direct sound or video support. As of November 1998 the MNG specification was close to being frozen, but was also quite large and still awaiting implementation in the form of a reference library similar to libpng. Until such time as either a reference library or some other form of complete implementation exists, the MNG spec will not be approved as a standard, nor is it likely that more than a handful of third-party developers will offer support for it.
If 1996 was the year of PNG's standardization, 1997 was the year of PNG applications. After having taken over libpng development from Guy Eric Schalnat in June 1996, Andreas Dilger shepherded it through versions 0.89 to 0.96, adding numerous features and finding and fixing bugs; application developers seemed not to mind the library's ``beta'' version number, and increasingly employed it in their mainstream apps. With native support in popular programs such as Adobe's Photoshop and Illustrator, Macromedia's Freehand, JASC's Paint Shop Pro, Ulead's PhotoImpact, and Microsoft's Office 97 suite, PNG's star was clearly rising. But perhaps the crowning moment came in the autumn, with fresh versions of the Big Two web browsers. Microsoft's Internet Explorer 4.0 in October and Netscape's Navigator 4.04 in November both included native, albeit somewhat limited, PNG support. At last, the widespread use of PNG on the Web came within the realm of possibility.
The theme for 1998 seems to have been maturity. Having been handed the reins of principal libpng development at the beginning of the year, Glenn Randers-Pehrson fixed many bugs, finished the documentation and generally polished libpng into a stable release worthy of a ``1.0'' version number by early March--three years to the day, in fact, after the PNG specification was frozen. In February, the UK Digital Television Group released the MHEG-5 UK Profile for next-generation teletext on digital terrestrial television; the profile included PNG as one of its bitmap formats, and as a result, manufacturers such as Philips, Sony, Pace and Nokia were expected to be shipping digital televisions and set-top boxes with built-in PNG support by the time this book reaches print. At the very end of March 1998, Netscape released Mozilla, the pre-alpha source code to Communicator 5.0, which allowed interested third parties (like the PNG Group) to tinker with the popular browser and make it work as intended. In October, the PNG Group approved some important additions and clarifications to one of the more difficult technical aspects of the PNG spec, namely, gamma and color correction; these changes defined the PNG 1.1 specification--the first official revision in three and a half years. And at roughly the same time, a joint committee of the International Organization for Standardization (ISO) and the International Electrotechnical Commission (IEC) began the yearlong process to make Portable Network Graphics an official international standard (to be known as ISO/IEC 15948 upon approval).
But a history bereft of darker events is perhaps not so interesting...and, sadly enough, for a brief period in April 1998, it appeared that things might once again be percolating on the legal front. Specifically, there were rumors that Stac, Inc., believed the deflate compression engine in zlib (which is used by libpng) infringed on two of their patents. Careful reading of the patents in question, United States patents 4,701,745 and 5,016,009, suggests that although it is possible to write an infringing deflate engine, the one actually used in zlib does not do so. Moreover, as this is written, a full year has passed with no public claims from Stac, no further private contacts, and no confirmation of the original rumors. However, until this is tested in court or Stac makes a public announcement clearing zlib of suspicion, at least a small cloud will remain over the Portable Network Graphics format as a whole. The irony should be evident to one and all.