Image compression in Portable Network Graphics (PNG)

The PNG standard is one of the first standards to be collaboratively developed over the Internet. The impetus for it was an announcement in December 1994 by Unisys (which had acquired the patent for LZW from Sperry) and CompuServe that they would start charging royalties to authors of software that included support for GIF. The announcement resulted in an uproar in the segment of the compression community that formed the core of the Usenet group comp.compression. The community decided that a patent-free replacement for GIF should be developed, and within three months PNG was born.

Unlike GIF, the compression algorithm used in PNG is based on LZ77. In particular, it is based on the deflate [59] implementation of LZ77. This implementation allows for match lengths of between 3 and 258. At each step the encoder examines three bytes. If it cannot find a match of at least three bytes it puts out the first byte and examines the next three bytes. So, at each step it either puts out the value of a single byte, or literal, or the pair . The alphabets of the literal and match length are combined to form an alphabet of size 286 (indexed by 0 − −285). The indices 0 − −255 represent literal bytes and the index 256 is an end-of-block symbol. The remaining 29 indices represent codes for ranges of lengths between 3 and 258, as shown in Table 5.17. The table shows the index, the number of selector bits to follow the index, and the lengths represented by the index and selector bits. For example, the index 277 represents the range of lengths from 67 to 82. To specify which of the sixteen values has actually occurred, the code is followed by four selector bits.

T A B L E Codes for representations of match length .  
Index # of selector bits LengthIndex # of selector bits LengthIndex # of selector bitsLength
265111, 12275351–582850258
266113, 14276359–66   
T A B L E Huffman codes for the match length alphabet
Index Ranges# of bitsBinary Codes
0–143800110000 through
144–2559110010000 through
256–27970000000 through
280–287811000000 through
   Arithmetic Coding of Pixel ValuesArithmetic Coding of Pixel Differences

Leave a Comment