IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.4 APRIL 2010

734

PAPER

Integer Discrete Cosine Transform via Lossless Walsh-Hadamard
Transform with Structural Regularity for Low-Bit-Word-Length
Taizo SUZUKI†a) , Student Member and Masaaki IKEHARA† , Member

SUMMARY
This paper presents an integer discrete cosine transform(IntDCT) with only dyadic values such as k/2n (k, n ∈ N). Althoughsome conventional IntDCTs have been proposed, they are not suitable forlossless-to-lossy image coding in low-bit-word-length (coeﬃcients) due tothe degradation of the frequency decomposition performance in the system. First, the proposed M-channel lossless Walsh-Hadamard transform(LWHT) can be constructed by only (log2 M)-bit-word-length and has
structural regularity. Then, our 8-channel IntDCT via LWHT keeps goodcoding performance even if low-bit-word-length is used because LWHT,
which is main part of IntDCT, can be implemented by only 3-bit-wordlength. Finally, the validity of our method is proved by showing the resultsof lossless-to-lossy image coding in low-bit-word-length.
key words: integer discrete cosine transform (IntDCT), dyadic values, lowbit-word-length, lossless Walsh-Hadamard transform (LWHT), lossless-tolossy image coding

1.

Introduction

Multimedia coding (compression) standards such as JPEG
[1] and MPEG [2] use the discrete cosine transform (DCT)[3] which has excellent properties, several types and many
fast algorithms [4]–[7]. In JPEG, DCT type-II (DCT-II)
and -III (DCT-III), which is the inverse transform of DCT-II,
are applied to lossy image coding, and the diﬀerential pulse
code modulation (DPCM) is applied to lossless image coding. We have to prepare lossy and lossless compressed data
separately according to application.
Recently, high speed transmission of high quality data
has become very desirable due to the advances in Internet
and multimedia contents. Several integer DCTs (IntDCTs),
which are constructed by lifting structures [8] and rounding operations based on DCT-II, have been proposed forlossless-to-lossy image coding [9]–[14]. For example, [9]and [10] have presented the 8-channel IntDCTs composedof the integer rotation transforms (IRTs), the 4-channel integer DCT type-IV (IntDCT-IV) and the 4-channel integer
Hadamard transforms (IHTs) etc. But, they require both
floating-point coeﬃcients and rounding operations. Then,[11], [12] and [13] have presented the low cost 8-channel
IntDCTs which are easy to implement because they do
not require floating-point coeﬃcients. However, [11] and[12] can not be used for lossless image coding due to nonconsideration of dynamic range and [13] is not suitable for
Manuscript received September 24, 2009.
Manuscript revised November 4, 2009.
†
The authors are with the Department of Electronics andElectrical Engineering, Keio University, Yokohama-shi, 223-8522
Japan.
a) E-mail: suzuki@tkhm.elec.keio.ac.jp
DOI: 10.1587/transfun.E93.A.734

lossless image coding in low-bit-word-length (coeﬃcients)
due to its construction. Although [14] is not only inexpensive in terms of hardware complexity but also operates wellin lossless-to-lossy image coding due to the optimum-wordlength-assignment (OWLA) of coeﬃcients, it requires ahigher-bit-word-length in some lifting structures and yields
DC leakage.
In image coding, IntDCT should not have huge dynamic range of the output signals and DC leakage. Huge
dynamic range requires many bits and DC leakage generates
a checker-board artifact in low bit rate in lossy image coding. On the other hand, for high-speed implementation, it
is required to approximate floating-point lifting coeﬃcientsto hardware-friendly dyadic values such as k/2n (k, n ∈ N)
which can be implemented by only bit-shift and addition operations. If lower-bit-word-length is allocated to every lifting coeﬃcients, it is ideal for real hardware. However, theconventional IntDCTs generate a checker-board artifact in
low-bit-word-length.
In this paper, we propose an IntDCT via LWHT withstructural regularity even if low-bit-word-length is used.
First, IntDCT is separated to Walsh-Hadamard transform(WHT) as the pre-processing part and the others as the postprocessing part [12]. Second, we present an M-channel
lossless WHT (LWHT) which can be constructed by only
(log2 M)-bit-word-length. It is achieved by using the scaling shift and considering the two-dimensional (2-D) separable transform of one-dimensional (1-D) WHT. The proposed IntDCT has regularity which is imposed structurally
by LWHT even if low-bit-word-length is used. As result, we
can achieve an IntDCT with low cost and fast implementation. Finally, the validity is shown by the comparison of our
methods and the conventional methods in coding gain, frequency response and the results of 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.
2.

Review

2.1 Multiplierless Lifting Structure
The lifting structure [8], also known as the ladder structure,
is a special type of lattice structure, a cascading construction using only elementary matrices - identity matrices withsingle nonzero oﬀ-diagonal element.
Figure 1 shows a basic lifting structure. In this case,c 2010 The Institute of Electronics, Information and Communication Engineers
Copyright SUZUKI and IKEHARA: INTDCT VIA LWHT WITH STRUCTURAL REGULARITY FOR LOW-BIT-WORD-LENGTH

735

Fig. 1

DCT-II and -III are often used for image and video coding.
The m-column and n-row element of M-channel DCT-II and[M]-III matrix C[M]
II and CIII are defined as⎞⎛⎜⎜⎜ m n + 12 π ⎟⎟⎟ [M] 2⎟⎟⎟⎠
CII m,n =cm cos ⎜⎜⎜⎝
M
M
⎞
⎛

⎜⎜⎜ m + 12 nπ ⎟⎟⎟ [M] 2⎟⎟⎠⎟cn cos ⎜⎜⎝⎜
=
CIII
m,n
M
M

A lifting structure (white circles: rounding operations).

Fig. 2 An approximation from floating multiplication to bit-shift andaddition operations.

In the past, many IntDCTs have been proposed for losslessto-lossy image coding [9]–[14]. They are based on lifting
structures and rounding operations. The lifting structure of
Givens rotation matrix Rθ is represented by cos θ−1    cos θ−1 
1 sin θ1 0 1 sin θ
Rθ =
.
(2)
sin θ 1 00
1
1

the lifting matrix and its inverse matrix are as follows:




−1 
1 −T
1 T
1 T
=
.
,
0 1
0 1
0 1
Then, they are represented byz = yi − round[T y j ] = xi
yi = xi + round[T x j ]→ izj = yj = xj
yj = xj

2.3 WHT

where T is lifting coeﬃcient and round[.] is rounding operation. Thus the lifting structure with rounding operation canachieve lossless-to-lossy coding.
For high-speed implementation, lifting coeﬃcients 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 real time software encoder
and reduce the circuit size. The multiplications are expressed by k/2n (k, n ∈ N) which is n-bit-word-length. For
example, a coeﬃcient 51/28 = 51/256 can be operated as
51
32
16
2
1
=
+
+
+
256 256 256 256 256
1
1
1
1
= +
+
+
8 16 128 256
11
1
1= 3 + 4 + 7 + 8.
2
2
2
2

√
where 0 ≤ m, n ≤ M − 1 and ci = 1/ 2 (i = 0) or 1 (i  0).
For simplicity, let us define that M = 2n (n ∈ N) and DCTmeans DCT-II.
Also, DCT can be constructed by cascade connectionof Givens rotation matrices [4]–[7]. Givens rotation matrix
Rθ is expressed by
cos θ − sin θRθ =.
sin θ cos θ(1)

From (1), we can replace the multiplier by 51/256 to sum
results from 3 bit-shift, 4 bit-shift, 7 bit-shift, and 8 bit-shiftoperations as illustrated in Fig. 2. We can find that the perfect reconstruction in lifting structure is always kept even if
lifting coeﬃcients are approximated.

As well known, WHT has interesting relationships withother discrete transforms such as DCT [3] etc. It is expressed by


 
1 1
W[1] = 1 , W[2] =
1 −1
 [M]
M 
W 2 W[ 2 ][M][2][ M2 ]
W =W ⊗W =M
M
W[ 2 ] −W[ 2 ]where ⊗ is Kronecker product. The 8-channel WHT kernel
arranged in Walsh order is⎡⎤⎢⎢⎢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⎥⎥⎥⎥⎥ .
W[8] = ⎢⎢⎢⎢
(3)⎢⎢⎢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 −1Note
√ that (3) is still not normalized by the scaling factor
1/ M.
2.4 IntDCT via WHT

2.2 DCT and IntDCTIn this paper, only type-II and -III in DCT are described.

√
Let us normalize W such that Ŵ = (1/ M)W is an orthonormal matrix: Ŵ−1 = ŴT . Then one can prove that

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.4 APRIL 2010

736

⎡
⎤
⎢⎢⎢ 0 −1 0 0⎥⎥⎥⎢⎢⎢ 0 0 0 1⎥⎥⎥⎥⎥× ⎢⎢⎢⎢⎢⎢⎣−1 0 0 0⎥⎥⎥⎥⎦
0 0 −1 0⎡⎢⎢⎢cos 3π
0
8
⎢⎢⎢
⎢⎢⎢ 0
cos 3π8× ⎢⎢⎢⎢⎢⎢⎢ sin 3π08⎢⎣0sin 3π8[3]T[M] [M]
C[M]Ŵ = P[M] Q[M] P[M] Ŵ[M]II = Q̂(4)

where Ŵ[M] and Q̂[M] are the pre- and post-processing part,respectively. In case of M = 8,⎡⎤⎢⎢⎢1 0 0 0 0 0 0 0⎥⎥⎥⎢⎢⎢0 0 0 0 1 0 0 0⎥⎥⎥⎢⎢⎢⎥⎥⎢⎢⎢⎢0 0 1 0 0 0 0 0⎥⎥⎥⎥⎥⎢⎢⎢0 0 0 0 0 0 1 0⎥⎥⎥⎥⎥P[8] = ⎢⎢⎢⎢⎢⎢⎢0 1 0 0 0 0 0 0⎥⎥⎥⎥⎥⎢⎢⎢⎢0 0 0 0 0 1 0 0⎥⎥⎥⎥⎢⎢⎢⎥⎢⎢⎣0 0 0 1 0 0 0 0⎥⎥⎥⎥⎦
0 0 0 0 0 0 0 1and⎡ [2]
⎤
0[2]
⎢⎢⎢ I
⎥
⎢⎢⎢ 0[2] R π 0[4] ⎥⎥⎥⎥⎥[8]Q = ⎢⎢⎥⎥⎦(− 8 )⎣
0[4]S[4]Fig. 3IntDCT via LWHT with Structural Regularity for
Low-Bit-Word-Length

The desired conditions 1 and 2 for IntDCT in lossless-tolossy image coding are as follows:
Table 1

α0
β0
α1
α2
β1
α3
α4
β2
α5
α6
β3
α7
α8
β4
α9

Lifting coeﬃcients of Chen’s IntDCT [12].

floatingpoint [12]0.1989123674−0.3826834324
0.1989123674−0.6681786379
0.9238795326−0.6681786379−0.6681786379
0.9238795326−0.6681786379−0.8206787908
0.9807852804−0.8206787908−0.3033466836
0.5555702330−0.3033466836

Eﬃcient decomposition of S[4] consisting of 4 rotation angles.

Fig. 4

⎤
⎥⎥⎥
0
⎥
3π ⎥
− sin 8 ⎥⎥⎥⎥
⎥⎥⎥
⎥⎥⎥
0
⎥⎥
3π ⎦
cos 8

and shown in Fig. 3. To obtain IntDCT via WHT, W[8] in(3) instead of Ŵ[8] and the lifting factorization of Givens
rotation matrix in (2) are used [12]. In this paper, all transform coeﬃcients α0 -α9 and β0 -β4 shown in Fig. 4 and Table 1 are rounded into the n-bit-word-length, k/2n (k, n ∈ N
and 3 ≤ n ≤ 6).
3.

where R(−π/8) is a Givens rotation matrix and S[4] is 4 × 4 orthogonal matrix which can be further factorized using only
4 angles as⎡⎤⎢⎢⎢cos 7π⎥⎥⎥00− sin 7π
16
16
⎢⎢⎢⎢
⎥⎥⎥⎥
3π
3π
⎢⎢⎢ 0
⎥⎥⎥
cos 16 − sin 16
0
[4]
⎥⎥⎥
S = ⎢⎢⎢⎢
3π
3π
⎥⎥⎥
⎢⎢⎢ 0
0
sin 16 cos 16
⎥⎥⎥
⎢⎢⎣
7π ⎦
0
0
cos
sin 7π1616− sin 3π80
cos 3π80Chen’s IntDCT [12] (white circles: rounding operations).

k/23
1/4
−3/8
1/4
−5/8
7/8
−5/8
−5/8
7/8
−5/8
−7/8
1
−7/8
−1/4
1/2
−1/4

rounded dyadic values
k/24
k/25
k/26
3/16
3/16
13/64
−3/8
−3/8
−3/8
3/16
3/16
13/64
−11/16−21/32−43/64
15/16
15/16
59/64
−11/16−21/32−43/64−11/16−21/32−43/64
15/16
15/16
59/64
−11/16−21/32−43/64−13/16−13/16−53/64
1
31/32
63/64
−13/16−13/16−53/64−5/16−5/16−19/64
9/16
9/16
9/16
−5/16
−5/16
−19/64

SUZUKI and IKEHARA: INTDCT VIA LWHT WITH STRUCTURAL REGULARITY FOR LOW-BIT-WORD-LENGTH

737

1: The transform should not have DC leakage.
→ If DC leakage is generated, the signal energy decomposed to frequency domain is not suﬃciently concentrated. And if so, high compression ratio can not be
achieved.
⇒ Regularity should be imposed.
2: Dynamic range of the output signals should be as small
as possible.
→ If dynamic range is huge, to avoid bit redundancy,
quantization part would be required after transformpart. And if so, realization of lossless image coding
is impossible due to its error.
⇒ The transform should be normalized without using
quantization part.
In low-bit-word-length, although most of the conventional
IntDCTs do not have regularity, one in [12] satisfies the condition 1. However, it does not satisfies the condition 2
because the coeﬃcients of the pre-processing part W[8] are
not normalized. Hence this paper√ solves the normalization
problem of WHT: Ŵ[8] = (1/ 8)W[8] , in IntDCT in [12]while keeping the other part as it is.

Fig. 5 2-D block transform: (a) standard transform, (b) separated
transform to the pre- and post-processing part.

3.1 Two-Dimensional (2-D) Block TransformWhen we apply a block transform matrix F into an 2-D input
signal x in column- and row-wise separately, the 2-D output
signal y is expressed by
y = (F(Fx)T )T = FxFT .

(5)

We call it 2-D separable block transform. If the transform F
is factorized as F = F1 F0 where F0 and F1 are the pre- andpost-processing part, (5) is represented by
y = F1 F0 x(F1 F0 )T = F1 F0 xFT0 FT1 .
This equation means that 2-D block transform by F1 is applied after 2-D block transform by F0 . Therefore this process is shown in Fig. 5(b). Then we regard F0 and F1 as Ŵ
and Q̂ in (4), respectively.
3.2 LWHT with Structural Regularity for Low-Bit-WordLength
In this subsection, we consider the normalization of W[M]in (4) and present M-channel LWHT which has only ±1 and±1/M, (± log2 M)-bit-word-length, and structural regularity.
According to√the condition 2, if W normalized by thescaling factor 1/ M is used in transform part, (5) can be
represented by
⎛

T ⎞T
⎜⎜ 1
⎟⎟
1
(6)
y = ŴxŴT = ⎜⎜⎝ √ W √ Wx ⎟⎟⎠ .
M
M√
In (6), one scaling factor 1/ M can be moved to anotherone as
⎛ 
T ⎞T

T
⎜⎜⎜
⎟⎟
1
1
T
⎜
W (Wx)
Wx ⎟⎟⎠ .
y=or y = ⎝W(7)
M
M

Fig. 6 LWHT with structural regularity for lower-bit-word-length (whitecircles: rounding operations).

Be careful that (7) can not be applied to lossless image coding as it is because real values generated by the merged scaling factor 1/M can not be eliminated. Now, we consider totransform two adjacent blocks simultaneously as ⎛ 1T ⎞T ⎜⎜⎜ W 0W 0
yi 0
xi 0 ⎟⎟⎟
M
⎟
(8)
= ⎝⎜
0 yj
0 W
0 M1 W 0 x j ⎠where xi and x j are adjacent M × M blocks in the 2-D image
and yi and y j are the output signals of them. (8) is illustrated
as the upper half in Fig. 6. Next, we can obtain a lifting
factorization as follows [15]:
 





W 0
0 I I 0 I − M1 W I 0=−I 0 W I 0
W I
0 M1 W
I
and

1

MW

0

 




I 0 I − M1 W I 0 0 I
0
=
W I 0
W I −I 0
W
Iwhere (1/M)W = W−1 . Consequently, the normalized
LWHT can be constructed by only ±1 and ±1/M without
losing structural regularity. The proposed LWHT is illustrated as the lower half in Fig. 6. Thus the 2-D separable transform by Ŵ can be implemented by eﬃcient lifting

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.4 APRIL 2010738

structure without any scaling.
4.1 Coding Gain and Frequency Response
3.3 Expansion from LWHT to IntDCTIn this paper, we set M = 8 as the most popular block size.
First, an original image is separated to upper half and lower
half. Second, the 2-D separable block transform of the images is implemented by our 8-channel LWHT such as Fig. 6.
This implementation requires only 3-bit-word-length. Next,
Q̂[8] in (4) is implemented. Thus, by using our normalized
LWHT for the pre-processing part in [12] which satisfies thecondition 1 but 2, our IntDCT achieves structural regularity and the normalized filter coeﬃcients at the same time inmore than 3-bit-word-length. If the floating-points in Table 1 are used and rounding operations are not used, our IntDCT shows the same performance as the original DCT. But,
if dyadic values k/2n (k, n ∈ N) in Table 1 and rounding operations are used, our IntDCT can achieve lossless-to-lossy
image coding by the lower cost implementation.
4.

Coding gain is one of the most important factors to beconsidered in compression applications. A transform withhigher coding gain compacts more energy into a fewer number of coeﬃcients. 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 our IntDCT has similar
coding gain to that of the original DCT. The biorthogonal
coding gain is defined as [16]Coding gain [dB] = 10 log10  M−1
k=0

σ2x
σ2xk

fk

2

where σ2x is the variance of the input signal, σ2xk is the variance of the k-th subbands and fk 2 is the norm of thek-th synthesis filter. Table 2 shows the comparisons of coding gain of the proposed IntDCT and the conventional ones.

Results

In this paper, the validity of the proposed IntDCTs is shownin lossless-to-lossy image coding by evaluating coding gain[dB], frequency response, lossless bit rate [bpp] in losslessimage coding, and PSNR [dB] in lossy image coding. We
chose [9]–[11] and [14] as the conventional IntDCTs.

Table 2 Comparisons of coding gain of the proposed IntDCT and theconventional IntDCTs.
Lifting
Coding gain [dB]
K’s [9]F’s [10]
T’s [11]
C’s [14]Prop.
coeﬃcients
float
8.82598.82596.22568.69608.82597.44208.48296.1446
8.11778.7344k/23
8.64988.77246.20778.55608.8206k/24
k/25
8.76858.80446.22588.68308.8155k/26
8.80868.82576.22438.67748.8244

Fig. 7 Frequency responses of the proposed IntDCT and the conventional IntDCTs in 4-bit-wordlength: (a) original DCT (infinite-word-length), (b) Komatsu’s RDCT [9], (c) Fukuma’s LDCT [10], (d)Tran’s BinDCT [11], (e) Chokchaitam’s IntDCT (OWLA) [14], (f) proposed IntDCT.

SUZUKI and IKEHARA: INTDCT VIA LWHT WITH STRUCTURAL REGULARITY FOR LOW-BIT-WORD-LENGTH

739
Table 3 Comparisons of lossless image coding by the proposed IntDCTs(Lossless bit rate [bpp]).
Image
512×512BaboonBarbaraBoat
ElaineFinger1
Finger2
Goldhill
Grass
Lena
Pepper
Avg.

k/23
6.29
5.07
5.26
5.27
6.14
5.98
5.19
6.19
4.72
5.02
5.51

Prop. IntDCT
k/24
k/25
6.28
6.28
5.02
5.02
5.22
5.22
5.25
5.26
6.08
6.08
5.87
5.89
5.18
5.18
6.18
6.18
4.68
4.69
4.98
4.98
5.47
5.48

k/26
6.28
5.01
5.22
5.25
6.08
5.87
5.18
6.18
4.68
4.98
5.47

Table 4 Comparisons of lossless image coding by the proposed IntDCT and the conventional IntDCTs in 4-bit-word-length (Lossless bit rate[bpp]).
Image
512×512BaboonBarbaraBoat
ElaineFinger1
Finger2
Goldhill
Grass
Lena
Pepper
Avg.

K’s
[9]
6.55
5.55
5.79
5.87
6.24
6.15
5.57
6.30
5.45
5.64
5.91

F’s
[10]
6.48
5.39
5.65
5.75
6.14
6.00
5.46
6.26
5.26
5.48
5.79

T’s
[11]
6.86
5.45
5.69
5.86
6.36
6.14
5.66
6.65
5.16
5.47
5.93

C’s
[14]
6.36
5.15
5.34
5.43
6.10
5.93
5.29
6.23
4.88
5.14
5.59

Prop.
IntDCT
6.28
5.02
5.22
5.25
6.08
5.87
5.18
6.18
4.68
4.98
5.47

It is clear that coding gains of the conventional IntDCTs are
not kept in low-bit-word-length, but that of the proposed IntDCT is almost kept even in 3-bit-word-length.
Next, frequency responses of the proposed IntDCTs
and the conventional ones are shown in Fig. 7. In Fig. 7,[9], [10] and [14] have DC leakage which may generate achecker-board artifact in low bit rate. The proposed IntDCT does not have DC leakage, because 8-channel LWHT
as the pre-processing part can be constructed with only 3bit-word-length and regularity can be always kept in morethan 3-bit-word-length. Also, although [11] does not have
DC leakage, it shows worse coding gain than ours.

Table 5 Comparisons of lossy image coding by the proposed IntDCTs(PSNR [dB]).
Image
512×512BaboonBarbaraGoldhill
Lena
PepperBaboonBarbaraGoldhill
Lena
PepperBaboonBarbaraGoldhill
Lena
PepperProp. IntDCT
k/23
k/24
k/25
bit rate: 0.25 [bpp]
22.54
22.56
22.57
26.83
26.92
26.93
29.26
29.34
29.32
31.62
31.80
31.76
31.22
31.35
31.35
bit rate: 0.50 [bpp]
24.75
24.80
24.80
30.48
30.62
30.62
31.78
31.87
31.86
34.98
35.35
35.31
34.03
34.28
34.27
bit rate: 1.00 [bpp]
28.16
28.22
28.20
35.50
35.78
35.78
34.97
35.12
35.14
38.10
38.54
38.49
36.42
36.61
36.62

k/26
22.56
26.93
29.35
31.81
31.36
24.80
30.65
31.90
35.39
34.31
28.25
35.81
35.13
38.54
36.61

Table 6 Comparisons of lossy image coding by the proposed IntDCT
and the conventional IntDCTs in 4-bit-word-length (PSNR [dB]).
Image
512×512BaboonBarbaraGoldhill
Lena
PepperBaboonBarbaraGoldhill
Lena
PepperBaboonBarbaraGoldhill
Lena
Pepper

K’s
[9]

F’s
T’s
[10]
[11]
bit rate: 0.25 [bpp]
21.60
22.16
20.84
25.42
26.30
23.86
27.11
28.19
27.41
27.28
29.16
29.03
27.33
29.01
28.57
bit rate: 0.50 [bpp]
23.60
24.19
21.89
27.95
28.95
27.27
29.57
30.55
29.54
29.50
31.57
32.34
29.76
31.59
31.68
bit rate: 1.00 [bpp]
26.62
27.18
24.63
31.84
32.97
31.25
32.72
33.77
31.33
33.03
35.47
35.70
32.81
34.71
34.43

C’s
[14]

Prop.
IntDCT

22.14
26.43
28.85
31.32
31.02

22.56
26.92
29.34
31.80
31.35

24.40
29.91
31.38
34.12
33.14

24.80
30.62
31.87
35.35
34.28

27.71
34.94
34.51
36.95
35.62

28.22
35.78
35.12
38.54
36.61

4.2 Application to Lossless Image Coding
4.3 Application to Lossy Image Coding
The proposed IntDCTs are applied to lossless-to-lossy image coding. The set partitioning in hierarchical trees(SPIHT) progressive image transmission algorithm [17] wasused to encode the transformed images. The comparisons ofLossless bit rate [bpp] =Total number of bits [bit]Total number of pixels [pixel]

in lossless image coding are shown in Table 3. Table 3
shows the performance at the almost same level all withoutaﬀecting diﬀerent bit-word-length in more than 4-bit-wordlength. We show also the comparisons of the proposed IntDCT and the conventional ones in 4-bit-word-length in Table 4. The proposed IntDCT showed better coding performance than all of the conventional ones.

If lossy compressed data is required, it can be achieved byinterrupting the obtained lossless bit stream. The comparisons of
2552
PSNR [dB] = 10 log10
MSE
where MSE is the mean squared error in lossy image coding
are shown in Table 5. Similar to Sect. 4.2, we show also thecomparisons of the proposed IntDCT and the conventional
ones in 4-bit-word-length in Table 6. Furthermore, Fig. 8
shows the enlarged images of ‘Lena’ which are lossy compressed images by the proposed IntDCT and the conventional ones in 4-bit-word-length when bit rate is 0.25 [bpp].

IEICE TRANS. FUNDAMENTALS, VOL.E93–A, NO.4 APRIL 2010

740

Fig. 8 Enlarged images of ‘Lena’ in 4-bit-word-length (bit rate: 0.25 [bpp]): (a) original image, (b)Komatsu’s RDCT [9], (c) Fukuma’s LDCT [10], (d) Tran’s BinDCT [11], (e) Chokchaitam’s IntDCT(OWLA) [14], (f) proposed IntDCT.

In Table 6 and Fig. 8, the proposed IntDCT presents bettercoding performance than the conventional ones in lossy image coding. Especially, in Fig. 8, we can find that a checkerboard artifact is not generated in the proposed IntDCT. Although [11] also does not have the artifact, it shows bad coding performance due to non-consideration of dynamic range
and no quantization part.
5.

Conclusion

This paper presents an integer discrete cosine transform(IntDCT) via lossless Walsh-Hadamard transform (LWHT)
with structural regularity even in low-bit-word-length (coeﬃcients). It can be achieved by using a novel LWHT
considering normalization as the pre-processing part in
IntDCT. Our M-channel LWHT can be constructed with
only (± log2 M)-bit-word-length and has structural regularity. Therefore, our IntDCTs are more suitable for losslessto-lossy image coding and show better coding performance
than the conventional IntDCTs when lower-bit-word-lengthis allocated to every lifting coeﬃcients.
Acknowledgment
This work is supported in part by a Grant-in-Aid for the

Global Center of Excellence for High-Level Global Cooperation for Leading-Edge Platform on Access Spaces from the
Ministry of Education, Culture, Sport, Science, and Technology in Japan.
References[1] W. Pennebaker and J. Mitchell, JPEG, Still Image Data Compression
Standard, Van Nostrand, NY, 1993.
[2] T. Sikora, “MPEG digital video-coding standards,” IEEE Signal Process. Mag., vol.14, no.5, pp.82–100, Sept. 1997.
[3] K.R. Rao and P. Yip, Discrete Cosine Transform Algorithms, Academic Press, 1990.
[4] W.H. Chen, C.H. Smith, and S.C. Fralick, “A fast computationalalgorithm for the discrete cosine transform,” IEEE Trans. Commun.,vol.25, no.9, pp.1004–1009, Sept. 1977.
[5] Z. Wang, “Fast algorithms for the discrete W transform and for thediscrete Fourier transform,” IEEE Trans. Acoust. Speech Signal Process., vol.ASSP-32, no.4, pp.803–816, April 1984.
[6] B.G. Lee, “A new algorithm to compute the discrete cosine transform,” IEEE Trans. Acoust. Speech Signal Process., vol.32, no.6,
pp.1243–1245, June 1984.
[7] Z. Wang, “On computing the discrete fourier and cosine transforms,”
IEEE Trans. Acoust. Speech Signal Process., vol.33, no.4, pp.1341–
1344, April 1985.
[8] W. Sweldens, “The lifting scheme: A custom-design construction ofbiorthogonal wavelets,” Appl. Comput. Harmon. Anal., vol.3, no.2,
pp.186–200, 1996.
[9] K. Komatsu and K. Sezaki, “Reversible discrete cosine transform,”

SUZUKI and IKEHARA: INTDCT VIA LWHT WITH STRUCTURAL REGULARITY FOR LOW-BIT-WORD-LENGTH

741

Proc. ICASSP’98, Seattle, WA, May 1998.
[10] S. Fukuma, K. Ohyama, M. Iwahashi, and N. Kambayashi, “Lossless 8-point fast discrete cosine transform using lossless Hadamardtransform,” IEICE Technical Report, DSP99-103, Oct. 1999.
[11] T.D. Tran, “The binDCT: Fast multiplierless approximation of the
DCT,” IEEE Signal Process. Lett., vol.7, no.6, pp.145–149, June
2000.
[12] Y.J. Chen, S. Oraintara, T.D. Tran, K. Amaratunga, and T.Q.
Nguyen, “Multiplierless approximation of transforms with adderconstraint,” IEEE Signal Process. Lett., vol.9, no.11, pp.344–347,
Nov. 2002.
[13] S. Chokchaitam and M. Iwahashi, “A new lossless/lossy image coding based on a multiplierless integer DCT,” Proc. ITC-CSCC’06,
Chiang-Mai, Thailand, July 2006.
[14] S. Chokchaitam and M. Iwahashi, “A new optimum-word-lengthassignment (OWLA) multiplierless integer DCT for unified lossless/lossy image coding,” Proc. IWAIT’07, Bangkok, Thailand, Jan.
2007.
[15] T. Suzuki and M. Ikehara, “Lifting factorization based on block parallel system of M-channel perfect reconstruction filter banks,” Proc.
EUSIPCO’09, Glasgow, Scotland, Aug. 2009.
[16] G. Strang and T. Nguyen, Wavelets and Filter Banks, WellesleyCambridge Press, 1996.
[17] A. Said and W.A. Pearlman, “A new, fast, and eﬃcient image codec
based on set partitioning in hierarchical trees,” IEEE Trans. Circuits
Syst. Video Technol., vol.6, no.3, pp.243–250, 1996.

Taizo Suzuki
received the B.E. and M.E.
degrees in electrical engineering from Keio University, Yokohama, Japan, in 2004 and 2006, respectively. He joined Toppan Printing Co., Ltd.,Tokyo, Japan, from 2006 to 2008. He is currently a Ph.D. candidate at Keio University. His
research interests in the field of filter banks andits application for multimedia signal processing.

Masaaki Ikehara
received the B.E., M.E.,
and Ph.D. degrees in electrical engineering from
Keio University, Yokohama, Japan, in 1984,
1986 and 1989, respectively. He was with the
Department of Electrical and Computer Engineering, Nagasaki University, Nagasaki, Japan,
as an Assistant Professor from 1989 to 1992. In
1992, he joined the Department of Electrical Engineering, Keio University. From 1996 to 1998,
he was a Visiting Researcher with the Universityof Wisconsin, Madison, and Boston University,
Boston, MA. He is currently a Professor with the Department of Electronics and Electrical Engineering, Keio University. His research interests arein the areas of multirate signal processing, wavelet image coding, and filter
design problems.