FOUR-CHANNEL LIFTING-HOUSEHOLDER-BASED HADAMARD TRANSFORM
Taizo Suzuki
Faculty of Engineering, Information and Systems, University of Tsukuba
Tsukuba, Ibaraki, 305-8573 Japan
Email: taizo@cs.tsukuba.ac.jp
ABSTRACTThis study presents a class of four-channel multiplierless reversible
Hadamard transforms (HTs), called lifting-Householder-based HT(LiftH2 T), for various signal processing and communication applications. This class is obtained by using a lifting-Householder factorization of a particular 4 × 4 symmetric orthogonal matrix and its
application to a four-channel HT. In spite of the simple multiplierless
structure with only nine adders, one shifter, and three process steps,
it basically outperforms the integer HT (IntHT) and lifting-based HT(LiftHT) in the JPEG XR standard at lossy-to-lossless image coding,thanks to its considering the dynamic range and having less rounding
error.

This study presents a class of four-channel multiplierless reversible HTs, called lifting-Householder-based HT (LiftH2 T), forvarious signal processing and communication applications. This
class is obtained by using a lifting-Householder factorization of aparticular 4 × 4 symmetric orthogonal matrix and its application toa four-channel HT. It has only nine adders, one shifter, and three
process steps. LiftH2 T basically outperforms IntHT and LiftHT in
the JPEG XR at lossy-to-lossless image coding in spite of having
one fewer adder and four fewer process steps than LiftHT, thanks to
its considering the dynamic range and having less rounding error.
Notation: IN , ⊗, and P4 respectively denote an N × N (N ∈N, N ̸= 0) identity matrix, the Kronecker product, and a 4 × 4
permutation matrix as follows:Index Terms— Hadamard transform (HT), Householder factorization, lifting factorization, lossy-to-lossless image coding.

10
P4 = 
00

1. INTRODUCTION
The Hadamard transform (HT) [1] is one of the most practical transforms for signal processing and communication applications suchas image compression (coding), image watermarking, face recognition, motion estimation, multicarrier CDMA, and multiband andultra-wideband OFDM [2]. It is often part of popular transforms,
e.g., DCT [3], used in image coding standards such as JPEG [4],H.264/AVC [5], and H.265/HEVC [6]. It has very low computational complexity because it only uses adders (and subtracters) andhas no multipliers, i.e., ±1; when the dynamic range is ignored, it iscalled an integer HT (IntHT). Note however that the dynamic range
should be implemented in the synthesis part for ensuring reversibility, and it is unsuitable for image coding, especially lossless mode.
Sweldens presented a lifting structure [7], which is an identity
matrix with one single nonzero off-diagonal element and a rounding
operation. Since the structure maps integer input signals to integer
output signals, it achieves a reversible transform even if the lifting
coefficient is any value. Also, when the coefficient is a dyadic value
n/2b (b, n ∈ N), it can be implemented by using only adders andshifters [8]. Additionally, thanks to its considering the dynamic
range, it can produce a normalized HT, unlike IntHT. The fourchannel lifting-based HT (LiftHT) [9], which is part of the lapped
transform (LT) of the JPEG XR [10], is a simple reversible transform that consists of only ten adders, one shifter, and seven process
steps. The process step means a set of steps that can be processed inparallel. Since many process steps delay signals, fewer process steps
are desired [11]. We have incorporated the LiftHT in a lifting-based
LT for effective lossy-to-lossless image coding [12].
This work was supported by JSPS Grant-in-Aid for Young Scientists (B),
Grant Number 25820152.

978-1-4799-8339-1/15/$31.00 ©2015 IEEE

2144

0
0
1
0

0
1
0
0


0
0
.
0
1

(1)

2. REVIEW AND DEFINITION
2.1. Hadamard Transforms (HTs)An M ×M (M = 2m , m ∈ N, m ̸= 0) HT matrix HM is expressed
as follows [1]:
[
]
HM
1 HM
2
2
,
(2)
HM = H2 ⊗ H M = √2
2 H M −H M
2

2

where
H1 = 1.

(3)

The HT in Eq. (2) is a normalized HT, and the four-channel case H4
can be simplified as follows (see the top-left of Fig. 1):1
1 1
H4 = 
2 1
1

1
−1
1
−1


1
1
1
= P4 
0
2
0


1
−1
−1
1


1
0
0
0
0 
1
P
1
1  4 0
0
1 −1

1
1
−1
−1

1
−1
0
0

1
−1
0
0

0
0
1
1


0
0 
,
1
−1

(4)

where the scaling 1/2s can be replaced by one-bit shifters.
√e M = M HM is constructed from only
Although IntHT H
adders, i.e., ±1, it is unsuitable for image coding, especially lossless mode, because it ignores the dynamic range. The four-channel

ICIP 2015

Fig. 1. Four-channel HTs (black circles and (≫ 1)s mean adders and one-bit shifters, respectively): (top) normalized HT and IntHT, (bottom)
LiftHT and LiftH2 T.
e 4 = 2H4 is shown at the top-right of Fig. 1. It has eightcase Hadders and two process steps.
On the other hand, a lifting structure [7] can achieve multiplierless reversible HTs and at the same time allow for the dynamic
range. The resulting four-channel LiftHT H4 , which is part of the
LT of the JPEG XR [10], is expressed as (see the bottom-left of Fig.
1),



1 0 0 −1
1 −1 0 0
0  01
0 0
0 1 1
H4 = P4 
0 0 1
0  0
0
1 0
0 0 0
1
0
0
0 1




1 0 0 01 0
0
0
1 0 0 010
0  0 1 0 0
1 0 0
 0 12· 0 0 1 0 0 0
0−1 0 1 1 0
0 0 −10
0 1 0 10 0 0 1




1
0 0 0
1 1 0 01 0
01
− 1 1 0 0 0 1 0 0 0 1 −1 0

2
·
.
 0
1
0
0 1 0 0 0 1 0 0 0
0 0 0 1
0 0
0
1
0
0 0 1
(5)
It has ten adders, one shifter, and seven process steps.
2.2. Lifting-Householder Factorization of Orthogonal Matrix
An M × M Householder matrix HM [uk ] is expressed as follows[13]:
HM [uk ] = IM − 2uk uTk ,(6)

Any M × M orthogonal matrix X can be always factorized into(M − 1) cascading Householder matrices as follows:
X = HM [u0 ] HM [u1 ] · · · HM [uM −2 ] ,where[

u0 u1 · · · uM −2

u0,0
0

 u0,1
u1,1

.
..
=
 ..
.

u
u
0,M −2

1,M −2u0,M −1

u1,M −1uk,1···uk,M −1]Tand uk,l (l = 0, 1, · · · , M − 1) is an arbitrary value that satisfies||uk || = 1. Also, any Householder matrix is identical to its inverse
because it is a symmetric orthogonal matrix, i.e.,(HM [uk ])−1 = (HM [uk ])T = HM [uk ] .

(8)

2145

···
..
.
..
.
···
···



0
..
.
0
uM −2,M −2
uM −2,M −1

HM [uk ] =




αk,0
Ir
0
Ir




..
[β




k,0
.
0
IM −r−10αk,M −1




−αk,0
Ir
0




..
·

,

.
I
0
M
−r−1
−αk,M −1where{
αk,l =
{

(7)

]



.




(10)

Furthermore, Chen and Amaratunga introduced a lifting factorization of an M × M Householder matrix [14]:where[uk = uk,0(9)

βk,l =

1
uk,l
uk,r

0

···

(l = r)(otherwise)−1−2uk,l uk,r(l = r),(otherwise)βk,M −1 ]
IM −r−1

(11)

(12)

(13)

and r for uk,r ̸= 0 is selected. It has 3(M − 1) adders, 3(M −1) multipliers, and three process steps. Consequently, an M × M
orthogonal matrix can be factorized into 3(M − 1) lifting matrices
after being factorized into (M −1) cascading Householder matrices.

Fig. 2. Test images: (left-right) 512 × 512 8-bit grayscale images in [15] (Barbara, Boat, Finger, Goldhill, Lena, and Room) and 1024 × 1024
8-bit clipped grayscale images in [16] (Bike, Cafe, Car, Falls, Sakura, and Woman).

3. FOUR-CHANNEL LIFTING-HOUSEHOLDER-BASEDHADAMARD TRANSFORM (LIFTH2 T)
3.1. Lifting-Householder Factorization of a Particular 4 × 4
Symmetric Orthogonal Matrix
Let Rθ be a rotation matrix with an arbitrary rotation angle θ:
[
] [
]
cos θ
sin θ
c
sθ
Rθ =
= θ
.
(14)
sin θ − cos θsθ −cθ
A particular 4×4 symmetric orthogonal matrix S θ with four rotation
matrices in Eq. (14) is obtained as follows: 2cθcθ s θ
cθ sθ
s2θ
cθ sθ
−c2θ
s2θ
−cθ sθ 
 . (15)S θ = Rθ ⊗ Rθ = cθ sθ
s2θ
−c2θ
−cθ sθ s2θ
−cθ sθ −cθ sθ
c2θ
Since any M × M orthogonal matrix can be factorized into (M − 1)
cascading Householder matrices as described in Sec. 2.2, the symmetric orthogonal matrix S θ in Eq. (15) can be also factorized into
them. Fortunately, the symmetric orthogonal matrix S θ is easily
composed of only a 4 × 4 permutation matrix P4 and a 4 × 4 Householder matrix H4 [uθ ]:S θ = P4 H4 [uθ ] ,

(16)

where
1 [
uθ = √ ±sθ
2

∓cθ

∓cθ

∓sθ

]T

.

(17)

This study selects r = 0 for simplicity though we can select the otherrs. The Householder matrix H4 [uθ ] in Eq. (16) can be factorized
into three lifting matrices as follows:
H4 [uθ ] =10−αθ 1
−α
0
θ
−1 0

0
0
1
0


0
−1
0  00  0
1
0

βθ
1
0
0

βθ
0
1
0



γθ
1
0  αθ0  αθ
1
1

0
1
0
0

0
0
1
0

cθ
,
sθ

βθ = cθ sθ ,and γθ = s2θ .

3.2. Application to Four-Channel Hadamard Transform
A four-channel LiftH2 T can be derived by using the lifting-Householder
factorization of a particular 4 × 4 symmetric orthogonal matrix described in Sec. 3.1. The symmetric orthogonal matrix S θ when
θ = π/4 in Eq. (15) is a special case, i.e., a four-channel HT H4 :


1
1
1
1
1 1 −1
1−1
H4 = S π4 = P4 H4 [u π4 ] = ,(20)
1−1 −1
2 1
1 −1 −1
1
where
]T
1[
±1 ∓1 ∓1 ∓1 .
(21)
2
The following multiplierless lifting structure can be easily derived
without any approximation (see the bottom-right of Fig. 1).
u π4 =

H4 [u π4 ] =
1
0 0
−1 1 0
−1 0 1
−1 0 0


0
−1
0 
0
0  0
1
0



0
0
,
0
1
(18)

(19)

It has nine adders, four multipliers, and three process steps. To
obtain a multiplierless structure, any lifting coefficient with an irrational (floating-point) value must be approximated to a rational(dyadic) coefficient n/2b . The resulting multiplierless structure will
yield fast implementations at the expense of decreasing the performance of the transform.

2146

1
2

1
0
0

1
2

0
1
0

1
2



1
0

 1
0  1
1
1

0
1
0
0

0
0
1
0


0
0
,
0
1

(22)

where
1
.
2
It has only nine adders, one shifter, and three process steps.
α π4 = 1

where
αθ =

Table 1. Number of operations and process steps.
IntHT
LiftHT
LiftH2 T
[1]
[9]
Prop.
Adder
8
10
9
Shifter01
1Multiplier000Process Step
2
7
3
Dynamic Range Ignoring Considering Consideringandβ π4 = γ π4 =(23)

4. EXPERIMENTAL RESULTS
This study compared the four-channel LiftH2 T with IntHT and
LiftHT.
4.1. Number of Operations and Process Steps
Table 1 shows the number of operations and process steps. IntHT
has the fewest operations and process steps, though it ignores the
dynamic range, unlike LiftHT and LiftH2 T. Moreover, LiftH2 T has
one fewer adder and four fewer process steps than LiftHT. Since theprocessing usually uses many HTs, LiftH2 T is efficient even if it
only has one fewer operation or one fewer process step in each HT.
The next subsection will prove that it is efficient.

Test
ImagesBarbaraBoat

FingerGoldhill

Lena

Room

Bitrate
[bpp]
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00

Table 3. Lossy image coding results (PSNR [dB]).
IntHT LiftHT LiftH2 T
Test
Bitrate
IntHT
[1]
[9]
Prop.
Images[bpp][1]25.504 26.696
26.7200.25
23.65629.372 30.422
30.435Bike
0.50
27.68334.823 35.111
35.1361.00
32.45226.824 27.576
27.6050.25
19.05830.400 30.857
30.892Cafe
0.50
22.29434.183 34.350
34.3711.00
26.46322.048 22.893
22.901
0.25
32.52724.743 25.485
25.493Car
0.50
36.44428.713 29.007
29.0451.00
40.81728.360 28.710
28.8560.25
30.23830.860 31.177
31.184Falls
0.50
34.06334.177 34.447
34.4581.00
38.72530.287 31.557
31.5720.25
27.83934.046 35.035
35.066
Sakura0.50
32.41537.513 38.355
38.3801.00
37.39527.300 28.147
28.2030.25
28.63831.922 32.338
32.366
Woman
0.50
31.53237.006 38.528
38.5371.00
35.489

Table 2. Lossless image coding results (LBR [bpp]).
Test
IntHT LiftHT LiftH2 T
Images
[1]
[9]
Prop.
Barbara 8.071
4.823
4.824
8.421
5.140
Boat
5.138
Finger
9.027
5.723
5.721
Goldhill 8.354
5.073
5.067
7.875
4.619
4.615
Lena
Room
7.539
4.362
4.360
Bike
8.402
5.129
5.126
9.304
6.002
6.001
Cafe
Car
7.136
4.003
4.002
7.142
4.059
4.049
Falls
Sakura
7.514
4.341
4.336
8.023
4.767
4.768
Woman

LiftHT although the differences between it and LiftHT were trivial.

This subsection compares the results of different HTs in lossy-tolossless image coding based on the LT of the JPEG XR and a simple
quadtree-based embedded image coder EZW-IP [17] by using thefollowing lossless bitrate (LBR) [bpp] and peak signal-to-noise ratio(PSNR) [dB] in lossy-to-lossless image coding:
Total number of bits [bit]Total number of pixels [pixel]()
2552
PSNR [dB] = 10 log10,
MSE

LiftH2 T
Prop.
24.25529.28033.871
20.21123.36027.52333.62837.23840.85431.40135.18339.84628.25132.33538.62129.16532.06835.723Fig. 3. Particular area of an image Lena reconstructed with different
HTs when the bit rate is 0.25 bpp: (left-right) IntHT, LiftHT in the
JPEG XR, and LiftH2 T.

4.2. Lossy-to-Lossless Image Coding

LBR [bpp] =LiftHT[9]
24.23129.25633.84920.19523.35327.51733.56037.21840.83731.37235.17439.83128.22032.29038.57329.10632.02835.707(24)(25)

where MSE is the mean squared error. A two-level decomposition
for the LT of the JPEG XR was employed, where only the core transform (reversible DCT) was used in the second stage in accordancewith the specification. Six 512 × 512 8-bit grayscale images in [15]and six 1024 × 1024 8-bit clipped grayscale images in [16] wereselected for this experiment (see Fig. 2).
Table 2, Table 3, and Fig. 3 show the results of the losslessand lossy image coding. LiftH2 T basically outperformed IntHT and

2147

5. CONCLUSION
This study presented a four-channel LiftH2 T having only nineadders, one shifter, and three process steps, that was obtained byusing a lifting-Householder factorization of a particular 4 × 4 symmetric orthogonal matrix and its application to a four-channel HT.
Since the processing usually uses many HTs, LiftH2 T is efficienteven if it only has one fewer operation or one fewer process stepin each HT. Moreover, LiftH2 T basically outperformed IntHT and
LiftHT in the JPEG XR at lossy-to-lossless image coding in spite of
having one fewer adder and four fewer process steps than LiftHT,
because it considers the dynamic range and has less rounding error.
It can be used in not only the LT of the JPEG XR but also various
signal processing and communication applications.

6. REFERENCES[1] B. J. Fino and V. R. Algazi, “Unified matrix treatment of thefast Walsh-Hadamard transform,” IEEE Trans. Computers, vol.
C-25, no. 11, pp. 1142–1146, Nov. 1976.
[2] S. Kyochi and Y. Tanaka, “General factorization of conjugatesymmetric Hadamard transforms,” IEEE Trans. Signal Process., vol. 62, no. 13, pp. 3379–3392, July 2014.
[3] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,
Academic Press, 1990.
[4] G. K. Wallace, “The JPEG still picture compression standard,”
IEEE Trans. Consum. Electr., vol. 38, no. 1, pp. xviii–xxxiv,
Feb. 1992.
[5] T. Wiegand, G. J. Sullivan, G. Bjøntegaard, and A. Luthra,“Overview of the H.264/AVC video coding standard,” IEEE
Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560–
576, July 2003.
[6] G. J. Sullivan, J.-R. Ohm, W.-J. Han, and T. Wiegand,“Overview of the high efficiency video coding (HEVC) standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 22, no.
12, pp. 1649–1668, Dec. 2012.
[7] W. Sweldens, “The lifting scheme: A custom-design construction of biorthogonal wavelets,” Appl. Comput. Harmon. Anal.,
vol. 3, no. 2, pp. 186–200, Apr. 1996.
[8] T. Suzuki, S. Kyochi, Y. Tanaka, M. Ikehara, and H. Aso,“Multiplierless lifting based FFT via fast Hartley transform,”in Proc. of ICASSP’13, Vancouver, Canada, May 2013, pp.
5603–5607.
[9] C. Tu, S. Srinivasan, G. J. Sullivan, S. Regunathan, and H. S.
Malvar, “Low-complexity hierarchical lapped transform forlossy-to-lossless image coding in JPEG XR/HD Photo,” inProc. of SPIE, San Diego, CA, Aug. 2008, vol. 7073, pp. 1–
12.
[10] F. Dufaux, G. J. Sullivan, and T. Ebrahimi, “The JPEG XR
image coding standard,” IEEE Signal Process. Mag., vol. 26,
no. 6, pp. 195–199, 204, Nov. 2009.
[11] M. Iwahashi, T. Orachon, and H. Kiya, “Three dimensional
discrete wavelet transform with deduced number of lifting
steps,” in Proc. of ICIP’13, Melbourne, Australia, Sep. 2013,
pp. 1651–1654.
[12] T. Suzuki and M. Ikehara, “Simplified DCT-lifting-based reversible lapped transforms using parallel processing of two
same type lapped transforms,” in Proc. of ICIP’14, Paris,
France, Oct. 2014, pp. 5586–5590.
[13] P. P. Vaidyanathan, Multirate Systems and Filter Banks, Englewood Cliffs, NJ: Prentice Hall, 1992.
[14] Y. J. Chen and K. S. Amaratunga, “M -channel lifting factorization of perfect reconstruction filter banks and reversible
M -band wavelet transforms,” IEEE Trans. Circuits Syst. II,
vol. 50, no. 12, pp. 963–976, Dec. 2003.
[15] “The USC-SIPI Image Database,” Univ. Southern California,
Signal and Image Processing Institute [Online], Available:
http://sipi.usc.edu/database/.
[16] “JPEG core experiment for the evaluation of JPEG XR image
coding,” EPFL, Multimedia Signal Processing Group [Online], Available: http://mmspg.epfl.ch/iqa.

2148[17] Z. Liu and L. J. Karam, “An efficient embedded zerotree
wavelet image codec based on intraband partitioning,” in Proc.
of ICIP’00, Vancouver, British Columbia, Canada, Sep. 2000.