Results 1 to 10 of 10

Thread: pngthermal: pseudo thermal view of PNG compression efficiency

  1. #1
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    154
    Thanks
    6
    Thanked 29 Times in 17 Posts

    pngthermal: pseudo thermal view of PNG compression efficiency

    Hello,
    early release (alpha grade) of pngthermal.

    Version 0.1a
    Usage: pngthermal input.png output.tga


    This sample case has been brought up to show the limitation of the 32k search window imposed by Deflate.
    The main difference between the image on the left and the right is that the latter one is one column wider (1080 bytes of raw data were added) unfortunately it's twice as big from the file size point of view, what went wrong?
    Both images were saved as PNG-32 files (RVBA, 4 bytes per pixel) thus a single set of kiwis and a flag take 90 x 90 x 4 + 90 bytes in the first case and 91 x 90 x 4 + 90 in the second case (X by Y by pixel-depth plus a single byte -the PNG filter type- for each raw).

    This sums up to 32490 vs. 32840 bytes.

    - 32490 is smaller than 32k (32768 the Deflate search window limit) the bytes representing the kiwis are still within the LZ match range when compressing the second and third set of kiwis and basically only the flags take a lot of space since large parts of the kiwis are simply encoded as highly efficient LZ matches (shown as deep blue).

    - 32840 is bigger than 32k the bytes representing the kiwis are now out of reach and each set of kiwis is encoded has if it had never been seen before, hence the way bigger file.


    In this case I show that PNG is very efficient at compressing mid 90's Unix workstation screen-shots as long as you keep a simple repeating wallpaper in the background... since replacing it by a photo-realistic wooden wallpaper makes the file size jump from 23 KB to a whopping 189 KB.

    To do list:
    - produce a .png file and not heavy .tga (Targa, "pngout -s2 bigfile.tga" can be used to turn it into a .png)
    - release source
    - 1, 2 & 4 bits bit-depth support
    - option to show RGB components and not pixels
    - WebP lossless support as source file
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	compo-vert90.png 
Views:	37 
Size:	19.8 KB 
ID:	2451   Click image for larger version. 

Name:	compo-vert91.png 
Views:	37 
Size:	40.1 KB 
ID:	2452   Click image for larger version. 

Name:	docusp-wood256.png 
Views:	41 
Size:	184.2 KB 
ID:	2519   Click image for larger version. 

Name:	docusp-sun256.png 
Views:	38 
Size:	22.4 KB 
ID:	2518  
    Attached Files Attached Files
    Last edited by caveman; 9th March 2014 at 00:12.

  2. The Following 5 Users Say Thank You to caveman For This Useful Post:

    Biozynotiker (7th October 2013),Bulat Ziganshin (5th October 2013),Jaff (18th May 2013),porneL (29th August 2013),seth (28th August 2013)

  3. #2
    Member
    Join Date
    Jun 2013
    Location
    USA
    Posts
    79
    Thanks
    3
    Thanked 8 Times in 6 Posts
    Do you have downloadable versions of the kiwi images?

  4. #3
    Member
    Join Date
    Aug 2013
    Location
    United States
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    What exactly does the heatmap represent? IE what makes a pixel "red" vs. "dark blue" ? What exactly are you defining as a "highly efficient LZ match" ?

    I threw together a quick script that output a .RAW file based upon what pixels in a PNG were found in a backwards 32k window, and could not reproduce the resulting heat-maps from your application (at the same image dimensions).

    ~Main

  5. #4
    Member
    Join Date
    Jul 2013
    Location
    there
    Posts
    16
    Thanks
    5
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by duhroach View Post
    What exactly does the heatmap represent? IE what makes a pixel "red" vs. "dark blue" ? What exactly are you defining as a "highly efficient LZ match" ?
    Dark blue is well compressed (cheap) and red is poorly compressed/uncompressed. Highly efficient LZ match means that encoder could say "reuse the data you've seen before" instead of actually storing that data again.

  6. #5
    Member
    Join Date
    Aug 2013
    Location
    United States
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by porneL View Post
    Dark blue is well compressed (cheap) and red is poorly compressed/uncompressed. Highly efficient LZ match means that encoder could say "reuse the data you've seen before" instead of actually storing that data again.
    Right. That's a binary operation however. Either this byte has been matched, and seen before, or it hasn't. e.g:
    1. LZ77 the image
    2. for each source pixel
    3. if this pixel landed in an lz match, then output 0xFF
    4. else output 0x00

    So what am I missing here that takes this binary test and makes a gradient scalar on it? Is a pixel value being normalized by the length of the LZ77 block that it resides in?

  7. #6
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    154
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Quote Originally Posted by Mangix View Post
    Do you have downloadable versions of the kiwi images?
    They are not on my laptop, I'll post them quickly once home (the kiwi samples have been added to the first post), but you can play with these two images in the meanwhile, they are build the same way as the kiwi sample 90x90 vs 90x91 RGBA tiles.
    The Firefox logos are here to illustrate the fact that pngthermal works on actual PNG files, the two logos are pixel perfect the same image, fox1.png has been heavily optimized (pngwolf, pngout, huffmix, deflopt...) whereas fox2.png did not benefit the same attentions, it turns out that the heat map for fox1 has clearly more dark blue areas compared to the fox2 heat map.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	AirDrop91.png 
Views:	42 
Size:	22.1 KB 
ID:	2446   Click image for larger version. 

Name:	AirDrop90.png 
Views:	39 
Size:	17.8 KB 
ID:	2445   Click image for larger version. 

Name:	AirDrop90t.png 
Views:	33 
Size:	3.2 KB 
ID:	2449   Click image for larger version. 

Name:	AirDrop91t.png 
Views:	29 
Size:	3.8 KB 
ID:	2450   Click image for larger version. 

Name:	fox1.png 
Views:	33 
Size:	48.3 KB 
ID:	2453  

    Click image for larger version. 

Name:	fox2.png 
Views:	33 
Size:	60.7 KB 
ID:	2454   Click image for larger version. 

Name:	fox1t.png 
Views:	39 
Size:	9.9 KB 
ID:	2455   Click image for larger version. 

Name:	fox2t.png 
Views:	39 
Size:	11.3 KB 
ID:	2456  
    Last edited by caveman; 6th September 2013 at 10:55.

  8. #7
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    154
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Quote Originally Posted by duhroach View Post
    Right. That's a binary operation however. Either this byte has been matched, and seen before, or it hasn't. e.g:
    1. LZ77 the image
    2. for each source pixel
    3. if this pixel landed in an lz match, then output 0xFF
    4. else output 0x00

    So what am I missing here that takes this binary test and makes a gradient scalar on it? Is a pixel value being normalized by the length of the LZ77 block that it resides in?
    One thing that is perhaps not clear is that pngthermal does not estimate the heat map based on the picture data (the pixels you see) but it reports how efficient the compression of an actual PNG file is and this based on the compressed stream analysis i.e. the same image compressed with two different tools say pngcrush and zopflipng will produce two different heat maps (for instance check the Firefox logos in the previous post).

    Thus it reflects the real cost of the LZ77 match (the bits actually written in the deflate stream in the PNG file) distributed across the n bytes recorded this way (n being the match length) plus a fraction of the deflate block header.
    pngthermal is closely related to defdb, pngthermal reprocesses what defdb reports in [size] to produce an image.

    - [size] XX, a literal value XX in hexa (ranges from 00 to FF that is 0 to 255), takes size bits.
    - [size] (length, distance), LZ pair in decimal, length (3 to 25 distance (1 to 3276, takes size bits.
    - [size] EofB, End of Block, takes size bits.

    Lets take a real world sample.
    sample_1.png is a small image (14x10 pixels) representing the national flag of France, recorded as a PNG-8 it takes 100 bytes, TweakPNG reports that the IDAT (Image Data) chunk takes 19 bytes, defdb goes further down:

    Code:
    defdb sample_1.png
    T Boundary   Tokens   h.size   b.size
    1        0        8        3       98
    98 bits that's 12 bytes and 2 bits rounded up it gives 13 bytes (13 + 2 header + 4 checksums = 19 bytes as reported by TweakPNG).

    Now lets take a closer look at these 98 bits:
    Code:
    defdb -d sample_1.png
     [1] Last block (val: 1)
     [2] Fixed Huffman Tree block (val: 1)
     [8] 00
     [8] 01
    [12] (4,1)
     [8] 02
    [12] (3,1)
     [8] 00
    [12] (5,1)
    [20] (134,15)
     [7] EofB
    Remember defdb reports the size of each element in the stream in bits, it's the first value written between square brackets at the beginning of each line (if you sum up all the values in square brackets 1, 2, 8, 8, 12, 8, 12, 8, 12, 20 and 7 you get 98 - the block size -)
    The first 3 bits are a deflate block header, since our sample deflate stream is extremely small it holds a single type 1 block (fixed - predefined in the specs - Huffman trees) larger streams usually hold one or more type 2 blocks (dynamic Huffman trees) and it roughly takes between 300 and 1000 bits to record the Huffman tables in the stream (this is reported under h.size by defdb).

    After this short header we find the payload of the deflate stream.
    The first token decoded is a literal (a single byte, valued 0 here) and it took 8 bits to record it, this is not the first (upper left) pixel of the image since it's actually the filter type applied to the first line (this is a PNG feature), by luck filter 0 is the none filter (it does nothing) and it avoids me to explain how PNG filters work.

    The next token is again a literal valued 1 and takes 8 bits in the stream, this is our first pixel, 1 means that the color of this pixel is the one defined in the palette (it's a PNG- at entry 1.
    The palette defined in the PLTE chunk holds 4 entries (which is a bit odd since the French flag is a blue-white-red tricolor):
    0) Red
    1) Blue
    2) White
    4) Black
    Thus our first pixel is blue.
    Now back to pngthermal, in this PNG-8 context where one byte = one palette entry = one displayed pixel, our first pixel has a temporary cost of 8 bits. The color ruler used by pngthermal fits to bits this way:

    - midnight blue = strictly less than a bit
    - dark blue = strictly less than 2 bits
    - royal blue = strictly less than 3 bits
    - teal = strictly less than 4 bits
    - emerald green = strictly less than 5 bits
    - chartreuse = strictly less than 6 bits
    - yellow = strictly less than 7 bits
    - orange = strictly less than 8 bits
    - bright red = strictly less than 9 bits
    - darker red tones are used the same way for 10, 11, 12... bits
    With an 8 bits cost the first pixel will display as bright red in the heat map.

    The next token is an LZ match (length = 4, distance = 1) and takes 12 bits in the stream. This match basically repeats the last value (distance = 1) four times (length =4) this mimics RLE, we now have 4 more blue pixels.
    4 pixels that did cost 12 bits, each pixel has a temporary cost of 3 bits (12/4), way better than 8 bits and will display as teal.

    The next token is a literal valued 2 and takes 8 bits in the stream, 2 is the entry for white in the palette, 8 bits means bright red.

    The next token is an LZ match (length = 3, distance = 1) and takes 12 bits in the stream, we now have 3 more white pixels (the white band is slightly narrower in this image).
    3 pixels that did cost 12 bits, each pixel has a temporary cost of 4 bits (12/3), and will display as emerald green.

    The next token is a literal valued 0 and takes 8 bits in the stream, 0 is the entry for red in the palette, 8 bits means bright red.

    The next token is an LZ match (length = 5, distance = 1) and takes 12 bits in the stream, huh?!? five red pixels?
    In fact no, it's 4 red pixels, the last 0 is the filter of the next line (the image is only 14 pixels wide). We had:
    01111122220
    and now:
    011111222200000
    0

    Ok, now lets take a bit of time to explain how pngthermal handles the filter type. It's pretty simple it puts it on display using a different (black to purple) scale, the two first pixels of each line represent the cost of the filter type, that's why pngthermal outputs are always 2 pixels wider than the input image (I choose two to get a better chance to actually see it). The filter type is part of the data handled over to the deflate engine along with the actual image data, it has sometimes a small negative impact on compression efficiency (especially when it works as a barrier that prevents long matches to wrap around from one line to another) but good filtering can largely improve compression rates.
    The four pixels and the filter type have a temporary cost of 2.4 bits (12/5), the pixels will display in royal blue and the filter type in dark purple. The filter type on the previous line had a higher cost and is in bright purple.

    The next token is an LZ match (length = 134, distance = 15) and takes 20 bits in the stream, a distance of 15 brings the beginning of the match at the level of the first 1, and 134 bytes will be copied starting here, this will unwrap the entire image.

    We had:
    011111222200000
    0
    and now:
    011111222200000
    011111222200000
    011111222200000
    011111222200000
    011111222200000
    011111222200000
    011111222200000
    011111222200000
    011111222200000
    011111222200000

    The mixed bag of 134 pixels and filter types has a temporary cost of 0.15 bits, the pixels will display in midnight blue and the filter types in black.

    The last token is an End of Block marker and it takes 7 bits in the stream, since I could not simply let the cost of the block header (3 bits here, but it could have been a thousand of bits) and the end of block vanish, their combined cost (10 bits, here) is redistributed over all the bytes the deflate block hold... that's why I used the term "temporary cost" so far. Thus 0,06 bits (10/150) are added to each temporary cost to get the real cost of each byte, in this sample it's pretty insignificant but when blocks of type 2 are involved it makes much more sense.

    When switching over to 3 or 4 bytes pixel depths (PNG-24 RGB, PNG-32 RGBA) the cost of each pixel is the sum of each individual component divided by the pixel depths. It could have been done differently, for instance the resulting image could be stretched to display each component individually.

    You may have noticed that in this sample literals always take 8 bits and are therefore in bright red this is due to the fixed Huffman tables, when dynamic Huffman tables are used literals size varies greatly usually in the 4 to 12 bits range and are the main source of yellow-orange-red dots, long matches stay in the blue-green tones whereas short matches tend to be green-yellow.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	sam1.png 
Views:	69 
Size:	2.2 KB 
ID:	2448  
    Attached Images Attached Images  
    Last edited by caveman; 9th March 2014 at 00:35. Reason: typos

  9. #8
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    154
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Quote Originally Posted by duhroach View Post
    What exactly does the heatmap represent? IE what makes a pixel "red" vs. "dark blue" ? What exactly are you defining as a "highly efficient LZ match" ?

    I threw together a quick script that output a .RAW file based upon what pixels in a PNG were found in a backwards 32k window, and could not reproduce the resulting heat-maps from your application (at the same image dimensions).
    You'll find a lot of answers in my previous post.
    A "highly efficient LZ match" is in fact a long match, a deflate match is limited to 258 bytes (64.5 pixels in a PNG-32) but such a match could be stored in 2 or 3 bytes (it also depends on the distance and frequency of such matches), lets take a peek at the end of the AirDrop90.png file presented here:
    Code:
     tail of defdb -d AirDrop90.png
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
    [15] (258,32490)
     [2] EofB
    It ends with maximum length (25 LZ matches that point 32490 bytes before, this is exactly 90x90x4 (image data) + 90 (PNG filter type in front of each line). The wooden box at the top is duplicated as is 64.5 pixels at a time and each such chunk takes 15 bits in the PNG file.
    Last edited by caveman; 6th September 2013 at 12:29.

  10. #9
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    47
    Thanks
    7
    Thanked 0 Times in 0 Posts
    good afternoon!
    Whether prompt, please, it is possible to define by pngthermal what version of the image created by means of cryopng better is suitable for compression?

  11. #10
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    154
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Another pngthermal use case was to validate cryopng and cryopngtk2 (will be released in the next days).

    Cedric Louvrier (the guy behind ScriptPNG) once came up with this image:
    Click image for larger version. 

Name:	sample1a.png 
Views:	45 
Size:	7.9 KB 
ID:	2506
    sample1a.png (8104 bytes)
    And he told me that he used cryopng several times (he rotated the image and overlaid the invisible pixels using Image Magick) to produce it, this sound counter intuitive and crazy but effectively the standard cryopng outputs did not seem to compress this image as well at first.

    Transparent pixels revealed and associated heat-map:


    8623 bytes, cryopng -f0 + zopflipng


    8342 bytes, cryopng -f1 + zopflipng


    8324 bytes, cryopng -f2 + zopflipng


    8701 bytes, cryopng -f3 + zopflipng


    8236 bytes, cryopng -f4 + zopflipng


    8104 bytes, original

    None of the files produced by cryopng and optimized with zopflipng gets close to the original file size and this one has a lot of "dirty" transparent pixels.

    Now, pay close attention to the first raw and the upper left border of the balloons.

    The files produced by cryopng (on the left) present this red border since when the pixels suddenly change from black to some bright color whatever filter is used it represents an important gap which is pretty uncommon in the rest of the image and therefore it requires a lot of information.
    On the original image heat-map (on the right) there's no such red border since this gap doesn't exist, in the other hand it appears that the first raw of the image was somewhat more complicated to compress.
    There's apparently a sort of trade off between complexity at the border / on the first raw, at first I thought that a good deflate block splitter would isolate the first raw from the rest and that this could explain the size difference but the deflate stream of the original file holds only a single block.
    I tried to further compress the file Cedric provided and this proved particularly hard to achieve! During this enduring task I discovered that this image was extremely sensitive to PNG filtering, both pngout and zopflipng were far from picking the best filters hence I had to call pngwolf to the rescue to reduce the file size.
    Click image for larger version. 

Name:	best-original.png 
Views:	38 
Size:	7.9 KB 
ID:	2513
    8079 bytes, optimized original, pngwolf, pngout random, huffmix...

    The same kind of strategies applied to the files produced by cryopng work pretty well on the f2 file...
    Click image for larger version. 

Name:	best-classic-cryopng.png 
Views:	36 
Size:	7.9 KB 
ID:	2514
    8092 bytes, cryopng f2, pngwolf, pngout random, huffmix...
    ...however the optimized original image is still smaller!

    Since I had an experimental version of cryopng able to propagate pixels a bit differently on the horizontal axis (that's cryopng take 2 - cryopngtk2 in short -, vertical propagation is a bit more difficult to achieve at the filter level) I used it on a rotated image to reproduce the same kind of effect as the original image.
    Click image for larger version. 

Name:	best-rotated-cryopngtk2-rgb.png 
Views:	34 
Size:	6.5 KB 
ID:	2515
    Click image for larger version. 

Name:	best-rotated-cryopngtk2.png 
Views:	32 
Size:	7.9 KB 
ID:	2516
    8070 bytes, rotated 90, cryopngtk2 f0, rotated back, pngwolf, pngout random, huffmix...
    Logically the heat-map looks the same as the original image.
    Click image for larger version. 

Name:	best-rotated-cryopngtk2-thermal.png 
Views:	33 
Size:	2.4 KB 
ID:	2517
    Last edited by caveman; 5th October 2013 at 19:32.

  12. The Following User Says Thank You to caveman For This Useful Post:

    porneL (6th October 2013)

Similar Threads

  1. Changing PNG compression
    By przemoc in forum Data Compression
    Replies: 5
    Last Post: 15th August 2012, 22:29
  2. Comparison of lossless PNG compression tools
    By Surfer in forum Data Compression
    Replies: 54
    Last Post: 19th September 2011, 23:58
  3. Idea for raising compression efficiency on disk images
    By Mexxi in forum Data Compression
    Replies: 10
    Last Post: 18th February 2010, 06:56
  4. NanoZip huge efficiency issue
    By m^2 in forum Data Compression
    Replies: 9
    Last Post: 10th September 2008, 22:51
  5. rnd - simple pseudo random number generator
    By encode in forum Forum Archive
    Replies: 21
    Last Post: 14th January 2008, 04:41

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •