Structurally Regular Integer Discrete Cosine Transform for
Low-Bit-Word-Length Coefficients
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— This paper presents an IntDCT with only dyadic values suchas k/2n (k, n ∈ N). Although some IntDCTs have been proposed, they
are unsuitable for lossless-to-lossy image coding in low-bit-word-length(coefficients). First, the proposed M -channel lossless WHT (LWHT)
can be constructed by only (log2 M )-bit-word-length and has structural
regularity. Then, our 8-channel IntDCT keeps good coding performanceeven in low-bit-word-length because LWHT, which is main part of
IntDCT, can be implemented by 3-bit-word-length. Finally, our method
is validated in lossless-to-lossy image coding.
Index Terms — IntDCT, dyadic values, low-bit-word-length, LWHT,
lossless-to-lossy image coding

I. I NTRODUCTION
Multimedia coding (compression) standards such as JPEG andMPEG use the discrete cosine transform (DCT) [1] which has
excellent properties, several types and many fast algorithms. InJPEG, DCT type-II (DCT-II) and -III (DCT-III), which is the inverse
transform of DCT-II, are applied to lossy image coding, and thedifferential pulse code modulation (DPCM) is applied to losslessimage coding. We have to prepare lossy and lossless compresseddata 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 bylifting structures [2] and rounding operations based on DCT-II, havebeen proposed for lossless-to-lossy image coding [3–6]. However,the conventional IntDCTs generate a checker-board artifact in lowbit-word-length (coefficients).
In this paper, we propose an IntDCT via LWHT with structural
regularity even if low-bit-word-length is used. First, IntDCT isseparated to Walsh-Hadamard transform (WHT) as the pre-processing
part and the others as the post-processing part [5]. Second, we present
an M -channel lossless WHT (LWHT) which can be constructed byonly (log2 M )-bit-word-length. It is achieved by using the scaling
shift and considering the two-dimensional (2-D) separable transformof one-dimensional (1-D) WHT. The proposed IntDCT has regularity
which is imposed structurally by LWHT even if low-bit-word-lengthis 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 the results of losslessto-lossy image coding.
Notations: I is an identity matrix, MT is a transpose of matrixM, and M[N] is an N × N square matrix, respectively.
II. R EVIEW
A. Multiplierless Lifting Structure
The lifting structure [2], also known as the ladder structure, isa special type of lattice structure, a cascading construction using
only elementary matrices - identity matrices with single nonzero offdiagonal element.

978-1-4244-5309-2/10/$26.00 ©2010 IEEE

Fig. 1.

A lifting structure (white circles: rounding operations).

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 ]zi = yi − round[T yj ] = xi→z j = yj = x j
yj = x j
where round[.] is rounding operation. Thus the lifting structure withrounding operation can achieve lossless-to-lossy coding.
For high-speed implementation, lifting coefficients are required toapproximate floating-point to hardware-friendly dyadic values suchas k/2n (k, n ∈ N) which can be implemented by only bit-shift
and addition operations. It performs fast implementation in a realtime 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 coefficient 51/28 = 51/256 can be operated as
32
1621
51
=+++256
256
256
256
256
1
111++= +816128
256
111
1
= 3 + 4 + 7 + 8.
(1)
2
2
22From (1), we can replace the multiplier by 51/256 to sum resultsfrom 3 bit-shift, 4 bit-shift, 7 bit-shift, and 8 bit-shift operations
as illustrated in Fig. 2. We can find that the perfect reconstruction
in lifting structure is always kept even if lifting coefficients areapproximated.
B. WHTAs well known, WHT has interesting relationships with otherdiscrete transforms such as DCT [1] etc. It is expressed by 
1 1
W[1] = 1 , W[2] =1 −1
MMW[ 2 ] W[ 2 ]
[M ]
[2]
[M]
2=W ⊗ W=(2)WM
M
W[ 2 ] −W[ 2 ]where ⊗ is Kronecker product.
Note that (2) is still not normalized√by the scaling factor 1/ M .

1607

TABLE I
L IFTING COEFFICIENTS OF C HEN ’ S I NT DCT [5].
α0β0α1α2β1α3α4β2α5α6β3α7α8β4
α9Fig. 2. An approximation from floating multiplication to bit-shift and addition
operations.

floating-point
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. . .

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

k/24
3/16
-3/8
3/16
-11/16
15/16-11/16-11/16
15/16-11/16-13/161-13/16
-5/16
9/16
-5/16

k/25
3/16
-3/8
3/16
-21/32
15/16-21/32-21/32
15/16-21/32-13/1631/32-13/16
-5/16
9/16
-5/16

k/26
13/64
-3/8
13/64
-43/64
59/64-43/64-43/64
59/64-43/64-53/64
63/64-53/64-19/64
9/16-19/64

C. IntDCT via WHT√
Let us normalize W such that Ŵ = (1/ M )W is an orthonormal matrix: Ŵ−1 = ŴT . Then one can prove that [1]T[M ]CII = Q̂[M ] Ŵ[M ] = P[M ] Q[M ] P[M ] Ŵ[M ]
[M ]

(3)

[M ]

where Ŵand Q̂
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⎥T⎥P[8] = 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][2]I π0 π [4]⎢⎣ [2]
c8 s8 ⎦ 0 ⎥⎥Q[8] = ⎢⎦⎣ 0−sπ8 cπ80[4]S[4]A. 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 bywhere⎡ 7π⎤0−s7πc16 0163π⎢ 0 c3π0 ⎥16 −s16⎥S[4] = ⎢3π⎣ 0 s3πc0 ⎦
16167π7π0c16s16 0⎡⎤ ⎡ 3π⎤c80 −1 0 00 −s3π083π
3π
⎢ 0 0 0 1⎥ ⎢ 0 c80−s8 ⎥⎥⎢⎥,×⎢⎣−1 0 0 0⎦ ⎣s3π
0c3π
0 ⎦880c3π0 s3π
0 0 −1 088cab

1: The transform should not have DC leakage.
→ If DC leakage is generated, the signal energy decomposed
to frequency domain is not sufficiently concentrated. And if so,better compression ratio can not be achieved.
⇒ Regularity should be imposed.
2: Dynamic range of the output signals should be as small aspossible.
→ If dynamic range is huge, to avoid redundant it, quantization
part would be required after transform part. And if so, realization of lossless image coding is impossible due to its error.
⇒ The transform should be normalized without using quantization part.
Although the other conventional ones do not have regularity in lowbit-word-length, IntDCT in [5] satisfies the condition 1. However, it
does not satisfies the condition 2 because the coefficients of the preprocessing part W[8] are not normalized. Hence√this paper solves thenormalization problem of WHT: Ŵ[8] = (1/ 8)W[8] , in IntDCT
in [5] while keeping the other part as it is.

y = (F(Fx)T )T = FxFT .

(5)

We call it 2-D separable block transform. If the transform F isfactorized as F = F1 F0 where F0 and F1 are the pre- and postprocessing part, (5) is represented by
y = F1 F0 x(F1 F0 )T = F1 F0 xFT0 FT1 .

= cos (a/b) and sab[8][8]= sin (a/b). To obtain IntDCT via WHT,
W instead of Ŵ and the lifting factorization of Givens rotation
matrix  cos θ−1  
θ−1
1 0 1 coscos θ − sin θ1 sin θsin θ(4)=01sin θ 1 01sin θ cos θare used [5]. In this paper, the n-bit-word-length, k/2n (k, n ∈ N
and 3 ≤ n ≤ 6), is applied to all transform coefficients α0 -α9 andβ0 -β4 as shown in Fig. 3 and Table I.
III. S TRUCTURALLY R EGULAR I NT DCT VIA LWHT FOR
L OW-B IT-W ORD -L ENGTH
The desired conditions 1 and 2 for IntDCT in lossless-to-lossy
image coding are as follows:This equation means that 2-D block transform by F1 is applied after
2-D block transform by F0 . Then we regard F0 and F1 as Ŵ andQ̂ in (3), respectively.
B. Structurally Regular LWHT for Low-Bit-Word-Length
In this subsection, we consider the normalization of W[M ] in(3) 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 the scaling
factor 1/ M is used in transform part, (5) can be represented by
T T
1
1T
y = ŴxŴ = √ W √ Wx.
(6)
M
M

1608

Fig. 3.

Chen’s IntDCT [5] (white circles: rounding operations).

TABLE IIC OMPARISON OF CODING GAIN .
Liftingcoefficients
float
k/23
k/24
k/25
k/26

F’s [3]8.82598.48298.77248.80448.8257

Coding gain [dB]
T’s [4]C’s [6]6.22568.69606.1446
8.11776.20778.55606.22588.68306.22438.6774Prop.
8.82598.73448.82068.81558.8244

C. Expansion from LWHT to IntDCT
Fig. 4. LWHT with structural regularity for lower-bit-word-length (whitecircles: rounding operations).

√In (6), one scaling factor 1/ M can be moved to another one as T T
T
1
1
Tor y = W. (7)W (Wx)
Wxy=M
M
Be careful that (7) can not be applied to lossless image coding as itis because real values generated by the merged scaling factor 1/M
can not be eliminated. Now, we consider to transform two adjacent
blocks simultaneously as  1
T T 
xi 0
W 0W 0yi 0M=(8)1W 0 xj0 yj
0 W0 M
where xi and xj are adjacent M × M blocks in the 2-D image andyi and yj are the output signals of them. (8) is illustrated as theupper half in Fig. 4. Next, we can obtain a lifting factorization asfollows:

10 I
I 0 I −MW0WI 0=1W−I 0 W I 00IW I

1 M 1W 0I 0 I −M W
I 00 IM=W I 0
W I −I 00W
I
where (1/M )W = W−1 . Consequently, LWHT can be constructedby only ±1 and ±1/M . The proposed LWHT is illustrated as thelower half in Fig. 4. Thus the 2-D separable transform by Ŵ can be
implemented by efficient lifting structure without any scaling.

In 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 byour 8-channel LWHT such as Fig. 4. This implementation requires
only 3-bit-word-length. Next, Q̂[8] in (3) is implemented. ThisIntDCT has structural regularity because the proposed LWHT has
structural regularity. If the floating-points in Table I are used androunding operations are not used, our IntDCT shows performancesame as the original DCT. But, if dyadic values k/2n (k, n ∈ N) inTable I and rounding operations are used, our IntDCT can achieve
lossless-to-lossy image coding by the lower cost implementation.
IV. R ESULTS
A. 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 theoptimal KLT closely, it is desired that the our IntDCT has similar
coding gain to that of the original DCT. The biorthogonal codinggain is defined as [7]σx2
22k=0 σxk  fk Coding gain [dB] = 10 log 10 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 II 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 low-bit-word-length, but
the proposed IntDCT almost kept it even in 3-bit-word-length.

1609

TABLE IV
C OMPARISON OF LOSSY IMAGE CODING IN 4- BIT- WORD - LENGTH .
Image
512×512
Barbarabit rate
[bpp]
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00

Lena

(a)

(b)
PepperFig. 5. Frequency responses in 4-bit-word-length: (a)Fukuma’s LDCT [3],(b)proposed IntDCT.

PSNR [dB]
F’s
T’s
[3]
[4]
26.30
23.86
28.95
27.27
32.97
31.25
29.16
29.03
31.57
32.34
35.47
35.70
29.01
28.57
31.59
31.68
34.71
34.43

C’s
[6]
26.43
29.91
34.94
31.32
34.12
36.95
31.02
33.14
35.62

Prop.
IntDCT26.92
30.62
35.78
31.80
35.35
38.54
31.35
34.28
36.61

TABLE IIIC OMPARISON OF LOSSLESS IMAGE CODING IN 4- BIT- WORD - LENGTH .
Lossless bit rate [bpp]
Image
F’s
T’s
C’s
512×512[3][4][6]Barbara
5.39
5.45
5.15
Lena
5.26
5.16
4.88
Pepper
5.48
5.47
5.14
Avg. of 10 images
5.79
5.93
5.59

Prop.
IntDCT
5.02
4.68
4.98
5.47

Frequency responses of the proposed IntDCTs and the conventional
ones are shown in Fig. 5. It is clear that [3] has DC leakage which
may generate a checker-board artifact in low bit rate. The proposed
IntDCT does not have DC leakage, because 8-channel LWHT as thepre-processing part can be constructed with only 3-bit-word-lengthand regularity can be always kept in more than 3-bit-word-length.
Also, although [4] does not have DC leakage, it shows worse coding
gain than ours.
B. Lossless-to-Lossy Image Coding
The proposed IntDCTs are applied to lossless-to-lossy image
coding. 10 test images, which have 512 × 512 size, were used and[3], [4] and [6] were chosen for comparison. The set partitioning inhierarchical trees (SPIHT) progressive image transmission algorithm[8] was used to encode the transformed images. The comparison of
Lossless bit rate [bpp] =Total number of bits [bit]Total number of pixels [pixel]

in lossless image coding is shown in Table III.
If lossy compressed data is required, it can be achieved byinterrupting the obtained lossless bit stream. The comparison of2552
PSNR [dB] = 10 log10
MSE
where MSE is the mean squared error in lossy image coding areshown in Table IV. Furthermore, Fig. 6 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 is0.25[bpp].
In Table III, IV and Fig. 6, the proposed IntDCT presents better
performance than the conventional ones in lossless-to-lossy image
coding. Especially, in Fig. 6, we can find that a checker-board artifact
is not generated in the proposed IntDCT due to structural regularity.
V. C ONCLUSION
This paper presents an integer discrete cosine transform (IntDCT)
via lossless Walsh-Hadamard transform (LWHT) with structural regularity even in low-bit-word-length (coefficients). It can be achieved by(a)(b)Fig. 6. Enlarged images of ‘Lena’ in 4-bit-word-length (bit rate: 0.25 [bpp]):(a)Fukuma’s LDCT [3], (b)proposed IntDCT.

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 lossless-to-lossy image coding andshow better performance than the conventional IntDCTs when lowerbit-word-length is allocated to every lifting coefficient. Naturally, 4channel our IntDCT for JPEG-XR can be also easily obtained.
ACKNOWLEDGMENT
This work is supported in part by a Grant-in-Aid for the Global
Center of Excellence for High-Level Global Cooperation for LeadingEdge Platform on Access Spaces from the Ministry of Education,
Culture, Sport, Science, and Technology in Japan.
R EFERENCES[1] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms, AcademicPress, 1990.
[2] W. Sweldens, “The lifting scheme: a custom-design construction ofbiorthogonal wavelets,” Appl. Comput. Harmon. Anal., vol. 3, no. 2,pp. 186–200, 1996.
[3] S. Fukuma, K. Ohyama, M. Iwahashi, and N. Kambayashi, “Lossless 8point fast discrete cosine transform using lossless Hadamard transform,”
Tech. Rep. of IEICE, DSP99-103, Oct. 1999.
[4] T. D. Tran, “The binDCT: fast multiplierless approximation of the DCT,”IEEE Signal Process. Lett., vol. 7, no. 6, pp. 145–149, June 2000.
[5] Y. J. Chen, S. Oraintara, T. D. Tran, K. Amaratunga, and T. Q. Nguyen,“Multiplierless approximation of transforms with adder constraint,” IEEE
Signal Process. Lett., vol. 9, no. 11, pp. 344–347, Nov. 2002.
[6] S. Chokchaitam and M. Iwahashi, “A new optimum-word-lengthassignment (OWLA) multiplierless integer DCT for unified lossless/lossy
image coding,” in Proc. of IWAIT’07, Bangkok, Thailand, Jan. 2007.
[7] G. Strang and T. Nguyen, Wavelets and Filter Banks, WellesleyCambridge Press, 1996.
[8] 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, 1996.

1610