History of the Portable Network Graphics (PNG) Format
The story of PNG actually begins way back in 1977 and 1978 when two Israeli researchers, Jacob Ziv and Abraham Lempel, first published a pair of papers on a new class of lossless data compression algorithms, now collectively referred to as “LZ77” and “LZ78.” Some years later, in 1983, Terry Welch of Sperry (which later merged with Burroughs to form Unisys) developed a very fast variant of LZ78 called LZW. Welch also filed for a patent on LZW, as did two IBM researchers, Victor Miller and Mark Wegman. The result was—you guessed it—the USPTO granted both patents (in December 1985 and March 1989, respectively).
Meanwhile CompuServe—specifically, Bob Berry—was busily designing a new, portable, compressed image format in 1987. Its name was GIF, for “Graphics Interchange Format,” and Berry, et al., blithely settled on LZW as the compression method. Tim Oren, Vice President of Future Technology at CompuServe (now with Electric Communities), wrote: “The LZW algorithm was incorporated from an open publication, and without knowledge that Unisys was pursuing a patent. The patent was brought to our attention, much to our displeasure, after the GIF spec had been published and passed into wide use.” There are claims (Reference 1) that Unisys was made aware of this as early as 1989 and chose to ignore the use in “pure software;” the documents to substantiate this claim have apparently been lost. In any case, for years Unisys limited itself to the pursuit of hardware vendors—particularly modem manufacturers implementing V.42bis in silicon.
All of that changed at the end of 1994. Whether due to ongoing financial difficulties or as part of the industry-wide bonk on the head provided by the World Wide Web, in 1993 Unisys began aggressively pursuing commercial vendors of software-only LZW implementations. CompuServe seems to have been its primary target at first, culminating in an agreement—quietly announced on 28 December 1994, right in the middle of the Christmas holidays—to begin collecting royalties from authors of GIF-supporting software. The news hit the Internet the following week; what was then the comp.graphics newsgroup went nuts, to use a technical term. As is the way of Usenet, much ire was directed at CompuServe for making the announcement, and then at Unisys once the details became a little clearer. Mixed in with the noise was the genesis of an informal Internet working group led by Thomas Boutell (Reference 2). Its purpose was not only to design a replacement for the GIF format, but a successor to it: better, smaller, more extensible and free.
The very first PNG draft—then called “PBF,” for Portable Bitmap Format—was posted by Tom to comp.graphics, comp.compression and comp.infosystems.www.providers on Wednesday, 4 January 1995. It had a three-byte signature, chunk numbers rather than chunk names, 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, if not yet accepted: delta-filtering for improved compression (Scott Elliott); deflate compression (Tom Lane, the Info-ZIP gang and many others); 24-bit support (many folks); the PNG name itself (Oliver Fromme); internal CRCs (myself); gamma chunk (Paul Haeberli); and 48- and 64-bit support (Jonathan Shekter). The first proto-PNG mailing list was also set up that week; Tom released the second draft of the specification; and I posted some test results that showed a 10% improvement in compression, if GIF's LZW method was simply replaced with the deflate (LZ77) algorithm. Sidebar 1 is a time-line listing many of the major events in PNG's history.
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 zip files; thumbnail images and/or generic multi-image support; little-endian byte order; Unicode UTF-8 character set for text; YUV and other lossy, i.e., non-lossless, image-encoding schemes; and so forth. Many of these topics produced an amazing amount of discussion—in fact, the main proponent of the zip-file idea is still making noise two years later.
One of the real strengths of the PNG group was its ability to weigh the pros and cons of various issues in a rational manner (well, most of the time, anyway), 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. All of the PNG authors were male—a fact that is still true. (I'm sure there's a dissertation in there somewhere.) But equally important was Tom Boutell, who, as the initiating force behind the PNG project, held the role of benevolent dictator—much the way Linus Torvalds does with Linux kernel development. 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. 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, etc. CompuServe was impressed enough by the design that on the 7th of February they announced support for PNG as the designated successor to GIF, thereby supplanting what had initially been referred to as the GIF24 development project (Reference 3). 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 (Reference 4).
- March 2015 Issue of Linux Journal: System Administration
- High-Availability Storage with HA-LVM
- DNSMasq, the Pint-Sized Super Dæmon!
- Localhost DNS Cache
- Real-Time Rogue Wireless Access Point Detection with the Raspberry Pi
- Days Between Dates: the Counting
- You're the Boss with UBOS
- The Usability of GNOME
- Multitenant Sites
- Linux for Astronomers