TWO-DIMENSIONAL NON-SEPARABLE BLOCK-LIFTING-BASED
M -CHANNEL BIORTHOGONAL FILTER BANKS
Taizo Suzuki and Hiroyuki Kudo
Faculty of Engineering, Information and Systems, University of Tsukuba
Tsukuba, Ibaraki, 305-8573 Japan
Email: {taizo, kudo}@cs.tsukuba.ac.jp
ABSTRACT
We propose a two-dimensional (2D) non-separable blocklifting structure (NSBL) that is easily formulated from the
one-dimensional (1D) separable block-lifting structure (SBL)
and 2D non-separable lifting structure (NSL). The NSBL
can be regarded as an extension of the NSL because a twochannel NSBL is completely equivalent to a NSL. We apply
the NSBL to M -channel (M = 2n , n ∈ N) biorthogonal filterbanks (BOFBs). The NSBL-based BOFBs (NSBL-BOFBs)
outperform SBL-based BOFBs (SBL-BOFBs) at lossy-tolossless coding, whose image quality is scalable from losslessdata to high compressed lossy data, because their rounding
error is reduced by merging many rounding operations, i.e.,
the number of the NSBL is the almost half that of the SBL.
Index Terms— Biorthogonal filter bank (BOFB), lossyto-lossless image coding, non-separable block-lifting structure (NSBL).
1. INTRODUCTION
Filter banks (FBs) [1] have been widely researched as a way
to efficiently compress various signals. The polyphase matrices of M -channel (M = 2n , n ∈ N) FBs are presented
as[]T
H0 (z) H1 (z) · · · HM −1 (z) = E(z M )e(z)T[]F0 (z) F1 (z) · · · FM −1 (z) = e(z)R(z M )where e(z) = [1, z −1 , · · · , z −(M −1) ], and Hi (z), Fi (z), z,and ·T denote an analysis filter, a synthesis filter, a delay element, and matrix transposition, respectively. If E(z) is invertible, the inverse of E(z) can be chosen as a synthesis
polyphase matrix R(z), and such FBs are called perfect reconstruction FBs (PRFBs). Especially, PRFBs without paraunitariness are called biorthogonal FBs (BOFBs). The JPEG
series and H.26x series of global standards use various classesof PRFBs, including the discrete cosine/sine transform (DCTand DST) [2], discrete wavelet transform (DWT) [3], andThis work was supported by JSPS Grant-in-Aid for Young Scientists (B)Grant Number 25820152.

291

Table 1. Classification of lifting structures.

Block-Lifting
Non-Separable

SL [5]——SBL [9]✓—NSL [10]
—
✓NSBL
✓
✓

lapped transform (LT) [4]. However, there is a growing needfor better FBs in order to alleviate the burden on servers andfree 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 to meetthis need. Reversible transforms that map integers to integers,
called integer-to-integer transforms, are important tools forlossy-to-lossless image coding. Sweldens presented a lifting
structure [5] with which to achieve integer-to-integer transforms, and this structure has been applied to many FBs [6–8].
Although JPEG XR has scalability ranging from lossless tolossy as a result of using a lifting-based LT (L-LT), its coding performance is not sufficient especially for images withhigh-frequency components (texture).
The one-dimensional (1D) separable block-lifting structure (SBL) of BOFB was proposed in [9] for the purposeof designing lifting-based FBs (L-FBs) with higher codingperformance. Usually, the design parameters and structureof L-FBs are constrained when factorizing the original FB
into lifting structures, whereas the SBL-based BOFBs (SBLBOFBs) presented in [9] do not constrain them except in theinitial block. The SBL is better at lossy-to-lossless image coding because it uses fewer rounding operations in comparison
with the standard 1D separable lifting structure (SL). Furthermore, the two-dimensional (2D) non-separable lifting structure (NSL) for DWTs, NSL-based DWTs (NSL-DWTs), proposed in [10] performs even better at coding because it uses
fewer rounding operations than the SL.
Here, we propose a 2D non-separable block-lifting structure (NSBL) that is easily formulated from the SBL and NSL
methods. The NSBL can be regarded as an extension of theNSL because a NSBL with M = 2 is completely equivalentthem. The block-lifting structure for a 1D implementation
is called “SBL” to distinguish it from the “NSBL” proposedin this paper. When M = 2, they will also be called “SL” and“NSL”.
2.2. SBL-BOFBs
Fig. 1. Block-lifting structures (black and white circles meanadders and rounding operations, respectively).
to a NSL. We apply the NSBL to M -channel BOFBs, NSBLbased BOFBs (NSBL-BOFBs), and show that the BOFBs perform better at lossy-to-lossless coding than the conventional
SBL-BOFBs do because their rounding error is reduced bymerging many rounding operations.
Notations: A classification of lifting structures is shownin Table. 1. Im , 0, det(·), and diag(· · · ) denote an m ×
m identity matrix, null matrix, determinant of a matrix, and(block) diagonal matrix, respectively. Im is simply expressedby I if its size is clear. Indexes x, y, w, and 2d in the matrices mean to operate horizontally, vertically, horizontally orvertically, and horizontally and vertically, respectively.

We factorized the BOFBs composed of building blocks with
McMillan degree γk , where γk = M/2 for simplicity, intothe SBL in [9] as1∏

{Ek (z)}G0(1)][][I UkI −UkI
Λ(z)0 I0I
Lk]
0,IE(z) =k=K−1

where[Ek (z) =I−Lk0I][

Λ(z) = diag{I, z −1 I}, and Lk and Uk are arbitrary M/2 ×M/2 matrices if paraunitariness is not required. In addition,
the first block G0 is constrained to be det(G0 ) = ±n (n ∈N) for the purpose of making a lifting factorization. To improve coding performance, Eq. (1) can be rewritten as

2. REVIEW AND DEFINITIONS
E(z) = WK (z)2.1. Block-Lifting Structure1∏{Λ(z)Wk (z)}G0 ,

(2)

k=K−1

We proposed the block-lifting structure [9], which is a specialclass of standard lifting structure [5], as shown in Fig. 1. It
is good for lossy-to-lossless image coding because it reduces
the rounding error by merging many rounding operations. InFig. 1, the analysis 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 + R(L(z)xi ),yi = xi + R(U(z)yj )zi = yi − R(U(z)yj ) = xi , zj = yj − R(L(z)yi ) = xj
where R(·) denotes a rounding operation. In these cases, thematrices and their inverse matrices are expressed by
[ ]
[ ]
[ ]
[ ] [ ]
yixi
ziyx
−1
= W(z),= W (z) i = iyjxj
zj
yj
xj
−1
where W(z) = BU BL , W−1 (z) = B−1
L BU ,[][]I U(z)I −U(z)
BU =, B−1=U0I0I[][]I0I0
BL =, B−1=.
LL(z) I−L(z) I

where[I Ûk (z)Wk (z) =0 I][][]
I 0I0, WK (z) =,−LK−1 IL̂k (z) IÛk (z) = (z −1 − 1)Uk , and L̂k (z) = L1 (k = 1) or Lk −Lk−1 (otherwise). In comparison with the SBL-BOFBs in Eq.
(1), the SBL-BOFBs in Eq. (2) are more effective at lossy-tolossless image coding because they reduce the rounding error
by merging more rounding operations.
2.3. NSL-DWTs
9/7-tap and 5/3-tap SL-based DWTs (9/7-SL-DWT and 5/3SL-DWT) [3] are used in the JPEG 2000 lossy and losslessmodes, respectively. Let EW (z) be a polyphase matrix ofSL-DWTs, expressed as0∏

EW (z) = diag{s, s−1 }wk (z)

k=N −1

where[Note that the rounding operations are actually implemented
even if the lifting matrix expression omits the notation of292

wk (z) =1 uk (z)
01][]
10.
lk (z) 1(3)

If an image is 2D-transformed by the NSL-DWT polyphasematrix E2dW,k (z2d ) in Eq. (3), one can write[ TYLL]TT
YHH[ T= E2dW,k (z2d ) XLL

TYHL

TYLH

TXHL

TXLH

TXHH]T

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, and0∏

2−2E2d}W,k (z2d ) = diag{s , 1, 1, sFig. 2. 2D implementation of SBL (black and white circles

wk2d (z2d ).

mean adders and rounding operations, respectively).

k=N −1The 2D implementation wk2d (z2d ) in E2d
W (z2d ) is represented
as [10][]][1 uxk (zx ) uyk (zy ) −u2dk (z2d )wk2d (z2d ) =0I3[x]T
Tlk (zx )lky (zy )T01
I2
× 0 [] 00 uyk (zy )T uxk (zx )T1][I30[]. (4)× 2d
lk (z2d ) lky (zy ) lkx (zx ) 1
The NSL is also more effective at lossy-to-lossless image coding than the SL is because it uses fewer rounding operations.
3. NSBL-BOFBS
3.1. Derivation of NSBL
We introduce NSBL in this subsection.
Theorem: Consider an image that has been 2D-transformedby the set of lower and upper block-lifting matrices in Fig. 1
as follows (Fig. 2):[ TYLL]TT
YHH[= W2d (z2d ) XTLL XTHL

T
YHL

T
YLH

XTLH

XTHH

2d2d
W2d (z2d ) = W2d2 (z2d )W1 (z2d )W0 (z2d )[]I3M/20[](z)=W2d2d0
L2d (z2d ) Ly (zy ) Lx (zx ) I[ x]TL (zx )T Ly (zy )TI0IMW2d1 (z2d ) = 0 [] 00 Uy (zy )T Ux (zx )TI[[]]I Ux (zx ) Uy (zy ) −U2d (z2d )(z)=.
W2d2d20I3M/2
It is clear that the NSBL is an extension of the NSL in [10]because the NSBL with M = 2 in Eq. (6) is completely
equivalent to the NSL in Eq. (4).
Proof: When a matrix T = Tn−1 · · · T0 (n ∈ N) is applied to a 2D input signal x in the horizontal and vertical directions, the output signal y is expressed as [11]]T[] [ y]Wx (zx )0W (zy )0PPxy0W (zx )0W (zy )
I 0 0 0
0 0 I 0
P=0 I 0 0 ,0 0 0 I

293

(7)This Eq. (7) means that the 2D implementation of Tk is performed after that of Tk−1 (1 ≤ k ≤ n − 1), i.e., the two SBLwmatrices Bw
L (zw ) and BU (zw ) in Eq. (5) can be operated
separately. The resulting representation of W2d (z2d ) is

W2d (z2d ) =w
and Ww (zw ) = Bw
U (zw )BL (zw ). Also, XLL , XHL , XLH ,and XHH are the top-left, top-right, bottom-left, and bottomright M/2×M/2 blocks of an M ×M image, and YLL , YHL ,YLH , and YHH are their respective output blocks. W2d (z2d )

(6)

where

y = TxTT = Tn−1 · · · T0 xTT0 · · · TTn−1 .

(5)wherein Eq. (5) can be factorized into three NSBL matrices, asfollows (Fig. 3):

2dW2d (z2d ) = B2dU (z2d )BL (z2d )

(8)

where
[ x] [ y]BL (zx )
0BL (zy )0PP0
BxL (zx )0
ByL (zy )I000
 Lx (zx )
I00

=
 Ly (zy )0I0
L2d (z2d ) Ly (zy ) Lx (zx ) I

B2dL (z2d ) =[] [ y]BxU (zx )0
BU (zy )0P
Pyx0
BU (zx )0
BU (zy )I Ux (zx ) Uy (zy ) U2d (z2d )0I0
Uy (zy ) .
=00IUx (zx ) 000I

B2dU (z2d ) =Since rounding operations will have inevitably be generated
in each process of the matrices, as described in Section 2.1,2dwe separate each of B2dL (z2d ) and BU (z2d ) into two NSBLmatrices:
2d2d
B2dL (z2d ) = BL1 (z2d )BL0 (z2d )

(9)

2d2d
B2dU (z2d ) = BU 1 (z2d )BU 0 (z2d )(10)where[]
I3M/20[]B2d(z)=L0 2dL2d (z2d ) Ly (zy ) Lx (zx ) I[]]T[I Lx (zx )T Ly (zy )T 02dBL1 (z2d ) =0I3M/2]T[I3M/20[]B2d(z)=
U 0 2d0 Uy (zy )T Ux (zx )TI[[ x]]
y2dI U (zx ) U (zy ) −U (z2d )2dBU 1 (z2d ) =.
0I3M/2

Consequently, W2d (z2d ) is expressed as
2d2d2dW2d (z2d ) = B2dU 1 (z2d ) BU 0 (z2d )BL1 (z2d ) BL0 (z2d )|{z}
can be merged

from Eqs. (8)-(10). The resulting equation is completely thesame as Eq. (6).
□Here, we will apply the NSBL in Eq. (6) to the conventional
SBL-BOFBs in Eq. (2). Let E2d (z2d ) be a 2D separable
polyphase matrix based on a 1D separable polyphase matrix
E(z) in Eq. (2). Since the 2D implementation of the separable block transform allows us to change the order in which theblocks are operated on, the polyphase matrix E2d (z2d ) can be
expressed as1∏{ 2d}
Λ (z2d )Wk2d (z2d ) G2d0
k=K−1whereWk2d (z2d ) =L-LT [4], (B) 5/3-NSL-DWT [10], (C-D) 8 × 16 and 8 × 24
SBL-BOFBs [9], and (E-F) 8 × 16 and 8 × 24 NSBL-BOFBs.
Images
(A)
(B)
(C)
(D)
(E)
(F)
Barbara 4.81 4.86 4.79 4.78 4.76 4.75
Boat
5.13 5.09 5.09 5.11 5.08 5.09
Elaine5.17 5.11 5.06 5.05 5.05 5.03
Finger
5.71 5.83 5.66 5.65 5.65 5.64
Table 3. Lossy image coding results (PSNR [dB]): (A) 4 × 8

L-LT [4], (B) 9/7-NSL-DWT [10], (C-D) 8 × 16 and 8 × 24
SBL-BOFBs [9], and (E-F) 8 × 16 and 8 × 24 NSBL-BOFBs.
[bpp]
(A)
(B)
(C)
(D)
(E)
(F)
Barbara0.25 26.85 27.24 28.04 28.64 28.05 28.65
0.50 30.43 30.46 31.63 32.18 31.67 32.20
1.00 35.05 34.85 35.88 36.26 35.94 36.38
Boat
0.25 27.62 28.45 28.26 28.62 28.25 28.63
0.50 30.87 31.38 31.35 31.61 31.36 31.63
1.00 34.31 34.48 34.66 34.85 34.70 34.91
Elaine0.25 30.81 31.50 31.34 31.56 31.36 31.59
0.50 32.47 32.93 33.07 32.98 33.10 33.08
1.00 34.22 34.61 35.06 35.24 35.11 35.36
Finger
0.25 22.96 23.49 23.52 23.86 23.51 23.86
0.50 25.56 25.98 26.43 26.93 26.43 26.95
1.00 29.01 29.07 30.06 30.78 30.07 30.81[3.2. Application to BOFBs

2dE2d (z2d ) = WK
(z2d )

Table 2. Lossless image coding results (LBR [bpp]): (A) 4×8

2dWK(z2d ) =[]]TI L̂xK (zx )T L̂yK (zy )T 00
I3M/2[]
I3M/20[]×,yxIL̂2dK (z2d ) L̂K (zy ) L̂K (zx )−1and Λ2d (z2d ) = diag{I, zx−1 I, zy−1 I, z2dI}. As is donein [9], we use the single-row elementary reversible matrix(SERM) presented in [6] for each initial block Gw
0 , where.
any other SL factorization can be applied to Gw
04. EXPERIMENTAL RESULTS[[]]
I Ûxk (zx ) Ûyk (zy ) −Û2dk (z2d )0I3M/2[ x]TTI0L̂k (zx )L̂yk (zy )TIM× 0 [] 0yTxT0 Ûk (zy )IÛk (zx )[]I3M/20]
× [ 2dL̂k (z2d ) L̂yk (zy ) L̂xk (zx ) I

By following the method presented in [9], 8 × 16 and 8 × 24
BOFBs with order-1 building blocks were designed. They
were compared in terms of the lossless bitrate (LBR) [bpp]in lossless image coding and the peak signal-to-noise ratio(PSNR) [dB] in lossy image coding. To evaluate transformperformance fairly, we employed 3, 6, and 2-level decompositions, respectively, on the L-LT [4], NSL-DWTs without
adaptive directionalities [10], and eight-channel BOFBs. TheSBL-BOFBs had the same transfer function as the proposed294

Fig. 3. NSBL (black and white circles mean adders and rounding operations, respectively).

FBs. The image set included several 512 × 512 grayscale test
images, such as Barbara. A quadtree-based embedded image coder EZW-IP [12] was used to encode the transformed
images. A periodic extension was used in the image boundary processing of the BOFBs, whereas the extensions used inJPEG XR and JPEG 2000 were used as the respective boundary processing of the L-LT and NSL-DWTs.
Tables 2 and 3 show lossless and lossy image coding
results. Although NSL-DWTs sometimes performed betteron images with many low frequency components, overall,
the NSBL-BOFBs outperformed the conventional methods.
These results are considered to be due to the merging (reducing) of many rounding operations in the NSBL-BOFBs.
Comparing Figs. 2 and 3, it is clear that the number of rounding operations of the NSBL is the almost half that of theSBL.
5. CONCLUSION
We devised a NSBL and applied it to M -channel BOFBs inlossy-to-lossless image coding. The NSBL is easily formulated from the SBL and NSL methods and can be regarded as
an extension of the NSL because it is completely equivalent
to a NSL when M = 2. A lossy-to-lossless image coding experiment confirmed the improvements that could be had withNSBL.
REFERENCES[1] P. P. Vaidyanathan, Multirate Systems and Filter Banks,Englewood Cliffs, NJ: Prentice Hall, 1992.
[2] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms, Academic Press, 1990.
[3] I. Daubechies and W. Sweldens, “Factoring wavelet
transforms into lifting steps,” J. Fourier Anal. Appl.,
vol. 4, no. 3, pp. 247–269, 1998.
[4] C. Tu, S. Srinivasan, G. J. Sullivan, S. Regunathan, andH. S. Malvar, “Low-complexity hierarchical lapped
transform for lossy-to-lossless image coding in JPEG

295

XR/HD Photo,” in Proc. of SPIE, San Diego, CA, Aug.
2008, vol. 7073, pp. 1–12.
[5] W. Sweldens, “The lifting scheme: A custom-designconstruction of biorthogonal wavelets,” Appl. Comput.
Harmon. Anal., vol. 3, no. 2, pp. 186–200, Apr. 1996.
[6] P. Hao and Q. Shi, “Matrix factorizations for reversible
integer mapping,” IEEE Trans. Signal Process., vol. 49,no. 10, pp. 2314–2324, Oct. 2001.
[7] Y. J. Chen and K. S. Amaratunga, “M -channel lifting
factorization of perfect reconstruction filter banks andreversible M -band wavelet transforms,” IEEE Trans.
Circuits Syst. II, vol. 50, no. 12, pp. 963–976, Dec.
2003.
[8] L. Wang, L. Jiao, J. Wu, G. Shi, and Y. Gong, “Lossyto-lossless image compression based on multiplier-lessreversible integer time domain lapped transform,” Signal Process. Image Commun., vol. 25, no. 8, pp. 622–632, Sep. 2010.
[9] T. Suzuki, M. Ikehara, and T. Q. Nguyen, “Generalizedblock-lifting factorization of M -channel biorthogonal
filter banks for lossy-to-lossless image coding,” IEEE
Trans. Image Process., vol. 21, no. 7, pp. 3220–3228,
July 2012.
[10] T. Yoshida, T. Suzuki, S. Kyochi, and M. Ikehara, “Twodimensional non-separable adaptive directional lifting
structure of discrete wavelet transform,” IEICE Trans.
Fundamentals., vol. E94-A, no. 10, pp. 1920–1927,Oct. 2011.
[11] T. Suzuki, S. Kyochi, Y. Tanaka, M. Ikehara, andH. Aso, “Multiplierless lifting based FFT via fast Hartley transform,” in Proc. of ICASSP’13, Vancouver,Canada, May 2013, pp. 5603–5607.
[12] 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.