More...

History of the Portable Network Graphics (PNG) format

Prehistory
      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 [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, Unisys for years limited itself to 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, Unisys in 1993 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 spit hit the fan on 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; but mixed in with the noise was the genesis of an informal Internet working group led by Thomas Boutell [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 Early Days (All Seven of 'Em)
      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. Figure 1 is a timeline listing many of the major events in PNG's history.

4	Jan 95	PBF draft 1 (Thomas Boutell)
4	Jan 95	delta-filtering (Scott Elliott)
4	Jan 95	deflate compression (Tom Lane et al.)
4	Jan 95	24-bit support (many)
5	Jan 95	TeleGrafix LZHUF proposal (same or slightly larger)
6	Jan 95	PNG name (Oliver Fromme)
7	Jan 95	PBF draft 2 (Thomas Boutell)
7	Jan 95	ZIF early results (Greg Roelofs)
7	Jan 95	internal CRC(s) (Greg Roelofs)
8	Jan 95	gamma chunk (Paul Haeberli)
8	Jan 95	48-, 64-bit support (Jonathan Shekter)
9	Jan 95	FGF proposal, implementation (Jeremy Wohl)
10	Jan 95	first NGF/PBF/proto-PNG mailing list (Jeremy Wohl)
15	Jan 95	PBF draft 3 (Thomas Boutell)
16	Jan 95	CompuServe announces GIF24 development (Tim Oren)
16	Jan 95	spec available on WWW (Thomas Boutell)
16	Jan 95	PBF draft 4 (Thomas Boutell)
23	Jan 95	PNG draft 5 (Thomas Boutell)
24	Jan 95	PNG draft 6 (Thomas Boutell)
26	Jan 95	final 8-byte signature (Tom Lane)
1	Feb 95	PNG draft 7 (Thomas Boutell)
2	Feb 95	Adam7 interlacing scheme (Adam Costello)
7	Feb 95	CompuServe announces PNG == GIF24 (Tim Oren)
13	Feb 95	PNG draft 8 (Thomas Boutell)
7	Mar 95	PNG draft 9 (Thomas Boutell)
11	Mar 95	first working PNG viewer (Oliver Fromme)
13	Mar 95	first valid PNG images posted (Glenn Randers-Pehrson)
1	May 95	pnglib 0.6 released (Guy Eric Schalnat)
1	May 95	zlib 0.9 released (Jean-loup Gailly, Mark Adler)
5	May 95	PNG draft 10 (Thomas Boutell)
13	Jun 95	PNG home page (Greg Roelofs)
8	Dec 95	PNG spec 0.92 released as W3C Working Draft
23	Feb 96	PNG spec 0.95 released as IETF Internet Draft
28	Mar 96	deflate and zlib approved as Informational RFCs (IESG)
22	May 96	deflate and zlib released as Informational RFCs (IETF)
1	Jul 96	PNG spec 1.0 released as W3C Proposed Recommendation
11	Jul 96	PNG spec 1.0 approved as Informational RFC (IESG)
4	Aug 96	VRML 2.0 spec released with PNG as requirement (VAG)
1	Oct 96	PNG spec 1.0 approved as W3C Recommendation
14	Oct 96	image/png approved (IANA)
Figure 1: a PNG timeline

Onward, Frigidity
      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. Most of them still are. 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 only happened 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, supplanting what they had initially referred to as the GIF24 development project. [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. [4]

Oy, My Head Hurts
      But specifying a format is one thing; implementing it is quite another. Although the original intent was to create a "lightweight" format--and, compared to TIFF or even JPEG, PNG is fairly lightweight--even a completely orthogonal feature set can introduce substantial complications. For example, consider progressive display of an image in a web browser. First comes straight decoding of the compressed data; no problems there. Then any line-filtering must be inverted to get the actual image data. Oops, it's an interlaced image: now pixels are appearing here and there within each 8x8 block, so they must be rendered appropriately (and possibly buffered). The image also has transparency and is being overlaid on a background image, adding a bit more complexity. So far we're not much worse off than we would be with an interlaced, transparent GIF; the line filters and 2D interlacing scheme are pretty straightforward extensions to what programmers have already dealt with. Even adding gamma correction to the foreground image isn't too much trouble.
      But wait, it's not just simple transparency; we have an alpha channel! And we don't want sparse display--we really like the replicating progressive method Netscape Navigator uses. Now things are tricky: each replicated pixel-block has some percentage of the fat foreground pixel mixed in with complementary amounts of the background pixels in the block. And just because the current fat pixel is 65% transparent (or, even worse, completely opaque) doesn't mean later ones in the same block will be, too: thus we have to remember all of the original background pixel-values until their final foreground pixels are composited and overlaid. Toss in the ability to render all of this nicely on an 8-bit, colormapped display, and most programmers' heads will explode.

Make It So!
      Of course, some of these things are application (presentation or front-end) issues, not general PNG-decoding (back-end) issues. Nevertheless, a good PNG library should allow for the possibility of such applications--which is another way of saying that it should be general enough not to place undue restrictions on any programmer who wants to implement such things.
      Once Draft 9 was released, many people set about writing PNG encoders and/or decoders. The true glory is really reserved for three people, however: Info-ZIP's Jean-loup Gailly and Mark Adler (both also of gzip fame), who originally wrote Zip's deflate() and UnZip's inflate() routines and then, for PNG, rewrote them as a portable library called zlib [5]; and Guy Eric Schalnat of Group 42, who almost single-handedly wrote the libpng reference implementation (originally ``pnglib'') from scratch. [6] The first truly usable versions of the libraries were released two months after Draft 9, on the first of May, 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 resulting from these first implementations.)

Fast-Forward to the Present
      The pace of subsequent developments slowed at that point. This was partly due to the fact that, after four months of intense development and dozens of e-mail messages every day, everyone was burned out; partly because Guy controlled libpng's development and became busy with other things at work; and partly because of the perception that PNG was basically ``done.'' The latter point was emphasized by a CompuServe press release to that effect in mid-June (and one, I might add, in which their PR guys claimed much of the credit for PNG's development, sigh).
      Nevertheless, progress continued. In June of 1995 I set up the PNG home page, now grown to roughly a dozen pages [7]; Kevin Mitchell officially registered the ``PNGf'' Macintosh file ID with Apple Computer. In August Alexander Lehmann and Willem van Schaik released a fine pair of additions to the NetPBM image-manipulation suite, particularly handy under Linux: 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.
      1996 saw the February 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. (However, the IETF secretary still hasn't issued the actual RFC number at the time of this writing, five months later. Sigh.) The Virtual Reality Modeling Language (VRML) Architecture Group in early August adopted PNG as one of the two required image formats for minimal VRML 2.0 conformance. [8] Meanwhile the W3C promoted the spec to Proposed Recommendation status in July and then to full Recommendation status on the first of October. [9] Finally, in mid-October 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.

Current Status
      So where are we today? The future is definitely bright for PNG, and the present isn't looking too bad, either. I now have over 125 applications listed [10] with PNG support either current or planned (mostly current); among the ones available for Linux are:

• XV (image viewer/converter)
• ImageMagick (image viewer/converter)
• GRAV (image viewer)
• Zgv (image viewer)
• xli (image viewer)
• XPaint (image editor)
• The GIMP (image editor)
• Image Alchemy (image converter)
• pnmtopng/pngtopnm (image converters)
• XEmacs (editor/web browser/operating system/etc.)
• gforge (fractal terrain generator)
• Fractint (fractal generator)
• Ghostscript (PostScript viewer/converter)
• GNUplot (plotting program)
• PV-WAVE (scientific visualization program)
• POV-Ray (ray-tracer)
• VRweb (VRML browser)
• X Mosaic (web browser)
• Arena (web browser)
• Chimera (web browser)
• Grail (web browser)
• Amaya (web browser/editor)
• Mapedit (image-map editor)
• WWWis (HTML IMG sizer)
• file(1) (Unix file-type identifier)

The Future
      As VRML takes off--which it almost certainly will, especially with the advent of truly cheap, high-performance 3D accelerators--PNG will go along for the ride. (JPEG, which is the other required VRML 2.0 image format, doesn't support transparency.) Graphic artists will use PNG as an intermediate format because of its lossless 24-bit (and up) compression and as a final format because of its ability to store gamma and chromaticity information for platform-independence. Once the ``big-name'' browsers support PNG natively, users will adopt it as well--for the 2D interlacing method, the cross-platform gamma correction, and the ability to make anti-aliased balls, buttons, text and other graphic elements that look good on *any* color background (no more ``ghosting,'' thanks to the alpha-channel support).
      Indeed, the only open issue is support for animations and other multi-image applications. In retrospect, the principal failure of the PNG group was its delay in extending PNG to MNG, the "Multi-image Network Graphics" format. As noted earlier, everyone was pretty burned out by May 1995; in fact, it was a full year before serious discussion of MNG resumed. As (bad) luck would have it, October 1995 is when the first Netscape 2.0 betas arrived with animation support, giving the (dying?) GIF format a huge resurgence in popularity.
      At the time of this writing (mid-December 1996), the MNG specification has undergone some 27 drafts--almost entirely written by Glenn Randers-Pehrson--and is close to being frozen. A couple of special-purpose MNG implementations have been written, as well. But MNG is too late for the VRML 2.0 spec, and despite some very compelling features, it may never be perceived as anything more than PNG's response to GIF animations. Time will tell.

At Last...
      It's always difficult for an insider to render judgment on a project like PNG; that old forest-versus-trees thing tends to get in the way of objectivity. But it seems to me that the PNG story, like that of Linux, represents the best of the Internet: international cooperation, rapid development and the production of a Good Thing that is not only useful but also freely available for everyone to enjoy.
      Then again, maybe I'm just a shameless egotist (nyuk nyuk nyuk). You decide....

Acknowledgments
      I'd like to thank Jean-loup Gailly for his excellent comp.compression FAQ, which was the source for much of the patent information given above. [11] Thanks also to Mark Adler and JPL, who have been the fine and generous hosts for the PNG home pages, zlib home pages, Info-ZIP home pages and my own, personal home pages. (Through no fault of Mark's, that will all come to an end as of the new year; oddly enough, JPL has decided that none of it is particularly relevant to planetary research. Go figure.)

References