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