2011 18th IEEE International Conference on Image Processing

BLOCK-LIFTING FACTORIZATION OF M -CHANNEL BIORTHOGONAL FILTER BANKSWITH AN ARBITRARY MCMILLAN DEGREETaizo Suzuki1 , Masaaki Ikehara2 , and Truong Q. Nguyen3
1: College of Eng., Nihon University, Koriyama, Fukushima 963-8642, Japan
2: EEE Dept., Keio University, Yokohama, Kanagawa 223-8522, Japan
3: ECE Dept., University of California, San Diego, La Jolla, CA 92093, USA
ABSTRACT
A block-lifting factorization of M -channel biorthogonal filter banks(BOFBs) with degree-N building blocks and even/odd M (M ≥ 2)for lossless-to-lossy image coding is introduced in this paper. In theprevious work, block-lifting factorization of M -channel BOFBs has
been proposed. Since the block-lifting structure does not require therestriction of determinant of each building block, it achieves better coding performance than the conventional methods. However,the factorization is not completed because McMillan degree in eachbuilding block is fixed M/2 (M is even). This paper proposes a
block-lifting factorization without restrictions for a fixed degree andeven block size. Our proposal is validated by several filter designs
and their application to lossless-to-lossy image coding.
Index Terms— Biorthogonal filter banks (BOFBs), blocklifting, degree-N building block, lossless-to-lossy image coding
1. INTRODUCTION
For a few decades, filter bank (FB) has been considered one of themost efficient techniques to compress multimedia signals [1]. FBs
are adopted to audio, image, and video coding standards as JPEG [2]and MPEG [3]. Fig. 1 illustrates an uniform maximally decimatedM -channel (M ≥ 2) FB where E(z) and R(z) are the type-I and-II polyphase matrices, respectively. If perfect reconstruction (PR) isachieved, the synthesis polyphase matrix R(z) can be chosen as theinverse of E(z), i.e., R(z) = E† (z −1 ). The obtained FB is called abiorthogonal FB (BOFB).
On the other hand, Sweldens has introduced lifting factorization of discrete wavelet transforms (DWTs) in [4]. When a rounding
operation is performed before addition, this lifting step is integerto-integer transform. Therefore, FBs factorized into cascading lifting structures can be regarded as integer-to-integer transforms. Theproblem is how to factorize these FBs into pure lifting structure withfewer constraints. 2-channel lifting based 5/3-tap DWT and an 4 × 8
hierarchical lapped biorthogonal transform (HLBT) has been proposed and adopted to JPEG2000 lossless compression standard [5]and JPEG XR [6], respectively. Also, several lifting factorizations
have been proposed [7–10]. However, they still have a strong restriction, i.e., paraunitary, fixed determinant or symmetry. Then, the authors have proposed a block-lifting structure which does NOT need
the above restrictions [11].
This work was supported in part by a Grant-in-Aid for the Japan Society for the Promotion of Science (JSPS) Fellows and a Grant-in-Aidfor the Global Center of Excellence (G-COE) for High-Level Global Cooperation for Leading-Edge Platform on Access Spaces from the Ministry of Education, Culture, Sport, Science, and Technology in Japan.
Email: taizo@ee.ce.nihon-u.ac.jp

978-1-4577-1302-6/11/$26.00 ©2011 IEEE249

Fig. 1. M -band filter bank: (a) regular and (b) polyphase structure.
In this paper, a block-lifting factorization for BOFBs withdegree-N building blocks and even/odd M for lossless-to-lossy image coding is proposed. Although McMillan degree in each building
block can be set freely, the previous work [11] limits the degree toM/2 (M is even). This paper considers the general case without
restriction on the degree or block size. Several designs using the proposed structure is implemented in the application of lossless-to-lossy
image coding.
Notations: IM , MT , and M† denote an M ×M identity matrix,
a transpose of a matrix M, and a conjugate transopose of a matrix
M respectively.
2. REVIEW
2.1. Lattice Structure
A class of causal M -channel maximally decimated FIR BOFBs withfilter length KM (K ∈ N) are factorized as follows [11]:E(z) = EK−1 (z)EK−2 (z) · · · E1 (z)X0(1)Ek (z) = Xk Λk (z)X−1k
Λk (z) = diag{Iδk , z −1 Iγk }where Xk (0 ≤ k ≤ K − 1) is an M × M nonsingular matrixand δk = M − γk , respectively. γk is called the McMillan degreeof Ek (z). When γk = N , Ek (z)s are called degree-N building
blocks. Especially, when γk = M/2 (M is even) or (M − 1)/2 (Mis odd), Ek (z)s are called order-1 building blocks. Hence, order-1
structure is considered as a subset of degree-N structure. This paper
proposes block-lifting factorization of degree-N structure which ismore general case than order-1 structure in the previous paper [11].
Hereafter, Λk (z) with γk = N is written as Λ(z).
Moreover, let Xk and X−1k be][[]××× uk0−1
and Xk = T
Xk =T× uk1
vk0 vk1

2011 18th IEEE International Conference on Image Processing

where S̄k and T̄k are γk × δk matrices. First, Sk is multiplied fromthe right side of Ek (z).
[]S (z) Skb (z)Ek (z)Sk = ka, Sk (z)Skc (z) Skd (z)whereTTSka (z) = Iδk + (z −1 − 1)uk0 vk0+ (z −1 − 1)uk0 vk1
S̄
TSkb (z) = (z −1 − 1)uk0 vk1
TT
Skc (z) = (z −1 − 1)uk1 vk0+ (Iγk + (z −1 − 1)uk1 vk1)S̄Fig. 2. A block-lifting structure (white circles represent roundingoperations).

TSkd (z) = Iγk + (z −1 − 1)uk1 vk1

Next, Tk is multiplied from the left side of Sk (z). Finally, the product is represented as follows:
where uk0 and vk0 are δk ×γk matrices, and uk1 and vk1 are γk ×γksquare matrices, respectively. Since Xk X−1= IM , a degree-Nkbuilding block Ek (z) is finally represented as
Ek (z) = IM − Uk VkT + z −1 Uk VkT
where[][]
uk0
vk0
Uk =, Vk =
uk1
vk1

and

VkT Uk = Iγk .

(2)

Tk Sk (z)[Ska (z)Skb (z)=T̄k Ska (z) + Skc (z)yu = xu , yl = xl + round[Ωxu ]zu = yu , zl = yl − round[Ωxu ]It is clear that the reconstructed signals zu and zl are exactly thesame value as xu and xl . Therefore, block-lifting structure would
be efficient for designing BOFBs for lossless-to-lossy image coding
due to having fewer number of rounding operations.
3. BLOCK-LIFTING FACTORIZATION OF BOFBS
3.1. Building Blocks
In this section, we introduce a block-lifting factorization of degree-Nbuilding blocks in BOFB according to [11]. We start with the factorization of Ek (z) into a block-lifting structure. Assume that two
block lifting matrices are multiplied from the left and right sides ofEk (z). If they can be represented as a block-lifting structure, Ek (z)will be factorized into the product of some block-lifting matrices.
Let Sk and Tk be M × M block-lifting matrices as]][[00IδkIδkand Tk =Sk =T̄k IγkS̄k Iγk

250

T̄k Skb (z) + Skd (z), Tk (z)As mentioned above, if the product Tk (z) has a pure block-lifting
structure, Ek (z) can be factorized into a number of block-lifting−1matrices such as Ek (z) = T−1
k Tk (z)Sk .
The conditions that Tk (z) has a block-lifting structure are obtained as follows:1

2.2. Block-Lifting Structure
The lifting structure is a special factorization of lattice structure. It
is a cascade of elementary matrices which are identity matrices withone single nonzero off-diagonal element [4]. Block-lifting structure
is a more efficient lifting structure [11]. A block-lifting structure isshown in Fig. 2. If M = δk +γk (δk , γk ≤ 1), xu , xl , yu , yl , zu , zl
and Ω are an δk × 1 analysis input signal vector, an γk × 1 analysis
input signal vector, an δk × 1 analysis output signal vector (synthesis
input signal vector), an γk ×1 analysis output signal vector (synthesis
input signal vector), an δk × 1 synthesis output signal vector, anγk × 1 synthesis output signal vector and an γk × δk lifting block,respectively. The lifting structure can be expressed as follows:]

Ska (z) = Iδk(3)T̄k Ska (z) + Skc (z) = 0(4)

T̄k Skb (z) + Skd (z) = Iγk .

(5)

From (3) and (4), the condition of S̄k and T̄k are obtained as−T TS̄k = −vk1
vk0−T Tand T̄k = vk1
vk0 .

TT
Under the conditions (6) and vk0
uk0 + vk1
uk1

(6)

= Iγk in (2), (5)can be rewritten as
T̄k Skb (z) + Skd (z) = z −1 Iγk .
Consequently, Tk (z) is formulated as[]TI(z −1 − 1)uk0 vk1
Tk Ek (z)Sk = δk.
−10z Iγk
Therefore, a degree-N building block of BOFB Ek (z) = IM −Uk VkT + z −1 Uk VkT in (1) can be factorized into][][TIδk0Iδk uk0 vk1
Ek (z) =Λk (z)−T T0I γk−vk1 vk0 Iγk[][]TIδk0I−uk0 vk1.
(7)× δk−T T0Iγ kvk1vk0 Iγk
The design parameters of degree-N building block Ek (z) are uti−T T
vk0 andlized for uk0 , vk0 and vk1 in (2). For simplicity, since vk1
Tuk0 vk1 can be any γk × δk and δk × γk matrices, respectively, (7)can be represented by]][][][[−Uk Iδk 0IIδk Uk0I
Λk (z) δk
Ek (z) = δk
Lk Iγk0 I γk0 Iγk−Lk Iγkwhere Lk and Uk are γk ×δk and δk ×γk any matrices, respectively,
as shown in Fig. 3. The number of design parameters is 2δk γk . Notethat the restriction det(Ek (z)) = ±1, which has been conventionally required for lifting factorization, is not required by using theproposed block-lifting structure. As a result, more efficient FBs canbe designed comparing to the conventional lifting based FBs.
1 Strictly speaking, to obtain an integer-to-integer transform, (3) and (5)do not have to be I. z −n I is also allowed.

2011 18th IEEE International Conference on Image Processing

Fig. 3. A block-lifting structure of degree-N building blocks ofBOFB (white circles, black circles and white triangles represent
rounding, adder and −1 operations, respectively).

Fig. 5. Frequency responses of the proposed BOFBs (N = 2): (top)
5×15 analysis and synthesis, (bottom) 8×24 analysis and synthesis.

4. DESIGN AND EXPERIMENTAL RESULTS
4.1. Design Examples
Fig. 4. The parameterization of the initial block X0 .

3.2. Initial BlockIn FB theory, the regularity is an important property for image compression. Therefore, we investigated lattice structures of FB with one
degree of regularity. This paper uses initial block X0 with structural(1, 1)-regularity as [12]]01diag{α0 , α1 , · · · , αM −1 }
0 XL
[]
10×
ΘM −1 ΘM −2 · · · Θ10 XR[X0 =In this paper, we present several design examples of the proposed
BOFBs. The cost function to design these FBs is a weighted linear
combination of the coding gain Ccdg and the stopband attenuationsof analysis and synthesis filters Cana,stpb and Csyn,stpb as follows[12]:∑Φ=(w1 Cana,stpb + w2 Csyn,stpb ) − w3 Ccdg
i,jThe weighting coefficients {w1 , w2 , w3 } have been set empirically. We optimized design parameters by cost function Φ usingfminunc.m in Optimization ToolBox of MATLAB. The proposed
method can design block-lifting based BOFBs even if M is odd orMcMillan degree is N as shown in Fig. 52 .

where XL and XR are (M − 1) × (M − 1) orthogonal matrices,and1(k = l ̸= 0 or j)√1 )(k= l = 0 or j)cos(arctank(k = 0 and l = j)
[Θj ]k,l = sin(arctan √1k )1
− sin(arctan √k ) (k = j and l = 0)0(otherwise)
as shown in Fig. 4.
Next, the initial block X0 must be factorized into lifting structures. However, since the proposed block-lifting factorization is
not applicable, we use the single-row elementary reversible matrix(SERM) structures in [9]. SERM factorization of X0 is implemented
by only M + 1 rounding operations if det(X0 ) = ±1. Sincedet(XL ) = det(XR ) = 1 is already satisfied, only D is restricted∏ −2 −1by αM −1 = M
to obtain the perfect lifting structures. Asi=0 αia result, X0 without the structural regularity is designed by M 2 − 1parameters. It means that only one parameter is restricted to implement whole lifting factorization of a BOFB.

251

4.2. Lossless-to-Lossy Image Coding
8 × 24 BOFBs with degree-2 and degree-4 [i.e. order-1] building
blocks are applied to lossless-to-lossy image coding. Based on theoptimized parameters, lifting coefficients are determined. Integerto-integer transform can be obtained by using a rounding operationat each lifting step. To evaluate transform performance fairly, awavelet-based coder EZW-IP [13] was used in the simulation. Also,
for image boundaries, the periodic extension was used in our proposals and [8], and the symmetric extension was used in 9/7 and 5/3-tap
DWTs.
Since the proposed FBs are integer-to-integer transforms, we canobtain lossless reconstructed images at high bitrate. Lossless coding
performance in lossless bitrate [bpp] is shown in Table 1. In Table 2,
we also compare the lossy coding results in peak signal-to-noise ratio (PSNR) [dB] at 0.25, 0.50 and 1.00 bit per pixel (bpp) for several
standard images. The results for the images contain rich textures
show the effectiveness of the proposed method. Fig. 6 illustrates
the comparison of the part of the enlarged images of Barbara. It
2 BLBOFBs in Fig. 5 were designed by considering only the coding gain
Ccdg .

2011 18th IEEE International Conference on Image Processing

Table 1. Comparison of lossless results (lossless bitrate [bpp]).
5/3-tap
4×88 × 24 BOFBs
ImagesDWT [5] HLBT [6] (N = 2) (N = 4)
Barbara
4.87
4.81
4.78
4.77
Boat
5.10
5.13
5.10
5.09
Elaine
5.11
5.17
5.07
5.04
Finger1
5.84
5.71
5.63
5.65
Finger2
5.60
5.42
5.37
5.37
Grass
6.06
6.05
6.04
6.05

Table 2. Comparison of lossy results (PSNR [dB]).
bitrate
9/7-tap
4×88 × 24 BOFBs[bpp]
DWT [5] HLBT [6] (N = 2) (N = 4)
Image: Barbara
0.25
27.28
26.85
27.94
28.67
0.50
30.55
30.43
31.60
32.23
1.00
35.16
35.05
36.01
36.41
Image: Finger1
0.25
23.52
22.96
23.56
23.85
0.50
26.02
25.56
26.67
26.95
1.00
29.15
29.01
30.55
30.81
Image: Grass
0.25
24.38
23.99
24.25
24.51
0.50
26.13
25.86
26.32
26.62
28.75
28.68
29.10
29.44
1.00

Fig. 6. Comparison of the part of the enlarged images of Barbara(bitrate: 0.25[bpp]): (top-left) 9/7-tap DWT (JPEG2000), (top-right)
4 × 8 HLBT (JPEG XR), (bottom-left) 8 × 24 BOFB (N = 2),(bottom-right) 8 × 24 BOFB (N = 4).

is obvious that the proposed FB achieves comparable or even better performance on perceptual visual quality of reconstructed image
against the conventional methods. Our FBs show the effectivenessfor the images with high frequency components in both lossless andlossy image coding.
5. CONCLUSION
In this paper, we introduced a block-lifting structure of M -channel
biorthogonal filter banks (BOFBs) with degree-N building blocks.
Since block-lifting structure with rounding operations can implement integer-to-integer transform, they can be easily used forlossless-to-lossy image coding scenario. Also, block-lifting structure of each building block of BOFBs does NOT require the restriction such as paraunitary, fixed determinant or symmetry. In addition,although the previous work is restricted to order-1 structure andeven M , the proposed method can achieve degree-N structure andeven/odd M . As a result, the proposed method showed excellent
coding performance due to a more efficient filter design for losslessto-lossy image coding. The reduction of computational cost is afuture work.
6. REFERENCES[1] P. P. Vaidyanathan, Multirate Systems and Filter Banks, Englewood Cliffs, NJ: Prentice Hall, 1992.
[2] ISO/IEC 10918-1, Information technology - Digital compression and coding of continuous-tone still images Requirements
and Guidelines.
[3] ISO/IEC 14496-10, Information technology - Coding of audiovisual objects - Part 10: Advanced Video Coding.

252[4] W. Sweldens, “The lifting scheme: A new philosophy inbiorthogonal wavelet constructions,” in Proc. of SPIE 2569,
1995.
[5] ISO/IEC 15444-1, Information technology - JPEG 2000 image
coding system: Core coding system.
[6] ISO/IEC 29199-2, JPEG XR image coding system - Part 2:Image coding specification.
[7] Y. J. Chen and K. S. Amaratunga, “M -channel lifting factorization of perfect reconstruction filter banks and reversible
M -band wavelet transforms,” IEEE Trans. Circuits Syst. II,
vol. 50, no. 12, pp. 963–976, Dec. 2003.
[8] T. Suzuki, Y. Tanaka, and M. Ikehara, “Lifting-based paraunitary filterbanks for lossy/lossless image coding,” in Proc. ofEUSIPCO’06, Florence, Italy, Sep. 2006.
[9] Y. She, P. Hao, and Y. Paker, “Matrix factorizations for parallel
integer transformation,” IEEE Trans. Signal Process., vol. 54,
no. 12, pp. 4675–4684, Dec. 2006.
[10] T. Suzuki and M. Ikehara, “Lifting factorization based onblock parallel system of M -channel perfect reconstruction filter banks,” in Proc. of EUSIPCO’09, Glasgow, Scotland, Aug.
2009, pp. 2245–2248.
[11] S. Iwamura, Y. Tanaka, and M. Ikehara, “An efficient lifting
structure of biorthogonal filter banks for lossless image coding,” in Proc. of ICIP’07, San Antonio, TX, Sep. 2007, pp.
433–436.
[12] T. Uto, T. Oka, and M. Ikehara, “M -channel nonlinear phasefilter banks in image compression: structure, design, and signalextension,” IEEE Trans. Signal Process., vol. 55, no. 4, pp.
1339–1351, Apr. 2007.
[13] 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.