Results 1 to 7 of 7

Thread: Better PNG IDAT compression with BWT and MTF does not work, why?

  1. #1
    Member
    Join Date
    Jul 2016
    Location
    Hamburg, Germany
    Posts
    5
    Thanks
    0
    Thanked 1 Time in 1 Post

    Better PNG IDAT compression with BWT and MTF does not work, why?

    Hi,

    I want to improve the compression of the IDAT chunk in a PNG by reorganizing the data so the huffman coder should have less work. The images are for use in websites so later I will revert the progress via javascript in a canvas object. But the IDAT chunk is getting bigger and I do not really know why.

    These are my steps:

    1. Extract the IDAT chunk
    2. Decompress the IDAT chunk (now I have the filter values, not the RGB values)
    3. For every filter row:
    3.1. Use Burrows Wheeler Transform (does not change the string length)
    3.2. Use Move to front encoder (does not change the string length)
    4. compress the rows
    5. write back the IDAT chunk to the PNG

    So the generation of the PNG works but it is always bigger.
    I think I have an error in reasoning. Can someone help me and explain it?

  2. #2
    Member
    Join Date
    Aug 2016
    Location
    Sweden
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Did you reverse the row filters? Even if you did, are you sure BWT/MTF works better as a filter for your images than the built-in PNG ones? I wouldn't assume it does for photos at any rate.

  3. #3
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    539
    Thanks
    192
    Thanked 174 Times in 81 Posts
    Just a rough guess, but I think for most images compression will get worse because you're optimizing rows, but the "2D context" (similiarities from row to row) will be lost. Especially since BWT/MTF is not a perfect sort of the pixel values, but contains some noise IIRC.

    Anyway, the idea sounds good, I'd try it on more pictures (e.g. 8-bit instead of RGB) or on the unfiltered image data to see where it helps and where not.
    http://schnaader.info
    Damn kids. They're all alike.

  4. #4
    Member
    Join Date
    Jul 2016
    Location
    Hamburg, Germany
    Posts
    5
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by gliptic View Post
    Did you reverse the row filters? Even if you did, are you sure BWT/MTF works better as a filter for your images than the built-in PNG ones? I wouldn't assume it does for photos at any rate.
    No, I do not reverse the filters. I just want to improve the ordering of the low numbers after the applied filters.

    Quote Originally Posted by schnaader View Post
    Just a rough guess, but I think for most images compression will get worse because you're optimizing rows, but the "2D context" (similiarities from row to row) will be lost. Especially since BWT/MTF is not a perfect sort of the pixel values, but contains some noise IIRC.
    Hmmm... thought huffman would find more equal areas if the filter values were ordered.
    [10 minutes later]
    Made a test with an image with random noise. It is also getting bigger after my changes were applied. That shouldn't be. The image should be an ideal case for my changes and a bad one for the huffman coder.

    Quote Originally Posted by schnaader View Post
    Anyway, the idea sounds good, I'd try it on more pictures (e.g. 8-bit instead of RGB) or on the unfiltered image data to see where it helps and where not.
    Not before the noisy image is smaller.

  5. #5
    Member
    Join Date
    Jul 2016
    Location
    Hamburg, Germany
    Posts
    5
    Thanks
    0
    Thanked 1 Time in 1 Post
    BTW Meant LZ77 not huffman

  6. #6
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    BWT is not really a good compression algorithm for filtered images. It works better for stationary sources with high order contexts, such as text. Remember that what you are compressing is a sequence of small, signed numbers (prediction errors), which have low order, localized statistics. For that you are better off with a low order, fast adapting context model (in zpaq, an order 0 or 1 ICM like -ms6.0c or -ms6.0c0.0.255 or a 0-1 ICM-ISSE chain like -ms6.0ci1).

    Also, MTF is not the best way to compress BWT output. BWT brings similar contexts together (which is not what you want for images anyway) so that the output can be compressed with (again) a low order, fast adapting model. zpaq -m3 for text uses -mx6.3ci1 where the 3 means BWT.

    LZ77 is not ideal for images either, so I am pretty sure that a context model would do better than deflate in PNG.

  7. #7
    Member
    Join Date
    Jul 2016
    Location
    Hamburg, Germany
    Posts
    5
    Thanks
    0
    Thanked 1 Time in 1 Post
    Hi, thanks for your answer.
    I am new to compression and found your book just this minute. So I think I have to read a lot before I am able to understand your answer completely.
    So I don't want to replace the complete compression of a PNG. I just want to reorder the filter values to prepare the data for LZ77. That way that I just need a litte Javascript to retransform the data.

  8. The Following User Says Thank You to McSodbrenner For This Useful Post:

    Matt Mahoney (12th August 2016)

Similar Threads

  1. ec-idat (7-zip Deflate compression PNG)
    By lorents17 in forum Data Compression
    Replies: 8
    Last Post: 3rd September 2016, 12:37
  2. BWTIL: a set of tools to work with BWT-based text indexes
    By Nicola Prezza in forum Data Compression
    Replies: 31
    Last Post: 29th August 2014, 14:58
  3. Why does BWT work on images?
    By m^2 in forum Data Compression
    Replies: 6
    Last Post: 21st September 2012, 03:46
  4. Changing PNG compression
    By przemoc in forum Data Compression
    Replies: 5
    Last Post: 15th August 2012, 21:29
  5. Comparison of lossless PNG compression tools
    By Surfer in forum Data Compression
    Replies: 54
    Last Post: 19th September 2011, 22:58

Posting Permissions

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