PNG

The Portable Network Graphics (PNG) file format was designed to improve and replace the commercial GIF format. Therefor unlike GIF, PNG is absolutely free for commercial use and it supports three modes:

• grayscale - the pixels are presented by 16 bit illumination value (0 - black, 2¹⁶-1 - white)
• true color - the pixels are presented by 24 bit RGB value. Each component uses 8 bits to specify it's influence in overall pixel color (0 – no component influence, 2ⁿ-1 – maximum component influence)
• palette based - the pixels are presented by color index specified in palette.

THE STRUCTURE OF A PNG FILE

The first 8 bits are always 137 80 78 71 12 10 26 10. This means that the following data contains one PNG image, array of chunks starting with IHDR chunk and ending with IEND chunk. Chunks can be described as image properties containers.

Each chunk contains four parts:

• length - 4 byte integer specifying the length of chunks data field
• type - 4 byte code specifying the type of a chunk
• data field - all the data required by the chunk
• CRC - 4 byte CRC calculated from the previous data

Critical chunks

Each PNG file must contain IHDR, at least one IDAT and IEND chunk.

IHDR chunk

It contains following data:

Width:              4 bytes

Height:             4 bytes

Bit depth:          1 byte

Color type:         1 byte

Compression method: 1 byte

Filter method:      1 byte

Interlace method:   1 byte

Width and height describe the size of the picture in pixels.

Bit depth describes depth of colors in bits (1,2,4,8 and 16)

Color type describes the interpretation of picture data. The value is the sum of the following options:

• The palette is used (1)
• The pixels are represented by color values (2)
• The alpha channel is used (4)

Compression method and filter method, for PNG file, must always be set to 0.

Interlace method specifies whether the interlace mode is used (1) or not (0).

PLTE chunk

It contains up to 256 color descriptors. Each descriptor contains 3 byte RGB color value. The number of descriptors is specified by the size if a chunk. N=sizeof (PLTE)/3.

IDAT chunk

It contains actual compressed picture data. In order to create IDAT, picture dimensions must be known, picture must be filtered and data compressed. The data can be split into more IDAT chunks to improve a chance of recovering broken files.

IEND chunk

It must be the last chunk in file and is used to mark the end of file. It contains no data.

Ancillary chunks

Optional chunks, called ancillary chunks, may be ignored by PNG file readers and need not be written by PNG file writers. However, failing to support ancillary chunks may leave a PNG reader unable to properly render many PNG images.

Critial and ancillary chunks defined in the PNG specification proper are termed standard chunks. There are also special-purpose public chunks, which are less widely implemented but may be of use to some applications, and private chunks, which application may define for their own purposes, if they wish to store data that need not be interpreted by other applications.

Let's see the summary of all of the standard and special-purpose chunks defined by revision 1.0 of PNG specification.

COMPRESSION

Compression used in PNG is lossless LZ77 compression used in zip, gzip, pkzip and similar programs.

Idea

Algorithm trys to find duplicated strings in the input data stream. When it finds it, it is replaced with the pointer to the first occurrence of a string and the following character (the output: pointer(S),C). The string S is the longest match. If a match for a string can't be found the output is a null pointer and that character. Note that character can represent any data type, not only one byte character.

Coding algorithm

1. Put the coding point at the beginning of the input stream.
2. Find the longest string in the window matching the string pointed by coding point.
3. Send to the output stream (P,C) with the following meaning:

• P is a pointer to a string in the windows
• C is the following character in the input stream

4. If the input stream is not empty, move the coding point and windows by L+1 character in advance and go to step 2.

Terms used

• Input stream - array of characters which are to be coded
• Character - basic data element
• Coding point - points to the first character of the string being coded in the input stream
• Current string - array of characters from the coding point to the end of input stream
• Windows - array of characters containing characters from the beginning of the input stream to the coding point (already coded data).
• Pointer - points to the matching array in the window and specifying its length

Searching for the duplicated strings is a very slow process. Therefor many methods are used to speed up the process. Hashing table is one of them. All processed strings from input stream are put into hashing table, and each matching string can be found faster.

The whole coding process can be accelerated if we limit the size of the matching string. This way coding process will be much faster, but compression ratio will be lower.

Decoding

Decoding algorithm is very simple and swift. The process moves through the input stream (coded data), reads pairs (P,C) and send string pointed by P and character C to the output stream. This is until the end of file.

Coding example

Let's take we have the following string to code: AABCBBABC

Coder first reads A. It is the first character so the output is a null pointer and character A: (0,0)A.

The next character is A. We have the first match but we read the next character B. There is no match for AB so the output us (1,1)B.

The next character is C and the output is (0,0)C

The next character is B. We have B 2 spaces before and we read the next character B. There is no match for BB so the output is (2,1)B.

The next characters are A,B and C. There is a match for AB so the output is (5,2)C.

The final output is: (0,0)A, (1,1)B, (0,0)C, (2,1)B, (5,2)C.

Deciding example

Firs we read (0,0)A. It is a null pointer so the output is just A.

The following pair is (1,1)B. So we take a look what was 1 space before. It is A so the output is AB.

The next pair is (0,0)C so the output is C.

Now we read (2,1)B. So we take a look at what was 2 spaces before and see it's a B. The output is BB.

The final pair is (5,2)C. This points to a string AB so the output is ABC

The final output is AABCBBABC.

               Books

               References

               Related Links

HomePage - Basic Facts -Commercial - Algorithms - Hardware - FAQ - Glossary

Maintained and Copyrighted © 1997-2000 by DataCompression Reference Center