[newt0311]

Very extreme jpeg pre 2000 compression would probably do considerably worse as it would degenerate into drawing in boxes of averaged color. jpeg200 would absolutely destroy this compression technique as it specifically uses a form of fourier analysis (wavelet analysis) which is provably optimal for this kind of compression. In fact, AFAIK jpeg2000 is designed so that as more bit are read from a file, it is possible to get a better and more accurate picture -- one of the benefits of using a fourier-analysis like technique. Sort of like a compression on steroids. Getting a lower res. picture is only slightly more complicated than truncating the file and requires minimal processing.

[DarkShikari]

JPEG2K is a terrible format that, in practice, often comes out worse than JPEG. This is partly because wavelets are terrible from a psychovisual standpoint, but also because the format is just badly designed; Snow, a similar wavelet format, trashes it completely even when using the exact same wavelet transform.

Also, wavelets are not at all "provably optimal." The only "provably optimal" transform is the KLT, and even that isn't really, since in practice overcomplete transforms tend to have better compression efficiency than complete ones, at the cost of turning compression from a simple O(nlog(n)) frequency transform into an NP-complete problem of matching pursuits.

[tlb]

"Provably optimal" always involves unwarranted assumptions. For example, least-squares fitting is provably optimal, assuming all your distributions are independent and gaussian. Image compression quality is all about sensitivity of the human visual system to various kinds of errors, so nothing can be proven optimal, ever.

[eru]

Proving still retains value. Because you reduce the burden of choosing a good algorihtm to choosing good assumptions.

[jibiki]

One common set of assumptions in image denoising is that:

1. The pixels in the output image should be close in value to the corresponding pixels in the input image.

2. Neighboring pixels in the output image should have similar values.

I wonder if anyone has compared compression techniques using these sorts of assumptions.