SIMPLIFIED DCT-LIFTING-BASED REVERSIBLE LAPPED TRANSFORMS USINGPARALLEL PROCESSING OF TWO SAME TYPE LAPPED TRANSFORMS
Taizo Suzuki

Masaaki Ikehara

Faculty of EIS, University of Tsukuba
Tsukuba, Ibaraki, 305-8573 Japan
Email: taizo@cs.tsukuba.ac.jp

EEE Dept., Keio University
Yokohama, Kanagawa, 223-8522 Japan
Email: ikehara@tkhm.elec.keio.ac.jp

ABSTRACT

They can also reuse any existing software/hardware for DCTs as thelifting coefficient blocks. The RevLTs in [14] had very complicatedlifting coefficient blocks in exchange for few lifting steps. Although
the another RevLTs in [15] obtained by considering parallel processing of two ‘different’ type LTs have simple lifting coefficients,
they have complicated implementations in exchange for removing
floating-point multipliers.
In this paper, we present a realization of the RevLTs with simplified implementations, which are constructed by DCT and DST
matrices, adders, and bit-shifters, for lossy-to-lossless image coding
than the conventional RevLTs. By considering parallel processingof two ‘same’ type LTs unlike the RevLTs in [15] and using DCTlifting factorizations in [14,17], more parts are implemented by only
simple DCT-lifting coefficients. Furthermore, the Hadamard transform and scaling parts in the RevLTs are effectively implemented
by extending 2D non-separable lifting structures derived from L-LT
in [12]. As a result, the proposed RevLTs achieve not only simplified
implementations with any block size, but also comparable lossy-tolossless image coding performance to the conventional RevLTs.
Notations: I, J, diag{· · · }, ·T , and ⊗ are an identity matrix, areversal identity matrix, a block diagonal matrix, matrix transposition, and a Kronecker product, respectively.

We present a realization of reversible lapped transforms (RevLTs)
with simplified implementations, which are constructed by DCT and
DST matrices, adders, and bit-shifters, for lossy-to-lossless image
coding in this paper. Each DCT or DST matrix is directly used toeach lifting coefficient block and it is called DCT-lifting structure.
The structure is obtained by considering parallel processing of two‘same’ type LTs and using DCT-lifting factorizations as our previous
work. Furthermore, the Hadamard transform and scaling parts in the
RevLTs are effectively implemented by extending 2D non-separable
lifting structures derived from lifting-based lapped transform (L-LT)
used for JPEG XR, the newest image coding standard. As a result,the proposed RevLTs achieve not only simplified implementations
with any block size, but also comparable lossy-to-lossless image
coding performance to the conventional RevLTs.
Index Terms— DCT, DST, lapped transform (LT), lifting structure, lossy-to-lossless image coding.
1. INTRODUCTION
JPEG and H.26x series are DCT [1]-based image/video compression(image coding) standards [2–5]. Since type-II DCT (DCT-II) has
high energy compaction capability, it is often applied to the transform part in image coding. Type-III DCT (DCT-III) is the inverse
transform of DCT-II. Such facts have provided many fast implementations for DCTs [6–9]. However, the DCTs generate an unpleasant
blocking artifact for the reconstructed signals in low-bitrate coding
due to the discontinuity between blocks. M -channel (M = 2k ,k ∈ N) lapped transform (LT) [10] has overcame such a problem.
Let LT in this paper be DCT-based LT well-known as a fast LT.
Several integer-to-integer transforms (integer transforms), mainly
constructed by lifting structures [11], have been researched toachieve lossy-to-lossless image coding which has the scalability
from lossless to lossy data. A 4 × 8 lifting-based lapped transform(L-LT) [12] used for JPEG XR [13], the newest image coding standard, is one of the most popular integer transforms. It has a very
simple 2D non-separable lifting structures with only several adders
and bit-shifters, and achieves low-complexity lossy-to-lossless image coding. Unfortunately, its filter size is too small to perform
sufficient coding. In [14] and [15], we have proposed reversible
LTs (RevLTs) to improve the coding performance with larger filter
size than the 4 × 8 L-LT. The conventional RevLTs were based on
DCT-lifting structures, which are directly applied DCT matrices tolifting coefficient blocks, i.e., direct-lifting structures of DCTs [16].
This work was supported by JSPS Grant-in-Aid for Young Scientists (B)Grant Number 25820152.

978-1-4799-5751-4/14/$31.00 ©2014 IEEE5586

2. REVIEW AND DEFINITION
2.1. Lapped Transform (LT)M -channel LT in this paper is based on polyphase structure fromcomponents with well-known fast-computable algorithms and a scaling coefficient s like L-LT in [12]. One of the most elegant solutions
is shown in Fig. 1 and expressed as [14, 15]E(z) = P diag{I, S IV C III }WΛ(z)W diag{C II , C IV }SWĨ
(1)
where
Λ(z) = diag{I, z −1 I}, S = diag{sI, s−1 I}
[
]
[
]
1 I
I
0 J
, Ĩ =,
W= √I 0
2 I −Iz is a delay element, and the (m, n)-element of permutation matrix
P as1 (n ≤ M/2 − 1 and m = 2n)[P]m,n = 1 (n ≥ M/2 and m = 2n − M + 1) ,
0 (otherwise)

ICIP 2014

Fig. 1. Lattice structure of M -channel LT.

respectively. Also, C II , C III , C IV , and S IV are DCT-II, DCT-III,
type-IV DCT (DCT-IV), and type-IV DST (DST-IV) matrices with
N × N (N = M/2) size. The (m, n)-elements of C II and C IV aredefined as√()
m (n + 1/2) π
2[C II ]m,n =cm cosNN√()
2(m + 1/2) (n + 1/2) π[C IV ]m,n =
cos
N
N
√
T
where cm = 1/ 2 (m = 0) or 1 (m ̸= 0), C −1
IV = C IV = C IV ,T
and C III and S IV are established as C III = C −1=
C
II and S IV =IID C IV J = J C IV D ([D]m,n = (−1)m (m = n) or 0 (m ̸= n)),respectively. The optimal s is experimentally-determined in eachblock size M , e.g., s = 0.8981 and 0.9360 in cases of M = 8 and16, respectively. It is clear that the LTs with the scaling coefficients = 1 are lapped orthogonal transforms (LOTs) with type-II lattice
structure in [10].

Fig. 2. Block-lifting structures (white circles mean rounding operations).

3. SIMPLIFIED DCT-LIFTING-BASED REVLT
We introduce a realization of RevLTs with simplified implementations in this section. When an image X is 2D-transformed to Y by
an 1D transform T = TK−1 · · · T1 T0 , the 2D-transformed image
Y is expressed by
Y = TK−1 · · · T1 T0 XTT0 TT1 · · · TTK−1 .

2.2. DCT-Lifting Structure
The block-lifting structure [18], a special class of standard lifting
structure [11], achieves an effective lossy-to-lossless image coding
by merging many rounding operations. In Fig. 2, the analysis input
signal vectors xi and xj , the analysis output and synthesis input
signal vectors yi and yj , the synthesis output signal vectors zi andzj , and the lifting coefficient blocks TL and TU are presented by

It means that X is 2D-transformed by Tk+1 (0 ≤ k ≤ K − 2,K ∈ N) after 2D transform by Tk . With the fact, the proposed
RevLTs are obtained by each 2D transform of Ĩ, W, S, P, and theresidual part in Eq. (1). The parts Ĩ and P are not discussed any
more because they just only reorder signals.

yj = xj + round{TL xi }yi = xi + round{TU yj }zi = yi − round{TU yj } = xi
zj = yj − round{TL yi } = xj .

3.1. 2D Non-Separable Lifting Factorization of Hadamard
Transform Part

In this case, the matrices and their inverse matrices are expressed by
[

]
I
0
,
TL I
[
]
I TU
,
0
I

[
[

I
TL
I
0

0
I

]−1

[

]

I
0
−TL I
]−1 [
]
TU
I −TU
=
.
I
0
I

The first Hadamard transform part W in Eq. (1) is effectively implemented by extending a 2D non-separable transform in [12]. Consider an image that has been 2D-transformed by W2D , which is the2D transform of W, as
[

T
T
T
T
YLL
YHL
YLH
YHH

]T

[
]T
= W2D XTLL XTHL XTLH XTHH=

where X×× s are the top-left, top-right, bottom-left, and bottom-right
N × N blocks of an M × M image, and Y×× s are their respective
output blocks. We extend the 4 × 4 2D non-separable transformin [12] to 2M × 2M 2D non-separable transform as

When the lifting coefficient block is directly expressed by a DCT or
DST matrix, e.g., TL = C II , the structure is termed DCT-lifting
structure, a special class of direct-lifting structure [16], in this paper.
The structure allows any DCT algorithm and software/hardware in
the block.

978-1-4799-5751-4/14/$31.00 ©2014 IEEE

5587



I
1 I
W2D = W ⊗ W = 
2 I
I

I
−I
I
−I

I
I
−I
−I


I
−I
,
−I
I

ICIP 2014

and its lifting structures are expressed by
W2D =




I 0 0 0I 0 0 0I −I 0 −II
0 0
0 0 I 0 0 I I 0 00 I 0 0 0 0 I 0 0 0
I0
0 0 0 I0 0 0 I
0 0 0
I




I 0 0 0I 0 0
0
I 0 0 01
00   2 I I 0 0  0 I 0 0 
0 I×
0 0 0 −I  0 0 I 0 0 I I 0
0 0 −I 0
0 I 0 I0 0 0 I




I
0 0 0
I I 0 II 0 0 01
− I I 0 0 0 I 0 0 0 I −I 0

2
×
.
 0
I
0
0 I 0 0 0 I 0 0 0
0 0 0 I
0 0 0
I
0
0 0 I
The lifting structure has very simple operations with only 5M
adders, M bit-shifters, and permutations. It is easier processing than
the implementation for the Hadamard transform part in [15].

Fig. 3. 1D separable block-lifting structure of Γ(z) (white circles
mean rounding operations).

The last part diag{C II , C III } in Eq. (3) is factorized into customized direct-lifting structures as [16][diag{C II , C III } =3.2. 2D Non-Separable Lifting Factorization of Scaling Part
In the same way as Section 3.1, S2D , which is the 2D transform of
the scaling part S, is also implemented by using a 2D non-separable
lifting structure as [12]
[
]T
[ T
]T
T
T
T
= S2D XTLL XTHL XTLH XTHHYLL YHL
YLH
YHH
where
S2D = S ⊗ S = diag{s2 I, I, I, s−2 I}



I
0 0 0
0 0 0 II 0 0
I 0 0 00=
0 I 0
0 0 I 0  0
2−I 0 0 0
s I 0 0 I


−2
I
0 0
I 0 0 −s I
0 I 0
0
I 0
0 



×
0 I
0 0 I
0  00 0 0
Is2 I 0 0


0
0
.
0
I

Since s2 and s−2 are floating-point coefficients which cause highcomplexity, they are experimentally approximated to dyadic coefficients as α/2β (α, β ∈ N) to delete multipliers, e.g., diag{s2 , s−2 } =diag{413/29 , 317/28 } and diag{449/29 , 292/28 } in cases of
M = 8 and 16, respectively.

(2)

which is a part of the residual part. After WΛ(z)W in Eq. (2) isfactorized into simple lifting structures as
]
[
][
]
[
][
I
0
I 0 I − 12 I
I 12 I
Λ(z)WΛ(z)W =
−I I
I I 0
I
0 I
√
√
by interchanging the scaling coefficients 2 and 1/ 2 between two
Ws, C II in Eq. (2) is moved from the right to the left as

978-1-4799-5751-4/14/$31.00 ©2014 IEEE

1
C
2 III

I

][

[

][
][
]
[ 1
][
]
0 −I
I 0 I 12 C III
I 0
I 2 C IIIΓ(z) =Λ(z)I 0−C II I 0 I−C II I
0 I
and shown in Fig. 3. Consequently, two redundant lifting-based Ws
required in [15] are grouped into the DCT-lifting structures with 1
bit-shifters. Moreover, the 1D separable block-lifting-based Γ(z) is
2D-implemented by using 2D non-separable block-lifting structuresin [17] for better coding.
Next, we consider the parallel processing of two LTs in Eq. (1)as with the RevLTs in [15], where the two LTs are completely ‘same’
types unlike those used in [15]. It means that when a row (column)
signal vector xi is processed by one of two LTs, other row (column)
signal vector xj is processed by another one. The DCT-IV and DSTIV matrices C IV and S IV in Eq. (1) are processed by direct-lifting
structures in each combination of C IV and S IV stepping over thetwo LTs. The direct-lifting structures are presented as [14, 15][diag{C IV , C IV } =diag{S IV , S IV } =Let Γ(z) beΓ(z) = diag{C II , C III }[][][I 0 I − 21 C IIII×Λ(z)C II I 0I0

By substituting Eq. (4) into Eq. (3), Γ(z) is simplified as[

3.3. Simplified DCT-Lifting Factorizations of Residual PartΓ(z) ≜ diag{I, C III }WΛ(z)W diag{C II , I}

][
][
][
]
0 −I
I
0 I C IIII
0.
−C II I 0
I
−C II I
I 0
(4)

]

I
0
.
−C II I
(3)

5588

0 I
−I 0
0 I
−I 0

][
][

I
C IV
I
S IV

][
]
I −C IVI
00
I
C IV I][][]
0 I −S IV
I
0
.
I 0
I
S IV I0
I][

The resulting lattice structure of RevLT is shown in Fig. 4. The
matrices Ĩ, W, S, Γ(z), and P are 2D-implemented as already described. Note that the RevLTs in [15] required two ‘different’ typeLTs, whereas the proposed RevLTs require two ‘same’ type LTs.
They produce a simpler implementation than the RevLTs in [15].
Also, they have simpler lifting coefficients than those of the RevLTs
in [14].
4. EXPERIMENTAL RESULTS
The proposed 8 and 16-channel RevLTs were designed and compared with the conventional methods in lossy-to-lossless image coding simulation by the lossless bitrate (LBR) [bpp] and peak signal-

ICIP 2014

Fig. 4. Lattice structure of the proposed RevLT (white circles mean rounding operations).

Table 1. Lossless image coding results (LBR [bpp]).
Test
L-LT
8 × 16 RevLTs
16 × 32 RevLTs
Images[12][14] [15] Prop. [14] [15] Prop.
Baboon6.23 6.21 6.21
6.21
6.21 6.22
6.21
Barbara 4.95 4.86 4.90
4.84
4.79 4.82
4.78
Boat
5.21 5.14 5.16
5.13
5.13 5.15
5.12
5.26 5.23 5.26
5.23
5.19 5.20
5.18
Elaine5.89 5.82 5.84
5.82
5.73 5.75
5.73
FingerFinger2
5.61 5.53 5.55
5.52
5.49 5.51
5.48
Goldhill
5.10 5.12 5.15
5.11
5.12 5.14
5.11
Grass
6.09 6.07 6.08
6.07
6.07 6.07
6.06
4.63 4.62 4.66
4.61
4.64 4.66
4.63
Lena
4.99 4.93 4.96
4.93
4.96 4.98
4.96
Pepper

Rate
[bpp]
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00

Fig. 5. Comparison of a particular area of an image Barbara (bitrate:
0.25[bpp]): (left-right) 4 × 8 L-LT, 16 × 32 RevLT in [14], 16 × 32
RevLT in [15], and 16 × 32 proposed RevLT.
to-noise ratio (PSNR) [dB] as follows:
Total number of bits [bit]Total number of pixels [pixel]()
2552
PSNR[dB] = 10 log10
MSE
LBR[bpp] =ing results. Although the RevLTs in [14] show good results by few
lifting steps on the surface, they have very complicated lifting coefficient blocks as already discussed. The proposed RevLTs achieved
not only simplified implementations with any block size, but also
comparable coding performance to the conventional RevLTs.
5. CONCLUSION

where MSE is the mean squared error. To fairly evaluate the performance of transforms, we used several 512 × 512 8-bit grayscale test
images and a wavelet-based coder SPIHT [19] to encode the transformed images as discussed in [20].
Table 1, Table 2, and Fig. 5 show lossless and lossy image cod-978-1-4799-5751-4/14/$31.00 ©2014 IEEE

Table 2. Lossy image coding results (PSNR[dB]).
L-LT
8 × 16 RevLTs
16 × 32 RevLTs
[12]
[14]
[15]
Prop.
[14]
[15]
Prop.
Barbara27.01 28.05 28.03 28.04 28.93 28.91 28.92
30.85 32.14 32.08 32.12 32.86 32.80 32.86
36.00 37.04 36.85 37.03 37.40 37.21 37.40
Finger
22.95 23.73 23.73 23.74 24.02 24.01 24.02
26.31 26.97 26.93 26.96 27.35 27.34 27.36
30.12 30.87 30.82 30.88 31.51 31.45 31.52
Goldhill
29.63 29.70 29.69 29.71 29.71 29.69 29.71
32.02 32.29 32.22 32.29 32.31 32.25 32.32
35.17 35.46 35.30 35.48 35.48 35.33 35.48
Lena
32.76 32.94 32.89 32.91 32.87 32.84 32.85
35.90 36.20 36.08 36.19 36.06 35.98 36.05
38.62 38.93 38.55 38.96 38.80 38.54 38.86
Pepper
32.53 32.42 32.39 32.41 32.16 32.14 32.14
34.71 34.82 34.72 34.81 34.43 34.35 34.42
36.39 36.75 36.52 36.80 36.60 36.42 36.67

5589

We have presented a realization of RevLTs with simplified DCTlifting structures in this paper. The RevLTs were achieved by using
two ‘same’ LTs unlike our previous work and extending 2D nonseparable lifting structures derived from L-LT used for JPEG XR.
As a result, they achieved not only simplified implementations withany block size, but also comparable lossy-to-lossless image coding
performance to the conventional RevLTs.

ICIP 2014

6. REFERENCES[1] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,
Academic Press, 1990.
[2] G. K. Wallace, “The JPEG still picture compression standard,”
IEEE Trans. Consum. Electr., vol. 38, no. 1, pp. xviii–xxxiv,
Feb. 1992.
[3] T. Sikora, “MPEG digital video-coding standards,” IEEE Signal Process. Mag., vol. 14, no. 5, pp. 82–100, Sep. 1997.
[4] T. Wiegand, G. J. Sullivan, G. Bjøntegaard, and A. Luthra,“Overview of the H.264/AVC video coding standard,” IEEE
Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560–
576, July 2003.

[18] T. Suzuki, M. Ikehara, and T. Q. Nguyen, “Generalized blocklifting factorization of M -channel biorthogonal filter banks forlossy-to-lossless image coding,” IEEE Trans. Image Process.,
vol. 21, no. 7, pp. 3220–3228, July 2012.
[19] 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.
[20] T. D. Tran, M. Ikehara, and T. Q. Nguyen, “Linear phase paraunitary filter bank with filters of different lengths and its application in image compression,” IEEE Trans. Signal Process.,
vol. 47, no. 10, pp. 2730–2744, Oct. 1999.

[5] G. J. Sullivan, J.-R. Ohm, W.-J. Han, and T. Wiegand,“Overview of the high efficiency video coding (HEVC) standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 22, no.
12, pp. 1649–1668, Dec. 2012.
[6] W. H. Chen, C. H. Smith, and S. C. Fralick, “A fast computational algorithm for the discrete cosine transform,” IEEE
Trans. Commun., vol. 25, no. 9, pp. 1004–1009, Sep. 1977.
[7] Z. Wang, “Fast algorithms for the discrete W transform and forthe discrete Fourier transform,” IEEE Trans. Acoust., Speech,
Signal Process., vol. ASSP-32, no. 4, pp. 803–816, Apr. 1984.
[8] 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.
[9] Z. Wang, “On computing the discrete Fourier and cosine transforms,” IEEE Trans. Acoust., Speech, Signal Process., vol. 33,
no. 4, pp. 1341–1344, Apr. 1985.
[10] H. S. Malvar, Signal Processing with Lapped Transforms, Norwood, MA: Artech House, 1992.
[11] W. Sweldens, “The lifting scheme: A new philosophy inbiorthogonal wavelet constructions,” in Proc. of SPIE, San
Diego, CA, July 1995, vol. 2569, pp. 1–12.
[12] C. Tu, S. Srinivasan, G. J. Sullivan, S. Regunathan, and H. S.
Malvar, “Low-complexity hierarchical lapped transform forlossy-to-lossless image coding in JPEG XR/HD Photo,” inProc. of SPIE, San Diego, CA, Aug. 2008, vol. 7073, pp. 1–
12.
[13] F. Dufaux, G. J. Sullivan, and T. Ebrahimi, “The JPEG XR
image coding standard,” IEEE Signal Process. Mag., vol. 26,
no. 6, pp. 195–199, 204, Nov. 2009.
[14] T. Suzuki and H. Kudo, “Integer fast lapped biorthogonal transform via applications of DCT matrices and dyadic-valued factors for lifting coefficient blocks,” in Proc. of ICIP’13, Merboulne, Australia, Sep. 2013, pp. 800–804.
[15] T. Suzuki and M. Ikehara, “Integer fast lapped transforms
based on direct-lifting of DCTs for lossy-to-lossless image
coding,” EURASIP J. Image. Video Process., vol. 2013, no.
65, pp. 1–9, Dec. 2013.
[16] T. Suzuki and M. Ikehara, “Integer DCT based on directlifting of DCT-IDCT for lossless-to-lossy image coding,” IEEE
Trans. Image Process., vol. 19, no. 11, pp. 2958–2965, Nov.
2010.
[17] T. Suzuki and H. Kudo, “Two-dimensional non-separable
block-lifting-based M -channel biorthogonal filter banks,” inProc. of EUSIPCO’14, 2014, accepted.

978-1-4799-5751-4/14/$31.00 ©2014 IEEE

5590

ICIP 2014