1

Extended Block-Lifting-based Lapped Transforms
Taizo Suzuki, Member, IEEE and Hiroyuki Kudo, Member, IEEE

Abstract—We extend an original lapped transform (LT) anduse block-lifting factorization to get an extended block-liftingbased LT (XBL-LT). The block-lifting structure maps integer
input signals to integer output signals and results in a reversible
transform that reduces rounding errors by merging many rounding operations. Although other such block-lifting-based LTs (BLLTs) have been proposed, they are forcibly constrained by the useof discrete cosine transform (DCT) matrices. In contrast, XBLLT is DCT-unconstrained and hence also embodies the DCTconstrained form. Furthermore, it has fewer rounding operations
by merging the scaling factor with block-lifting coefficients.
The both DCT-constrained and unconstrained XBL-LTs perform
well at lossy-to-lossless image coding which has scalability fromlossless data to lossy data.

described in our previous studies are removed by merging thescaling factor with block-lifting coefficients. As a result, theboth DCT-constrained and unconstrained XBL-LTs perform
well at lossy-to-lossless image coding.
Notation: The italic letter M (M = 2n , n ∈ N) denotes
the block size. Boldface letters Im , Jm , 0, and Dm denote an
m×m identity matrix, an m×m reversal matrix, a null matrix,
and an m×m diagonal matrix with alternating ±1 entries (i.e.,diag{1, −1, 1, −1, · · · }), respectively. The superscripts T and−1 respectively mean the transpose and inverse of a matrix.

Index Terms—Block-lifting structure, lapped transform (LT),lossy-to-lossless image coding

II. R EVIEW AND D EFINITION

I. I NTRODUCTION
APPED transforms (LTs) [1] are popular subband transforms that can be used as substitutes for the discretecosine transform (DCT) [2] used in image/video compression(image coding). Although almost all of the JPEG and H.26x
series [3–5], image coding standards, use DCTs for their
good energy compaction, DCT-based image codings generate
unpleasant artifacts, i.e., blocking artifacts, at low bit rates dueto their ignoring the continuity of the blocks. LT-based image
coding solves that problem by using a processing that works
over the blocks.
The lifting structure [6] is a very important technology toachieve a lossless mode in subband transform-based image
coding. It maps integer input signals to integer output signals;
i.e., it is an integer-to-integer transform. The 4 × 8 liftingbased LT (L-LT) [7] in JPEG XR [8], the newest image
coding standard, is a time-domain LT (TDLT) [9] with simple
scaling factors and lifting structures. In spite of its simple
structure, it performs well at lossy-to-lossless image coding,which has scalability from lossless to lossy data. The blocklifting structure [10] is a class of lifting structures and results ina reversible transform that reduces rounding errors by merging
many rounding operations. Inspired by the L-LT in JPEG XR,
we have proposed block-lifting-based LTs (BL-LTs) [11], [12]that perform well with larger block size than those of the L-LT
in JPEG XR. However, they are forcibly DCT-constrained anddegrade coding performance at high bit rates.
Here, we extend an original LT and use block-lifting factorization to get an extended BL-LT (XBL-LT). The XBL-LT
is DCT-unconstrained, unlike the BL-LTs presented in [11],[12], and hence also embodies the DCT-constrained form.
Furthermore, more rounding operations than the methods

L

T. Suzuki and H. Kudo are with the Faculty of Engineering, Information and
Systems, University of Tsukuba, Tsukuba, Ibaraki, 305-8573 Japan (e-mail:{taizo, kudo}@cs.tsukuba.ac.jp).

A. Lapped Transform (LT)In accordance with [11], [12], let E(z) be a polyphasematrix of an M × 2M LT with a scaling factor s derived
from the L-LT in JPEG XR [7]:
[
]
[ II
]
I
0
CN
0
f M,
E(z) = P N
Γ(z)
SWJ
III
0 S IV
0 C IV
N CN
N JN
(1)
where
Γ(z) = WΛ(z)W, Λ(z) = diag{IN , z −1 IN }
[
]
[
]
1 IN
IN
JN
f = √1 IN, W
W= √2 IN −IN
2 JN −INS = diag{sIN , s−1 IN }.
X
CX
M and S M are type-X DCT (DCT-X) and type-X discretesine transform (DST-X) matrices, and the (i, j)-elements ofIV
C II
M and C M are
√
(
)
[
]
2
i (j + 1/2) πII=CMci cos
M
M
i,j
√
(
)
[
]
(i + 1/2) (j + 1/2) π
2
IV
CM
=
cos
,
M
M
i,j
√
where ck = 1/ 2 (k = 0) or 1 (k ̸= 0), respectively. The
following relationships between matrices can be established:

(
)−1 (
)T
II
II
IV
C III
=
C
=
C
, S IVM
M
M
M = DM C M JM .

(2)

Here, P is an M ×M permutation matrix. The optimal scalings in S is empirically determined, e.g., s = 0.8981 if M = 8
and 0.9360 if M = 16. Since the LT in Eq. (1) with s = 1 iscompletely equivalent to a lapped orthogonal transform (LOT),
we will use the LT in Eq. (1) as a representative expressionof LT.

2

where√e , V = √1 V,e W
c=
U = 2s U
2sFig. 1. Block-lifting structure (black and white circles mean adders androunding operations, respectively).

B. Block-Lifting Structure
The block-lifting structure [10] (Fig. 1) is a class of lifting
structures. The structure can be expressed as follows:
yj = xj + round(B0 xi ),yi = xi + round(B1 yj )zi = yi − round(B1 yj ) = xi , zj = yj − round(B0 zi ) = xj ,where x× , y× , and z× are N × 1 input/output vector signals, round(·) is a rounding operation, and the block-lifting
coefficients B0 and B1 are N × N arbitrary matrices. In thiscase, the matrices and their inverses are expressed as lower
and upper block-lifting matrices as follows:
[
]
I
0
−1
L [B0 ] ≜ N, L [B0 ] = L [−B0 ]
B0 IN
[
]
I
B1
−1
U [B1 ] ≜ N, U [B1 ] = U [−B1 ] .
0 IN
Rounding errors generated by the rounding operation in eachlifting step degrade coding performance. The block-lifting
structure reduces such rounding errors by merging manyrounding operations. A special class of block-lifting structureis expressed as [13][][ −1 ][]M
0eM
U [−M] L M−1 J(3)−1 = L M
0 M[]
bM L [−M] U M−1 L [−M] ,
=J
(4)
where
eM =
J

[

0
−IN

]
IN
,
0

bM =
J

[

0
IN

]
−IN
,
0

and M is an N × N arbitrary nonsingular matrix.
III. E XTENDED B LOCK -L IFTING - BASED L APPEDT RANSFORM (XBL-LT)
Theorem: We can extend the DCT-constrained LT in Eq.
(1) to a DCT-unconstrained LT as follows:
[
]
[
]
e
IN
0
U
0
f
E(z) = P
Γ(z)e N SWJM ,e −1 JN U
e −1
0 VJ
0 DN Ve and Ve are N × N arbitrary nonsingular matrices.
where UThis equation can be simplified as
[
]
[
]
IN
0
U
0
c M,
E(z) = P
Γ(z)
WJ
0 VJN
0 V −1 JN U −1
(5)

[1

2 IN
JN

1
2 JN
−IN

]
,

by using Eq. (2) and skipping the sign inversion matrix DN .
The scaling matrix S is being embedded in U and V. Whene = C II and V
e = C IV , the LT in Eq. (5) is completely
U
N
N
equivalent to the LT in Eq. (1) except that the signs aredifferent. Then, we factorize the LT in Eq. (5) into blocklifting structures as
E(z) = PL [B4 ] U [B3 ] Λ(z)U [B3 ] L [B2 ] U [B1 ] L [B0 ]
[
]
1
eM ,
· U − JN L [JN ] J(6)2
wherein each matrix is defined as
B0 = −V −1 , B1 = V, B2 = B0 + B4
1
B3 = − U JN V, B4 = V −1 JN U −1 .
2
Actually, the block-lifting matrices U [B3 ] on both sides ofthe delay matrix Λ(z) are collectively implemented, as shownin Fig. 2.
Proof: We can perform an easy matrix manipulation as
follows:
[
M0
0

0
M1

][

]
I N N0
N1 IN[
IN=
M1 N1 M−10

M0 N0 M−1
1
IN

][
M0
0

]
0
,
M1

where M× and N× are an N ×N arbitrary nonsingular matrix
and N × N arbitrary matrix, respectively. First, Γ(z) in Eq.
(5) can easily be represented by
[

]
[
]
1
1
Γ(z) = L [IN ] U − IN Λ(z)U IN L [−IN ] .
2
2
Next, U −1 in Eq. (5) is moved to the right side of Γ(z) andsimplified as
[

]
[
]
IN
0
U 0
Ψ(z) ≜
Γ(z)0 IN
0 U −1
[
]
[
]
]
[
[
] U 0
[ −1 ]
1
1−1=L U
U − U Λ(z)U U L −U
0 U −1
2
2
]
[
]
[
[
]
[
]
1
1
eM ,
= L U −1 U − U Λ(z)U − U L U −1 J22because the block diagonal matrix diag{U , U −1 } in Ψ(z) can
be factorized into block-lifting structures as in Eq. (3). Then,
V −1 JN in Eq. (5) is moved to the right side of Ψ(z) and3

Fig. 2. XBL-LT (black and white circles mean adders and rounding operations, respectively).

TABLE IC ODING GAINS OF XBL-LT S .
Block Size
8
16

DCT-Constrained
9.44759.8455

DCT-Unconstrained
9.45389.8621TABLE IIN UMBERS OF ROUNDING OPERATIONS OF BL-LT S .
Block Size
816
M

BL-LT [11]
48
96
6M

BL-LT [12]
28
56
7M/2

XBL-LT
24
48
3M

simplified as
[
]
[
]
I
0
IN
0
Ω(z) ≜ N
Ψ(z)0 VJN
0 V −1 JN[][][ −1 ]
1
1=L W
U − W Λ(z)U − W
2
2
]
[ −1
[ −1 ]
V
J
0
N
eM
·L W
J
0
VJN
[
]
[
]
[ −1 ]
1
1=L W
U − W Λ(z)U − W
2
2
[
[ −1
]
[
] JN
· L W − V −1 U [V] L −V −10

Fig. 3. Frequency responses of analysis and synthesis parts of XBL-LTs(dashed and solid lines indicate DCT-constrained and unconstrained cases,
respectively): (top) 8 × 16 XBL-LT, (bottom) 16 × 32 XBL-LT.

]
0
,
JN

where W = U JN V, because the block diagonal matrix
diag{V −1 , V} in Ω(z) can also be factorized into blocklifting structures as in Eq. (4). Finally, the residual partc M in Eq. (5) and diag{JN , JN } in Ω(z) are collectively
WJ
factorized as
[
]
[
]
1
JN
0 c
eM .
WJM = U − JN L [JN ] J
0 JN
2□IV. E XPERIMENTAL R ESULTS
A. Coding Gain, Frequency Response, and Number of Rounding Operations
We designed 8 × 16 and 16 × 32 XBL-LTs by optimizing
the coding gain (CG) [14]CG [dB] = 10 log10 ∏M −1
k=0

σx2
σx2k ∥ fk ∥2,

where σx2 is the variance of the input signal, σx2k is the varianceof the k-th subbands and ∥ fk ∥2 is the norm of the k-th
synthesis filter. To simplify the design in DCT-unconstrained

e and Ve in Eq. (6) as N × N arbitrary unitarycase, we set Uematrices, where U is designed such that it has structural onedegree regularity [10] to achieve good image coding. Table
I compares of the CGs[dB] of the XBL-LTs in the DCTconstrained and unconstrained cases. In addition, Fig. 3 shows
the frequency responses of the analysis and synthesis parts of
the XBL-LTs for the same cases as in Table I. In Table I and
Fig. 3, the DCT-unconstrained case had slightly better results
than the DCT-constrained case. Table II shows the numbersof rounding operations of BL-LTs. It is clear that the XBLLTs have fewer rounding operations than those of conventional
BL-LTs.
B. Lossy-to-Lossless Image Coding
For convenience regarding the number of pages, lossy-tolossless image coding was implemented in only the M = 8
case. We used L-LTs in [7], [9], [11], [12] as the conventional
L-LTs. The L-LT in [7] is the 4 × 8 L-LT for JPEG XR.
The L-LT in [9] is the 8 × 16 TDLT with the pre-filtering
part indicated by Cfg. 5 in Table V in [9] and the DCTpart indicated by [15]. The L-LTs in [11], [12] are the DCTconstrained BL-LTs. After the images were transformed by
the L-LTs and periodic extension at the boundaries, the transformed coefficients were rearranged from the subband modeto the multiresolution mode similar to the wavelet transform.
They were encoded with a common wavelet-based zerotree

4Fig. 4. Results of lossy image coding (blue dotted, blue chained, blue dashed, green solid, and red bold solid lines indicate 8 × 16 L-LT in [9], 8 × 16 BL-LT
in [11], 8 × 16 BL-LT in [12], 8 × 16 DCT-constrained XBL-LT, and 8 × 16 DCT-unconstrained XBL-LT, respectively): (top) Baboon, Barbara, Finger, andGoldhill, (bottom) Grass, Lena, Pepper, and Tank.

TABLE IIIR ESULTS OF LOSSLESS IMAGE CODING (LBR [ BPP ], (α) AND (β) MEAN
DCT- CONSTRAINED AND DCT- UNCONSTRAINED CASES , RESPECTIVELY.)
Test
ImagesBaboonBarbaraBoat
ElaineFingerFinger2
Goldhill
Grass
Lena
PepperRoom
SakuraStation
Tank

L-LTs
[7]
[9]
6.23 6.26
4.96 4.90
5.20 5.15
5.27 5.24
5.89 5.92
5.62 5.64
5.12 5.17
6.09 6.14
4.63 4.64
5.00 4.93
4.47 4.51
5.94 6.03
5.16 5.25
5.16 5.19

BL-LTs[11][12]
6.21 6.21
4.90 4.86
5.16 5.14
5.26
5.23
5.84
5.82
5.55 5.53
5.15 5.12
6.08 6.07
4.66 4.62
4.96 4.93
4.55 4.48
5.95 5.93
5.21 5.16
5.18 5.16

XBL-LTs
(α)
(β)
6.21
6.20
4.84
4.83
5.13
5.12
5.23
5.23
5.82
5.82
5.52
5.51
5.11 5.11
6.07
6.06
4.61
4.60
4.92
4.91
4.46
4.44
5.92
5.90
5.15
5.14
5.15 5.15

coder (SPIHT) [16]. The XBL-LTs were compared with theconventional L-LTs by using the lossless bit rate (LBR) andpeak-to-noise ratio (PSNR) in lossy-to-lossless image coding:
Total number of bits [bit]Total number of pixels [pixel]()
2552
PSNR [dB] = 10 log10.
MSE
LBR [bpp] =Table III and Fig. 4 show the results of lossless and lossy
image coding. The vertical axes in Fig. 4 are the differencesin PSNRs relative to the 4 × 8 L-LT in [7] for JPEG XR. It
is clear that the XBL-LTs outperformed the conventional LLTs in lossy-to-lossless image coding. In particular, althoughlifting-based transforms tended to degrade coding performanceat high bit rates, the XBL-LTs preserved coding performanceeven at such high bit rates.
V. C ONCLUSION
By extending an original LT and using block-lifting factorization, we developed an XBL-LT with fewer rounding

operations. It is DCT-unconstrained and hence can be DCTconstrained as well; i.e., it can be considered to be a moregeneral structure than other BL-LTs. Although we constrained
the design by using unitary matrices in this paper, the DCTunconstrained structures have the potential to achieve bettercoding.
ACKNOWLEDGMENT
This work was supported by JSPS Grant-in-Aid for Young
Scientists (B), Grant Number 25820152.
R EFERENCES[1] H. S. Malvar, Signal Processing with Lapped Transforms, Norwood,
MA: Artech House, 1992.
[2] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms, Academic
Press, 1990.
[3] G. K. Wallace, “The JPEG still picture compression standard,” IEEE
Trans. Consum. Electr., vol. 38, no. 1, pp. xviii–xxxiv, Feb. 1992.
[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 of thehigh efficiency video coding (HEVC) standard,” IEEE Trans. Circuits
Syst. Video Technol., vol. 22, no. 12, pp. 1649–1668, Dec. 2012.
[6] W. Sweldens, “The lifting scheme: A custom-design construction ofbiorthogonal wavelets,” Appl. Comput. Harmon. Anal., vol. 3, no. 2, pp.
186–200, Apr. 1996.
[7] 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,” in Proc. of SPIE, San Diego,
CA, Aug. 2008, vol. 7073, pp. 1–12.
[8] 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.
[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] T. Suzuki, M. Ikehara, and T. Q. Nguyen, “Generalized block-lifting
factorization of M -channel biorthogonal filter banks for lossy-to-losslessimage coding,” IEEE Trans. Image Process., vol. 21, no. 7, pp. 3220–
3228, July 2012.
[11] 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.

5[12] 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.
[13] T. Suzuki and M. Ikehara, “Integer DCT based on direct-lifting of DCTIDCT for lossless-to-lossy image coding,” IEEE Trans. Image Process.,
vol. 19, no. 11, pp. 2958–2965, Nov. 2010.
[14] G. Strang and T. Nguyen, Wavelets and Filter Banks, WellesleyCambridge Press, 1996.
[15] 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.
[16] 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.