Why does BWT work on images?

[m^2]

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?

[Bulat Ziganshin]

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

[m^2]

Thx for the answer.

1. probably ST4 rather than BWT

Yeah, maybe. But it the same kind of redundancy.

2. specialized codecs should hvae better speed/compression ratio and in particular much better compression

But somehow they don't.

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?

[Piotr Tarsa]

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.

[Shelwien]

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.

[m^2]

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.

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.

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.

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.

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.

[Karhunen]

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.