Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

I am trying to teach myself about the WHT but there dont seem to be many good explanations of it online anywhere. I think I have figured out how to calculate the WHT, but I am really trying to understand why it is considered useful within the image recognition domain.

What is so special about it, and what properties does it bring out in a signal that would not show up on classical Fourier transforms, or other wavelet transforms? Why is it useful for object recognition as pointed out here?

share|improve this question
    
One application is measurement systems that use Maximum Length Sequences (MLS) as an excitation (e.g. mlssa.com). It's supposed to be faster since no multiplies are required. In practice it's not much of a benefit and the MLS have other problems –  Hilmar Mar 12 '12 at 17:03
    
@DilipSarwate Why is the WHT useful and/or unique? –  Mohammad Mar 12 '12 at 23:12
add comment

4 Answers

up vote 8 down vote accepted

NASA used to use the Hadamard transform as a basis for compressing photographs from interplanetary probes during the 1960's and early '70s. Hadamard is a computationally simpler substitute for the Fourier transform, since it requires no multiplication or division operations (all factors are plus or minus one). Multiply and divide operations were extremely time intensive on the small computers used on board those spacecraft, so avoiding them was beneficial both in terms of compute time and energy consumption. But since the development of faster computers incorporating single-cycle multipliers, and perfection of newer algorithms such as the Fast Fourier Transform, as well as the development of JPEG, MPEG, and other image compression, I believe Hadamard has fallen out of use. However, I understand it may be staging a comeback for use in quantum computing. (NASA use is from an old article in NASA Tech Briefs; exact attribution unavailable.)

share|improve this answer
    
Fantastic historical account Mr Peters, thank you for it. Can you expand on what/how you mean that it might be staging a come back in quantum computing? In what way do you allude to it in your post? –  Mohammad Jan 17 '13 at 21:19
    
According to an article in Wikipedia, many quantum algorithms use the Hadamard transform as an initial step, since it maps n qubits to a superposition of all 2n orthogonal states in the quantum basis with equal weight. –  Eric Peters Jan 17 '13 at 21:23
    
Eric, can you provide a link to the wikipedia article you cite? If you do, I can accept your answer. –  Mohammad Jan 17 '13 at 22:15
    
Surely. It is en.wikipedia.org/wiki/Hadamard_transform –  Eric Peters Jan 18 '13 at 0:02
    
Eric, I thought it was another source you were referring to. Never mine. :-) –  Mohammad Jan 18 '13 at 0:05
add comment

The coefficients of the Hadamard transform are all +1 or -1. The Fast Hadamard Transform can therefor be reduced to addition and subtraction operations (no division or multiply). This allows the use of simpler hardware to calculate the transform.

So hardware cost or speed may be the desirable aspect of the Hadamard transform.

share|improve this answer
1  
Thanks for the answer but I would like to understand the transform please? I dont care right now about fast-implementation. What is this transform? Why is it useful? What insight does it give us VS other wavelet transforms? –  Mohammad Mar 12 '12 at 15:41
add comment

Take a look at this paper if you have access, I've pasted the abstract here Pratt, W.K.; Kane, J.; Andrews, H.C.; , "Hadamard transform image coding," Proceedings of the IEEE , vol.57, no.1, pp. 58- 68, Jan. 1969 doi: 10.1109/PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Abstract The introduction of the fast Fourier transform algorithm has led to the development of the Fourier transform image coding technique whereby the two-dimensional Fourier transform of an image is transmitted over a channel rather than the image itself. This devlopement has further led to a related image coding technique in which an image is transformed by a Hadamard matrix operator. The Hadamard matrix is a square array of plus and minus ones whose rows and columns are orthogonal to one another. A high-speed computational algorithm, similar to the fast Fourier transform algorithm, which performs the Hadamard transformation has been developed. Since only real number additions and subtractions are required with the Hadamard transform, an order of magnitude speed advantage is possible compared to the complex number Fourier transform. Transmitting the Hadamard transform of an image rather than the spatial representation of the image provides a potential toleration to channel errors and the possibility of reduced bandwidth transmission.

share|improve this answer
    
Thanks for this link, I will certainly read it, but it might take some time. Just from the abstract, it seems that the Hadamard Transform is being able to be used as a ... substitute?... for the Fourier transform, in part because it is computationally very efficient, but for perhaps another reason as well? What was your general take on this? –  Mohammad Mar 14 '12 at 21:32
    
Using the hadamard transform we are able to transmit a coded version of the image and then reconstruct it at the receiver. In this particular case the author is using the transform in order to concentrate the energy of the signal in a more narrow band than the original image so it is less effected by noise and can be reconstructed by using the inverse hadamard at the receiver. –  Charna Mar 15 '12 at 0:15
    
Hmm, yes, I just finished reading the paper - it seems like the Hadamard transform is just a faster alternative to the fourier transform, but nothing else really stands out. It conserves energy, and entropy etc, but more or less seems to be just like the FFT. –  Mohammad Mar 15 '12 at 0:51
    
Does Hadamard Transform do good enough (even if not better) job against other transform like DFT or even DCT. Being fast is good, but can it really do as good compression as say DCT is real question. Most conventional standards JPEG, MPEGx don't quite use it BTW. –  Dipan Mehta Mar 15 '12 at 7:58
add comment

Would like to add that any m-transform (Toeplitz matrix generated by an m-sequence) can be decomposed into

P1 * WHT * P2

where WHT is the Walsh Hadamard Transform, P1 and P2 are permutations (ref: http://dl.acm.org/citation.cfm?id=114749).

m-transform is used for a number of things: (1) system identification when the system is plagued with noise and (2) by virtual of (1) identify phase lag in a system that is plagued with noise

for (1), m-transform recovers the system kernel(s) when the stimulus is a an m-sequence, which is useful in neurophysiology (e.g. http://jn.physiology.org/content/99/1/367.full and others) because it is high power for a wide-band signal.

For (2), Gold code is constructed from m-sequences (http://en.wikipedia.org/wiki/Gold_code).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.