DESIGN OF BLOCK LIFTING-BASED DISCRETE COSINE TRANSFORM TYPE-II AND IV
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
ABSTRACTasThis paper presents a novel lifting factorization of discrete cosine
transform type-II and IV (DCT-II and IV). Although some conventional integer DCT-IIs (IntDCT-IIs) with block size 8 have been
proposed, they are not generalized as arbitrary block size M . Using block lifting factorization which has an efficient structure forlossless-to-lossy image coding, we present IntDCT-IIs and IVs with
arbitrary block size M that is called block lifting-based DCT-IIs andIVs (BLDCT-IIs and IVs). Finally, the validity of our method isproved by showing the results of lossless-to-lossy image coding in
the most general case of the block size 8 and the extended size 16.
Index Terms— discrete cosine transform (DCT), block lifting
factorization, lossless-to-lossy image coding

[M ]

CII

[M ]

The discrete cosine transform (DCT) [1] is used to image, video
and audio coding (compression) standards such as JPEG [2] andMPEG [3], because it has excellent property and many fast algorithms. There are several types in DCT. DCT type-II (DCT-II) and
DCT type-III (DCT-III) which is the inverse transform of DCT-II are
adapted to image and video coding. And DCT type-IV (DCT-IV) is
also important for some fast algorithms of DCT-II or modified DCT(MDCT) [4] in audio coding. In JPEG, DCT-II is applied to lossy
image coding, and a linear prediction is applied to lossless image
coding [5]. We have to prepare both lossy and lossless compresseddata because DCT-II and linear prediction do not have correlationeach other.
Recently, higher quality data is demanded by the spread ofbroadbands and the development of multimedia contents. Some
integer DCT-IIs (IntDCT-IIs) have been proposed for lossless-tolossy image coding [6–8]. However the conventional methods aredescribed about only block size 8.
This paper presents a general block lifting factorization of M channel DCT-II and IV. We call them M -channel block lifting-based
DCT-II and IV (BLDCT-II and IV). Finally, the validity is shownby the comparison of our methods and conventional methods inlossless-to-lossy image coding.
Notations: I, J, MT and M[N ] are an identity matrix, a reversal
matrix, a transpose of matrix M and a N × N square matrix.

=




I 0
U0 U0
= PUW = P
U1 −U1 0 J
⎧
[M
]
1
⎪
2
⎪
⎨ U0 = √2 CII
M
where U = √1 C[ 2 ]
1
⎪
2 IV
⎪
⎩
P : a permutation matrix

[M ]

(1)

[M ] T

Using CIII = CII , we can easily obtain a matrix factorized
DCT-III.
Next, note that the matrix of DCT-IV can be presented as
[M ]

CIV =



V0 V1
V1T V2

where[M ][M ] T

because CIV = CIV[M ] [M ]CIV CIV

V0 = V0T
V2 = V2T = −V1−1 V0 V1

(2)

and





V0 V1 V0 V1=
V1T V2 V1T V2
V02 + V1 V1T V0 V1 + V1 V2
=
T
T
T
2
V1 V0 + V2 V1 V1 V1 + V2
= I.

2.2. Lifting Structure
2.2.1. Basic Lifting Structure

2. REVIEW
2.1. Discrete Cosine Transform (DCT)
The m column and n row element of M -channel DCT-II matrix
[M ]
[M ]
[M ]
CII , DCT-III matrix CIII and DCT-IV matrix CIV are defined978-1-4244-3677-4/09/$25.00 ©2009 IEEE√
where 0 ≤ m, n ≤ M − 1 and cm = 1/ 2 (m = 0) or 1 (m = 0).
DCT can be factorized to some matrices for a fast algorithm.
Chen et. al., present a fast algorithm of DCT-II [1] as follows:
CII

1. INTRODUCTIONm(n + 1/2)π2
cm cos
M
M
m,n





(m + 1/2)nπ
2
[M ]
CIII
=
cn cos
M
M
m,n





(m
+
1/2)(n+ 1/2)π
2
[M ]
CIV
=
cos
M
M
m,n



480

Lifting structure [9] with rounding operators which quantize input
signals can achieve lossless-to-lossy image coding. Fig.1(a) shows
basic lifting structure. Analysis input signals xi and xj , analysis output and synthesis input signals yi and yj , synthesis output signals zi

3. BLOCK LIFTING-BASED DISCRETE COSINE
TRANSFORM TYPE-II AND IV (BLDCT-II AND IV)
The block lifting structure is an efficient structure for lossless-tolossy image coding [10]. In this paper, LUL (lower-upper-lower triangular matrix) and ULU (upper-lower-upper triangular matrix) decomposition based block lifting factorization of DCT-II and IV are
proposed.

(a)3.1. Block Lifting Factorization based on LUL Decomposition
A novel block lifting factorization of DCT-II based on LUL decomposition is explained. First, the block lifting matrix are multiplied
from the right sides of U in (1) as
 



I U0
I 0
U0 U0
=
U1 −U1 −S0 I
S1 −U1(b)

whereFig. 1. Lifting structure: (a)basic lifting structure, (b)block lifting
structure.

and zj , lifting coefficient P and rounding operator R are representedasyi = xi + R[P xj ]yj = xj
zi = yi − R[P yj ] = xi
zj = yj = xj
where R[.] is rounding operation. In this case, the lifting matrix andits inverse matrix are as follows:

 
−1 

1 P
1 P
1 −P
,
=
.
0 1
0 1
0 1
2.2.2. Block Lifting Structure
Block lifting structure [10] is an efficient structure for lossless-tolossy image coding. The structure achieves higher compression ratio
because it can merge many rounding operators. Fig.1(b) shows block
lifting structure. Analysis input signal vectors xi and xj , analysis
output and synthesis input signal vectors yi and yj , synthesis output
signal vectors zi and zj , N × N lifting coefficient matrix P androunding operator R are represented asyi = xi + R[Pxj ]yj = xj
zi = yi − R[Pyj ] = xi
zj = yj = xj
where R[.] is rounding operation. In this case, the block lifting matrix and its inverse matrix are as follows:

 
−1 

I P
I P
I −P
,
=
.
0 I
0 I
0 I

(3)

And the other block lifting matrix is multiplied from the right sideof (3) as

 


I U0
I 0
I −S2
=
S1 −U1 0 I
S1 S3
where

S 2 = U0.
S3 = −2U1 U0(4)

Then, the other block lifting matrix is multiplied from the right sideof (4) as
 



I 0
I 0
I 0
=
0 S3
S1 S3 −S4 I
1where S4 = U−2
− U−1
(5)
0 .
2 0
Consequently, U can be factorized into the lifting structures using(3)-(5) as




 

U0 U0
I 0
I 0
I 0 I S2.
=
U1 −U1
S0 I
0 S3 S4 I 0 I√
Using U0 = √12 CII , U−1
2CIII and U1 = √12 CIV , (1) can
0 =be factorized into the lifting structures as follows:





I 0
I 0 I X01
I
0
[M ]
W
CII = P
X00 I
0 −X03 X02 I 0 I
⎧
√ [M
]
2
⎪
⎪
III
⎪ X00 = I − 2C
⎪
M]
⎪
[
1
⎨X
2
01 = √2 CII
where
. (6)
M ]2
√ [M
[
]
⎪
2
2
⎪
X
=
C
−
2C
⎪
02
III
III
⎪
⎪
⎩
[M ] [M ]X03 = CIV2 CII2
Fig.2(a) shows M -channel BLDCT-II in (6).
Next, a novel block lifting factorization of DCT-IV is explained.
The block lifting matrix are multiplied from the right sides of (2) as
 



V0 V1
I
V1
I
0
=
−Y00 T0
V1T V2 −Y00 I
where

481

S0 = I − U−10.
S1 = 2U1 − U1 U−1
0

Y00 = V1−1 (V0 − I).
T0 = −V1−1 V0 V1

(7)

(b)

(a)

Fig. 2. M -channel BLDCT-II: (a)based on LUL decomposition, (b)based on ULU decomposition.

(a)

(b)

Fig. 3. 4-channel BLDCT-II: (a)based on LUL decomposition, (b)based on ULU decomposition.

And the other block lifting matrix is multiplied from the right sideof (7) as

I
V1−Y00 T0



 


I 0
I 0
I −Y01=0I
0 −I Y00 I
where

Y01 = V1 .

(8)Consequently, (2) can be factorized into the lifting structures using(7) and (8) as follows:
[M ]



CIV =

I 0
0 −I



I 0
Y00 I



I Y01
0 I




I 0
.
Y00 I

(9)

Previous block lifting factorizations are based on LUL decomposition. We also propose another novel block lifting factorization of
DCT-II and IV based on ULU decomposition.
Computing three matrices without P, diag{I, −X03 } and W
in (6), we can obtain the following matrix.


X 

(10)

The block lifting matrices are multiplied from the left side of X as


where




I
0 I −X12
I −X10
X=I
0I−X11 I 0
I
⎧
√ [M
]
⎪
2CII2 − I
⎪ X10 =⎨
M
[ 2 ]where X11 = − √12 CIII
.
⎪
⎪
2
M
√ [2]
⎩
[M
]
X12 =
2CII − CII2

M

M

[
] [
]
X13 = X03 = CIV2 CII2 . (11)Fig.2(b) shows M -channel BLDCT-II in (11).
Similarly, we can obtain M -channel BLDCT-IV based on ULU
decomposition as follows:





I 0 I Y10
I 0
I Y10
[M ]
CIV =
Y11 I 0 I
0 −I 0 I
where

3.2. Block Lifting Factorization based on ULU Decomposition




I 0
I 0 I X01
X00 I
X02 I 0 I

 [M ]
M
[
]
1
CII2
CII2
= √
M]
[M
]
[
2
2
2 −CIII
CIII

Hence, we can obtain M -channel BLDCT-II based on ULU decomposition as follows:





I 0 I X10
I X12
I
0
[M ]
W
CII = P
X11 I 0 I
0 −X13 0 I

Y10 = −V1T.
Y11 = (I − V0 )V1−T(12)

3.3. Completion of Lifting Factorization
Although (6) and (11) are not complete lifting structure due to X03
and X13 in (6) and (11), we can achieve the completeness by iterat[M ][M ]ing lifting factorization of CII and CIV with shrunk size shown[4]
as Fig.2. Therefore, CII has special lifting structures as




1 1 1
0 −1
[2]
[2]
[2]
, X01 =
X00 = X02 =−1 2
2 1 −1
1 −1 −1
0 1
[2]
[2]
[2]
X10 = X12 =, X11 =1 −2
2 −1 1
1 α 1 0 1 α[2][2]
X03 = X13 =0 1 β 1 0 1
where

α=

cos(− π8 ) − 1π, β = sin(− ).
sin(− π8 )8Fig.3(a) and (b) show 4-channel BLDCT-IIs in (6) and (11). The
white circles are rounding operators and the black ones are adders. It
is clear that 4-channel BLDCT-IIs have an efficient structure because
they have only five rounding operators, respectively.

482

Table 1. Comparison of lossless image coding (Entropy [bpp]).
M =8
M = 16
Image
Komatsu’s
Tran’sBLDCT-II
BLDCT-II(512 × 512) RDCT [6] BinDCT [8]
LUL
ULU
LUL
ULU
Baboon6.275
6.896
6.273 6.273 6.257 6.239
Barbara5.022
5.511
5.015 5.010 5.082 5.002
5.217
5.732
5.216 5.211 5.275 5.231
Boat
5.248
5.913
5.249 5.244 5.289 5.250
Elaine
6.071
6.384
6.072 6.067 5.917 5.870
Finger1
Finger2
5.869
6.145
5.866 5.859 5.702 5.624
5.189
5.711
5.183 5.179 5.248 5.195
Goldhill
6.179
6.679
6.178 6.177 6.148 6.129
Grass
Lena
4.686
5.217
4.676 4.676 4.830 4.754
4.976
5.516
4.975 4.973 5.077 5.032
Pepper
Ave.
5.473
5.970
5.470 5.467 5.483 5.433

Image(512 × 512)
BaboonBarbaraGoldhill
Lena
PepperTable 2. Comparison of lossy image coding (PSNR [dB]).
M =8
Bit rate Komatsu’s
Chen’sTran’sBLDCT-II[bpp]
RDCT [6] IntDCT [7] BinDCT [8]
LUL
ULU
0.25
22.56222.55920.71322.566 22.567
0.50
24.79924.76821.85124.794 24.803
1.00
28.23728.15924.54228.241 28.245
0.25
26.92826.90323.70226.935 26.936
0.50
30.65330.54827.14130.657 30.660
1.00
35.88235.82731.18335.893 35.895
0.25
29.35529.36027.35229.354 29.364
0.50
31.92031.93829.27431.927 31.926
1.00
35.19535.30731.30635.210 35.210
0.25
31.83431.79729.02831.832 31.836
0.50
35.45235.41432.25435.459 35.458
1.00
38.70238.95135.51538.774 38.765
0.25
31.38031.37828.48731.389 31.392
0.50
34.37734.37131.52534.363 34.373
1.00
36.67836.84234.15936.700 36.703

4. RESULTS

M = 16BLDCT-II
LUL
ULU
22.711 22.709
25.033 25.019
28.394 28.366
27.900 27.904
31.625 31.600
36.180 35.979
29.607 29.606
32.112 32.064
34.898 34.744
32.522 32.508
35.658 35.501
36.815 36.980
31.924 31.923
34.192 34.127
35.835 35.660

4.2. Application to lossy image coding

In this paper, we design four 8 and 16-channel BLDCT-IIs based on
LUL and ULU decomposition. They are compared to the conventional methods, and the validity of them are shown in lossless-tolossy image coding.

If lossy compressed data is required, it can be achieved by interrupting the obtained lossless bit stream. The comparison of2552
PSNR [dB] = 10 log10MSE

4.1. Application to lossless image coding

where MSE is the mean squared error in lossy image coding areshown in Table 2. We chose Komatsu’s RDCT [6], Chen’s IntDCT [7] and Tran’s BinDCT [8] as the conventional methods. In
Table 2, our BLDCT-IIs present better performance than the conventional IntDCT-IIs in lossy image coding. In low bit rate, thetexture remained by using 16-channel BLDCT-II is more crear than
8-channel IntDCT-IIs because high frequency components can beanalyzed by bigger block size. Fig.4 shows the enlarged images of‘BARBARA’ which are the original image and its lossy compressed
images by the conventional IntDCT-IIs and the proposed BLDCT-IIs
when bit rate is 0.25 [bpp].

Our BLDCT-IIs are applied to lossless-to-lossy image coding. The
set partitioning in hierarchical trees (SPIHT) progressive imagetransmission algorithm [11] was used to encode the transformed
images. The comparison of
Entropy [bpp] =Total number of bits [bit]Total number of pixels [pixel]

in lossless image coding are shown in Table 1. We chose Komatsu’s
reversible DCT (RDCT) [6] and Tran’s binary DCT (BinDCT) [8]as the conventional methods. Chen’s IntDCT [7] was not chosenbecause it has so bad results for lossless image coding. In Table 1, it
is obvious that our BLDCT-IIs present better performance than theconventional IntDCT-IIs in lossless image coding. Each of BLDCTII shows the different performance depending on an image.

483

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Fig. 4. Enlarged image of ‘Barbara’ (bit rate: 0.25 [bpp]): (a)original image, (b)compressed image by 8-channel Komatsu’s RDCT [6], (c)8channel Chen’s IntDCT [7], (d)8-channel Tran’s BinDCT [8], (e)8-channel BLDCT-II (LUL), (f)8-channel BLDCT-II (ULU), (g)16-channel
BLDCT-II (LUL), and (h)16-channel BLDCT-II (ULU) .

5. CONCLUSION
In this paper, we proposed a novel IntDCT-II and IV based on block
lifting structure. Our IntDCT-II and IV, called M -channel BLDCTII and IV, have arbitrary block size M that is not only 8. In addition,
our BLDCT-II included BLDCT-IV are more suitable for losslessto-lossy image coding, because it shows better performance than theconventional IntDCT-IIs. Our BLDCT-II and IV can be easily extended into ones with different size which is more suitable.
6. 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.
7. REFERENCES[1] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,
Academic Press, 1990.
[2] W. Pennebaker and J. Mitchell, JPEG, Still Image Data Compression Standard, NY: Van Nostrand, 1993.
[3] T. Sikora, “MPEG digital video-coding standards,” IEEE Signal Process. Mag., vol. 14, no. 5, pp. 82–100, Sept. 1997.
[4] J. P. Princen and A. B. Bradley, “Analysis/synthesis filter bankdesign based on time domain aliasing cancellation,” IEEE
Trans. Acoust., Speech, Signal Process., vol. 34, no. 5, pp.
1153–1161, Oct. 1986.

484[5] M. J. Weinberger, G. Seroussi, and G. Sapir, “The LOCOI lossless image compression algorithm: principles and standardization into JPEG-LS,” IEEE Trans. Image Process., vol.
9, no. 8, pp. 1309–1324, Aug. 2000.
[6] K. Komatsu and K. Sezaki, “Reversible discrete cosine transform,” in Proc. of ICASSP’98, Seattle, WA, May. 1998.
[7] Y. J. Chen, S. Oraintara, and T. Q. Nguyen, “Integer discretecosine transform (IntDCT),” in Proc. of 2nd ICICS’99, Singapore, Dec. 1999, Invited paper.
[8] T. D. Tran, “The binDCT: fast multiplierless approximationof the DCT,” IEEE Signal Process. Lett., vol. 7, pp. 145–149,
2000.
[9] W. Sweldens, “The lifting scheme: a custom-design construction of biorthogonal wavelets,” Appl. Comput. Harmon. Anal.,
vol. 3, no. 2, pp. 186–200, 1996.
[10] S. Iwamura, Y. Tanaka, and M. Ikehara, “An efficient lifting
structure of biorthogonal filter banks for lossless image coding,” in Proc. of ICIP’07, San Antonio, TX, Sept. 2007.
[11] 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.