Hadamard transform
In the last blog entry ive mentioned the hadamard transform, so its high time to dissuss it
the hadamard transform is a linear transform, and all linear transforms can be written as a vector-matrix multiplication, here the matrix is orthogonal, symmetric and all it elements are either a or -a. Actually this is commonly written as a matrix of 1 and -1 which is multiplied by a which is sqrt(size of the transform), you also might want to take a look at Wikipedia/Hadamard_transform.
The hadamard transform is also somewhat similar to the DCT but simpler, thats also why its used as part of a SATD motion estimation comparission function, the dct would be slightly better quality wise but significantly slower …
How to calculate it
Well there are many ways
a slow and simple one is:
for(i=0; i<n; i++){
dst[i]=0;
for(j=0; j<n; j++){
int sign= parity(i&j) ? -1 : 1;
dst[i] += src[j] * sign;
}
}
a faster one is:
void transform(int *data, int step, int n){
int i, j;
for(i=0; i<n; i+=2*step){
for(j=i; j<i+step; j++){
int a= data[j];
data[j] = a + data[j+step];
data[j+step] = a - data[j+step];
}
}
if(2*step<n)
transform(data, 2*step, n);
}
You should of course not implement this recursively, but instead remove recursion, unroll the loops where cleanly possible and replace step and n by constants if you can.
Ive just written it like above as its IMHO easier to understand that way then 2 pages of unrolled loops
Look up my fact sheet on the Hadamard Transform where I have presented the in-place algorithm and the out-of-place algorithm and other information. You’ll find it on the news groups somewhere.
Sean O’Connor
Comment by Sean OConnor — 2007-02-11 @ 05:20
I found this very good book about the Walsh Hadamard Transform a few
days ago:
http://www.jjj.de/fxt/
Here is some source code of mine with a novel neural network I dreamed
up:
http://uk.geocities.com/greenpandan/ghostsweeper.zip
Comment by Sean O'Connor — 2007-05-23 @ 14:09
Oh yes. The fact sheet such as it is:
http://groups.google.de/group/comp.ai.genetic/msg/76af84cd88c22c7f?&hl=de&q=hadamard+transform+fact+sheet
I wrote it in a hurry and some people have said it is nearly unreadable, but there are some interesting ideas to follow up for those who can do, those who will do.
Comment by Sean O'Connor — 2007-05-24 @ 09:53
Not a comment, but request, I need more tutorials on Hadamand Transform as well as Fourier Transform in digital image processing. I am student worker, ie, Medical Laboratory Technician as well as final year student of Biomedical Engineering.
Comment by ebo ochir — 2009-04-28 @ 09:01
BinDCT is nice for HW but in SW (given fast SIMD multipliers) a few palalrel muls+adds are usually better than lots of adds+shifts with long dependency chains.Also, after the original BinDCT papers, there’s been some improvements. State of the art (as far as I know) in integer-only DCTs is ISO/IEC 23002-2. See (paper) and (code).The really big win (both HW and SW) is reducing width of arithmetic needed. In HW, you can make each stage just as wide as it needs to be; in SW, if you never have to go >16 bits, that’s very notable (needs less regs *and* saves a lot of ops).
Comment by Kanchan — 2015-12-23 @ 17:37