|
|
|
|
|
|
|
|
PNG is a new, awesome graphics format designed to take the place of GIF--here's how it came about.
by Greg Roelofs
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).
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. Then any line filtering must be inverted to get the actual image data. Oops, it's an interlaced image: 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. At this point 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.
However, it's not just simple transparency; we have an alpha channel. And we don't want a sparse display--we like the replicating progressive method that 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, color-mapped display, and most programmers' heads will explode.
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 (Reference 5), and Guy Eric Schalnat of Group 42, who almost single-handedly wrote the libpng reference implementation (originally ``pnglib'') from scratch ([Reference 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.
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. A press release, 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 (Reference 7), and 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, six 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 (Reference 8). Meanwhile the W3C promoted the spec to Proposed Recommendation status in July and then to full Recommendation status on the first of October (Reference 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.
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 (Reference 10) with PNG support either current or planned (mostly current). Among the ones available for Linux are:
Discerning readers will note the conspicuous absence of Netscape Navigator. Netscape is still only ``considering'' future support of PNG despite the following facts:
Until Netscape either supports PNG natively or gets swept away by Microsoft or someone else, PNG's usefulness as an image format for the Web is considerably diminished.
On the other hand, our friends at Microsoft recognized the benefits of PNG and apparently embraced it wholeheartedly. They have not only made it the native image format of the Office97 application suite but have also repeatedly promised to put it into Internet Explorer. (Theoretically by the time of the 4.0 betas--we'll see if that happens.) Assuming they do, Netscape is almost certain to follow suit. (See? Microsoft is good for something!) At that point PNG should enjoy a real burst of WWW interest and usage.
In the meantime, PNG viewing actually is possible with Linux Netscape; it's just not very useful. Rasca Gmelch is working on a Unix plug-in with (among other things) PNG support. Although it's still an alpha version and requires ImageMagick's convert utility to function, that's not the problem, Netscape's brain-damaged plug-in architecture is. Plug-ins have no effect on HTML's IMG tag: if there's no native support for the image format and no helper application defined, the image is ignored regardless of whether an installed plug-in supports it. Instead you must use Netscape's EMBED extension. That means anyone who wants universally viewable web pages loses either way: PNG with IMG doesn't work under Netscape, and PNG with EMBED doesn't work under much of anything except Netscape and MSIE, and then only if the user has installed a working PNG plug-in.
However, support by five or six other Linux web browsers isn't bad, and even mainstream applications like Adobe's Photoshop now do PNG natively. More are showing up every week. Life is good.
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, 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-January 1997), the MNG specification has undergone some 31 drafts--almost entirely written by Glenn Randers-Pehrson--and is close to being frozen, although there has been a recent burst of new activity. 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.
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.
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 (Reference 11). Thanks also to Mark Adler and the Jet Propulsion Lab (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 all came 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.
Greg Roelofs escaped from the University of Chicago with a degree in astrophysics and fled screaming to Silicon Valley, where he now does outrageously cool graphics, 3D and compression stuff for Philips Research. He is a member of Info-ZIP and the PNG group, and he not only maintains web pages for both of those but also for himself and for the Cutest Baby in the Known Universe. He can be reached by e-mail at newt@pobox.com or on the Web at http://pobox.com/~newt/. The Cutest Baby in the Known Universe can be seen at http://pobox.com/~newt/greg_lyra.html. The Info-ZIP home page moved to http://www.cdrom.com/pub/infozip/ at the beginning of the year, and the PNG home page moved to http://www.wco.com/~png/, as noted above.