matlab - How we can use the Hadamard transform in feature extraction from an image?

Which coefficients of the Hadamard transform contain the highest energy compaction? Is there any regular pattern in them as for the DCT?

Answer

The Hadamard transform is a linear and orthogonal transformation. It belongs to a wider class, under the names of Paley, Walsh, Rademacher and Hadamard. The ordering of the rows or columns of an Hadamard matrix is not well suited to a frequencial interpretation, notably because of the standard recursive definition (for Hadamard matrices of order $2^m$):

$$H_m = \frac{1}{\sqrt2} \begin{pmatrix} H_{m-1} & H_{m-1} \\ H_{m-1} & -H_{m-1} \end{pmatrix}$$

It is illustrated in the center matrix of the picture below. However, the Walsh ordering (right most matrix) order the rows by the number of sign changes in the sequence (transition between the green and the red): the first row is of constant sign, the second one has only one sign change, etc. It can be interpreted as related to the sign of a basic vector of the DCT (roughly), and then has "regular patterns". One then talks about the notion of sequency instead of frequency.

Basically, Hadamard and Walsh have the same compaction properties, in the sense of the $\ell_0$ count: for each coefficient with some energy in Hadamard, there is a coefficient with the same energy in Walsh.

However, for real data, the high energy coefficients tend to be scattered for Hadamard, and better localized toward some sequency band for Walsh. For low-sequency signals, Walsh can be equipped with a zig-zag like ordering.

The quality of compaction depends on the data. For checkerboard-like patterns, Walsh-Hadamard can be better than the DCT. For a Gaussian white noise, both would perform equally (as for any orthogonal transform). For correlated signals, esp. whose autocorrelation can be modelled by an simple autoregressive model, the DCT tends to perform better. The relative performance of the DCT wrt Haar, Fourier, Walsh-Hadamard and Karhunen-Loève transforms is assessed for instance since Discrete Cosine Transfom, Ahmed et al., 1974. The DCT enjoys a close to optimal (Karhunen-Loève) performance, while retaining fast algorithm. You could find an adapted ordering for Hadamard, to keep the high-energy coefficients, but using Walsh is more convenient, as coefficients will tend to group in blocks, more than with Hadamard.

Finally, when even faster is needed, especially when the data is mildly correlated, Walsh or close-to-Walsh transforms (requiring no multiply) are quite effective (for instance in the residue after block prediction in video compression).