Results 1 to 7 of 7

Thread: Why does BWT work on images?

  1. #1
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts

    Why does BWT work on images?

    I have a question...I've seen in benchmarks that Bulat's FreeArc is a Pareto frontier on images when using a simple delta(of a kind)+bwt.
    Now, I don't see why BWT even works here. I've searched the web, but can only find empirical evaluations (and a ton of dead links), but no theory.
    Could somebody help me with a few pointers?

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    1. probably ST4 rather than BWT
    2. specialized codecs should hvae better speed/compression ratio and in particular much better compression

    the theory afaik is that color of the point depends on the adjancent points and ST4 here works as quicker variant of PPM(4) predictor, i.e. it predicts (delta of) color depending on the previous point. in lack of 2D prediction it's the maximum we can do. and take into account that ST4 in grzip is extremely fast plus it can be multithreaded

    btw, i will be glad to replace delta+grzip in freearc with real image codec

  3. #3
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Thx for the answer.

    Quote Originally Posted by Bulat Ziganshin View Post
    1. probably ST4 rather than BWT
    Yeah, maybe. But it the same kind of redundancy.
    Quote Originally Posted by Bulat Ziganshin View Post
    2. specialized codecs should hvae better speed/compression ratio and in particular much better compression
    But somehow they don't.

    Quote Originally Posted by Bulat Ziganshin View Post
    the theory afaik is that color of the point depends on the adjancent points and ST4 here works as quicker variant of PPM(4) predictor, i.e. it predicts (delta of) color depending on the previous point. in lack of 2D prediction it's the maximum we can do. and take into account that ST4 in grzip is extremely fast plus it can be multithreaded
    So it's that when you see a pixel in some context, both pixel and context are likely to repeat in the next row, right?

  4. #4
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    The question isn't "why BWT works on images?" but "why BWT works on images better than other codecs?". It could be that because assumptions made by author of other codecs aren't that good, or because FreeArc and associated codecs have a lot of speed optimizations, or something else.

  5. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Obviously BWT is better than LZ for this, as they use the same kind of redundancy, but BWT is more efficient.

    Also which benchmarks?.. I don't see fa in here, for example: http://compressionratings.com/img1.html

    Anyway, I'm not aware (besides paq and stuffit maybe) of any specialized image codecs which could provide
    real lossless compression (including headers and all), and otherwise they're useless for archivers.

    Well maybe Bulat could adopt BCIF somehow - other open-source image codecs (like jpeg ones) don't seem
    to have really good compression, while using them would be much harder.
    Unfortunately BMF and stuffit are not open-source.

    Another reason may be the fact that no (afair) specialized image codec supports solid compression, while LZ/BWT does.

    Compression-wise, optimized png + reflate + BWT would be probably still better than freearc's delta + BWT.

  6. #6
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Piotr Tarsa View Post
    The question isn't "why BWT works on images?" but "why BWT works on images better than other codecs?". It could be that because assumptions made by author of other codecs aren't that good, or because FreeArc and associated codecs have a lot of speed optimizations, or something else.
    At the time I didn't know why does it work at all, so the question was right. It could be changed now.

    Quote Originally Posted by Shelwien View Post
    Obviously BWT is better than LZ for this, as they use the same kind of redundancy, but BWT is more efficient.

    Also which benchmarks?.. I don't see fa in here, for example: http://compressionratings.com/img1.html
    W/out access to the files it's hard to tell what's up. Sorry, I don't have time too search, I remember seeing it more than once. I remember my own tests: the single-image test I did years ago and another single-image one that was never finished and published. I think there was something in the BCIF thread. And I'm sure that's not all what I've seen.


    Quote Originally Posted by Shelwien View Post
    Well maybe Bulat could adopt BCIF somehow - other open-source image codecs (like jpeg ones) don't seem
    to have really good compression, while using them would be much harder.
    Unfortunately BMF and stuffit are not open-source.
    BCIF needs to do something about highly redundant files. I view it as something with a good potential, but unfinished because of this flaw.

    Quote Originally Posted by Shelwien View Post
    Another reason may be the fact that no (afair) specialized image codec supports solid compression, while LZ/BWT does.
    Most image compression benchmarkers compress images individually.

    Quote Originally Posted by Shelwien View Post
    Compression-wise, optimized png + reflate + BWT would be probably still better than freearc's delta + BWT.
    Yeah, but slow as hell. A simple 2d gradient-based filter like in PNG+BWT would be only slightly weaker, several times simpler and much faster.
    I'm thinking about experimenting with this and even faster schemes...but it depends on some ongoing changes in my life.

    ADDED: BTW, solid mode is a good idea.
    Last edited by m^2; 11th September 2012 at 20:28.

  7. #7
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    I have noticed that some images that are compressed with the png2webpll utility which are then decompressed back with webpll2png and compared for difference tend to compress better with FreeArc's delta+grzip filters afterward, even if the WebP png2webpll utility is constrained to operate "fast" with parameter -c 0. Unless the alpha channel is nontrivial, I use imagemagick convert to dump it.
    The point is, maybe there is something in the webpll code that may be useful.
    Prior to this I would use crude methods like clamping values to 16 bit targa files or color averaging them to a pseudo "18 bit" color.
    An even more inaccuate method would be to use a shared chroma value in YUV colorspace like the cirrus logic "AccuPak" video codec, which libav can write.

Similar Threads

  1. Rawzor, how does it work?
    By SZGY in forum Data Compression
    Replies: 33
    Last Post: 23rd November 2017, 00:43
  2. Detector for ex-JPEG images
    By Alexander Rhatushnyak in forum Data Compression
    Replies: 22
    Last Post: 13th September 2012, 03:18
  3. Getting JOCL to work.
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 1
    Last Post: 27th October 2010, 23:50
  4. Images PreProcessor - PrePNG
    By PAQer in forum Data Compression
    Replies: 3
    Last Post: 21st May 2010, 12:21
  5. Precompression of Tiff Images
    By Simon Berger in forum Data Compression
    Replies: 52
    Last Post: 8th May 2009, 00:14

Posting Permissions

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