Re: complexity of the compression algorithm

Dear Thomas,

> The complexity of a DCT algorithm for a block length of size n is O(n
> log n).  Since the block size is fixed for JPEG (a bad thing to do,
> but that's it), the running time asymptotically only depends on the
> number of blocks, and is thus O(n). If you'd scale the blocks along
> with the data (which would be a good idea, but cannot be handled in
> classical JPEG) you would get O(n log n).

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?


> 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!

I am curious about how you get this 5+ factor? Do you have any
pointer/resources of comparisons? 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?

Thanks a lot,

-Walala