[XviD-devel] Hadamard Transform

[Christoph Lampert]

On Thu, 5 Sep 2002, Marc FD wrote:
> > since so many people seem to be good at programming and ASMing (and I am
> > not): Could you try and tell me how much work calculation of
> >
> > Hadamard's transform (e.g.
> >
> http://www.iro.umontreal.ca/~pigeon/science/ondelettes/Hadamard/Hadamard.htm
> l
> > )
> >
> > is compared to fDCT and/or SAD?
> >
> > Hadamard is used in H.26L as apporoximation for DCT, when information on
> > transformed coefficients is needed, but DCT itself is too slow
> > (e.g. mode decision). If it's good and fast, it would come handy in
> > advanced adaptive quantization, too.
> >
> 
> argh ! i'm only 17. my math basics are to weak to understand this :(


You don't need much maths, honestly! Not for Hadamard Transform... look at
the URL I wrote up there (don't forget the 'l' in '.html'): There's a
"butterfly", the GIF with red and blue lines. 
That can be understood easily with only + and -, and programmed just as
well. And because it uses only + and -, it's alsa much easier and possibly
faster than DCT (dicrete cosine transformation). 



Take eight bytes (e.g. one column of an 8x8 block) with values a to h
(so a is a value between 0 and 255, b is a value between 0 and 255 etc.) 

a
b
c
d
e
f
g
h

Then you want to calculate the "Hadamard transform" of those bytes, which
is again 8 bytes, called then a', b', c' ... to h' , with the values 

a'  =  (a + b + c + d + e + f + g + h) /8
b'  =  (a + b + c + d - e - f - g - h) /8
c'  =  (a + b - c - d - e - f + g + h) /8
d'  =  (a + b - c - d + e + f - g - h) /8
e'  =  (a - b - c + d + e - f + g - h) /8
f'  =  (a - b - c + d - e + f + g - h) /8
g'  =  (a - b + c - d - e + f - g + h) /8
h'  =  (a - b + c - d + e - f + g - h) /8

Voila, the first Hadamard transform is finished. 
This you have to do for all the eight columns of an 8x8 block. 
You end up with 8 new columns, again it's an 8x8 block. 

Now do the same, but this time for the rows of this new block
instead of columns. Each step gives you a new row. 
Again you end up with an 8x8 block, which is the 

"Twodimensional Hadamard-Transform" of the block you started with.

The only problem is: To get this transform, you needed to calculate 
2*(8*(7) operations (2 for the dimensions, the 8 because you had to
go through all the rows or columns, the 7 because you had to add/subtracts
the values from a to h). I don't count the dividing by eight, for the
moment. 

The big quenstion is: Can it be done faster? And the answer is of course
"Yes" and the red-blue butterfly shows a nice way of doing it: 
Instead of calculating the big a+b-c+d-e+... etc in one step, 
calculate intermedia results and reuse them in the right way. 
>From the butterfly you can see how the original data is to be combined and
if you should add together them (blue) or subtract them (red) from each
other. 

Then you count the endpoints of red and blue lines, you see you get one
step of Hadamard transform with 24 add/subtract operations instead of
7*8=56 in the first case. Not bad. 

Now the real fun starts when you do this with MMX/XXM... then operation
for several rows/column can be done simultanously. But that's what you
know better than me, I guess...


gruel