| > Does anyone know the formula of Walsh Transformation,
> both 1-D and 2-D are required.
You'll find the information on Walsh transformations (as well as
related transformations such as Hadamard, Fourier, Discrete Cosine,
etc.) in most books on digital image processing, such as Gonzalez
and Wintz "Digital Image Processing", Addison-Wesley. If you can
find a copy, the book by Sloan and Harwitt "Hadamard Transform Optics"
has a great deal of fascinating and useful info on these transforms.
It would be best to get ahold of one of these books - I could give you
the formulas but these books will have programs as well as detailed
explanations and better typesetting...
- Jim
|
| >You'll find the information on Walsh transformations (as well as
>related transformations such as Hadamard, Fourier, Discrete Cosine,
>etc.) in most books on digital image processing, such as Gonzalez
>and Wintz "Digital Image Processing", Addison-Wesley. If you can
>find a copy, the book by Sloan and Harwitt "Hadamard Transform Optics"
>has a great deal of fascinating and useful info on these transforms.
Thanks a lot
>It would be best to get ahold of one of these books - I could give you
>the formulas but these books will have programs as well as detailed
>explanations and better typesetting...
Could you give me a simple formula here? I may need a few days to get
the books you mentioned above.
- CL
|
| > Could you give me a simple formula here? I may need a few days to get
> the books you mentioned above.
The one dimensional forward and reverse Walsh transformations are
identical, except for a scale factor.
If N is a power of 2, N = 2^n and indices x and y are n bit numbers.
N-1
F(y) = SUM f(x) * K(x,y) / N
x = 0
N-1
f(x) = SUM F(y) * K(x,y)
y = 0
The Walsh kernel is an array of +/- 1, where the sign of the element
at K(x,y) is given by
n-1
K(x,y) = PROD (-)^(b[i](x)*b[n-1-i](y))
I = 0
b[i](x) is the i'th bit in the binary number x.
The 2 dimensional kernels are the tensor product of two one dimensional
kernels, much as for 2D FFT's.
Because the kernel decomposes, you can use divide and conquer to
compute a fast transform in N log N time, the code is just the same
as for an FFT, except you don't have complex roots of unity to worry
about, just adds/subtracts!
It has been a number of years since I played with this stuff, but
I do have some code to do Walsh, FFT, and Hadamard transforms of
images backed up somewhere. It's actually nothing to write home
about, as you can see from these formulas here the code comes out
pretty simple. In fact, it was more work get the images to and from
the display than do the transforms!
If you have difficulty getting the books, I can send a copy of a few
pages from mine - but it's best to look thru the books. There is
a lot of interesting detail and pictures that are hard to communicate
in notes.
By the way, another book well worth getting ahold of is the recent
one by by Kim or Kip (?) and someone else on the Discrete Cosine Transform.
This book has lots of C code, a large bibliography, and is very up to date
(just puplished in 1990.)
Hope this helps for now - the DEC libraries have most of these books.
- Jim
|
| Although it's not immediately apparent from the formula, all the
butterflies in the fast Walsh transform are of the form
x = x + y
y = x - y
The organization of the nested loops is just the same as an FFT,
except that all the computions are nearly trivial - no complex
roots of unity are involved...
- Jim
|