Compression - Re: silly question on haar implementation

Author

Re: silly question on haar implementation

Thomas Richter

2004-06-25, 6:56 pm

Hi Alexis,

> Well, don't blame yourself here, because it's impossible ;-)

No, not quite. If you just allow a minor modification, it's very well
possible without range extension. Mathematically, the range of
characters [0,255] with "unsigned arithmetic addition" is just the
ring Z_256, which has a perfectly valid group structure for addition,
thus the set of all pairs form a module and straight matrix algebra
applies.

If we define the haar transformation as

(a,b) -> (a+b,(a-b)/2)

then this is invertible. The /2 is a kind of "sloppy" notation, it should
rather say:

-((a-b) >> 1) + b

in usual "C" syntax. Ok, here's the proof:

The above transformation can be lifted into the following matrix products
B * A with A =

1 1
0 1

and B =

1 0
-1/2 1

both of which are clearly invertible. (Multiplication with -1/2 to be understood
in the above sense: Divide by two, round down, take the negative.)

Ok, now the above in common speach: You can reconstruct the pair (a,b)
from (x,y) := (a+b,b-(a+b)>>1) mod 256 by the following procedure:

i) get b = y + (x >> 1)
i) get a = x - b

if you choose rounding consistently for forwards and backwards (i.e.
always round down), nothing is lost here and all "wrap arounds" cancel.

> Applying a
> wavelet transform typically leads to an expansion of the dynamic range of
> the data. Just change your pixel type from char* to short* and it'll work.
> If you want to perform compression with wavelets, you'll have to overcome
> this expansion by studying the statistics of the coefficients and their
> correlations.

Though that's also correct. (-;

Now, where's the point:

The point is that the above group Z_256 has "wrap-arounds" in its addition
(as it should have), e.g. 254+5 = 3. While these are completely invertible,
they typically "destroy" the statistics of the output coefficient and make
them less compressible than just let the wavelets expand their range and
compress this expanded range. Thus, even the above works fine, it is rather
unpractical and should possibly not be done. Well, I haven't actually tried,
so maybe that's the job for a tiny research product.

(Thus spoken, "guard bits" in JPEG2000 are "actually not required"... ;-)

So long,
Thomas

Michael Schöberl

2004-06-25, 6:56 pm

> [...]
> While these are completely invertible,
> they typically "destroy" the statistics of the output coefficient and make
> them less compressible than just let the wavelets expand their range and
> compress this expanded range. Thus, even the above works fine, it is
rather
> unpractical and should possibly not be done. Well, I haven't actually
tried,
> so maybe that's the job for a tiny research product.

As I remember they use the warp-around in JPEG-LS to avoid
the expansion after the predictor ... with negligible impact on
the statistics ..

bye,
Michael

Sponsored Links