24
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Hilmar
    Mar 12, 2012 at 17:03
  • $\begingroup$ @DilipSarwate Why is the WHT useful and/or unique? $\endgroup$
    – Spacey
    Mar 12, 2012 at 23:12

6 Answers 6

14
$\begingroup$

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.)

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Spacey
    Jan 17, 2013 at 21:19
  • $\begingroup$ 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. $\endgroup$ Jan 17, 2013 at 21:23
  • $\begingroup$ Eric, can you provide a link to the wikipedia article you cite? If you do, I can accept your answer. $\endgroup$
    – Spacey
    Jan 17, 2013 at 22:15
  • $\begingroup$ Surely. It is en.wikipedia.org/wiki/Hadamard_transform $\endgroup$ Jan 18, 2013 at 0:02
  • $\begingroup$ Eric, I thought it was another source you were referring to. Never mine. :-) $\endgroup$
    – Spacey
    Jan 18, 2013 at 0:05
8
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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? $\endgroup$
    – Spacey
    Mar 12, 2012 at 15:41
6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Spacey
    Mar 14, 2012 at 21:32
  • $\begingroup$ 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. $\endgroup$
    – Charna
    Mar 15, 2012 at 0:15
  • $\begingroup$ 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. $\endgroup$
    – Spacey
    Mar 15, 2012 at 0:51
  • $\begingroup$ 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. $\endgroup$ Mar 15, 2012 at 7:58
2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

I am quite glad to witness a revival around the Walsh-Paley-Hadamard (or sometimes called Waleymard) transformations, see How we can use the Hadamard transform in feature extraction from an image?

They are particular instance of Rademacher functions. They form orthogonal transformations which can, omitting power normalizations, be implemented with only adds and subtracts, and potentially binary shifts. Basically, they require no multiply, allowing fast computations and little fancy floating point needs.

Their vector coefficients are made of $\pm 1$, that mimic a binarized version of sine or cosine bases. The ordering of Walsh vectors is in sequency (instead of frequency) that counts the number of sign changes. They enjoy similar butterfly algorithms for even faster implementation.

Walsh-sequences of length $2^n$ can also be interpreted as instances of a Haar wavelet packet.

As such, they can be used in any application where cosine/sine or wavelet bases are used, with a very cheap implementation. On integer data, they can remain integer, and allow truly lossless transformations and compression (similarly to integer DCT or binary wavelets or binlet). So one can use them in binary codes. They are used in compressive sensing as well.

Their performance is often considered poorer than other harmonic transforms on natural signals and images, because of their blocky nature. However, some variants are still in use like for reversible color transformations (RCT) or low-complexity video coding transforms (Low-complexity transform and quantization in H.264/AVC).

Some literature:

$\endgroup$
-3
$\begingroup$

Some links: Web Page

General description

For Gaussian distribution

Report

$\endgroup$
3
  • $\begingroup$ It's better if you can give an explanation of why each link is good. Even a full title of the linked-to document would be better. $\endgroup$
    – Peter K.
    Jul 17, 2018 at 12:28
  • $\begingroup$ I tried but the forum software was flaking out, hence you get a summary version. If you want to wiki-police style delete everything, by all means do. $\endgroup$ Jul 18, 2018 at 14:49
  • $\begingroup$ I don't think that it is so much "wiki-policing" in this case as trying to maintain a standard on the format of Q&A on this board. Its objective is not to function as a forum. So, the feedback on your contribution is not about deleting it, it is about taking it onboard but also making sure that it conforms to the standard. This is common across the stack exchange network. I would think that it is worth editing the post. $\endgroup$
    – A_A
    Jul 19, 2018 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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