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