A SIMPLIFIED REALIZATION OF NORMALIZED INTEGER WHT
FOR MULTIPLIERLESS INTEGER DCT
Taizo Suzuki and Masaaki Ikehara
Department of Electronics and Electrical Engineering, Keio University
Yokohama, Kanagawa, 223-8522 Japan
Email: {suzuki, ikehara}@tkhm.elec.keio.ac.jp
ABSTRACT
Walsh-Hadamard transform (WHT) based multiplierless integer discrete cosine transform (IntDCT) has structural regularity even in
short word length lifting coefficients. It, however, cannot apply toimage coding without the quantization part because WHT was implemented by only ±1 adder operations without the normalization
scaling factors. Although we have already presented a normalized
integer WHT (IntWHT) as its solution, it also has many adder operations. In this paper, using a two-dimensional (2-D) separable transform of one-dimensional (1-D) normalized WHT is applied to eachlifting coefficient, we present a more simplified realization of normalized IntWHT with structural regularity for short word length lifting coefficients. Finally, in lossless-to-lossy image coding, IntDCT
based on the proposed IntWHT is validated.
Index Terms— Integer discrete cosine transform (IntDCT), integer Walsh-Hadamard transform (IntWHT), lossless-to-lossy image
coding
1. INTRODUCTION
JPEG [1] based on discrete cosine transform (DCT) is the first standard for still image coding and is limited to only lossy image coding. Although lossless JPEG [2] based on differential pulse code
modulation (DPCM) has been proposed for lossless image coding,each algorithm is required to obtain both lossy and lossless data due
to incompatibility between DCT and DPCM, respectively. On theother hand, JPEG2000 [3] and JPEG XR [4] achieve the unificationof lossy and lossless image coding, which is called lossless-to-lossy
image coding, by a discrete wavelet transform (DWT) and a hierarchical lapped biorthogonal transform (HLBT) constructed by lifting
structures [5] and rounding operations. Nevertheless, these next generation standard cannot decode the existing JPEG data because they
do not have the compatibility with JPEG standard.
Then, an integer DCT (IntDCT) compatible with DCT in JPEG
is required and several IntDCTs have been already proposed [6–9].
However, the conventional IntDCTs generate checker-board artifacts
in short word length lifting coefficients, k/2n (k, n ∈ N), and low
bitrate coding. Such coefficients are extremely desired for a realization of software/hardware of IntDCT.
In this paper, we present a more simplified realization of normalized IntWHT with structural regularity for short word length
This work was supported in part by a Grant-in-Aid for the Japan Society for the Promotion of Science (JSPS) Fellows and a Grant-in-Aid for the
Global Center of Excellence (G-COE) for High-Level Global Cooperation
for Leading-Edge Platform on Access Spaces from the Ministry of Education, Culture, Sport, Science, and Technology in Japan.

978-1-61284-227-1/11/$26.00 ©2011 IEEE

472

Fig. 1. A lifting structure (white circles: rounding operations).

lifting coefficients. Our previous work [10] has already achievedby using a transposition of normalization factors and considering a
two-dimensional (2-D) separable transform of one-dimensional (1D) normalized WHT. This paper improves coding performance bydirect application of a 2-D separable transform of 1-D normalized
WHT to each lifting structure in IntWHT. As result, our IntDCT isvalidated in lossless-to-lossy image coding.
Notations: I is an identity matrix, MT is a transpose of matrix
M and M[N ] is an N × N square matrix, respectively. Also, forsimplicity, M = 2m (m ∈ N).
2. REVIEW
2.1. Multiplierless Lifting Structure
The lifting structure [5], also known as the ladder structure, is a
special type of lattice structure, a cascading construction using
only elementary matrices - identity matrices with single nonzero
off-diagonal element.
Fig. 1 shows a basic lifting structure. In this case, the lifting
matrix and its inverse matrix are as follows:




−1 
1 −T
1 T
1 T
=
,
0
1
0 1
0 1
where T is lifting coefficient. Then, they are represented byyi = xi + round[T xj ]z = yi − round[T yj ] = xi
→ izj = yj = xj
yj = x j
where round[.] is a rounding operation. Thus the lifting structurewith rounding operation can achieve lossless-to-lossy coding.
For high-speed implementation, lifting coefficients are required
to approximate floating-point to hardware-friendly dyadic values
such as k/2n (k, n ∈ N) which can be implemented by only bit
shift and addition operations. It performs fast implementation in a

DSP/SPE 2011

Fig. 2. An approximation from floating multiplication to bit shift
and addition operations.

real time software encoder and reduces the circuit size. The multiplications are expressed by k/2n which is n-bit word length. For
example, a coefficient 49/28 = 49/256 can be operated as
1
1
32
16
1
1
49
=
+
+
= 3 + 4 + 8.
256
256
256
256
2
2
2

(1)

From (1), we can replace the multiplier by 49/256 to sum resultsfrom 3-bit shift, 4-bit shift and 8-bit shift operations as illustrated inFig. 2. We can find that the perfect reconstruction in lifting structureis always kept even if lifting coefficients are approximated.
2.2. Regularity
In filter bank (FB) included DCT theory, the regularity is an important property for image compression [11]. An M -channel DCT has
one regularity condition if DCT matrix C[M ] satisfies⎡⎤⎡ ⎤ ⎡√ ⎤
1
1
M
−1
⎢ z
⎢1⎥ ⎢ 0 ⎥⎥⎢⎥⎥[M ] ⎢[M ] ⎢ ⎥
(2)
=C
C
⎢
⎥
⎢ .. ⎥ = ⎢ . ⎥ .
..
.
⎣
⎦
⎣
⎦
⎣
.
.
. ⎦
1
0
z −(M −1) z=1
The conventional IntDCTs generate checker-board artifacts in shortword length lifting coefficients, k/2n , and low bitrate coding due tolosing regularity condition. However, IntDCT by Chen [8] generates
no artifacts even in such case because it has structural regularity.
3. SIMPLIFIED MULTIPLIERLESS INTDCT BASED ON
NORMALIZED INTWHT
3.1. Multiplierless IntDCT based on WHT

Fig. 3. 8-channel IntDCT based on WHT (white circles and white
triangles: rounding operations and −1 operations, respectively).

Table 1. Lifting coefficients of 8-channel IntDCT based on WHT.
floating-point
k/23
k/24
k/25
k/26
α0
0.1989123674. . .
1/4
3/16
3/16
13/64
-3/8
-3/8
-3/8
-3/8
β0 -0.3826834324. . .
α1 -0.6681786379. . .
-5/8-11/16 -21/32 -43/64
β10.9238795326. . .
7/8
15/16
15/16
59/64
α2 -0.6681786379. . .
-5/8-11/16 -21/32 -43/64
0.9238795326. . .
7/8
15/16
15/16
59/64
β2
α3 -0.8206787908. . .
-7/8-13/16 -13/16 -53/64
0.9807852804. . .
1
1
31/32
63/64
β3
α4 -0.3033466836. . .
-1/4
-5/16
-5/16
-19/640.5555702330. . .
1/2
9/16
9/16
9/16
β4

where P is a permutation matrix and Q is an orthogonal matrix.
Using this factorization, Chen has proposed an IntDCT [8]. Fig. 3
and Table 1 show 8-channel IntDCT based on WHT by Chen andits lifting coefficients, respectively. In this regard, however, this
IntDCT by Chen is ill-suited for lossless image coding because it
needs a quantization part due to use of unnormalized WHT. On theother hand, we find that (2) is represented by⎡ ⎤⎡ ⎤ ⎡√ ⎤1
1
M⎢ 1⎥⎢1 ⎥ ⎢ 0 ⎥
⎢
⎥
⎥
⎥
⎢
⎢
C[M ] ⎢ . ⎥ = Ŵ[M ] ⎢ . ⎥ = ⎢ . ⎥⎣ .. ⎦⎣ .. ⎦ ⎣ .. ⎦1
1
0

As well known, WHT has interesting relationships with other discrete transforms such as DCT. It is expressed by
11W[1] = 1 , W[2] =
1 −1

M
M
M
W[ 2 ]
W[ 2 ]
W[M ] =W[2] ⊗ W[ 2 ] =(3)MM
W[ 2 ] −W[ 2 ]where Ŵ[M ] is the pre-processing part in DCT. This means that
WHT satisfies all regularity condition in DCT. Hence, similar to ourprevious work [10],√this paper solves the normalization problem of
WHT: Ŵ[8] = (1/ 8)W[8] , in IntDCT by Chen while keeping theother part as it is.

where ⊗ is Kronecker product.
Note that (3) is still not normalized
√
M
.
Let
us normalize W such that Ŵ =by thescalingfactor1/√(1/ M )W is an orthonormal matrix: Ŵ−1 = ŴT . Then one canprove that [8]We have presented a multiplierless IntDCT based on normalized IntWHT [10]. First, a 2-D separable transform of 1-D DCT C is considered. When we apply C into a 2-D input signal x in column- androw-wise separately, the 2-D separable transform is expressed by

T

C[M ] = Q̂[M ] Ŵ[M ] = P[M ] Q[M ] P[M ] Ŵ[M ]

(4)

473

3.2. A Realization of Normalized IntWHT

y = (C(Cx)T )T = CxCT

(5)

Fig. 4. 1-D transform of normalized IntWHT (white circles: rounding operations).

Table 2. Comparison of coding gain (CG [dB]).
Lifting coefficients k/23 k/24 k/25 k/26 float
Tran’s [6]
6.14
6.21
6.23
6.22
6.23
7.98
8.41
8.75
8.75
8.83
Hao’s [7]
8.08
8.61
8.72
8.75
8.76
Chokchaitam’s [9]
8.73
8.82
8.82
8.82
8.83
Previous work [10]Prop. IntDCT
8.73
8.82
8.82
8.82
8.83

3.4. Expansion from Normalized IntWHT to IntDCT
where y is the output signal. Since the transform C can be factorized
as C = Q̂Ŵ in (4), (5) is represented by
y = Q̂Ŵx(ŴQ̂)T = Q̂ŴxŴT Q̂T .
This equation means that 2-D separable transform by Q̂ is applied
after 2-D separable transform by Ŵ.
Next, we consider to process two individual signals xi and xj
by normalized WHT Ŵ as shown in the left part of Fig. 4. The
output signals are transformed by
 
  
xi
yi
Ŵ 0
=
.
(6)
yj
0 Ŵ xj
diag{Ŵ, Ŵ} in (6) can be factorized into the complete lifting
structures such as
 





I
0 I −Ŵ
I
0
0
I
Ŵ 0
=
(7)
−I 0 Ŵ I 0
I
Ŵ I
0 Ŵ
where ŴŴ = I.
Thus the parallel block system of normalized WHTs can be implemented as shown in the right part of Fig. 4. However, if Ŵ is anormalized WHT with nonideal coefficients, the system in (7) cannot be consisted because of ŴŴ = I. It means short word length
allocation cannot be applied to lifting coefficients. In [10], using atransposition of normalization factors and considering a 2-D separable transform of 1-D normalized WHT as shown in Fig. 5(a), theproblem has been solved.
3.3. A More Simplified Realization of Normalized IntWHT
In this paper, we consider that Ŵ is applied to an M × M input
signal x in column- and row-wise separately in each lifting structure.
If W(x) is defined as
W(x)  ŴxŴT =(7) is represented by


W(x)
0
0
W(x)


0
I
I
=
−I 0 W(x)1
WxWT ,
M

Finally, the normalized IntWHT is applied to the pre-processing partin IntDCT. In that time, Q̂[M ] as post-processing is implemented as
it is. This IntDCT has structural regularity because the normalized
IntWHT has structural regularity. In this paper, M is 8 and all transform coefficients exclusive of ones in WHT are used ones in [10].
4. RESULTS
4.1. Coding Gain and Frequency Response
Coding gain is one of the most important factors to be considered
in compression applications. A transform with higher coding gain
compacts more energy into a fewer number of coefficients. As a result, higher objective performances such as PSNR would be achieved
after quantization. Since coding gain of the DCT approximates the
optimal KLT closely, it is desired that the our IntDCT has similar
coding gain to that of the original DCT. The biorthogonal coding
gain CG is defined as [11]σx222k=0 σxk  fk 

CG [dB] = 10 log10 M −1

where σx2 is the variance of the input signal, σx2k is the variance of
the k-th subbands and  fk 2 is the norm of the k-th synthesis
filter. Table 2 shows the comparison of coding gain of the proposed
IntDCT and the conventional ones. It is clear that coding gains of
the conventional IntDCTs are not kept in short word length lifting
coefficients, but the proposed IntDCT almost kept it even in 4-bit
word length lifting coefficients.
Frequency responses of the proposed and conventional IntDCTs are shown in Fig. 6. It is clear that the conventional IntDCTs have DC leakage which may generate a checker-board artifact
in low bitrate coding. The proposed IntDCT does not have DC leakage because regularity in the proposed normalized IntWHT as preprocessing in IntDCT can be always kept in short word length lifting
coefficients. Also, although Tran’s BinDCT [6] without the scaling
factors do not have DC leakage, it shows worse coding gain than others. Thus, it is deselected from a target for comparison in losslessto-lossy image coding.
4.2. Lossless-to-Lossy Image Coding

0
I



I
0

−W(x)
I



I
W(x)


0
.
I

As result, the normalized IntWHT can be constructed by only
log2 M -bit shifts and ±1 adder operations without losing structural
regularity. Also, since lifting structures are reduced by half in caseof our previous work [10] as shown in Fig. 5(b), it is obvious that3M 2 adder operations are eliminated.

474

The proposed IntDCT is applied to lossless-to-lossy image coding.
twenty test images, which have 512 × 512 size, were used. The set
partitioning in hierarchical trees (SPIHT) progressive image transmission algorithm [12] was used to encode the transformed images.
The comparison of lossless bitrate (LBR)
LBR [bpp] =Total # of bits [bit]Total # of pixels [pixel]

(a)

(b)
Fig. 5. 2-D separable transform of normalized IntWHTs (white circles and .T : rounding operations and a transpose of .): (a) our previous
work [10], (b) the proposed IntWHT.

Fig. 6. Frequency responses in 4-bit word length lifting coefficients: (left) Hao’s [7], (middle) Chokchaitam’s [9], (right) the proposed
IntDCT.

signal-to-noise ratio (PSNR)

Table 3. Comparison of lossless image coding in 4-bit word length
lifting coefficients (LBR [bpp]).
Images[7][9][10] Prop.
Baboon 6.84 6.35 6.28
6.27
Barbara 5.88 5.14 5.02
4.97
6.19 5.34 5.22
5.19
Boat
6.31 5.42 5.27
5.24
Elaine6.07
Finger1 6.48 6.10 6.08
Finger2 6.45 5.92 5.87
5.85
5.16
Goldhill 5.89 5.28 5.18
6.52 6.22 6.18
6.17
Grass
Lena
5.89 4.87 4.68
4.64
6.05 5.13 4.98
4.95
PepperAvg.
6.23 5.54 5.43
5.40


PSNR [dB] = 10 log10

2552
MSE



where MSE is the mean squared error in lossy image coding areshown in Table 4. Furthermore, Fig. 7 shows the enlarged images of“Lena” which are lossy compressed images by the proposed IntDCT
and the conventional ones with 4-bit word length lifting coefficients
when bitrate is 0.25[bpp].
In Table 3, 4 and Fig. 7, the proposed IntDCT presents better
performance than the conventional ones in lossless-to-lossy image
coding. Also, in Fig. 7, we can find that a checker-board artifact is
not generated in the proposed IntDCT due to structural regularity.
5. CONCLUSION
This paper presents a more simplified realization of normalized integer Walsh-Hadamard transform (IntWHT) for multiplierless integer
discrete cosine transform (IntDCT). It is obtained by considering that
normalized WHT is applied to an input signal in column- and rowwise separately in each lifting structure. It has not only structural
regularity even in short word length lifting coefficients, but also lessadder operations and better performance than our previous work. It

in lossless image coding is shown in Table 3 where Avg. is averageof LBRs in twenty images.
If lossy compressed data is required, it can be achieved by interrupting the obtained lossless bit stream. The comparison of peak475

Fig. 7. Comparison of lossy reconstructed images “Lena” in 4-bit word length lifting coefficients (bitrate: 0.25 [bpp]): (left)-(right) Hao’s [7],Chokchaitam’s [9], our previous work [10] and the proposed IntDCT.

[4] ISO/IEC 29199-2, JPEG XR image coding system - Part 2:
Image coding specification.

Table 4. Comparison of lossy image coding in 4-bit word length
lifting coefficients (PSNR [dB]).
Imagesbitrate [bpp]
[7]
[9]
[10]
Prop.
Barbara0.25
23.78 26.49 26.92 26.94
25.95 29.99 30.64 30.66
0.50
29.71 35.04 35.77 35.95
1.00
Boat
0.25
23.21 28.14 28.61 28.63
0.50
25.17 31.21 31.79 31.85
28.63 34.54 35.26 35.43
1.00
Finger1
0.25
20.96 22.19 22.53 22.53
22.90 25.28 25.53 25.54
0.50
26.43 29.31 29.55 29.60
1.00
Goldhill
0.25
25.37 28.88 29.34 29.37
27.20 31.42 31.87 31.94
0.50
30.69 34.56 35.11 35.29
1.00
Lena
0.25
24.14 31.37 31.79 31.84
26.31 34.22 35.45 35.50
0.50
1.00
30.17 37.03 38.54 38.98
Pepper
0.25
24.22 31.05 31.35 31.39
26.52 33.17 34.35 34.39
0.50
30.53 35.68 36.59 36.86
1.00[5] W. Sweldens, “The lifting scheme: A new philosophy inbiorthogonal wavelet constructions,” in Proc. of SPIE 2569,
1995.
[6] T. D. Tran, “The BinDCT: fast multiplierless approximationof the DCT,” IEEE Signal Process. Lett., vol. 7, no. 6, pp.
141–144, June 2000.
[7] P. Hao and Q. Shi, “Matrix factorizations for reversible integer
mapping,” IEEE Trans. Signal Process., vol. 49, no. 10, pp.
2314–2324, Oct. 2001.
[8] Y. J. Chen, S. Oraintara, T. D. Tran, K. Amaratunga, and T. Q.
Nguyen, “Multiplierless approximation of transforms withadder constraint,” IEEE Signal Process. Lett., vol. 9, no. 11,
pp. 344–347, Nov. 2002.
[9] S. Chokchaitam and M. Iwahashi, “A new optimum-wordlength-assignment (OWLA) multiplierless integer DCT for
unified lossless/lossy image coding,” in Proc. of IWAIT’07,
Bangkok, Thailand, Jan. 2007.
[10] T. Suzuki and M. Ikehara, “Structurally regular integer discrete cosine transform for low-bit-word-length coefficients,” inProc. of ISCAS’10, Paris, France, June 2010.
[11] G. Strang and T. Nguyen,
Wavelets and Filter Banks,
Wellesley-Cambridge Press, 1996.

was proved by the comparisons of coding gains, frequency responses
and lossless-to-lossy image coding simulations.

[12] A. Said and W. A. Pearlman, “A new, fast, and efficient image
codec based on set partitioning in hierarchical trees,” IEEE
Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 243–250,
June 1996.

6. REFERENCES[1] ISO/IEC 10918-1, Information technology - Digital compression and coding of continuous-tone still images Requirements
and Guidelines.
[2] ISO/IEC 14495-1, Information technology - Lossless and nearlossless compression of continuous-tone still images: Baseline.
[3] ISO/IEC 15444-1, Information technology - JPEG 2000 image
coding system: Core coding system.

476