Re: complexity of the compression algorithm

Hi,

> Scale means viriation the blocksize adaptive to the local properties of
> image? That should leads to lower complexity than O(n), the fixed 8x8 case,
> right?

Simpler. Just adaption to the image size. For typical images, the size
of typical image details scales along with the image size, and as the
DCT in JPEG tries exactly a frequency analysis on the image details, you
need to scale the block size along with the image. Or rather, you should,
though traditional JPEG doesn't offer this.

>> The answer gets considerably different if you ask a different question:
>> Approximate running time on typical images (let's say, 1280x1024 pixels).
>> Of course, the details sure depend on the architecture and the code, and
>> also on some degree on the image quality. Here, traditional JPEG is for
>> sure a lot(!) faster. A lot means around a factor of five or more.

> That's what I meant. I was actually asking about running time... Actually I
> guess I also like to know the "complexity" for hardware implementation
> too..., in terms of size of the chip, power consumption, etc. 5+ times
> faster is a lot!

Yes.

> I am curious about how you get this 5+ factor? Do you have any
> pointer/resources of comparisons? 

Oh, I'm sorry. Nothing published in terms of papers, just a couple of
experiences I made. Actually, you can try some test runs yourself, there
are some freely available JPEG2000 codecs around. Commercial codes can
get better by a factor of two or so (depending on image and the code) 
compared to the free ones, but the general difference in required CPU
power remains.

> As I said, the DWT part should be lighter
> weighted in computation than DCT, (not in the asympototical O(...) sense),
> ... so all the heavy weighted computation comes from EBCOT?

To a major degree, at least. I'm not saying that it is guilty for
making it bad, as the EBCOT provides one of the core features
(embeddedness of the code), but it is easy to write a faster code
without it (with less features, of course). As for the wavelet
transform: The hard (though not impossible) part is to make this
operate locally such as to allow the CPU to keep data in cache. For
the classical DCT, you get this for free since it has blocks, with all
the drawbacks involved. For wavelets, you need to think about a smart
algorithm.  This is one of the points where the "free" codecs fail:
Keeping data localized. (It's, for example, the prime reason why
jasper is so slow, it doesn't run in cache). The beast is, definitely,
a lot lot lot more complex (algorithmically) than JPEG, no questions
asked.

In other words: As in the real world, you get nothing for free. At the
time JPEG was introduced, it was unbearably slow on the available
hardware. Given Moore's law stays correct for another couple of years,
I don't have too much problems with the higher demand of CPU
power. (-;

So long,
        Thomas