PNG (Portable Network Graphics)

Juan Francisco Rodríguez Herrera
Vicente González Ruiz

June 24, 2014

1 Posibilities
2 Codec
3 Filtering (encoding)
4 “Deflate” (encoding)

1 Posibilities

http://www.libpng.org/pub/png.
Fully lossless.
Only raster (not vectorized) images.
Better funtionality and performance than GIF (Graphics Interchange Format), that uses an patented implementation of the LZW algorithm, and TIFF (Tagged Image File Format).
Free usage and free from patents.
Palletized images (up to 256 colors), true color images (up to 48-bits/pixel) and grayscale images (p to 16-bits/pixel).
On-the-fly encoding and decoding (streamability).
Alpha channels (variable transparency).
Gamma correction (cross-platform control of image brightness).
Progressive and interlazed images.
Progressive reconstructions by means of spatial scalability.

2 Codec

3 Filtering (encoding)

Optional.
Predictive encoder that reduces the spatial correlation.
Pixels are translated to prediction residues (errors): $E = X − ˆX$
where X is the pixel-value and its prediction.
The entropy of the residue image is typically smaller than the original image’s one, and the residues follow a Lapace probability distribution, centered in 0 (the average of the prediction error is 0).

Available predictors (“filters”):

Type	Predictor	Prediction

0	None	← 0
1	Sub	← A
2	Up	← B
3	Average	← (A + B)∕2
4	Paeth	← A + B − C

The predictor can be changed in the middle (of the encoding) of an image.

4 “Deflate” (encoding)

It’s a generic text-compression algorithm based on LZ77 and Huffman and written by Jean-loup Gailly and Mark Adler¹ .
LZ77 removes the statistical redudancy of high order (remember that the preditor has removed the spatial redundancy).
The Huffman encoder removes the statisctical redundancy of order 0. The probabilistic model used is adaptive and initially empty.

The PPM (Portable aNyMap) container

struct PPM_image {
  "P6\n",        /* Magic number */
  char* width, " ", height,  /* Columns and rows */
  "\n",
  char* depth,   /* 2^number_of_bits_per_component */
  "\n",
  struct RGB_pixel pixel[width][height];
}

if (depth == "255") {
  struct RGB_pixel {
    unsigned char R;
    unsigned char G;
    unsigned char B;
  }
} else if (depth == "65535") {
  struct RGB_pixel {
    unsigned short R;
    unsigned short G;
    unsigned short B;
  }
}

Let’s go to the lab!

Use the pnmtopng command line tool to fill the table:
Codec | lena boats pepers zelda Average
---------+--------------------------------
pnmtopng |

References

[1] M. Nelson and J. Gailly. The Data Compression Book. M&T Books, 1996.