1

Two-Dimensional Non-Separable Block-Lifting
Structure and Its Application to M -Channel Perfect
Reconstruction Filter Banks for Lossy-to-LosslessImage Coding
Taizo Suzuki, Member, IEEE and Hiroyuki Kudo, Member, IEEE

Abstract—We propose a two-dimensional non-separable blocklifting structure (2D-NSBL) that is easily formulated from the
one-dimensional separable block-lifting structure (1D-SBL) and2D non-separable lifting structure (2D-NSL). The 2D-NSBL canbe regarded as an extension of the 2D-NSL because a two-channel
2D-NSBL is completely equivalent to a 2D-NSL. We apply the
2D-NSBL to M -channel (M = 2n , n ∈ N) perfect reconstruction
filter banks (PRFBs). The 2D-NSBL-based PRFBs outperform
1D-SBL-based PRFBs at lossy-to-lossless coding, whose image
quality is scalable from lossless data to high compressed lossy
data, because their rounding errors are reduced by merging manyrounding operations.
Index Terms—Lossy-to-lossless image coding, perfect reconstruction filter bank (PRFB), two-dimensional non-separable
block-lifting structure (2D-NSBL)

I. I NTRODUCTIONT

HE amount of video being sent over communications
networks has been steadily increasing as a result ofdevelopments in multimedia devices and communication tools.
Filter banks (FBs) [1] have been widely researched as a way
to efficiently compress such signals. The polyphase matricesof M -channel (M = 2n , n ∈ N) FBs shown in Fig. 1 arepresented as[]T
H0 (z) H1 (z) · · · HM −1 (z)[]T= E(z M ) 1 z −1 · · · z −(M −1)[]
F0 (z) F1 (z) · · · FM −1 (z)][= 1 z −1 · · · z −(M −1) R(z M ),where Hi (z), Fi (z), z, and ·T denote an analysis filter, asynthesis filter, a delay element, and matrix transposition,
respectively. If E(z) is invertible, the inverse of E(z) can bechosen as a synthesis polyphase matrix R(z), and such FBs
are called perfect reconstruction FBs (PRFBs). When R(z) =ET (z −1 ), the FBs are called paraunitary FBs (PUFBs) which
are special classes of PRFBs. On the other hand, PRFBs
that are not PUFBs are commonly called biorthogonal FBs(BOFBs). In particular, the JPEG series [2–4] and H.26x
series [5], [6] of global standards use various classes of
PRFBs, including the discrete cosine/sine transform (DCTand DST) [7], discrete wavelet transform (DWT) [8], andT. 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).

Fig. 1. Polyphase structure of M -channel FB.
TABLE IC LASSIFICATION OF LIFTING STRUCTURES .

Block-Lifting
Non-Separable

1D-SL[10–12]——

1D-SBL[13]✓—

2D-NSL[14], [15]—✓2D-NSBLProp.
✓✓

hierarchical lapped transform (HLT) [9]. However, there is a
growing need for better FBs in order to alleviate the burden
on servers and free up communication bandwidth.
Lossy-to-lossless image coding, which merges two or more
pieces of data into one piece of data of the same pieceof content, i.e., “one source multi-use” image coding, has
attracted attention from researchers as a possible way tomeet this need. Reversible transforms that map integers tointegers, called integer-to-integer transforms, are important
tools for lossy-to-lossless image coding. Sweldens presented
a lifting structure [10–12] with which to achieve integer-tointeger transforms, and this structure has been applied to many
FBs [16–23]. Although JPEG XR [4] has scalability ranging
from lossless to lossy as a result of using a lifting-based HLT,
its coding performance is not sufficient especially for images
with high-frequency components (texture).
The one-dimensional separable block-lifting structure (1DSBL) of BOFB was proposed in [13] for the purpose ofdesigning lifting-based FBs with higher coding performance.
Usually, the design parameters and structure of lifting-based
FBs are constrained when factorizing the original FB into lifting structures, whereas the 1D-SBL-based BOFBs presented
in [13] do not constrain them except in the initial block.1 The
1D-SBL is better at lossy-to-lossless image coding because
it uses fewer rounding operations in comparison with the
1 The determinant of the initial block is constrained to be an integer value.

2standard 1D separable lifting structure (1D-SL). Furthermore,
the two-dimensional non-separable lifting structure (2D-NSL)
for DWTs proposed in [14], [15] performs even better atcoding because it uses fewer rounding operations than the 1DSL.
Here, we propose a 2D non-separable block-lifting structure(2D-NSBL) that is easily formulated from the 1D-SBL and
2D-NSL methods. The 2D-NSBL can be regarded as anextension of the 2D-NSL because a 2D-NSBL with M = 2 iscompletely equivalent to a 2D-NSL. We apply the 2D-NSBL
to M -channel PRFBs and show that the PRFBs perform betterat lossy-to-lossless coding than the conventional 1D-SBLbased PRFBs do because their rounding errors are reducedby merging many rounding operations.
The remaining part of this paper is organized as follows. We
review and define the block-lifting structure, 1D-SBL-based
PRFBs, and 2D-NSL-based DWTs in Section II. Section III
presents the derivation of the 2D-NSBL and its application to
M -channel PRFBs. Design examples, lossy-to-lossless image
coding simulations, and comparisons with the conventional
PRFBs are shown in Section IV. Section V concludes thispaper.
Notations: A classification of lifting structures is shown in
Table. I. Im , 0, det(·), and round(·) denote an m×m identity
matrix, a null matrix, determinant of a matrix, and a rounding
operation, respectively. Im is simply expressed by I if its size
is clear. Indexes x, y, w, and 2d in the matrices mean to operatehorizontally, vertically, horizontally or vertically (w = x or y),and horizontally and vertically, respectively. For example,
Tx x = xTT , Ty x = Tx, and T2d x = TxTT ,where T and x are a transform matrix and a 2D input signal,
respectively.

II. R EVIEW AND D EFINITIONS
A. Block-Lifting Structure
A lifting structure [10–12] is a transform that map integers
to integers by implementing rounding operation in each lifting
step; i.e., it is a means of lossy-to-lossless image coding.
The elementary matrices are identity matrices with one single
nonzero off-diagonal element. However, an FB with too many
lifting steps cannot perform good coding because it generates
a rounding error in each lifting step.
We proposed the block-lifting structure in [13], which is a
special class of standard lifting structure (Fig. 2). It is good forlossy-to-lossless image coding because it reduces the rounding
error by merging many rounding operations. In Fig. 2, theanalysis input signal vectors xi and xj , the analysis output(synthesis input) signal vectors yi and yj , the synthesis output
signal vectors zi and zj , and the lifting coefficient blocks L(z)and U(z) are related as follows:
yj = xj + round(L(z)xi )
yi = xi + round(U(z)yj )zi = yi − round(U(z)yj ) = xi 
zj = yj − round(L(z)xi ) = xj
yi = xi + round(U(z)xj )
yj = xj + round(L(z)yi )zj = yj − round(L(z)yi ) = xj zi = yi − round(U(z)xj ) = xi

(Case A)

(Case B).

In these cases, the matrices and their inverse matrices are
expressed by
[ ]
[ ]
[ ]
[ ] [ ]yixziyx
= W(z) i ,= W−1 (z) i = i ,
yj
xj
zj
yj
xj
where

{
W(z) ={BU (z)BL (z) (Case A)
BL (z)BU (z) (Case B)−1
B−1
L (z)BU (z) (Case A)−1
B−1
U (z)BL (z) (Case B)[][]
I U(z)I −U(z)−1
BU (z) =, BU (z) =
0
I
0
I
[
]
[
]
I
0
I
0
BL (z) =
, B−1
(z)
=
.
L
L(z) I−L(z) I
−1

W

(z) =

Note that the rounding operations are actually implemented
even if the lifting matrix expression omits the notation of them.
The block-lifting structure for a 1D implementation is called“1D-SBL” to distinguish it from the “2D-NSBL” proposed inthis paper. When M = 2, they will also be called “1D-SL”
and “2D-NSL”.
B. 1D-SBL-based PRFBs
The polyphase matrix E(z) of an M -channel PRFB of filter
length M K (K ∈ N, K ≥ 2) is expressed as [24]E(z) =

1∏{Ek (z)}G0 ,

(1)

k=K−1

where the initial block G0 is an M × M nonsingular matrix
and the building block Ek (z) is expressed by
Ek (z) = I − U k V Tk + z −1 U k V Tk .
The M × γk parameter matrices U k and V k satisfy
1 × ··· ×.
0 1 . . . .. 
V Tk U k = 
≜ Wk,
. .

. . . . . ×
 ..
0 · · · 0 1 γ ×γkkwhere × indicates possibly nonzero elements and γk is a
McMillan degree (γk ∈ N, 1 ≤ γk ≤ M − 1). W k = I
when the filter lengths in analysis and synthesis banks areequal. A synthesis polyphase matrix R(z) is defined as one
that has the PR property R(z)E(z) = I. Moreover, U k andT
T T
V k are defined as U k = [uTk0 , uTk1 ]T and V k = [vk0
, vk1
] ,

3

Fig. 2. Block-lifting structures. Black and white circles mean adders and rounding operations, respectively: (left) Case A and (right) Case B.

where uk0 and vk0 are (M − γk ) × γk matrices and uk1 andvk1 are γk × γk square matrices. When V k = U k , the PRFB
has the paraunitary property, i.e., PUFB. In this paper, we fix
W k = I and γk = M/2.
We factorized the PRFBs into the 1D-SBL in [13]. The 1DSBL-based PRFBs represent Ek (z) in Eq. (1) as
[
][
]
[
][
]
I
0 I UkI −Uk
I 0
Ek (z) =Λ(z),−Lk I 0 I
0
I
Lk I
−T T
T
where Lk = vk1
vk0 , Uk = uk0 vk1
, and
[
]
I
0
Λ(z) =.
0 z −1 I

In addition, det(G0 ) is constrained to be det(G0 ) = ±n(n ∈ N) for the purpose of making a lifting factorization.
If paraunitariness is not required, Lk and Uk can be arbitrary
M/2×M/2 matrices. To improve coding performance, Eq. (1)can be rewritten as (Fig. 3)
E(z) = WK (z)1∏{Λ(z)Wk (z)}G0 ,

(2)

k=K−1

where

[

][
]
b k (z)I0I U
b k (z) I
0IL{(k = K)b k (z) = 0
U−1(z − 1)Uk (otherwise)(k = 1)
L1b
Lk (z) = −LK−1(k = K) .

Lk − Lk−1 (otherwise)

Wk (z) =In comparison with the 1D-SBL-based PRFBs in Eq. (1), the1D-SBL-based PRFBs are more effective at lossy-to-losslessimage coding because they reduce the rounding error by
merging more rounding operations.

where

[

1 uk (z)wk (z) =
0
1

][

]
1
0
.
lk (z) 1

For example, 5/3-DWT has N = 1, s = 1, u0 (z) = (1 + z)/4
and l0 (z) = −(1 + z −1 )/2. If an image is transformed by
the 2D-NSL-based DWT polyphase matrix e2d
k (z2d ), one can
write
[ T
]T
T
T
T
YLH
YHH
YLL YHL
[ T
]T
T
T
T
XHH
= e2d
,
k (z2d ) XLL XHL XLH
where XLL , XHL , XLH , and XHH are the top-left, top-right,
bottom-left, and bottom-right pixels in 2×2 blocks composing
the image, YLL , YHL , YLH , and YHH are their output pixels,
and
 2

0
s
0
0
∏
 0 I20 
e2d
wk2d (z2d ).
k (z2d ) =−20 0 s
k=N −1wk2d (z2d ) in e2d (z2d ) is represented as [14], [15]]][ [ x
1 uk (zx ) uyk (zy ) −u2dk (z2d )wk2d (z2d ) =0
I3[ x 1 ] 0 [ y0 ]
 l (zx )uk (zy ) 
k

·
I2
 ly (zy )uxk (zx ) 
k
0
0
1
]
[
I
0
3
[
]
.
· 2d
lk (z2d ) lky (zy ) lkx (zx ) 1(3)

The 2D-NSL is also more effective at lossy-to-lossless image
coding than the 1D-SL is because it uses fewer rounding
operations.
III. 2D-NSBL- BASED PRFB S

C. 2D-NSL-based DWTs

A. Derivation of 2D-NSBL

1D-SL-based 9/7-tap and 5/3-tap DWTs (9/7-DWT and 5/3DWT) [8] are used in the JPEG 2000 [3] lossy and losslessmodes, respectively. Let e(z) be a polyphase matrix of 1DSL-based DWTs, expressed as
[
] ∏
0
s
0
e(z) =wk (z),−1
0 s

We introduce 2D-NSBL in this subsection.
Theorem: Consider an image that has been 2Dtransformed by the set of lower and upper block-lifting matrices in Fig. 2 as follows:
[ T
]T
T
T
T
YLL YHL
YLH
YHH
[
]T
= W2d (z2d ) XTLL XTHL XTLH XTHH , (4)k=N −1

4

Fig. 3. 1D-SBL-based PRFB. Black and white circles mean adders and rounding operations, respectively.

where

[

x

]

[

y

]

W (zx )0
W (zy )0PP
0Wx (zx )0
Wy (zy ){w
Bw
U (zw )BL (zw ) (Case A)
Ww (zw ) =ww
BL (zw )BU (zw ) (Case B)
I 0 0 0
0 0 I 0P =0 I 0 0 ,0 0 0 I

W2d (z2d ) =XLL , XHL , XLH , and XHH are the top-left, top-right, bottomleft, and bottom-right M/2×M/2 blocks of an M ×M image,and YLL , YHL , YLH , and YHH are their respective output
blocks (Fig. 4). W2d (z2d ) in Eq. (4) can be factorized into
three 2D-NSBL matrices, as follows (Fig. 5):2d2dW2d (z2d ) = W2d
2 (z2d )W1 (z2d )W0 (z2d ),y = TxTT = Tn−1 · · · T0 xTT0 · · · TTn−1 .

(6)This Eq. (6) means that the 2D implementation of Tk is
performed after that of Tk−1 (1 ≤ k ≤ n − 1), i.e., the twow
block-lifting matrices Bw
L (zw ) and BU (zw ) in Eq. (4) can be
operated separately. The resulting representation of W2d (z2d )
is
{
2d
B2d
U (z2d )BL (z2d ) (Case A)
W2d (z2d ) =2d2dBL (z2d )BU (z2d ) (Case B),

(7)

(5)
where

where

]
[
I3M/2
0


[
]


2d
y
x


I
 L (z2d ) L (zy ) L (zx )(Case A)[]][W2d
0 (z2d ) =
x
y
2d

I
U
(z
)
U
(z
)
U
(z
)

x
y
2d





0
I3M/2



(Case B)[ I ] 0 [ y0 ]
 Lx (zx )U (zy ) 2d
W1 (z2d ) =  yIML (zy )Ux (zx ) 
0
0
I
[
]]
[
x
y
2d

I
U
(z
)
U
(z
)
−U
(z
)
x
y
2d





0
I3M/2




(Case A)[]W2d
2 (z2d ) =

I
0
3M/2

[
]



2d
y
x

I
 −L (z2d ) L (zy ) L (zx )(Case B)

Proof: When a matrix T = Tn−1 · · · T0 (n ∈ N) is
applied to a 2D input signal x in the horizontal and verticaldirections, the output signal y is expressed as [25]

]
] [ y
0
BxL (zx )0
BL (zy )PP
0By (zy )0
BxL (zx )

 L
I
0
0
0
 Lx (zx )
I
0
0

=
 Ly (zy )0I0
L2d (z2d ) Ly (zy ) Lx (zx ) I
[ x
] [ y
]
BU (zx )0
BU (zy )02d
BU (z2d ) =P
P
0BxU (zx )0
ByU (zy )I Ux (zx ) Uy (zy ) U2d (z2d )0I0Uy (zy ) 
.
=
0
0
I
Ux (zx ) 
0
0
0
I
[

B2d
L (z2d ) =.

It is clear that the 2D-NSBL is an extension of the 2D-NSL
in [14], [15] because the 2D-NSBL with M = 2 in Eq. (5)(Case A) is completely equivalent to the 2D-NSL in Eq. (3).
Furthermore, a 2D-NSBL with the McMillan degree γk ̸=
M/2 can be easily obtained.

Since the lifting matrix will have inevitably generated rounding operations in a process, as described in Section II-A, we
2dseparate each of B2d
L (z2d ) and BU (z2d ) into two 2D-NSBL
matrices:{
B2d
L (z2d ) ={B2dU (z2d ) =2d
B2d
L1 (z2d )BL0 (z2d ) (Case A)
2d
B2d
L2 (z2d )BL1 (z2d ) (Case B)

(8)

2d
B2d
U 2 (z2d )BU 1 (z2d ) (Case A)2d
B2d
U 1 (z2d )BU 0 (z2d ) (Case B),

(9)

5

Fig. 4. 2D implementation of 1D-SBL. Black and white circles mean adders and rounding operations, respectively: (left) Case A and (right) Case B.

where

[

]
I3M/2
0
2d
[
]
BL0 (z2d ) =L2d (z2d ) Ly (zy ) Lx (zx ) I[ xI ] 0 0
 L (zx )


B2d
IM 0
L1 (z2d ) =  Ly (z )

y
0
0 I
]
[
I3M/2
0
[
]
B2d
(z
)
=
L2 2d
−L2d (z2d ) Ly (zy ) Lx (zx ) I[[]]
I Ux (zx ) Uy (zy ) U2d (z2d )
B2d
(z
)
=
U 0 2d0I3M/2
I 0 [ 0 ]Uy (zy ) 
B2d
U 1 (z2d ) = 0 IM
Ux (zx ) 
0 0
I
[
[ x
]]
I
U (zx ) Uy (zy ) −U2d (z2d )2d
BU 2 (z2d ) =
.
0
I3M/2

Consequently, W2d (z2d ) is expressed as
{
2d
2d
B2d
2d
U 2 (z2d )BU L (z2d )BL0 (z2d )W (z2d ) =2d2d2dBL2 (z2d )BLU (z2d )BU 0 (z2d )where[ I ] 0
 Lx (zx )2d2d
BU L (z2d ) = BLU (z2d ) = IM Ly (zy )00
[ y0 ]
U (zy ) Ux (zx ) I

B. Application to PRFBs
Here, we will apply the 2D-NSBL in Eq. (5) to the conventional 1D-SBL-based PRFBs in Eq. (2). Let E2d (z2d ) be a 2D
separable polyphase matrix based on a 1D separable polyphasematrix E(z) in Eq. (2). Since the 2D implementation of
the separable block transform allows us to change the orderin which the blocks are operated on, the polyphase matrix
E2d (z2d ) can be expressed as
1
∏
{ 2d
}
Λ (z2d )Wk2d (z2d ) G2d
0 ,
k=K−1

[
] [
]
Λ(zx )0Λ(zy )0Λ (z2d ) =PP0Λ(zx ))0Λ(zy ))[ x] [ y]Wk (zx )0
Wk (zy )0
Wk2d (z2d ) =P
P0
Wkx (zx )0
Wky (zy )
[ x
] [ y
]
G0
0
G0 0
P
G2d
=
P.
y
0
0 Gx0
0 G0
2d

Applying Case A of the proposed 2D-NSBL in Eq. (5) toWk2d (z2d ) yields[
Wk2d (z2d ) =(Case A)
(Case B),

from Eqs. (7)-(9). The resulting equation is completely thesame as Eq. (5).
□2dE2d (z2d ) = WK
(z2d )

where

[

]]
b y (zy ) −U
b 2d (z2d )
U
k
k
I3M/2

[ I ] 0 [ 0 ] bxb y (zy ) U L (z )k·  b ky xIMb x (zx )  Lk (zy )

U
k
0
0
I
[
]
I3M/2
[
] 0
· b 2d.
b y (zy ) Lb x (zx )I
Lk (z2d ) L
k
k
I
0


b x (zx )U
kFor G2d0 , a 1D-SL factorization is used. As is done in [13],we use the single-row elementary reversible matrix (SERM)
presented in [16] for each initial block Gw
0 , where any other
1D-SL factorization can be applied to Gw
0.

IV. E XPERIMENTAL R ESULTS
A. Filter Design
By following the method presented in [13], 8 × 16 and8 × 24 BOFBs with order-1 building blocks were designed by using the cost function Φ and fminunc.m in
Optimization ToolBox of MATLAB. Φ was a weighted
linear combination of the coding gain CCG and the stopband
attenuation values of analysis and synthesis filters CSAa and
CSAs :
Φ = (w1 CSAa + w2 CSAs ) − w3 CCG ,6Fig. 5. 2D-NSBL. Black and white circles mean adders and rounding operations, respectively: (top) Case A and (bottom) Case B.

TABLE IIL OSSLESS IMAGE CODING RESULTS (LBR [ BPP ]).

Test
ImagesBarbaraBoat
FingerGrass
Lena
PepperBridge
Deer
Arri
Face

Not Lifting
8 × 8 DCT [26]
—
—
—
—
—
—
—
—
—
—

Conventional Methods
1D-NSL
4 × 8 HLT [9]5/3-DWT [14], [15]
4.81
4.86
5.13
5.09
5.71
5.83
6.05
6.06
4.61
4.48
4.96
4.85
4.63
4.65
4.77
4.76
11.28
11.40
10.33
10.37

where wk s are weighted coefficients. CCG , CSAa , and CSAsare
CCG = 10 log10 ∏M −1
CSAa =

M
−1 ∫
∑

k=0

σx2

CSAs =

k=0

Proposed Method
2D-NSBL
8 × 16 BOFB 8 × 24 BOFB
4.76
4.75
5.08
5.09
5.65
5.64
6.05
6.05
4.61
4.61
4.92
4.92
4.63
4.63
4.74
4.74
11.27
11.27
10.28
10.28

region of Hi (z) and Fi (z), respectively. The input signalx(n) is the AR(1) process with an intersample autocorrelation
coefficient ρ = 0.95 in common use.

σx2i ∥ fi ∥2

Wia |Hi (ejω )|2 dω

ω∈Ωi

k=0
M
−1 ∫
∑

1D-SBL [13]8 × 16 BOFB
8 × 24 BOFB
4.79
4.76
5.09
5.10
5.66
5.65
6.05
6.05
4.63
4.62
4.93
4.92
4.65
4.67
4.76
4.76
11.27
11.27
10.28
10.28

Wis |Fi (ejω )|2 dω,ω∈Ωiwhere σx2 , σx2i , ∥ fi ∥2 , Wia , Wis , and Ωi are the variance of
the input signal, the variance of the i-th subbands, the norm of
the i-th synthesis filter, weighting functions for the stopband
attenuation of the analysis, synthesis bank, and the stopband

B. Lossy-to-Lossless Image Coding
The resulting BOFBs were implemented with a rounding
operation at each lifting step and compared in terms of thelossless bitrate (LBR) [bpp] in lossless image coding:

LBR [bpp] =Total number of bits [bit],Total number of pixels [pixel]

7

TABLE IIIL OSSY IMAGE CODING RESULTS (PSNR [ D B]).

Test
ImagesBarbaraBoat

Finger

Grass

Lena

PepperBridge

Deer

Arri

Face

Bitrate
[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
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

Not Lifting
8 × 8 DCT [26]
26.96
30.40
34.98
27.85
30.87
34.39
22.78
25.42
29.17
24.00
25.94
28.70
30.55
34.43
38.87
29.84
32.83
35.75
31.11
33.76
36.64
34.14
35.10
37.45
31.92
36.82
41.80
45.01
47.85
50.87

Conventional Methods
1D-NSL
4 × 8 HLT [9]9/7-DWT [14], [15]
26.85
27.24
30.43
30.46
35.05
34.85
27.62
28.45
30.87
31.38
34.31
34.48
22.96
23.49
25.56
25.98
29.01
29.07
23.99
24.35
25.86
26.09
28.68
28.68
31.65
32.50
35.03
35.49
38.65
38.63
31.20
31.90
33.95
34.45
35.59
36.08
31.14
31.79
34.06
34.25
37.35
36.83
33.96
34.10
34.83
34.88
36.97
36.83
33.22
33.28
36.75
37.30
42.28
41.97
45.49
45.96
48.40
48.72
51.47
51.68

and the peak signal-to-noise ratio (PSNR) [dB] in lossy image
coding:()
MAX2p,
PSNR [dB] = 10 log10
MSE
where MAXp and MSE are the maximum possible pixel valueof the image and the mean squared error, respectively. To
evaluate transform performance fairly, we employed two-,
three-, six-, and two-level decompositions, respectively, on theeight-channel DCT [26] (H.265/HEVC)2 , HLT [9] (JPEG XR),
1D-NSL-based DWTs without adaptive directionalities [14],[15], and eight-channel BOFBs. The 1D-SBL-based BOFBs
had the same transfer function as the proposed FBs. The image
set included six 512 × 512 eight-bit standard grayscale imagesin [27], two 2048 × 2048 eight-bit clipped grayscale images in[28], and two 2816 × 1600 16-bit grayscale images in [29]. A
quadtree-based embedded image coder EZW-IP [30] was used
to encode the transformed images. EZW-IP is more suited toblock transforms than are the popular zerotree-based coders,e.g., EZW [31] and SPIHT [32]. A periodic extension was usedin the image boundary processing of the BOFBs, whereas theextensions used in JPEG XR and JPEG 2000 were used as therespective boundary processings of the HLT and DWTs.
Tables II, III, and Fig. 6 show lossless and lossy image
coding results. Although the conventional methods sometimes
2 Since the DCT in H.265/HEVC is not composed of lifting structures, it isunsuitable for lossless image coding.

1D-SBL [13]8 × 16 BOFB 8 × 24 BOFB
28.04
28.64
31.63
32.18
35.88
36.26
28.26
28.62
31.35
31.61
34.66
34.85
23.52
23.86
26.43
26.93
30.06
30.78
24.27
24.50
26.30
26.61
29.08
29.42
32.20
31.85
35.41
35.65
38.68
38.76
31.45
31.08
33.97
33.70
35.92
36.01
31.93
32.19
34.57
34.54
37.24
37.27
33.88
34.02
34.99
35.06
37.11
37.04
33.63
34.14
38.26
38.98
43.87
43.93
46.27
46.67
48.98
49.31
51.89
52.22

Proposed Method
2D-NSBL
8 × 16 BOFB 8 × 24 BOFB
28.05
28.65
31.67
32.20
35.94
36.38
28.25
28.63
31.36
31.63
34.70
34.91
23.51
23.86
26.43
26.95
30.07
30.81
24.28
24.50
26.30
26.62
29.10
29.44
32.20
31.86
35.44
35.73
38.78
38.95
31.45
31.10
34.01
33.76
35.97
36.11
31.94
32.22
34.60
34.63
37.38
37.42
33.90
34.06
35.03
35.13
37.20
37.27
33.63
34.14
38.26
38.98
43.87
43.93
46.27
46.67
48.98
49.31
51.89
52.22

performed better on images with many low frequency components, overall, the 2D-NSBL-based BOFBs outperformed
the conventional methods. These results are considered to be
due to the merging (reducing) of many rounding operationsin the 2D-NSBL-based BOFBs. Comparing Figs. 4 and 5,
it is clear that the number of rounding operations of the
2D non-separable implementation is the almost half that of
the 1D separable implementation. However, there were nodifferences between the 1D-SBL and 2D-NSBL of BOFBs
in 16-bit images. In the future, we should solve the problem
in high bit images.
V. C ONCLUSION
We devised a 2D-NSBL and applied it to M -channel PRFBs
in lossy-to-lossless image coding. The 2D-NSBL is easily
formulated from the 1D-SBL and 2D-NSL methods and canbe regarded as an extension of the 2D-NSL because it iscompletely equivalent to a 2D-NSL when M = 2. A lossy-tolossless image coding experiment confirmed the improvementsthat could be had with 2D-NSBL.
ACKNOWLEDGMENT
The authors would like to thank the anonymous reviewers
for providing many constructive suggestions that significantly
improve the presentation of this paper. This work was supported by JSPS Grant-in-Aid for Young Scientists (B), Grant
Number 25820152.

8

Fig. 6. Comparison of a particular area of an image Barbara (bitrate: 0.25 [bpp]): (left-right) 8 × 8 DCT, 4 × 8 HLT, 2D-NSL-based 9/7-DWT, 8 × 24
1D-SBL-based BOFB [13], and 8 × 24 2D-NSBL-based BOFB.

R EFERENCES[1] P. P. Vaidyanathan, Multirate Systems and Filter Banks. Englewood
Cliffs, NJ: Prentice Hall, 1992.
[2] G. K. Wallace, “The JPEG still picture compression standard,” IEEE
Trans. Consum. Electr., vol. 38, no. 1, pp. xviii–xxxiv, Feb. 1992.
[3] A. Skodras, C. Christopoulis, and T. Ebrahimi, “The JPEG2000 still
image compression standard,” IEEE Signal Process. Mag., vol. 18, no. 5,
pp. 36–58, Sep. 2001.
[4] 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.
[5] 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.
[6] 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.
[7] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms. Academic
Press, 1990.
[8] I. Daubechies and W. Sweldens, “Factoring wavelet transforms into
lifting steps,” J. Fourier Anal. Appl., vol. 4, no. 3, pp. 247–269, 1998.
[9] 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, vol. 7073,
San Diego, CA, Aug. 2008, pp. 1–12.
[10] W. Sweldens, “The lifting scheme: A new philosophy in biorthogonal
wavelet constructions,” in Proc. of SPIE, vol. 2569, San Diego, CA, July
1995, pp. 1–12.
[11] ——, “The lifting scheme: A custom-design construction of biorthogonal wavelets,” Appl. Comput. Harmon. Anal., vol. 3, no. 2, pp. 186–200,
Apr. 1996.
[12] ——, “The lifting scheme: A construction of second generation
wavelets,” SIAM J. Math. Anal., vol. 29, no. 2, pp. 511–546, 1998.
[13] 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.
[14] T. Yoshida, T. Suzuki, S. Kyochi, and M. Ikehara, “Two dimensional
non-separable adaptive directional lifting structure of discrete wavelet
transform,” IEICE Trans. Fundamentals., vol. E94-A, no. 10, pp. 1920–
1927, Oct. 2011.
[15] M. Iwahashi and H. Kiya, “Reversible 2D 9-7 DWT based on nonseparable 2D lifting structure compatible with irreversible DWT,” IEICE
Trans. Fundamentals., vol. E94-A, no. 10, pp. 1928–1936, Oct. 2011.
[16] P. Hao and Q. Shi, “Matrix factorizations for reversible integer mapping,” IEEE Trans. Signal Process., vol. 49, no. 10, pp. 2314–2324,
Oct. 2001.

[17] Y. J. Chen and K. S. Amaratunga, “M -channel lifting factorizationof perfect reconstruction filter banks and reversible M -band wavelet
transforms,” IEEE Trans. Circuits Syst. II, vol. 50, no. 12, pp. 963–976,
Dec. 2003.
[18] Y. J. Chen, S. Oraintara, and K. S. Amaratunga, “Dyadic-based factorizations for regular paraunitary filterbanks and M -band orthogonal
wavelets with structural vanishing moments,” IEEE Trans. Signal Process., vol. 53, no. 1, pp. 193–207, Jan. 2005.
[19] Y. She, P. Hao, and Y. Paker, “Matrix factorizations for parallel integertransformation,” IEEE Trans. Signal Process., vol. 54, no. 12, pp. 4675–
4684, Dec. 2006.
[20] C. M. Brislawn, “Group lifting structures for multirate filter banks
I: Uniqueness of lifting factorizations,” IEEE Trans. Signal Process.,
vol. 58, no. 4, pp. 2068–2077, Apr. 2010.
[21] ——, “Group lifting structures for multirate filter banks II: Linear phasefilter banks,” IEEE Trans. Signal Process., vol. 58, no. 4, pp. 2078–2087,
Apr. 2010.
[22] L. Wang, L. Jiao, J. Wu, G. Shi, and Y. Gong, “Lossy-to-lossless image
compression based on multiplier-less reversible integer time domain
lapped transform,” Signal Process. Image Commun., vol. 25, no. 8, pp.
622–632, Sep. 2010.
[23] L. Jiao, L. Wang, J. Wu, J. Bai, S. Wang, and B. Hou, “Shape-adaptive
reversible integer lapped transform for lossy-to-lossless ROI coding of
remote sensing two-dimensional images,” IEEE Geosci. Remote Sens.
Lett., vol. 8, no. 2, pp. 326–330, Mar. 2011.
[24] Y. J. Chen, S. Oraintara, and K. S. Amaratunga, “Theory and factorization for a class of structurally regular biorthogonal filter banks,” IEEE
Trans. Signal Process., vol. 54, no. 2, pp. 691–700, Feb. 2006.
[25] T. Suzuki, S. Kyochi, Y. Tanaka, M. Ikehara, and H. Aso, “Multiplierless
lifting based FFT via fast Hartley transform,” in Proc. of ICASSP’13,
Vancouver, Canada, May 2013, pp. 5603–5607.
[26] P. Kumar, S. Y. Park, B. K. Mohanty, K. S. Lim, and C. Yeo, “Efficient
integer DCT architectures for HEVC,” IEEE Trans. Circuits Syst. Video
Technol., vol. 24, no. 1, pp. 168–178, Jan. 2014.
[27] “The USC-SIPI Image Database,” Univ. Southern California,
Signal and Image Processing Institute [Online], Available:
http://sipi.usc.edu/database/.
[28] “The New Test Images - Image Compression Benchmark,” Rawzor- Lossless Compression Software for Camera RAW Images [Online],
Available: http://www.imagecompression.info/test images/.
[29] S. Andriani, H. Brendel, T. Seybold, and J. Goldstone, “Beyond the
Kodak image set: A new reference set of color image sequences,” inProc. of ICIP’13, Melbourne, Australia, Sep. 2013, pp. 2289–2293.
[30] Z. Liu and L. J. Karam, “An efficient embedded zerotree wavelet image
codec based on intraband partitioning,” in Proc. of ICIP’00, Vancouver,
British Columbia, Canada, Sep. 2000.
[31] J. M. Shapiro, “Embedded image coding using zerotrees of wavelet

9coefficients,” IEEE Trans. Signal Process., vol. 41, no. 12, pp. 3445–
3462, Dec. 1993.
[32] 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.

Taizo Suzuki (M’11) received the B.E., M.E., andPh.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. From2010 to 2011, he was a Research Fellow of the Japan
Society for the Promotion of Science (JSPS) anda Visiting Scholar at the Video Processing Group,
the University of California, San Diego, CA. From2011 to 2012, he was an Assistant Professor in the Department of Electricaland 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 researchinterests are theory and design of filter banks and their application to image
and video processing.

Hiroyuki Kudo In 1985, Hiroyuki Kudo received
the B.Sc. degree from Department of Electrical Communications, Tohoku University, Japan. In
1990, he received the Ph.D. degree from the Graduate School of Engineering, Tohoku University,
Japan. In 1992, he joined the University of Tsukuba,
Japan as an assistant professor. Currently, he isa professor at the Division of Information Engineering, Faculty of Engineering, Information and
Systems, University of Tsukuba, Japan. His researchareas include medical imaging, image processing,and inverse problems. In particular, he is actively working on tomographic
image reconstruction for X-ray CT, PET, SPECT, and Electron Tomography.
Since 2011, he is working as an Editor in Chief, Journal of Medical Imaging
Technology (MIT). He obtained the best paper award several times fromvarious domestic and international academic societies. In particular, his papers
on interior tomography published in 2008 were selected as High Lights of thetwo journals, Physics in Medicine and Biology and Inverse Problems. He is amember of IEEE, Japanese Society of Medical Imaging Technology (JAMIT),and IEICE Japan.