Tuesday, June 15, 2010

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 and Mark Adler); 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, Mark Adler)
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)
15 Jan 97 PNG spec 1.0 released as Informational RFC 2083 (IETF)

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 (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 zipfile idea is still making noise two years later.

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. (It was finally released by the IETF as RFC 2083 [8] in mid-January 1997, a full six months later...) 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. [9] Meanwhile the W3C promoted the spec to Proposed Recommendation status in July and then to full Recommendation status on the first of October. [10] 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 [11] 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)
* VRwave (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)

Discerning readers will note the conspicuous absence of Netscape Navigator. Despite the fact that Netscape was aware of the PNG project from the beginning and unofficially indicated ``probable support''; despite the nice benefits gamma correction, alpha support and 2D interlacing bring to WWW applications; despite the fact that the WWW Consortium, of which Netscape is a member, released the PNG spec as its first official Recommendation; despite the requirement to support PNG in VRML 2.0 viewers like Netscape's own Live3D plug-in; and despite considerable pestering by members of the PNG group and the Internet community at large, Netscape is still only ``considering'' future support of PNG. 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 buds 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 about that). 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 app 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 those only if the user has installed a working PNG plug-in).

But support by five or six other Linux web browsers ain't bad, and even mainstream applications like Adobe's Photoshop now do PNG natively. More are showing up every week, too. Life is good.

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-January 1997), the MNG specification has undergone some 31 drafts--almost entirely written by Glenn Randers-Pehrson--and seems fairly 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.

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. [12] 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 all came to an end as of the new year; oddly enough, JPL decided that none of it is particularly relevant to planetary research and exploration. Go figure.)

References

1. Raymond Gardner, rgardner@teal.csn.org, 8 Jan 1995 23:11:58 GMT, comp.graphics / comp.compression, Message-ID <3eprfu$jqs@news-2.csn.net>. See also Michael Battilana's article discussing the legal history of the GIF/LZW controversy: http://www.cloanto.com/users/mcb/19950127giflzw.html
2. http://www.boutell.com/boutell/
3. http://www.w3.org/Graphics/PNG/CS-950214.html
4. http://www.rpi.edu/~randeg/paleo_pngs.html
5. http://www.zlib.net/
6. ftp://ftp.simplesystems.org/pub/libpng/png/src/
7. http://www.libpng.org/pub/png/
8. ftp://ftp.isi.edu/in-notes/rfc2083.txt
9. http://www.vrml.org/Specifications/VRML97/part1/conformance.html
10. http://www.w3.org/TR/png.html
11. http://www.libpng.org/pub/png/pngapps.html
12. http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html

For Website Designing and Development
web site designers Hyderabad
eMail : varadesigns@yahoo.com
phone : +91 9247457705

Source : http://www.libpng.org/pub/png/pnghist.html