Digital Image Processing Communication And Media Engineering

DIGITAL IMAGE PROCESSING

Report

On

WALSH-HADAMARD TRANSFORM

Cherukuri Shyam Babu

CME-II
00163536

Cherukuri Shyam Babu CME-2 06/16/02 00163536 0

Digital Image Processing Communication And Media Engineering

Table of Contents
1.Description of Walsh-Hadamard Transform
2.Properties of Hadamard Transform
3.Few Images of Walsh-Hadamard Transform
4.Walsh-Hadamard Transform-I
5.Walsh-Hadamard Transform-II
6.Lossless 2D Discrete Walsh-Hadamard Transform
7.Compatability with WHT
8.Strong Points and Weak Points
9.References

Cherukuri Shyam Babu CME-2 06/16/02 00163536 1

Digital Image Processing Communication And Media Engineering

Walsh-Hadamard Transform

In the Walsh-Hadamard transform the basis functions are based on square or

rectangular waves with peaks of +/- 1. The primary advantage of this transform is that
the computations are very simple. Beyond the simple observation that these two
transform look a lot like each other, Walsh and Hadamard are more strongly related.
In deed, since the walsh transform matrix is a permutation of the Hadamard
transform matrix. Ordered Hadamard as its rows sorted according to the sequency,
or number of transition between +1 and 1, while this is not the case in the walsh
transform. Since one is a permutation of the other, we often hear of the Walsh-
Hadamard transform, even if it is not strictly correct.

Description:

Unlike the other fast transforms, the elements of the basis vectors of the Hadamard
transform take only the binary values +/-1 and are, therefore, well suited for digital
signal processing. The Hadamard transform matrices,Hn , are N x N matrices, where
N= 2n , n = 1,2,3 . These can be easily generated by the core matrix

1 1
H1 = 1
........(1)
1 1
2

and the Kronecker product recursion

1 Hn 1 Hn 1
Hn = Hn-1 H1 = H1 H n-1 = ....(2)
2 Hn 1 Hn 1

As an example , for n=3, the Hadamard matrix becomes

H3 = H1 H2 ....(3)

H2 = H1 H1 .....(4)

Cherukuri Shyam Babu CME-2 06/16/02 00163536 0

Digital Image Processing Communication And Media Engineering

Which gives

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1
H3=
8 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1

Sequence

0
7
3
4
1
6
2
5

The basis vectors of the Hadamard transform can also be generated by sampling a
class of functions called the Walsh functions. These functions also take only the
binary values +/-1 and form a complete orthonormal basis for square integrable
functions. For this reason the Hadamard transform just defined is also called the
Walsh-Hadamard transform.

The number of Zero crossings of a Walsh function or the number of transitions in a

basis vector of the Hadamard transform is called its sequency. Recall that for
sinusoidal signals, frequency can be defined in terms of the zero crossings. In the
Hadamard matrix generated via (2),the row vectors are not sequency ordered. The
existing sequency order of these vectors is called the Hadamard order. The
Hadamard transform of an N x 1 vector u is written as

Cherukuri Shyam Babu CME-2 06/16/02 00163536 1

Digital Image Processing Communication And Media Engineering

V= Hu.......(6)

And the inverse transform is given by

U = Hv........(7)

Where H= Hn, n= log2 N. In series form the transform pair becomes

N 1
1
v (k ) =
N
u (m)(1) b(k,m),
m =0
0<k<N-1........(8)

N 1
1
u(m) =
N
v(k ) (-1)b(k,m), 0<m<N-1......(9)
k =0

Where

n 1
B(k,m) = Ki mi ;
i =0
m i,k i = 0,1

and {Ki } , {Mi } are the binary representations of K and M respectively, that is,

K = K0 + 2K1 + .......+2 n-1 Kn-1

...........(10)
M = M0 + 2M1 + ......+2 n-1 M n-1

Cherukuri Shyam Babu CME-2 06/16/02 00163536 2

Digital Image Processing Communication And Media Engineering

Properties of Hadamard Transform

1. The Hadamard transform H is real, systematic, and orthogonal ,that is,

H = H * = HT= H -1

2. The Hadamard transform is a fast transform. The one-dimensional transform of

Eq (6) can be implemented in O (N log2 N ) additions and subtractions. Since the
Hadamard transform contains +/-1 values, no multiplications are required in the
transform calculations. Moreover , the number of additions or subtractions
required can be reduced from N2 to about N log2 N. This is due to the fact that
Hn can be written as a product of n sparse matrices,

that is,

H = Hn = Hn, n =log2N

where

1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0

0 0 0 0 1 1 0 0

1 0 0 0 0 0 0 1 1
H= ------ N/2 rows
2 1 1 0 0 0 0 0 0

0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0

0 0 0 0 0 0 1 1

Since H contains only two nonzero terms per row, the transformation

V=Hnnu = HH......Hu, n = log2N

Cherukuri Shyam Babu CME-2 06/16/02 00163536 3

 Digital Image Processing Communication And Media Engineering

Can be accomplished by operating H n times on u. Due to the structure of H only N

additions or subtractions are required each time H operates on a vector, giving a total
of Nn = N log2N additions or subtractions.

3. The natural order of the Hadamard transform coefficients turns out to be equal to the
bit reversed gray code representation of its sequency s. If the sequency s has the
binary representation bnbn-1....b1 and if the corresponding gray code is gngn-1.....g1,
then the bit-reversed representation g1g2.....gn gives the natural order. The below
table gives the conversion of sequency s to natural order h, and vice versa, for N=8.
In general,
gk = bk bk+1, k= 1,.....,n-1
gn = bn
hk = gn-k+1

and
gk = hn-k+1
bk = gk bk+1, k=n-1,....,1
bn = gn

give the forward and reverse conversion formulas for the sequency and natural
ordering.

Natural order Binary Gray code of s sequency

representation or reverse binary Sequency
binary representation
representation

h h3h2h1 g3g2g1 =h1h2h3 b3b2b1 s

0 000 000 000 0

1 001 100 111 7
2 011 010 011 3
3 011 110 100 4

Cherukuri Shyam Babu CME-2 06/16/02 00163536 4

Digital Image Processing Communication And Media Engineering

4 100 001 001 1

5 101 101 110 6
6 110 011 010 2
7 111 111 101 5

Few Images of Walsh-Hadamard transform:

Original Image Walsh-Hadamard transform linearly remapped

Walsh-Hadamard transform log remapped

Cherukuri Shyam Babu CME-2 06/16/02 00163536 5

Digital Image Processing Communication And Media Engineering

Cherukuri Shyam Babu CME-2 06/16/02 00163536 6

Digital Image Processing Communication And Media Engineering

LOSSLESS 2D DISCRETE WALSH-HADAMARD TRANSFORM

ABSTRACT
The 64-point separable lossless two dimensional (2D) WHT is composed of the 8-
point lossless one dimensional WHT. The latter is obtained by first ecomposing the
8-point WHT into the 2-point WHTs and second replacing very 2-point WHT by a
adder network. Since the coefficients in the ladder network hen become real, the
advantage of multiplierfree vanishes. This paper therefore roposes a 64-point
nonseparable lossless 2D WHT without multiplication as follows. First the 64-point
separable 2D WHT is decomposed into the 4-point 2D WHTs. Second every 4-point
2D WHT, is replaced by a 2D ladder network which is multiplier-free. It is also shown
that the transform coefficients of the proposed transform are closer to those of the
64-point lossy 2D WHT than those of the 64-point separable lossless 2D WHT.

1. INTRODUCTION
A unified lossless/lossy image coding system is useful for various applications, for
example, medical images, satellite images and images in the art world, since we can
reconstruct
lossy and lossless images from a part and the whole of an encoded data,
respectively. In JPEG, lossless and lossy image coding systems are not unified, that
is, the discrete cosine transform (DCT) coding system is used for lossy reconstruction
and the DPCM coding system is used for lossless reconstruction. The unified
lossless/lossy image coding system can berealized by using the lossless block
transforms [1]-[2], the lossless lapped orthogonal transform [3] or the lossless
wavelet transforms [4]-[8]. In these lossless transforms, integer input signals are
transformed into integer transform coefficients and losslessly reconstructed. The
mean first order entropy of the integer transform coefficients is smaller than that of
input for image compression. The progressive transmission is possible by
transmitting the integer transform
coefficients decomposed into bit planes from significant bit plane to insignificant one
or by transmitting the coefficients from low-frequency component to high-frequency
one. Thanks to International Communications Foundation for funding. Fig. 1. 8-point
WHT.

Cherukuri Shyam Babu CME-2 06/16/02 00163536 7

Digital Image Processing Communication And Media Engineering

In the unified lossless/lossy image coding system, the number of computations is

desired to be small. The 8-pointlossless one dimensional (1D) Walsh-Hadamard
transform(WHT) has multiplications, although the lossy (non-lossless)WHT is
multiplier-free [1]. The reason is that the coefficients in ladder network [9] become
real, when every 2-point WHT into which the normalised 8-point WHT is decomposed
is replaced by a ladder network. On the other hand, the normalized 4-point WHT is
able to be replaced by a ladder network which is multiplier-free[10]. The reason is
that the elements of the normalized 4-point WHT are +0.5 or -0.5. This paper
therefore proposes a 64-point nonseparable lossless two dimensional (2D) WHT
without multiplication as follows. First the 64-point separable 2D WHT is decomposed
into the 4-point 2D WHTs. Second every 4-point 2D WHT is replaced by a 2D ladder
network which is multiplier-free. The compatibility of the lossless transform with the
corresponding lossy transform is desired to be high. That is, the difference between
the transform coefficients of a lossy transform and its lossless version is desired to be
small. We therefore investigate the compatibility of the proposed lossless 2D WHT
with the WHT.

2. LOSSLESS 1D WHT

Cherukuri Shyam Babu CME-2 06/16/02 00163536 8

Digital Image Processing Communication And Media Engineering

The 8-point lossless 1D WHT which we name 1D LWHT is obtained by first

decomposing the 8-point WHT into the 2-point WHTs as shown in fig. 1 and second
replacing every2-point WHT by a ladder network, where the absolute value of the
determinant of the 2-point WHT must be 1 [9]. The 2-point and 4-point ladder
networks are shown in fig. 2, where quantizer, R, represents rounding to the nearest
integer. The coefficients in the ladder network corresponding to the normalized. 2-
point WHT, c1, c2 and c3, are -0.41421, 0.70711 and 0.41421 respectively. Each
number of multiplications. adds and quantizers in the 1D LWHT is then 36. Note that
the advantage of multiplier-free vanishes.

3. LOSSLESS 2D WHT

Now consider a 1D transform S that consists of four 2-point WHTs and an 8-point
transform A as shown in fig. 3. The transform coefficients yi,j of an 8x8 block of
image pixels xi,j

are then given by

where the S is applied in the horizontal direction and ai, j are elements of the A. The
transform coefficients zi,j of an 8x8 block of yi,j are given by

where the S is applied in the vertical direction. Substituting

Cherukuri Shyam Babu CME-2 06/16/02 00163536 9

Digital Image Processing Communication And Media Engineering

On the other hand, the transform coefficients yi,j of an 8x8 block of xi,j , where the A
is applied in the horizontal direction, are given by

The transform coefficients zi,j of an 8x8 block of yi,j , where the A is applied in the
vertical direction, are given by

It is derived from comparing (3) and (6) that applying the S in the vertical direction
after the horizontal direction is equivalent to first applying the 4-point 2D WHT and
second applying the A to its output in the vertical direction after the horizontal
direction.
It is seen from the above result that applying the 8-point 1D WHT in the vertical
direction after the horizontal direction is equivalent to applying the sixteen 4-point 2D

Cherukuri Shyam Babu CME-2 06/16/02 00163536 10

Digital Image Processing Communication And Media Engineering

WHTs three times. The 64-point 2D WHT is shown in fig. 4. The 4-point lossless 2D
WHT is obtained by using {c1=1, c2=-1, c3=1, c4=-1, c5=1, c6=-0.5, c7=0, c8=0.5,
c9=0, c10=-0.5, c11=0, c12=0, c13=-1, c14=-1, c15=1} in the 4-point ladder network.
The number of multiplications, adds, shifts and quantizers of the 4-point lossless 2D
WHT is 0, 11, 2

and 3, respectively. The 64-point lossless 2D WHT which we name 2D LWHT is

obtained by replacing every 4-point 2D WHT by the 4-point lossless 2D WHT. The
number of computations per an 8x8 block of image pixels is shown in table 1. Note
that the number of multiplications of the 2D LWHT is 0.

COMPATIBILITY WITH WHT

In this section the compatibility of the 2D LWHT with the WHT is investigated.
Entropies of the transform coefficients of the 2D LWHT, 1D LWHT, and WHT are
shown in table 2, where the transform coefficients of the WHT are quantized to
integer values. PSNRs [dB] are also shown there, where the transform coefficients
are transformed by the inverse WHT. The six input images are 512x512 and

Cherukuri Shyam Babu CME-2 06/16/02 00163536 11

Digital Image Processing Communication And Media Engineering

8bit/pixel gray scale. It is seen from the table that the compatibility of the 2D LWHT
with the WHT is higher than that of the 1D LWHT. The distribution of the difference
between the transform coefficients of the 2D LWHT or the 1D LWHT and those of the
WHT which are quantized to integer values are shown in table 3. The transform
coefficients of the 2D LWHT are closer to those of the WHT than those of the 1D
LWHT. Relations between PSNR and entropy of the transform coefficients are shown
in figure 5, where the transform coefficients are quantized by uniform quantizers and
then transformed by the inverse WHT. The input is an image Lenna. The
performance of the 2D LWHT is superior to that of the 1D LWHT. The reason for high
compatibility of the 2D

Table 1. Number of computations per an 8x8 block of image pixels.

Table 2. Entropy of transform coefficients (bit/pel, upper

row) and PSNR (dB, lower row) of the images reconstructed
by the inverse WHT.

Cherukuri Shyam Babu CME-2 06/16/02 00163536 12

Digital Image Processing Communication And Media Engineering

LWHT with the WHT is that the number of quantizers is small.

4. CONCLUSION

A 64-point lossless 2D WHT without multiplication was proposed. This is based on

the 4-point lossless 2D WHT that is multiplier-free. It was shown that the transform
coefficients of the proposed transform were closer to those of the WHT than those of
the lossless 1D WHT, and it therefore had high lossy compression efficiency. The
lossless 2D WHT seems to be useful for a unified lossless/lossy image coding
system to which low computation cost is necessary.

Strong Points and Weak Points

As with Walsh transform, the Hadamard transform is really simple to compute; since
we only have additions and subtractions, then we divide by N , which is often a power
of 2 ( which can be efficiently computed with shifts, if we work with integer or fixed
point numbers ).

Hadamard transform is not continuous, and approximation produce strong block and
rectangle artefacts, as with Haar and Walsh transforms.

Cherukuri Shyam Babu CME-2 06/16/02 00163536 13

Digital Image Processing Communication And Media Engineering

REFERENCES

[1] K. Komatsu and K. Sezaki, Reversible Discrete Cosine Transform, in Proc. IEEE
ICASSP98, pp.1769- 1772, May 1998.

[2] K.Komatsu and K.Sezaki, Design of Lossless Block Transforms and Filter Banks
for Image Coding, IEICE Transactions, Vol.E82-A No.8 p.1656-1664, Aug. 1999.

[3] K.Komatsu and K.Sezaki, Design of Lossless LOT and Its Performance
Evaluation, in Proc. IEEE ICASSP2000, pp.2119-2122, June 2000.

[4] K.Komatsu and K.Sezaki, Reversible Subband Coding of Images, in Proc. SPIE
VCIP, vol.2501, pp.676- 684, May 1995.

[5] K. Komatsu and K. Sezaki, Lossless filter banks based on two point transform
and interpolative prediction, in Proc. IEEE ICASSP99, pp.1469-1472, Mar. 1999.

[6] A. Said and W. Perlman, Reversible image compression via multiresolution

representation and predictive coding, in Proc. SPIE VCIP, vol. 2094, pp. 664-674,
Nov. 1993.

[7] A. Zandi, J. D. Allen, E L. Schwartz and M. Boliek, CREW: Compression with

reversible embedded wavelets, in Proc. Data Compression Conf., pp.212-221,
Mar. 1995.

Cherukuri Shyam Babu CME-2 06/16/02 00163536 14

Digital Image Processing Communication And Media Engineering

[8] A. R. Calderbank, I. Daubechies, W. Sweldens and B. Yeo, Lossless image

compression using integer to integer wavelet transforms, in Proc. IEEE ICIP, vol. 1,
pp.596-599, Oct. 1997.

[9] F. Bruekers and A. Enden, New Networks for Perfect Inversion and Perfect
Reconstruction, IEEE JSAC, vol.

[10] no.1. pp.130-137, Jan. 1992. [10]S. Fukuma, K. Ohyama, M. Iwahashi and N.
Kambayashi, Lossless 8-point fast discrete cosine transform using lossless
hadamard transform, IEICE Technical Report, DSP99-103, Oct. 1999. (in Japanese)

[11] Fundamentals Of Digital Image Processing, Prentice-Hall, Anil K.Jain.

Cherukuri Shyam Babu CME-2 06/16/02 00163536 15