INTEGER FAST LAPPED ORTHOGONAL TRANSFORM BASED ON
DIRECT-LIFTING OF DCTS FOR LOSSLESS-TO-LOSSY IMAGE CODING
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
Integer lapped orthogonal transforms (LOTs) are vital technologies
for the unification of lossless and lossy image coding, called losslessto-lossy image coding. In this paper, we present an efficient realization of integer fast LOT (FLOT) based on direct-lifting of discretecosine transforms (DCTs) which are type-II, III and IV. Although theconventional integer FLOTs suffer from degradation of coding performance due to much rounding error generated by cascading lifting
structures, this paper presents a realization of a simpler, faster andmore efficient transform with only some adders, 1-bit shifters anddirect use of DCTs for lifting coefficients. As result, the proposed
method is validated in lossless-to-lossy image coding.
Index Terms— Direct-lifting, discrete cosine transform (DCT),
fast lapped orthogonal transform (FLOT), lossless-to-lossy image
coding
1. INTRODUCTION

2. REVIEW
2.1. Discrete Cosine Transform (DCT)

With the rapid development of hardware such as PCs and mobile
phones etc. and the continual expansion of broadband, lossless-tolossy image coding, which is the unification of lossy and losslessimage coding, is required to obtain higher quality and compression
ratio. Since JPEG [1], which is the international standard in image coding, separately uses discrete cosine transform (DCT) [2] anddifferential pulse code modulation (DPCM) for lossy and losslessimage coding, respectively, it cannot achieve lossless-to-lossy image
coding. In lossless-to-lossy image coding, lossy compression is obtained by interrupting the scalable lossless data which is coded byinteger transform. Although 5/3-tap discrete wavelet transform (5/3DWT) by lifting structures [3] with integer coefficients and rounding
operations is used for lossless compression in JPEG2000 [4] whichis the next generation standard, its lossy performance is undesirable.
Also, a hierarchical lapped biorthogonal transform (HLBT) in JPEG
XR [5], which is the another next generation standard, has achieved
lossless-to-lossy image coding, but it does not have sufficient coding
performance.
On the other hand, DCT in JPEG is known as one of the fastest
and the most efficient transforms for image coding. HLBT in JPEG
XR is also a DCT-based lapped transform. As such DCT-basedlapped transform, fast lapped orthogonal transform (FLOT) [6] iswell-known. FLOT is constructed by cascading DCT type-II (DCTII), type-III (DCT-III), type-IV (DCT-IV), rotation matrices withThis 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-4577-0539-7/11/$26.00 ©2011 IEEE

π/4 angles, ±1 operations, a delay matrix and permutation matrices. Although it is easy that FLOT is applied to lossless-to-lossy
image coding by lifting factorization of rotation matrices, called integer FLOT, the obtained integer-to-integer transform is unsuitable
due to much rounding error by many rounding operations.
In this paper, we present an efficient realization of integer FLOT
based on direct-lifting of DCTs. The proposed FLOT is a simpler,
faster and more efficient transform with only some adders, 1-bit
shifters and direct use of DCTs for lifting coefficients. Finally, ourmethod is validated in lossless-to-lossy image coding simulation.
Notations: I, J, MT and D are an identity matrix, a reversal
identity matrix, transpose of a matrix M and a diagonal matrix withalternating ±1 entries (i.e., D = diag{1, −1, 1, −1, · · · }), respectively.

1525

DCT is basically classified into four types [2]. Among them, type-II,
type-III and type-IV (DCT-II, DCT-III and DCT-IV) are famous andoften used for image coding such as JPEG [1] and JPEG XR [5] etc.
and many devices and fast algorithms for DCT have been developed.
The m-column and n-row element of M -channel DCT-II, DCT-III
and DCT-IV matrices CII , CIII and CIV are defined asm (n + 1/2) π
2[CII ]m,n =cm cosMM2(m + 1/2) nπ[CIII ]m,n =cn cosMM(m + 1/2) (n + 1/2) π2
cos[CIV ]m,n =
M
M
−1
T
T
where C−1
II = CII = CIII , CIV = CIV = CIV ,


√1
√1
(m = 0)(n = 0)2
2
cm =, cn =
1(m = 0)1(n = 0)

and 0 ≤ m, n ≤ M − 1, respectively. For simplicity, let us define
as that M = 2n (n ∈ N). Also, when “cos” is replaced by “sin”, itis called discrete sine transform (DST).
2.2. Fast Lapped Orthogonal Transform (FLOT)An M -channel fast lapped transform can be constructed in polyphasestructure from components with well-known fast-computable algorithms such as DCT and DST. One of the most elegant solution is

ICASSP 2011

Fig. 1. A direct-lifting (white circles represent rounding operations).
the type-II FLOT whose polyphase matrix is [6]




I
0
CII 0
E(z) =
WΛ(z)W
WĨ
0 SIV CIII
0 CIV

(1)

where







1 I I
I 0
0 J
, Λ(z) =, Ĩ =
W= √
−1
I 0
0 z I
2 I −Iand SIV is type-IV (DST-IV) in DST. Since the following relationship between DST-IV and DCT-IV matrix can be easily established:
SIV = DCIV J, (1) can be represented by




CII 0
I
0
WΛ(z)W
WĨ. (2)E(z) =
0 DCIV JCIII
0 CIV
The FLOT with this polyphase matrix is implemented in the top halfin Fig. 2.
2.3. Direct-Lifting Structure
The lifting structure is cascading elementary matrices which are
identity matrices with one single nonzero off-diagonal element [3].
In [7], we have presented the direct-lifting. It is a breakthroughstructure because a combination of every block and its inverse one
can be directly applied to the lifting coefficient as shown in Fig.
1 where xi , xj , yi and yj are the input signals and their output
signals, respectively. It is also expressed by




 

U 0
I 0 I −U−1
I 0
0 I
=
U I
−I 0 U I 0
0 U−1
Iwhere U is an arbitrary nonsingular matrix.

where CII CIII = CIII CII = I. The FLOT with this polyphasematrix are implemented in the bottom half in Fig. 2. The filter properties of (3) completely accord with them of (2) because it is obtainedby only transposition of CII .
Next, as already mentioned, we consider the parallel process of
two different type FLOTs in (2) and (3). It means that when a row(column) signals are processed by (2), other row (column) signals
are processed by (3). However, each DCT matrix in both FLOT is
processed by direct-lifting between each system which is each combination of DCT-II in (2) and DCT-III in (3), DCT-III in (2) and
DCT-II in (3) and DCT-IV in (2) and DCT-IV in (3). These combinations are shown in dashed line area in Fig. 2 and factorized into
direct-liftings as follows:




 

CII 0
I 0
0 I
I 0 I −CIII
=
I
CII I
−I 0 CII I 0
0 CIII



 


I 0
0 I
I 0 I −CII
CIII 0=I
CIII I−I 0 CIII I 0
0 CII




 

I 0
CIV
0 I
I 0 I −CIV
0
=
I
CIV I
−I 0 CIV I 0
0 CIV
3.2. More Multiplierless Structure
In above subsection, DCT parts were implemented with lifting structures. This subsection produces the lifting factorizations of Ws.
Since W is constructed by rotation matrices with π/4 angles, it canbe simply factorized into lifting structures. But such case generates
many multipliers. To eliminate multipliers, the following matrices
are used in place of Ws.
 1 

 1
√ I
0
I 0
I 0
I 2I
2
√
W=
W1 =
0 −I 0 I
−I I
2I
0



 

√
2I 0
I 0 I − 12 I I 0=
W2 = W1
0 √2 I
0 −I
I I 0 I
√





2I 0
I 0 I −I I 0
W3 =
W
=
1
1
0 √2 I
0 −I
I I 0 I
2

 


 1
√ I
0
I 0
I 0
I I
2
√
=
W4 = W
0 −I 0 I − 12 I I
02IFirst, we present another class of FLOT. DCT-II matrix CII in (2) is
moved to the last building block. Since
 


CII 0
CII 0
=
WΛ(z)W,WΛ(z)W
0 CII
0 CII

Note that a combination of an 1/2 multiplier and a rounding operation can be replaced by an 1-bit shifter [8]. Using these matrices, (2)and (3) are represented as follows:

 1
√ I
0
2
√
E(z)
E1 (z) 
0
2I




I
0
CII 0
=
W1 Λ(z)W2
W1 Ĩ
0 DCIV JCIII
0 CIV
(4)
√

2I 0
E2 (z) E(z)0 √12 I




I
0
0
CII
W3 Λ(z)W2
W1 Ĩ
=
0 CIII CIV
0 DCIV J(5)(2) is rewritten as




CII
I
0
0
E(z) =
WΛ(z)WWĨ
0 CIII CIV
0 DCIV J

Fig. 3 shows the process of the two-dimensional transform of animage by the proposed FLOTs. Let M (M = 2k , k ∈ N) be block
size, the i-th (1 ≤ ((i + 1) mod M ) ≤ M/2) row signals andthe j-th ((M/2 + 1) ≤ ((j + 1) mod M ) ≤ M ) row signals,

3. FLOT BASED ON DIRECT-LIFTING OF DCTS
In this section, a realization of FLOT for lossless-to-lossy image coding is presented. The system is implemented by the parallel processof two different type FLOTs, direct-lifting of DCTs in the process,some adders and some 1-bit shifters. It means that the proposed
FLOT is a simple, fast and efficient transform for lossless-to-lossy
image coding.
3.1. Application of Direct-Lifting of DCTs

(3)

1526

Fig. 2. The parallel process of two different type FLOTs: (top) FLOT in (2), (bottom) FLOT in (3).

Table 1. Comparison of lossless image coding (LBR [bpp]).
Test
HLBT
Conv. FLOTs
Prop. FLOTs
images[5]
8 × 16 16 × 32 8 × 16 16 × 32
Barbara
4.95
5.00
4.95
4.95
4.85
Boat
5.21
5.22
5.22
5.19
5.16
5.89
5.91
5.79
5.89
5.75
FingerE4 (z)  E(z)

=

CII
0


0
√
0
2I



I
0
0
W4 Λ(z)W3
W4 Ĩ
0 CIII CIVDCIV J
(7)

 1
√

2

I

Similarly, the i-th column signals and the j-th column signals, i.e.,
the red and blue areas in Fig. 3, are processed by FLOTs in (6) and(7), respectively.
4. LOSSLESS-TO-LOSSY IMAGE CODING RESULTS

Fig. 3. The process of the two-dimensional transform of an image
by the proposed FLOTs.

i.e., the yellow and green areas in Fig. 3, are processed by FLOTsin (4) and (5), respectively. Here, note that the scales in the√ one2 anddimensionally-transformed
outputsignals
are
risen
to
×1/
√
× 2 as compared with the output signals transformed by normal
FLOTs as shown in the dashed√ line√area in Fig. 3. In this regard,
considering these scales 1/ 2 and 2 for the next column process,(2) and (3) are represented again as follows:√
E3 (z)  E(z)

0



√1 I
2




CII 0
I
0
W2 Λ(z)W1
W2 Ĩ
0 CIV
0 DCIV JCIII
(6)


=

2I
0

1527

In this paper, the proposed 8 × 16 and 16 × 32 FLOTs are validated in lossless-to-lossy image coding. As targets for comparison,
HLBT in JPEG XR [5] and 8 × 16 and 16 × 32 FLOTs, which areapplied the simple lifting factorizations of rotation matrices, werechosen. To evaluate transform performance fairly, a very common
wavelet-based coder SPIHT [9] was adopted for all. Also, for image
boundaries, the periodic extension was used in all LOTs. Moreover,
we used 512 × 512 gray scale test images such as Barbara.
First, the proposed LOTs and the conventional methods are applied to lossless image coding. The comparison of lossless bitrate(LBR):
LBR [bpp] =Total number of bits [bit]Total number of pixels [pixel]

in lossless image coding is shown in Table 1.
If lossy compressed data is required, it can be achieved by interrupting the obtained lossless bitstream. The comparison of peaksignal-to-noise ratio (PSNR):2552
PSNR [dB] = 10 log10
MSE
where MSE is the mean squared error in lossy image coding areshown in Table 2. Furthermore, Fig. 4 shows the enlarged images ofBarbara which are lossy compressed images by the proposed FLOTs
and the conventional methods when bitrate is 0.25[bpp].

Table 2. Comparison of lossy image coding (PSNR [dB]).
Test
HLBT
Conv. FLOTs
Prop. FLOTs[5]
8 × 16 16 × 32 8 × 16 16 × 32
imagesbitrate: 0.25 [bpp]Barbara
27.01
27.80
28.72
27.83
28.77
Boat
28.80
28.93
28.98
28.97
29.04
22.95
23.65
23.94
23.57
23.97
Fingerbitrate: 0.50 [bpp]Barbara
30.85
31.70
32.55
31.76
32.67
32.02
32.05
32.00
32.13
32.13
Boat
Finger
26.31
26.76
27.27
26.79
27.32
bitrate: 1.00 [bpp]Barbara
36.00
36.33
36.65
36.59
37.13
Boat
35.21
35.20
35.07
35.44
35.43
Finger
30.12
30.57
31.29
30.64
31.44

Table 3. Comparison of number of rounding operations in each onedimensional transform of M × 1 signals.
Conv. FLOTs Prop. FLOTs
8 × 1690
36
16 × 32
240
72

Even though the proposed FLOTs and the conventional LOTs
have same transfer function, all proposed FLOTs showed better coding performance than the conventional methods, especially lossy image coding results showed excellent performance. We consider that
this is mainly due to the reduction of rounding operations as shownin Table 3. On the other hand, note that our FLOTs have a simple andfast implementation due to the construction with only some adders,some 1-bit shifters and direct use of DCTs for lifting coefficients.
Despite such fact, the results in this section showed good performance. It means that the advantages in our methods were proved.

Fig. 4. Enlarged images of Barbara in lossy image coding (bitrate:
0.25 [bpp]): (top-left) original image, (top-right) HLBT in JPEG
XR, (middle-left) conv. 8 × 16 FLOT, (middle-right) conv. 16 × 32
FLOT, (bottom-left) prop. 8×16 FLOT, (bottom-right) prop. 16×32
FLOT.

5. CONCLUSION
In this paper, we presented a fast lapped orthogonal transform(FLOT) for efficient lossless-to-lossy image coding, which is basedon direct-lifting of discrete cosine transforms (DCTs) for lifting
coefficients, some adders and some 1-bit shifters. Due to merging
many rounding operations by use of direct-lifting, our proposals
show better coding performance than the conventional methods inlossless-to-lossy image coding. However, the proposed method cannot be applied the symmetric extension for image boundaries. If theuse will becomes possible, it should achieves more efficient coding performance. In addition, although has less blocking artifacts
than the conventional methods, generated ringing artifacts should be
improved.
6. REFERENCES[1] ISO/IEC 10918-1, Information technology - Digital compression and coding of continuous-tone still images Requirements
and Guidelines.
[2] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,
Academic Press, 1990.

1528[3] W. Sweldens, “The lifting scheme: A new philosophy inbiorthogonal wavelet constructions,” in Proc. of SPIE 2569,
1995.
[4] ISO/IEC 15444-1, Information technology - JPEG 2000 image
coding system: Core coding system.
[5] ISO/IEC 29199-2, JPEG XR image coding system - Part 2: Image coding specification.
[6] H. S. Malvar, Signal Processing with Lapped Transforms, Norwood, MA: Artech House, 1992.
[7] T. Suzuki and M. Ikehara, “Integer DCT based on direct-liftingof DCT-IDCT for lossless-to-lossy image coding,” IEEE Trans.
Image Process., vol. 19, no. 11, pp. 2958–2965, Nov. 2010.
[8] Y. J. Chen, S. Oraintara, T. D. Tran, K. Amaratunga, andT. Q. Nguyen, “Multiplierless approximation of transforms withadder constraint,” IEEE Signal Process. Lett., vol. 9, no. 11, pp.
344–347, Nov. 2002.
[9] 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.