More...
More...
|
History of the Portable Network Graphics (PNG) format
by Greg Roelofs
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:
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
| [1] |
Raymond Gardner, [email protected], 8 Jan 1995 23:11:58 GMT,
comp.graphics/comp.compression, Message-ID <[email protected]>.
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/pub/WWW/Graphics/PNG/CS-950214.html |
| [4] | http://www.rpi.edu/~randeg/paleo_pngs.html |
| [5] | http://quest.jpl.nasa.gov/zlib/ |
| [6] | ftp://swrinde.nde.swri.edu/pub/png/src/ |
| [7] | http://quest.jpl.nasa.gov/PNG/ (but probably moved to http://www.wco.com/~png/ by 1 January 1997) |
| [8] | http://vag.vrml.org/VRML2.0/FINAL/spec/part1/conformance.html |
| [9] | http://www.w3.org/pub/WWW/TR/REC-png.html |
| [10] | http://quest.jpl.nasa.gov/PNG/pngapps.html |
| [11] | http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html |
|
|
| © 1996 by Michael J. Hammel |