IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.5 MAY 2017

1109

PAPER

Dual-DCT-Lifting-Based Lapped Transform with
Improved Reversible Symmetric Extension
Taizo SUZUKI†a) , Member and Masaaki IKEHARA†† , Fellow

SUMMARY We present a lifting-based lapped transform (L-LT) anda reversible symmetric extension (RSE) in the boundary processing for
more eﬀective lossy-to-lossless image coding of data with various qualities
from only one piece of lossless compressed data. The proposed dual-DCTlifting-based LT (D2 L-LT) parallel processes two identical LTs and consistsof 1-D and 2-D DCT-liftings which allow the direct use of a DCT matrix ineach lifting coeﬃcient. Since the DCT-lifting can utilize any existing DCT
software or hardware, it has great potential for elegant implementations thatare dependent on the architecture and DCT algorithm used. In addition, we
present an improved RSE (IRSE) that works by recalculating the boundary
processing and solves the boundary problem that the DCT-lifting-based LLT (DL-LT) has. We show that D2 L-LT with IRSE mostly outperforms
conventional L-LTs in lossy-to-lossless image coding.
key words: discrete cosine transform, lapped transform, lifting structure,
lossy-to-lossless image coding, reversible symmetric extension

1.

Introduction

Discrete cosine transform (DCT) [1] is classified into several types and they have many fast implementations. Imageand video compression (image coding) standards such as the
JPEG and H.26x series [2]–[5] use M-channel (M = 2k ,k ∈ N, k ≥ 2) type-II DCT (DCT-II) with a high energy
compaction capability and its inverse transform, type-III
DCT (DCT-III). However, the use of DCT-II and III generates unpleasant blocking artifacts in images reconstructedfrom low-bit compressions because they do not consider thecontinuity between adjacent M × M blocks.
To solve the blocking artifact problem, many M-channel(M × 2M) lapped transforms (LTs) have been presented. The
frequency-domain LT (FDLT) in [6] composed of a DCT-II
and a post-filtering on the block boundaries. The modulated LT (MLT) in [6], that is used in audio coding standards
such as MP3 and AAC [7], [8], composed of a type-IV
DCT (DCT-IV) and window functions as the pre-filteringpart. Moreover, the time-domain LT (TDLT) in [9], that
overcomes the blocking artifact problem while keeping the
traditional DCT-based frameworks, composed of a DCT-II
and a pre-filtering on the block boundaries. Hence, theseLTs can be simply derived from a DCT with a pre- or postfiltering. Although the M-channel (M ×K M, K ∈ N, K ≥ 2)
generalized lapped orthogonal and biorthogonal transform
Manuscript received March 11, 2016.
Manuscript revised November 1, 2016.
† The author is with the Faculty of Engineering, Information and
Systems, University of Tsukuba, Tsukuba-shi, 305-8573 Japan.
†† The author is with the Department of Electronics and ElectricalEngineering, Keio University, Yokohama-shi, 223-8522 Japan.
a) E-mail: taizo@cs.tsukuba.ac.jp
DOI: 10.1587/transfun.E100.A.1109(GenLOT and GLBT) without DCT constraints [10], [11]achieve good coding, the complexity reduction by DCT algorithms cannot be contributed unlike the DCT-based LTs.
The lifting structure [12]–[14] has yielded several
integer-to-integer transforms that map integer input signals to
integer output signals for lossy-to-lossless image coding suchthat data with various qualities can be obtained from only
one piece of lossless compressed data. In particular, several
lifting-based DCTs (L-DCTs) have been researched [15]–[18] in part because the DCT is the most-used transformin image coding and L-DCTs enable lossy-to-lossless image coding while preserving compatibility with DCT-based
frameworks. Obviously, L-DCTs cause the blocking artifact
problem in low-bit compressions.
JPEG XR [19] uses a lifting-based LT (L-LT) [20] to
overcome the blocking artifact problem and achieve lossyto-lossless image coding. The L-LT in JPEG XR performs
better than L-DCTs because LT prevents blocking artifacts
generated by DCT algorithm in low-bit compressions. Nevertheless, the block size is too small, i.e., M = 4, to elicit
suﬃcient resolution in the frequency domain. A simple
expansion of the block size degrades the transform performance because of rounding errors in each lifting step. Wanget al. proposed an L-LT in [21] based on triangular elementary reversible matrices (TERMs) [22]. However, it cannot
directly use any existing DCT software or hardware for low
complexity. We proposed an L-LT in [23] using parallel
processing of two diﬀerent LTs and a DCT-lifting [17] which
is a lifting structure with a DCT matrix in each lifting coeﬃcient. The DCT-lifting not only elicits high transformperformance by merging many rounding operations, but canalso utilize any existing DCT software or hardware; as aresult, the DCT-lifting-based LT (DL-LT) has great potential for elegant implementations that are dependent on thearchitecture and DCT algorithm used.
On the other hand, the LT requires a certain signal
extension for the boundary processing unlike DCT. In particular, a symmetric extension [24] is usually used to avoid
boundary errors and send no extra signals to the decoder. Although it is often simplified as a symmetric non-expansive
convolution [25], we will call it symmetric extension. A reversible symmetric extension (RSE) [26] has been proposed
as a smooth boundary processing that extends the symmetricextension even further, because the conventional symmetricextensions cannot be directly utilized in the L-LTs due to therounding errors in each lifting step. However, the DL-LT
cannot use any conventional smooth boundary processing,

Copyright © 2017 The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.5 MAY 2017

1110
Table 1 Advantages of each LT: (A) lossy-to-lossless image coding, (B)DCT-lifting, (C) smooth boundary solution.
Transform
LT
L-LT
DL-LT
D2 L-LT

(A)
N/A
✓
✓
✓

(B)
N/A
N/A
✓
✓

Table 2

(C)
✓
✓
N/A
✓

including the RSE in [26], because of the anomalous structure it uses to improve the transform performance. The L-LT
in JPEG XR solves the boundary problem by using a pseudo
symmetric extension (PSE), whereas the DL-LT has to adopt
a periodic extension (PE) that suﬀers the boundary error.
We present a novel DL-LT and RSE for lossy-to-losslessimage coding. The DL-LT has great potential for elegant
implementations as described above and the RSE yields aneﬀective boundary solution for the DL-LT. Table 1 showsadvantages of each LT. In Sect. 2, we review and define an
LT. In Sect. 3, we introduce a novel DL-LT that parallel
processes two identical LTs, unlike the DL-LT presented
in [23]† . In Sect. 4, this novel DL-LT is then improvedby using 2-D blockwise implementations derived from aseparable 2-D transform [9]. The conventional DL-LT can
only use a 1-D DCT-lifting, whereas the proposed DL-LT
can use both 1-D and 2-D DCT-liftings based on blockliftings in [28] and [29], and hence, it is called a dual-DL-LT(D2 L-LT). The 2-D DCT-lifting operates more eﬀectively
than the 1-D DCT-lifting by making productive use of the
2-D space of an image. In Sect. 5, we present an improved
RSE (IRSE) by recalculating the boundary processing andsolve the boundary problem. It is achieved thanks to parallel
processing of two identical LTs. In Sect. 6, we show that
D2 L-LT with IRSE mostly outperforms the conventional LLTs at lossy-to-lossless image coding. Sect. 7 concludes thispaper.
Notation: Iα , Jα , Dα , D {· · · }, ⊗, and ·T denote an α ×α
identity matrix, an α × α reversal identity matrix, an α × α
diagonal matrix with (−1) β in the ( β, β)-element, a (block)
diagonal matrix, a Kronecker product, and transpose of amatrix, respectively (α, β ∈ N, α ≥ 2, 0 ≤ β ≤ α − 1). Let
N be N = M/2. Superscripts x, y, and x y in the matrices
mean to operate horizontally, vertically, and horizontally andvertically, respectively. For example,
Ax x = xAT
A y x = Ax

(1)
(2)

Ax y x = Ax A y x = AxAT ,(3)

where A and x are a matrix and a 2-D input signal block,respectively. Superscript w means a 2-D transform of thematrix, which is expressed by a Kronecker product, Aw =Ax ⊗A y . Table 2 shows summary of the special abbreviationsin this study.
† Although we have proposed a similar DL-LT that parallel
processes two identical LTs in [27] unlike the new DL-LT in thisstudy, the RSE in this study is inapplicable to the DL-LT in [27].

Summary of special abbreviations in this study.

LT
L-LT
DL-LT
D2 L-LT
PSE
PE
RSE
IRSE

Lapped Transform
Lifting-based LT
DCT-Lifting-based LT
Dual-DCT-Lifting-based LT
Pseudo Symmetric Extension
Periodic Extension
Reversible Symmetric Extension
Improved RSE

2. Lapped Transform
The M × 2M LT used in this study is based on the lattice
structure of TDLT [9], a fast-computable structure. The
structure is shown in Fig. 1, where x and y are an input
signal vector and its output signal vector, respectively, andits polyphase matrix is expressed as††[]C
0
E(z) = P1 II
P f
W Λ(z)
0 C IV 0|{z}postprocessing

·f
WP0
|

[

IN
0

]
0
P f
W,
C III C IV V 0
{z
}

(4)

preprocessing

where

[

]
IN 0
P0 =
0 JN
[
]
0
IN
Λ(z) = −1
z IN 0[]1 IN JNf
W= √,2 J N −I N

(5)
(6)
(7)

z −1 is a delay element, the (m, n)-element of an M × M
permutation matrix P1 is
1 (n ≤ N − 1 and m = 2n)[P1 ]m,n =  1 (n ≥ N and m = 2n − M + 1) ,
 0 (otherwise)(8)

and V is an arbitrary N × N nonsingular matrix to improvethe coding performance, respectively. If V = I N , it is calleda lapped orthogonal transform (LOT). C II , C III , and C IV
are N × N DCT-II, DCT-III, and DCT-IV matrices, and the(m, n)-elements of C II and C IV are defined as√()
m (n + 1/2) π
2[C II ]m,n =cm cos
(9)
N
N
√
(
)
2
(m + 1/2) (n + 1/2) π[C IV ]m,n =cos, (10)
N
N√
where cm = 1/ 2 (m = 0) or 1 (m , 0). Moreover, C −1
IV =
†† C

III SC IV in [9] is replaced by C III C IV V . In the simplest
form in [9], S is a scale factor.

SUZUKI and IKEHARA: DUAL-DCT-LIFTING-BASED LAPPED TRANSFORM WITH IMPROVED REVERSIBLE SYMMETRIC EXTENSION

1111

Fig. 1

Lattice structure of LT.

T
C TIV = C IV , C III = C −1
II = C II , and the postprocessing in
Eq. (4) is an M × M DCT-II.

3.

DCT-Lifting-Based Lapped Transform that Parallel
Processes Two Identical Lapped Transforms

This section presents a DL-LT that parallel processes two
identical LTs. This DL-LT is unlike the DL-LT in [23] thatparallel processes two diﬀerent LTs.
3.1

1-D DCT-Lifting of C II and C III

This subsection presents the 1-D DCT-lifting [17], which is a
lifting structure with a DCT matrix in each lifting coeﬃcient,of C II and C III in the proposed LT. Eq. (4) is represented by
[
]
C II
0
E(z) = P1 D M
W Λ(z)
0 S IV|{z}[

postprocessing

I
·W N
0
|

]
0
WP0,
C III C IV V
{z
}

(11)

preprocessing

where

[
1 IN
W= √
2 IN

]
IN
,
−I N

(12)

C II = D N C II J N , and type-IV DST (DST-IV) S IV =D N C IV J N . We can obtain the following 1-D DCT-liftingfrom Eq. (11).
[][]C II 0IN
0WΛ(z)W
0 IN
0 C III][][IN0
I N −C II
Λ(z)
=−
1
0
IN
IN
2 C III
[
]
[
]
1
IN
0
C
I
· N 2 III(13)
−C II I N0
IN
The sign inversions such as D M in Eq. (11) and − in Eq. (13)can be removed because they have no impact on the transfer
function. Consequently, Eq. (4) can be represented by

E(z)

[

I
= P1 N
0
|
[

I
· N
0
|

0
S IV

][

IN
0

−C II
IN
{z

postprocessing

1
2 C III
IN

][

IN
−C II

0
IN
{z

][

][

IN
1
2 C III

IN
0

]
0
Λ(z)
IN
}
0

C IV V]WP0 .
}preprocessing(14)
Most of this structure includes very simple operations with
DCT matrices, adders, bit-shifters, and permutations, but it
is not a complete lifting structure.
3.2 1-D DCT-Lifting of C IV or S IV
This subsection describes the C IV and S IV parts in Eq. (14).
We consider two identical LTs as shown in Fig. 2, where x,Dx, y, and D
y are an input signal vector, an input signal vector
that is not x, the output signal vector of x, and the output
signal vector of D
x, respectively. Consider a 1-D simultaneous implementation of D {I N , T} on diﬀerent horizontal orvertical lines, where T is an N × N symmetric orthogonal
matrix such that T−1 = TT = T:
[ ] [
][ ]
y
D {I N , T}
0
x
=
,
(15)
D
y
0
D {I N , T} Dxwhere D {T, T} is factorized into block-liftings as [23]
[
] [
][
][
][
]
T 0
0 I N I N 0 I N −T I N 0=.
0 T−I N 0
T IN
0 IN
T IN
(16)
Since C IV and S IV are N × N symmetric orthogonal matrices, the block-lifting in Eq. (16) can be applied to eachcombination of C IV and S IV framed by dash-dotted lines inFig. 2.
3.3 1-D Block-Lifting of W
The W in Eq. (14) can be easily factorized into block-lifting
structures as
]
[
][
I√N
0
IN
0
W=
0 −I N (1 − 2)I N I N

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.5 MAY 2017

1112

Fig. 2[

Represented structure of LT by parallel processing of two identical LTs.

][
√1 I N
I√N
2
(1
−
2)I N
IN

IN
·
0

]
0
.
IN

(17)

√
√
However, the floating-point multipliers (1 − 2) and 1/ 2
cause the structure to have high complexity. The problem
will be solved by using a 2-D blockwise implementation, as
described in Sect. 4.4.
3.4

2-D blockwise implementation of LT.

1-D Implementation of P0 and V

The permutation matrix P0 in Eq. (14) is already reversible
because it only permutes signals. Also, we can easily define
V in Eq. (14) as an upper triangle matrix with 1s in all
diagonal coeﬃcients,
1

0
V =  .
 .
 .
0

×
1
..
.

···

···
..
.
..
.
0

×
.. 
. 
 ,
×
1 

4.1 Separable 2-D TransformWhen an M × M∏ image X is 2-D transformed by an M × M
transform T = 0k=K Tk (K ∈ N), the transformed image Y
can be expressed as
xy

(18)

where × indicates any real (floating-point) value determined
to improve the coding performance. It is clear that the V
already has the complete lifting structure. LT with an upper
triangular matrix V shows better coding gain than LOT with
V = I, e.g., the coding gains of 16 × 32 LOT and LT are
9.76 dB and 9.89 dB, respectively. For low complexity,
the floating-point lifting coeﬃcients are approximated byrational (dyadic) coeﬃcients γ/2δ (γ, δ ∈ N). We allocateda 6-bit word length (δ = 6) to each coeﬃcient in this study.
The coding gain of the approximated LT is almost equivalent
to that of the original LT.
4.

Fig. 3Dual-DCT-Lifting-Based Lapped Transform

This section describes a 2-D blockwise implementation of aseparable 2-D transform [9] of the 1-D LT presented above.

xyxy

Y = TK · · · T1 T0 XTT0 TT1 · · · TTK = TK · · · T1 T0 X.
(19)
It means that X is 2-D transformed with Tk+1 after the
2-D transform by Tk . Using this fact, the D2 L-LT canbe implemented by cascading the 2-D transform of the
pre/postprocessing blocks in Fig. 2. Note that the 2-D blockwise implementation of LT is overlapped via the preprocessing and postprocessing as shown in Fig. 3. DL-LT in[23] cannot use a separable 2-D transform due to its parallel processing of two diﬀerent LTs, whereas D2 L-LT cando so, thanks to its use of two identical LTs. Consequently,
it is easy to make a 2-D blockwise implementation in eachM × M block as in [20].
4.2 2-D DCT-Lifting of C II and C III
We proposed a 2-D block-lifting in [29]. Let B k be a set oflower and upper DCT-lifting matrices in Eq. (14), i.e.,[][]
IN U k IN0
Bk =for k = 0 or 1, (20)0
IN Lk INSUZUKI and IKEHARA: DUAL-DCT-LIFTING-BASED LAPPED TRANSFORM WITH IMPROVED REVERSIBLE SYMMETRIC EXTENSION

1113

 Y LL  I N
 Y   0
 HL  =  Y LH   0
Y HH   0

0
Tx
0
0

0
0
Ty
0

0   X LL 
0   X HL .
0   X LH xyT  X HH (23)

It can be simplified as

Fig. 4

 Y HL  Tx
 Y  =  0
 LH  
Y HH   0

M × M input and output blocks.

Fig. 5 2-D block-lifting derived from a combination of lower and upper block-lifting matrices (gray blocks mean changed blocks and rounding
operations are omitted).

where U 0 = L 1 = −C II and U 1 = L 0 = 21 C III . For the
M × M image in Fig. 4, a 2-D DCT-lifting of B k can be
implemented by (see Fig. 5)
 X LL  Y LL X  Y 
 HL  = B kw  HL  , X LH  Y LH YX HH 
 HH 

(21)

0   X HL 
0   X LH  ,T y  X HH (24)

where Y LL = X LL . Here, X HL and X HH are horizontally
implemented after the vertical implementations of X LH and
X HH . D {Tx, Tx } and D {T y, T y } in Eq. (24) can be factorized into 1-D DCT-liftings as in Eq. (16). Unfortunately,
unlike the DCT-lifting of C II and C III , the 1-D DCT-liftingsof C IV and S IV cannot be replaced by 2-D DCT-liftings. The
2-D blockwise implementations of the 1-D DCT-liftings of
C IV and S IV are shown in Fig. 6. We must take care of theimplementation directions, i.e., horizontally or vertically.
This structure also has simple operations like those of thestructure in Sect. 4.2.
4.4 2-D Block-Lifting of W
The W in Eq. (14) can be implemented by extending the nonseparable 2-D transform of the Hadamard transform that isreally used in JPEG XR [30]† as follows:

(25)

where
I N
1 I
Ww = Wx ⊗ W y =  N
2 I N
I N

IN
−I N
IN
−I N

IN
IN
−I N
−I N

I N 
−I N 
.
−I N 
I N 
(26)

The Ww is factorized into lifting structures (see Fig. 7),(22)

X LL , X HL , X LH , and X HH are the top-left, top-right, bottomleft, and bottom-right N × N blocks of an M × M image, andY LL , Y HL , Y LH , and Y HH are their respective output blocks.
The 2-D DCT-lifting reduces rounding errors compared withthe 1-D DCT-lifting.
4.3

0
Ty
0

 X LL  Y LL  Y HLw  X HL , = W  X LH  Y LH X HH Y HH where
I N U kx U y −U x y 
k
k
 0
IN
0
0 
w

B k = 
0
IN
0 
 0
0
0
I N 
0 I N00L x I N 0 U y k·  kyx
L k 0 I N U k 
0
0
IN 
 0
 I N
0
0
0 
 0
IN
0
0 
,
· 
0
IN
0 
 0x yyx
L k L k I N L k0  I N
0   0
T x   00IN02-D Blockwise Implementation of 1-D DCT-Lifting of
C IV or S IV

This subsection describes a 2-D blockwise implementationof the C IV or S IV part:I N 00
0  I N 0
0 −I N  0  0 I
0
I
0
I
0 
N
N
N

 
Ww = 
00
0 IN
0 
 0 I N 000 IN   0
00
I N 
0 I N00 0  I N 0
0
0 

 0
IN
0 0   0 I N 0
0 
 

·  1 I − 1 I I
0

0
0
0
−I
N
N
N
 
 2
N 
2
 1 I N − 1 I N 0 I N   0 0 −I N 0 
2

I N
0
· 
 0
0

2

0
IN
0
0

0
−I N
IN
0

I N 
0 
.
0 
I N 

(27)† Note that this simple transform is diﬀerent from the Hadamardtransform described in [20].

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.5 MAY 2017

1114

Fig. 6 2-D blockwise implementation of 1-D block-lifting of T x and T y (gray blocks mean changed
blocks and rounding operations are omitted).

Fig. 72-D block-lifting of W (gray blocks mean changed blocks and rounding operations are omitted).

Fig. 8 2-D blockwise implementation of P0 and V (gray blocks meanchanged blocks).

This structure also has very simple operations with only
adders, bit-shifters, and permutations.
4.5

2-D Blockwise Implementation of P0 and V

A 2-D blockwise implementation P0w of an M × M block isexpressed as
 X LL  Y LL X  Y 
 HL  = P0w  HL  ,Y
 X LH  LH Y
X HH 
 HH 
y

(28)
y

xy

where P0w = P0x ⊗ P0 = D {I N , JxN , J N , J N }, as shown at theleft side of Fig. 8. Similarly, a 2-D blockwise implementationof the V part is shown at the right side of Fig. 8. The
V already has the complete lifting structure as defined in
Eq. (18).
5.

Improved Reversible Symmetric Extension

Here, we devise an IRSE for D2 L-LT by recalculating theboundary processing derived from the RSE we proposed in
[26].
5.1

Boundary Processing of 1-D Signals

Consider a boundary processing of 1-D signals in Eq. (14)as shown at the left of Fig. 9. If the symmetric input signals, [(Jx)T , xT ]T are input to the boundaries and rounding
operations are excluded, the processing can be expressed as[ ]  1
 √2 Jx 
Jx
,
P
= √
(29)
x
− 2C II Jx
where P is the preprocessing part in Eq. (14),
[
][
][
]
IN
0 IN
0
I N 12 C IIIP=
WP0 . (30)
−C II I N
0 C IV V0INThe left of Fig. 9 with the symmetric extension is redrawn
at the right of Fig. 9. The DCT-II matrix C II can be easily
factorized into lifting structures by using a lifting factorization due to det(C II ) = 1. In this study, we used the L-DCT
in [18] to factorize C II in Eq. (29) into lifting√ structures.
√
On the other hand, although a combination of 2 and 1/ 2
can be easily factorized into a lifting factorization, we will
not use the lifting structures with the floating-point√lifting
coeﬃcients.
The floating-point scaling coeﬃcients 2 and√1/ 2 are instead with dyadic coeﬃcients by considering a
2-D implementation, as described in the next subsection.
5.2 Boundary Processing of 2-D Signals
If a boundary processing of 2-D signals (image) is consideredwith symmetric extended input signals, a special processing
is implemented in the gray area in Fig. 10. The boundary
processing of X×× s, whose size is N × N, in the figure areexpressed using several separable 2-D transforms:
Xtl : 2C II J N Xtl J N C TII
1
Xbr : Xbr2
Xtr : −C II J N Xtr

(31)
(32)
(33)

SUZUKI and IKEHARA: DUAL-DCT-LIFTING-BASED LAPPED TRANSFORM WITH IMPROVED REVERSIBLE SYMMETRIC EXTENSION

1115

Fig. 9 Boundary processing in 1-D signals (dash-dotted lines mean signal boundaries): (left) appearance of signal extension; (right) non-expansive convolution derived from symmetric extension.

[
]
√
I
IN
2W = N≜LW
I N −I N
1L
1√ W = W.
2
2

(39)
(40)

Since LW−1 = 12 LW, each combination of L
W and 12 L
W in
Eqs. (35)–(38) can be factorized into block-liftings without
multipliers:[

Fig. 10 Boundary processing in 2-D signals (gray area means boundary
processing area).

Xbl : −Xbl J N C TII√
Xt j : 2C II J N Xt j PT
1
Xb j : √ Xb j PT
2√
Xli : 2PXli C TII
1
Xri : √ PXri
2

(34)

L
W
0

] [
0
0
1 L = −I
N
W
2
[
I
· N
0

]
IN 0
L
W IN
]
[
]
1L
− 2 W IN 0
.
L
IN
W IN
IN
0

][

(41)

Each residual DCT part of P is directly implemented by 1-D
DCT-liftings. Furthermore, the combinations of 2 and 1/2
in Eqs. (31) and (32) can be simply factorized into lifting
structures without multipliers:
[
] [
][
][
][
]
2 0
0 1 1 0 1 − 12 1 0=(42).
−1 0 2 1 0 1 2 1
0 21

(35)
(36)
(37)
(38)

for i =√0, 1, · · · , √m and j = 0, 1, · · · , n. The scaling coeﬃcients 2 and 1/ 2 appearing in Eqs. (35)–(38) are merged
into W in each P in order to eliminate the floating-point
coeﬃcients:

6. Experimental Results
We designed 16 × 32 D2 L-LT and compared it with conventional methods, such as the L-LT in JPEG XR [20] and
DL-LT [23] with the same transfer function as the D2 L-LT,
by using the following lossless bitrate (LBR) [bpp] and peaksignal-to-noise ratio (PSNR) [dB] in lossy-to-lossless image
coding:
LBR [bpp] =Total number of bits [bit]Total number of pixels [pixel](43)

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.5 MAY 2017

1116

Fig. 11 Comparison of whole and particular areas of a reconstructed image Woman for a bitrate of
0.25 bpp: (a-d) whole areas, (e-h) particular areas which left sides indicate image boundaries, (a,e) 4 × 8
L-LT in [20] with PSE, (b,f) 16 × 32 DL-LT in [23] with PE, (c,g) 16 × 32 D2 L-LT with PE, (d,h) 16 × 32
D2 L-LT with IRSE.

(PSNR [dB] = 10 log10

)
2552
,
MSE

Table 3(44)

where MSE is the mean squared error. To evaluate the transform performance fairly, we employed 2-level decomposition for the L-LT in JPEG XR, where only core transform(L-DCT) was used in the second stage in accordance with thespecification, whereas we employed 1-level decompositionsfor 16×32 DL-LT and D2 L-LT. We used PSE, PE, and IRSE
for the boundary processing, eight 512 × 512 8-bit grayscale
images such as Barbara in [31], and six 1024 × 1024 8-bit
clipped grayscale images such as Bike in [32] and Bridge in[33]. A very common wavelet-based coder SPIHT [34] wasused to encode the transformed images after the transformed
coeﬃcients were ordered to a tree of wavelet coeﬃcients asin [35].
Tables 3 and 4 respectively show lossless and lossy
image coding results. Although the D2 L-LT with PE did
not show the obvious advantage compared with the DLLT in [23] and the L-LT in [20] showed the best perfor-

Lossless image coding results (LBR [bpp]).

Test
Images

L-LT [20]PSE

DL-LT [23]PE

D2 L-LTIRSE (PE)BaboonBarbaraBoat
ElaineFingerGoldhill
Lena
Pepper
Bike
Cafe
Woman
BridgeCathedral
Deer

6.24
4.95
5.22
5.28
5.90
5.10
4.62
5.00
5.10
6.00
4.79
4.31
4.18
5.16

6.22
4.80
5.12
5.17
5.75
5.13
4.64
4.95
5.16
6.11
4.86
4.34
4.26
5.02

6.19 (6.21)
4.74 (4.77)
5.09 (5.10)
5.13 (5.16)
5.74 (5.74)
5.08 (5.12)
4.57 (4.61)
4.92 (4.93)
5.12 (5.14)
6.08 (6.10)
4.81 (4.83)
4.28 (4.29)
4.19 (4.21)
5.01 (5.01)

mance in some lossless image coding results, the D2 L-LT
with IRSE mostly outperformed other L-LTs. Moreover, theperceptual visual quality at the boundaries was clearly im-

SUZUKI and IKEHARA: DUAL-DCT-LIFTING-BASED LAPPED TRANSFORM WITH IMPROVED REVERSIBLE SYMMETRIC EXTENSION

1117
Lossy image coding results (PSNR [dB]).

Table 4
Test
Image
BaboonBarbaraBoat

ElaineFingerGoldhill

Lena

Pepper

Bike

Cafe

Woman

BridgeCathedral

Deer

Bitrate[bpp]

L-LT [20]PSE

DL-LT [23]PE

D2 L-LTIRSE (PE)

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
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
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00
0.25
0.50
1.00

22.42
24.67
28.12
26.96
30.92
36.13
28.84
32.05
35.26
31.52
32.31
34.22
23.09
26.43
30.20
29.66
32.20
35.31
32.96
36.10
38.80
32.54
34.80
36.49
26.35
30.76
35.29
20.94
24.24
28.82
30.04
33.10
36.90
34.38
36.92
39.86
33.17
36.94
40.72
32.89
33.48
34.70

22.95
25.21
28.52
28.96
32.96
37.49
29.29
32.38
35.63
31.73
33.06
35.48
24.00
27.38
31.55
29.72
32.38
35.49
33.02
36.22
38.85
32.38
34.60
36.71
27.08
31.11
35.36
21.54
24.52
28.73
30.21
33.25
36.97
34.90
37.43
40.27
33.88
37.67
41.00
33.12
34.07
35.66

23.02 (22.96)
25.30 (25.22)
28.65 (28.53)
29.15 (28.95)
33.21 (32.96)
37.72 (37.52)
29.38 (29.29)
32.49 (32.38)
35.74 (35.66)
32.02 (31.72)
33.23 (33.07)
35.66 (35.53)
24.03 (24.00)
27.42 (27.38)
31.62 (31.56)
30.17 (29.72)
32.65 (32.40)
35.72 (35.54)
33.43 (33.02)
36.56 (36.21)
39.17 (38.98)
32.55 (32.38)
34.75 (34.64)
36.91 (36.83)
27.20 (27.08)
31.27 (31.11)
35.56 (35.41)
21.58 (21.54)
24.58 (24.52)
28.83 (28.73)
30.49 (30.21)
33.45 (33.25)
37.20 (37.04)
35.05 (34.88)
37.56 (37.43)
40.50 (40.42)
34.10 (33.87)
37.86 (37.66)
41.19 (41.12)
33.12 (33.12)
34.09 (34.09)
35.75 (35.75)

proved as shown at Fig. 11. The experimental results indicatethat the DCT-lifting, especially 2-D DCT-lifting, suppressed
the rounding error to preserve transform performance bymerging many rounding operations and the IRSE solved theboundary problem that conventional DL-LT has.
7.

Conclusion

We presented a DL-LT composed of 1-D and 2-D DCTliftings by considering parallel processing of two identical
LTs and improved the conventional RSE by recalculating
the boundary processing for more eﬀective lossy-to-losslessimage coding. These developments are called D2 L-LT and
IRSE, respectively. The DCT-lifting suppresses the rounding
error to preserve transform performance and allows for direct use of a DCT matrix in each lifting coeﬃcient. The 2-D
DCT-lifting operates more eﬀectively than the 1-D DCT-

lifting by making productive use of the 2-D space of animage. Furthermore, we solved the boundary problem thatconventional DL-LT has by formulating IRSE. Finally, we
showed that D2 L-LT with IRSE mostly outperformed conventional L-LTs in lossy-to-lossless image coding.
Acknowledgment
This work was supported by a JSPS Grant-in-Aid for Young
Scientists (B), Grant Number 16K18100.
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. Electron., 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, Sept. 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.
[5] G.J. Sullivan, J.R. Ohm, W.J. Han, and T. Wiegand, “Overview ofthe high eﬃciency video coding (HEVC) standard,” IEEE Trans.
Circuits Syst. Video Technol., vol.22, no.12, pp.1649–1668, Dec.
2012.
[6] H.S. Malvar, “Lapped transforms for eﬃcient transform/subband
coding,” IEEE Trans. Acoust., Speech, Signal Process., vol.38, no.6,
pp.969–978, June 1990.
[7] P. Noll, “MPEG digital audio coding,” IEEE Signal Process. Mag.,
vol.14, no.5, pp.59–81, Sept. 1997.
[8] J. Hilpert and S. Disch, “The MPEG surround audio coding standard,” IEEE Signal Process. Mag., vol.26, no.1, pp.148–152, Jan.
2009.
[9] T.D. Tran, J. Liang, and C. Tu, “Lapped transform via time-domainpre- and post-filtering,” IEEE Trans. Signal Process., vol.6, no.6,
pp.1557–1571, June 2003.
[10] R.L. de Queiroz, T.Q. Nguyen, and K.R. Rao, “The GenLOT: Generalized linear-phase lapped orthogonal transform,” IEEE Trans. Signal
Process., vol.44, no.3, pp.497–507, March 1996.
[11] T.D. Tran, R.L. de Queiroz, and T.Q. Nguyen, “The generalized
lapped biorthogonal transform,” Proc. ICASSP’98, pp.1441–1444,
Seattle, WA, May 1998.
[12] W. Sweldens, “Lifting scheme: A new philosophy in biorthogonal
wavelet constructions,” Proc. SPIE, pp.68–79, San Diego, CA, July
1995.
[13] W. Sweldens, “The lifting scheme: A custom-design construction ofbiorthogonal wavelets,” Appl. Comput. Harmon. Anal., vol.3, no.2,
pp.186–200, April 1996.
[14] W. Sweldens, “The lifting scheme: A construction of second generation wavelets,” SIAM J. Math. Anal., vol.29, no.2, pp.511–546,
1998.
[15] K. Komatsu and K. Sezaki, “Reversible discrete cosine transform,”
Proc. ICASSP’98, pp.1769–1772, Seattle, WA, May 1998.
[16] J. Liang and T.D. Tran, “Fast multiplierless approximations of the
DCT with the lifting scheme,” IEEE Trans. Signal Process., vol.49,
no.12, pp.3032–3044, Dec. 2001.
[17] T. Suzuki and M. Ikehara, “Integer DCT based on direct-lifting of
DCT-IDCT for lossless-to-lossy image coding,” IEEE Trans. Image
Process., vol.19, no.11, pp.2958–2965, Nov. 2010.
[18] T. Suzuki and H. Aso, “M-channel fast Hartley transform based
integer DCT for lossy-to-lossless image coding,” IEICE Trans. Fundamentals., vol.E96-A, no.4, pp.762–768, April 2013.
[19] F. Dufaux, G.J. Sullivan, and T. Ebrahimi, “The JPEG XR image
coding standard,” IEEE Signal Process. Mag., vol.26, no.6, pp.195–

IEICE TRANS. FUNDAMENTALS, VOL.E100–A, NO.5 MAY 2017

1118

199, 204, Nov. 2009.
[20] C. Tu, S. Srinivasan, G.J. Sullivan, S. Regunathan, and H.S. Malvar,“Low-complexity hierarchical lapped transform for lossy-to-losslessimage coding in JPEG XR/HD Photo,” Proc. SPIE, pp.70730C–
70730C–12, San Diego, CA, Aug. 2008.
[21] L. Wang, L. Jiao, J. Wu, G. Shi, and Y. Gong, “Lossy-to-losslessimage compression based on multiplier-less reversible integer time
domain lapped transform,” Signal Process. Image Commun., vol.25,
no.8, pp.622–632, Sept. 2010.
[22] P. Hao and Q. Shi, “Matrix factorizations for reversible integer mapping,” IEEE Trans. Signal Process., vol.49, no.10, pp.2314–2324,
Oct. 2001.
[23] 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.
[24] M.J.T. Smith and S.L. Eddins, “Analysis/synthesis techniques for
subband image coding,” IEEE Trans. Signal Process., vol.38, no.8,
pp.1446–1456, Aug. 1990.
[25] T. Nagai, M. Ikehara, M. Kaneko, and A. Kurematsu, “Generalized unequal length lapped orthogonal transform for subband image
coding,” IEEE Trans. Signal Process., vol.48, no.12, pp.3365–3378,
Dec. 2000.
[26] T. Suzuki and M. Ikehara, “Reversible symmetric non-expansive
convolution: An eﬀective image boundary processing for M-channel
lifting-based linear-phase filter banks,” IEEE Trans. Image Process.,vol.23, no.6, pp.2744–2749, June 2014.
[27] T. Suzuki and M. Ikehara, “Simplified DCT-lifting-based reversible
lapped transforms using parallel processing of two same type lapped
transforms,” Proc. ICIP’14, pp.5586–5590, Paris, France, Oct. 2014.
[28] T. Suzuki, M. Ikehara, and T.Q. Nguyen, “Generalized block-lifting
factorization of M-channel biorthogonal filter banks for lossy-tolossless image coding,” IEEE Trans. Image Process., vol.21, no.7,
pp.3220–3228, July 2012.
[29] T. Suzuki and H. Kudo, “2D non-separable block-lifting structure andits application to M-channel perfect reconstruction filter banks forlossy-to-lossless image coding,” IEEE Trans. Image Process., vol.24,
no.12, pp.4943–4951, Dec. 2015.
[30] “T.835:
Information technology - JPEG XR image coding system - Reference software,” ITU [Online]. Available:
https://www.itu.int/rec/T-REC-T.835-201201-I/[31] “The USC-SIPI Image Database,” Univ. Southern California, Signal and Image Processing Institute [Online]. Available:
http://sipi.usc.edu/database/[32] “JPEG core experiment for the evaluation of JPEG XR image coding,” EPFL, Multimedia Signal Processing Group [Online]. Available: http://mmspg.epfl.ch/iqa[33] “The New Test Images - Image Compression Benchmark,” Rawzor Lossless Compression Software for Camera RAW Images [Online].
Available: http://www.imagecompression.info/test_images/[34] 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, June 1996.
[35] T.D. Tran, M. Ikehara, and T.Q. Nguyen, “Linear phase paraunitary
filter bank with filters of diﬀerent lengths and its application in image
compression,” IEEE Trans. Signal Process., vol.47, no.10, pp.2730–
2744, Oct. 1999.

Taizo Suzuki
received the B.E., M.E.,
and Ph.D. degrees in electrical engineering from
Keio University, Japan, in 2004, 2006 and 2010,
respectively. From 2006 to 2008, he was with
Toppan Printing Co., Ltd., Japan. From 2008
to 2011, he was a Research Associate of the
Global Center of Excellence (G-COE) at Keio
University, Japan. From 2010 to 2011, he was a
Research Fellow of the Japan Society for the Promotion of Science (JSPS) and a Visiting Scholar
at the Video Processing Group, the University ofCalifornia, San Diego, CA. From 2011 to 2012, he was an Assistant Professor in the Department of Electrical and Electronic Engineering, College
of Engineering, Nihon University, Japan. Since 2012, he has been an Assistant Professor in the Faculty of Engineering, Information and Systems,
University of Tsukuba, Japan. His current research interests are theory anddesign of filter banks and their application to image and video processing.

Masaaki Ikehara
received the B.E., M.E.,
and Dr.Eng. degrees in electrical engineeringfrom Keio University, Yokohama, Japan, in
1984, 1986, and 1989, respectively. He was Appointed Lecturer at Nagasaki University, Nagasaki, Japan, from 1989 to 1992. In 1992, hejoined the Faculty of Engineering, Keio University. From 1996 to 1998, he was a visiting
researcher at the University of Wisconsin, Madison, and Boston University, Boston, MA. He iscurrently a Full Professor with the Department
of Electronics and Electrical Engineering, Keio University. His research interests are in the areas of multirate signal processing, wavelet image coding,and filter design problems.