PNG decoding notes

2015 A. Tarpai

About

PNG is well-documented and patent-free (http://www.libpng.org).

It lossless compresses true-color, grayscale and palette-based images of 1,2,4,8 and 16 bit depths of packed pixel formats.

Compression is based on encoding differences from neighbour pixel data (filters) and using the DEFLATE algorithm.

PNG compression principles

For me, it seems PNG was thinking to compress some 'raw' RGB image, where pixels are stored on bytes in a packed format.

Compression is a line-by-line differential encoding (similar to JPEG-LL). The encoder takes an image line and looks at neighbour pixel values of the same line and the line above (OK, it takes two lines). Then it figures out somehow which filter type gives the best result, i.e. smallest value in difference for pixels of the line (see Note). This is done on a line-by-line basis. The Filter type is the same for the whole line, and each line can have a different Filter. Computation is performed ON BYTE VALUES.

                    b         c    b
                    ^           \  ^        PNG Filter principles: which one is best?
                    |            \ |
a <-- x       a <-- x        a <-- x

Note. Because these 'd' difference values will be Huffman coded by Deflate, I'd rather say the best result is when 'd' values show the least variation. Huffman coding is entropy coding, which gives better result when symbol frequency groups in the original data is low. Huffman coding doesn't care about the original symbol values itself, only about symbol frequences. Furthermore, Deflate can break up the original data into blocks using their own Huffman table. This is hell to optimize.

When the correct Filter type is determined, the encoder computes the 'd' values for the whole line, byte-by-byte, and makes 'filtered image data':

r g b r g b r g b r g b r g b     filtering
r g b r g b r g b r g b r g b   ------------>  F d d d d d d d d d d d d d d d  

                                               (note the extra Filter-type byte)

After each scan line of the original image, the filtered image data is compressed with Deflate and put into IDAT Chunks as a zlib stream:

  R G B R G B R G B R G B R G B     Original image
  R G B R G B R G B R G B R G B 
  R G B R G B R G B R G B R G B 
  R G B R G B R G B R G B R G B 
  R G B R G B R G B R G B R G B 
  R G B R G B R G B R G B R G B 
  
              |
              | filtering
              |
              |
              
F d d d d d d d d d d d d d d d     Filtered Image Data
F d d d d d d d d d d d d d d d
F d d d d d d d d d d d d d d d 
F d d d d d d d d d d d d d d d 
F d d d d d d d d d d d d d d d 
F d d d d d d d d d d d d d d d 

              |
              | compress with Deflate 
              |
              |

      +----------------------------------------------------------------------------+
      |010.......................EOD.|001..................EOD.|110............EOD.|
      +----------------------------------------------------------------------------+
      |block                         |block                    |block 
      |header                        |header                   |header
                                                               |final
              |
              | make zlib  
              |  
              |  
+---+---+  +=====================+  +---+---+---+---+
|CMF|FLG|  |...compressed data...|  |    ADLER32    |
+---+---+  +=====================+  +---+---+---+---+
              |  
              |  
              | put it into chunk(s)
              |

   IDAT..................IDAT...........................IDAT..........   

PNG decoding

Goes backwards. Extracts data from one or more IDAT Chunks, Inflates, unfilters line-by-line to get back the original RGB-data.
Then what? PNG supports a lots of pixel types. Display devices, known file types of other image formats may not support all.
Because I wanted to blit images into the frame buffer I have chosen to make in-memory BMP of some direct-color format that matches the video hardware.

IDAT........................IDAT.............IDAT.............................. 
                           
                          |
                          |  concatenation 
                          |
                           
................................................................... compressed image data
                           
                          |
                          |   inflate 
                          |

F----------------------------F--------------------------F----------------------------F---------------    uncompressed image data
                                                                                                              (Filtered)


The uncompressed PNG Image (Filtered):
                                                                                                                                         
F----------------------------       <---- Scan Line (byte aligned)   
F----------------------------
F----------------------------          F: Filter Byte (0..4) 
F----------------------------          -: PNG image pixel byte
F----------------------------
F----------------------------
F----------------------------
                       
                      |
                      |  line unfiltering 
                      | 
                       
----------------------------       Raw Pixel Data 
----------------------------        
----------------------------           indexed-color           (1,2,4,8)
----------------------------           grayscale      /alpha   (8,16)   
----------------------------           truecolor      /alpha   (8,16)
----------------------------
----------------------------

                      |
                      |
                      |  converting 
                      | 

          +----------------------+
          |                      |         This decoder's output is BM-format
          |    Image in target   |           RGB8888:  [B][G][R][A]
          |       format         |           RGB888:   [B][G][R]
          |                      |           RGB565:   [bg][r]
          |                      |           RGB555:   [bg][r]
          +----------------------+

This is a per-image-line decoder (to reduce buffers):

                                                                                  +-------------------+
                                                                                  |                   |
----------------+         filter              decoded pixel data       convert    |                   |
  inflated data |    ---------------->      +--------------------+    -------->   |xxxxxxxxxxxxxxxxxxx|
----------------+                           +--------------------+                |                   |
                                                   ||                             |                   |
                                                   ||                             |                   |
                                            +--------------------+                +-------------------+
                                            +--------------------+                        BITMAP
                                                 image line 
                                                filter buffer

PNG PIXEL BYTE STRUCTURE

PNG supports a lot of pixel formats to compress, all from bits to 8 bytes per pixel (BPP).
Here [] means one byte of PNG pixel format (IHDR.ColourType). BPP is byte-per-pixel, bpp is bit-per-pixel:

ColourType     Byte storage                    name                        bpp        BPP

     3         [.]                          indexed-color pixel            1,2,4,8    1        + PALETTE (1,2,4 grayscale implemented here)
     0         [Y]                          grayscale pixel                8          1                                                    
     0         [Y][Y]                       grayscale pixel                16         2                                                    
     2         [R][G][B]                    truecolor pixel                8          3                                                    
     2         [R][R][G][G][B][B]           truecolor pixel                16         6                                                    
     4         [Y][A]                       grayscale pixel with alpha     8          2                                                    
     4         [Y][Y][A][A]                 grayscale pixel with alpha     16         4                                                    
     6         [R][G][B][A]                 truecolor pixel with alpha     8          4                                                    
     6         [R][R][G][G][B][B][A][A]     truecolor pixel with alpha     16         8                                                    

"Image line filter buffer": PNG pixel bytes in buffer before conversion

8 zero byte padding is used for the 'a' neighbour of the first pixel.

Truecolour 8-bit             
                              
       padding    |           
                  |
   0 0 0 0|0 0 0 0|R G B               
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE (DWORD aligned)
                  |
   
Truecolour 8-bit with Alpha
           
       padding    |           
                  |
   0 0 0 0|0 0 0 0|R G B A              
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |

                  
Truecolour 16-bit             
   
       padding    |           
                  |
   0 0 0 0|0 0 0 0|R R G G B B         
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |
   
Truecolour 16-bit with Alpha
           
       padding    |           
                  |
   0 0 0 0|0 0 0 0|R R G G B B A A         
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |
   
          
Greyscale 8-bit              
                          
                  
       padding    |           
                  |
   0 0 0 0|0 0 0 0|Y                   
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |
   
Greyscale 8-bit with Alpha
       
       padding    |           
                  |
   0 0 0 0|0 0 0 0|Y A               
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |

   
Greyscale 16-bit              
                  
       padding    |           
                  |
   0 0 0 0|0 0 0 0|Y Y                  
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |
   
Greyscale 16-bit with Alpha
             
       padding    |           
                  |
   0 0 0 0|0 0 0 0|Y Y A A              
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |
   
                  
Packed pixel/Palette types                 
Greyscale 1,2,4-bit and             
Indexed-colour 1,2,4,8-bit 


       padding    |           
                  |
   0 0 0 0|0 0 0 0|I                   
   - - - - - - - -|- - - - - - - - - - - - - - - - - - - - - - - - - - - - -   FILTER LINE
                  |

PNG pixel formats

Based on IHDR.ColourType (= 0,2,3,4,6)
"Color type codes represent sums of the following values: 1 (palette used), 2 (color used), and 4 (alpha channel used). Valid values are 0, 2, 3, 4, and 6."

              PNG byte  
                                     - Greyscale sample
          +---------------+          - RGB sample
          |               |          - Palette index (always 8-bit) + PLTE
          +---------------+
          
          
GREYSCALE VALUE
                                                   +----->  R
     = one color channel, one value per pixel -----+----->  G        Grey Convert to RGB = sending same value to all three (it will look 'grey')
                                                   +----->  B

                                                 
                                                 
                                                 
                               PNG byte                                                      Implemented as:                   Writers: gets int color
            Bit Depths                                     
                           +---------------+   
                8          |               |      ---> 1 pixel    0..255 gray colors          ----> ConvertGrey()                          
                           +---------------+                                       
                                                       
                           +---------------+
                4          |       |       |      ---> 2 pixels   each is 16 grey colors      ----> GreyPalette4
                           +---------------+
                                          
                           +---------------+
                2          |   |   |   |   |      ---> 4 pixels   each is 4 grey colors       ----> GreyPalette2
                           +---------------+
                                          
                           +---------------+              
                1          | | | | | | | | |      ---> 8 pixels   either black or white       ----> GreyPalette1 
                           +---------------+              
                           
                           
                           
  
                        
  PALETTE
  
                           
            PNG byte                           PALETTE
                                            
        +---------------+                +-----+-----+-----+   
        |     idx       |  ------->      |  R  |  G  |  B  |           
        +---------------+                +-----+-----+-----+   
                                         |  R  |  G  |  B  |
                                         +-----+-----+-----+        R,G,B
                                         |  R  |  G  |  B  |     ---------->
                                         +-----+-----+-----+
                                         |  R  |  G  |  B  | 
                                         +-----+-----+-----+ 
                                           ...   ...   ...   
                           
   
            Bit Depths                   Max number of PALETTE ENTRY                     
                                      (PNG doesn't have to carry full palettes)
                           
                8              ---->         256               
                4              ---->         16               
                2              ---->         4               
                1              ---->         2               


.