17th European Signal Processing Conference (EUSIPCO 2009)

Glasgow, Scotland, August 24-28, 2009LIFTING FACTORIZATION BASED ON BLOCK PARALLEL SYSTEM OF
M-CHANNEL PERFECT RECONSTRUCTION FILTER BANKS
Taizo Suzuki and Masaaki Ikehara
Department of Electronics and Electrical Engineering, Keio University
Yokohama, Kanagawa 223-8522 Japan
Email: {suzuki, ikehara}@tkhm.elec.keio.ac.jp

x(n)

x(n)
z -1

2.1 Perfect Reconstruction Filter Bank (PRFB)
Fig. 1 shows an M-channel FB which consists of parallel analysis
filters Hk (z), synthesis filters Fk (z), decimaters and interpolators.
Fig. 2 illustrates its equivalent polyphase representation where E(z)and R(z) are the polyphase matrices, respectively. The polyphaserepresentation is formulated as follows [8]:[H0 (z) H1 (z) · · · HM−1 (z)]T = E(zM )e(z)T[F0 (z) F1 (z) · · · FM−1 (z)] = e(z)R(zM )© EURASIP, 2009

H1(z)

↓M

HM-1(z)

↓M

↑M

F0(z)

↑M

F1(z)

↑M

FM-1(z)

z -1

↓M

↓M

↑M

Processingz -1

2. REVIEW↓My(n)

Figure 1: An M-channel filter bank.

1. INTRODUCTION
Image coding has lossy and lossless mode. Lossy image coding
is adopted to Internet contents and mobile etc., and lossless image
coding is adopted to medical and art field etc. Then lossless andlossy compressed data are usually independent each other. For example, in the international standard JPEG [1], discrete cosine transform (DCT) [2] is applied to lossy image coding and DCM is applied to lossless image coding.
With the rapid development of Internet and multimedia technology, the unification of lossy and lossless compressed data isdemanded to obtain higher quality and compression ratio suchas JPEG2000 [3] with 9/7 and 5/3-tap discrete wavelet transform(DWT) for lossy and lossless image coding, respectively. Several
lifting-based filter banks (LBFBs) which are filter banks (FBs) withthe lifting structure [4] are widely researched for the unification oflossy and lossless data [5–7]. This coding is called lossless-to-lossy
image coding. However, they are not practical because [5, 6] can
not achieve good coding performance due to many rounding operations, and [7] may have wide dynamic range of lifting coefficients
due to inverse matrix.
In this paper, using the block parallel system of perfect reconstruction FBs (PRFBs) with an imposed condition, we can factorize
them into a novel lifting structure which is called the parallel lifting.
The every building blocks have more practical structure which consists of three block lifting matrices with same lifting coefficient matrix without an inverse operation. Finally, the validity of our structures is shown by applying them to lossless-to-lossy image coding.
Notations: I, MT and M[M] are an identity matrix, a transposeof a matrix M and an M × M matrix M, respectively.

H0(z)Processing

ABSTRACT
Several lifting-based filter banks (LBFBs) are proposed for losslessto-lossy image coding. However, the conventional methods can notachieve good coding performance due to many rounding operations,and they may have wide dynamic range of lifting coefficients due
to inverse matrix. This paper presents a more practical lifting factorization of M-channel perfect reconstruction filter bank (PRFB).
Using the block parallel system of PRFBs with an imposed condition, we can factorize them into a novel lifting structure which iscalled the parallel lifting. The validity of our structures is shown by
applying them to lossless-to-lossy image coding.
Index Terms — Perfect reconstruction filter bank (PRFB), blockparallel system, parallel lifting, lossless-to-lossy image coding.

E(z)

R(z)

↓M

↑M

↑M

z -1

z -1

z -1
y(n)

Figure 2: A polyphase structure of filter bank.
[]where e(z) = 1 z−1 · · · z−(M−1) .

If perfect reconstruction isachieved, the synthesis polyphase matrix R(z) can be chosen as theinverse of E(z). The obtained FB is called a perfect reconstruction
FB (PRFB). If ET (z−1 )E(z) = I and R(z) = ET (z−1 ), the FB belongs to a special class of PRFBs called a paraunitary FB (PUFB).
PRFB without PUFB is called a biorthogonal FB (BOFB).
Therefore, M-channel PRFBs can be implemented by the lattice
structure that consists of the product of the first and several building
blocks. In this paper, we assume that the filter length is MK(K ∈ N).
The polyphase matrix E(z) of the PRFB is expressed by [8]E(z) = WL ΛL (z) · · · W1 Λ1 (z)W0(1)where L = K − 1, Wk is arbitrary M × M nonsingular matrix andΛk (z) is expressed asΛk (z) =[ [M−γ ]]k0I.
0z−1 I[γk ]Although γk is arbitrary integer 1 ≤ γk < M, we set γk = M/2and Λ(z) , Λk (z) for simplicity when M is even. Fig. 3 showsa lattice structure of PRFB. When Wk is an orthogonal matrix,
Wk−1 = WkT , it is a PUFB.
2.2 Block Lifting Structure
Lifting structure [4] is researched widely. Since the structure
achieves integer-to-integer transform, lossless-to-lossy image coding can be realized. Fig. 4 shows a lifting structure. In Fig. 4,analysis input signals xi and x j , analysis output and synthesis input signals yi and y j , synthesis output signals zi and z j and a lifting2245

Output Signals

Input Signals

Output Signals

Input Signals
Figure 3: A lattice strcture of PRFB.

Figure 6: A time-series processing of lattice strcture of PRFB.

Figure 4: Lifting structure (White circles: rounding operations.)Xk =→zi = yi − R[Ty j ] = xi
zj = yj = xj

where R[.] is rounding operation.
In other hand, the block lifting structure [7] is known as an efficient one. The structure achieves higher compression ratio because
it can merge many rounding operations. Fig. 5(a) shows a block
lifting structure before merging the rounding operations, and Fig.
5(b) shows one afrer merged them. It is clear that the number ofrounding operations is reduced from N 2 to N when the size of thelifting coefficient matrix T is N × N. In Fig. 5(b), analysis input
signals vector xi and x j , analysis output and synthesis input signals
vector yi and y j , synthesis output signals vector zi and z j and alifting coefficient matrix T are represented asyi = xi + R[Tx j ]yj = xj→(2)

A system in (2) is called the block parallel system. Then, if Xk in(2) can be factorized into lifting structure, we can achieve losslessto-lossy image coding. In conclusion, a method of approach forlossless-to-lossy image coding is boiled down to how to factorize
Xk into lifting structure.

coefficient T are represented asyi = xi + R[T x j ]yj = xj

[]
Wk 0.
0 Wk

3.2 Parallel Lifting Factorization
First, let define X̃k as
[]
[]
0 I
0 WkX̃k ,
Xk =.
I 0
Wk 0

(3)

Second, the block lifting matrix is multiplied from the right sides of(3) as][] [I0I Wk.
(4)=X̃kWk 0
Wk−1 I
Next, the other block lifting matrix is multiplied from the right sidesof (4) as[][] []
I0I Wk I −Wk=.
(5)
Wk 00I
Wk −Wk2

zi = yi − R[Ty j ] = xi
zj = yj = xj

where R[.] is rounding operation.
3. PARALLEL LIFTING-BASED PERFECTRECONSTRUCTION FILTER BANK (PLPRFB)In this section, we propose an efficient lifting structure using theblock parallel systemof PRFB.
3.1 Block Parallel System
First, the lattice structure can be expressed as a time-series processing such as Fig. 6 [9]. Two building blocks Wk framed by dashedline in Fig. 6 are expressed as

Therefore, the block lifting matrix which is same as (4) is multiplied
from the right sides of (5) as[][] []
I0I0I0=.
(6)−1
2
2
Wk −Wk Wk I0 −Wk
Consequentry, X̃k in (3) can be factorized into the lifting structuresusing (4)-(6) as(a)(b)

Figure 5: Block lifting structure: (a)before merging, (b)after merging rounding operations. (White circles: rounding operations.)2246

3.3 Merging Rounding Operations
Many rounding operations can be merged because the lifting coefficient of PLPRFB can be expressed as a matrix (block). This is anefficient for lossless image coding [7]. Table 2 shows the number ofrounding operations when the numbers are in one system. Although
the numbers in [7] are the least, PLPRFB can reduce it to the almostsame number.
(b)

(a)

4. RESULTS

Figure 7: A block parallel system of PRFB: (a)basic structure,(b)parallel lifting structure. (White circles: rounding operations.)

Table 1: Comparison of the number of free parameters.
[6][7]
PLPUFB PLBOFB
8×16 44963272
8×24 60 144
48108[I00 −Wk2][I0−Wk−1 I][I Wk0 I]
I0.
−Wk−1 I

where w1 , w2 and w3 are weighting factors. We designed only 8×24
PLPUFB and PLBOFB because its filter size have better performance than the other size. Their frequency responses are depicted
in Fig. 8.
4.2 Application to Lossless-to-Lossy Image Coding][(7)

However, (7) is not the complete lifting structure due to Wk2 .
Let impose a condition Wk−1 = Wk for the completion of lifting
factorization of PRFB. In case of PUFB, Wk must be a symmetricorthogonal matrix where Wk−1 = WkT = Wk as follows [10]:][][][ TUk,0 0Uk,0 0Ck Sk
Wk =0 Uk,1 Sk −Ck
0 UTk,1In this paper, we focus on image coding applications. The cost function to design the FBs is a weighted linear combination of coding
gain CCG , stopband attenuation CST OP and DC leakage CDC [8].
C = −w1CCG + w2CST OP + w3CDC

Table 2: Comparison of the number of merged rounding operations.
[6][7]
PLPUFB
PLBOFB
8×16 132 → 62 112 → 20 192 → 24 192 → 24
8×24 180 → 82 176 → 28 288 → 36 288 → 36X̃k =4.1 Filter Bank Design(8)

where Uk,0 and Uk,1 are M/2 × M/2 arbitrary orthogonal matrices,[Ck ]ii = cos αki and [Sk ]ii = sin αki (0 ≤ i < M/2), respectively. In
case of BOFB, (8) is extended as follows:][][] [ −1Vk,0 0Vk,0 0Ck Sk
Wk =(9)−10 Vk,1 Sk −Ck
0 Vk,1
where Vk,0 and Vk,1 are M/2 × M/2 arbitrary nonsingular matrix,[Ck ]ii = cos αki and [Sk ]ii = sin αki (0 ≤ i < M/2), respectively.
As a result, Xk in (2) can be factorized into the complete block
lifting structure such as[][][][]0 −I
I
0 I WkI0Xk =.
(10)
I 0 −Wk I 0 I−Wk I
The block parallel system Xk and its lifting factorization in (10) areshown in Fig. 7(a) and (b).
PRFB using (10) is called parallel lifting-based PRFB (PLPRFB). Especially, PLPRFB based on (8) and (9) are called parallel lifting-based PUFB (PLPUFB) and parallel lifting-based BOFB
(PLBOFB). Table 1 shows the comparison of the number of freeparameters (PLPUFB: KM 2 /4, PLBOFB: KM(M + 1)/2).
In (10), it is clear that the each building block Xk is constructedby using three block lifting matrices with same lifting coefficientmatrix without an inverse operation. This is a practical structure.

In this subsection, our PLPRFBs are applied to lossless image coding by using the rounding operations in the each lifting structure.
We adopted the periodic extension at the image boundaries andEZW-IP as a wavelet based coder [11]. The lossless image coding
results are compared byLossless bit rate[bpp] =Total number of bits[bit]Total number of pixels[pixel]

which indicate how the FBs efficiently reduce the spatial redundancy of the input signals.
If lossy compressed data is required, it can be achieved by interrupting the lossless bit stream obtained. The lossy image coding
results are compared by
PSNR[dB] = 10 log102552
MSE

where MSE is the mean squared error. Table 3 and Fig. 9 show thecomparison of lossless bits rate and PSNRs between our PLPRFBs
and the conventional methods and lossy compressed images of ‘Barbara’ when bit rate is 0.25[bpp]. 5/3-tap DWT [3], 8×24 PUFB [6]and 8×24 BOFB [7] are selected as the conventional method forlossless image coding. Similarly, 9/7-tap discrete wavelet transform(DWT) [3], 8×24 PUFB [6] and 8×24 BOFB [7] are selected as theconventional method for lossy image coding. Our PLPRFBs present
same or better performance than the conventional FBs in both lossless and lossy image coding.
5. CONCLUSION
In this paper, we proposed a more practical lifting factorization ofM-channel perfect reconstruction filter banks (PRFBs) using theblock parallel system. This PRFBs are called parallel lifting-based
PRFBs (PLPRFBs). The every building blocks can be factorized
into the three block lifting matrix with same lifting coefficient matrix without an inverse operation. Although the condition for lifting factorization is imposed, our PLPRFBs are comparable or evenbetter performance in comparison with the conventional FBs in
lossless-to-lossy image coding.
Acknowledgment
This work is supported in part by a Grant-in-Aid for the Global Center of Excellence for High-Level Global Cooperation for LeadingEdge Platform on Access Spaces from the Ministry of Education,Culture, Sport, Science, and Technology in Japan.

2247

0-5-10-10-10-15-20-25-30-35-40

00.2

0.4

0.6

0.8

1

Magnitude Response [dB]0-5Magnitude Response [dB]

Magnitude Response [dB]0-5-15-20-25-30-35-40

00.2

0.4

0.6

0.8

1-15-20-25-30-35-40

0

0.2

0.4

0.6

Normalized Frequency

Normalized Frequency

Normalized Frequency

(a)

(b)

(c)

0.8

1Figure 8: Frequency responses of PLPRFBs: (a)8×24 PLPUFB, (b)8×24 PLBOFB(analysis), (c)8×24 PLBOFB(synthesis).

Table 3: Comparison of lossless-to-lossy image coding (Lossless
bit rate[bpp] and PSNR[dB]).
Lossless
PSNR[dB]FILTERbit rate
1.00
0.50
0.25
[bpp]
[bpp] [bpp] [bpp]‘Barbara’
5/3 and 9/7-tap DWT
4.87
34.88 30.49 27.25
4.82
36.07 31.98 28.38
8×24 PUFB [6]8×24 BOFB [7]4.77
36.18 32.03 28.40
8×24 PLPUFB
4.77
36.14 31.92 28.33
8×24 PLBOFB
4.76
36.21 31.99 28.36‘Elaine’
5/3 and 9/7-tap DWT
5.1134.61 32.94 31.51
8×24 PUFB [6]5.06
35.24 33.29 31.34
8×24 BOFB [7]5.04
35.32 33.24 31.26
8×24 PLPUFB
5.05
35.31 33.28 31.33
5.03
35.38 33.33 31.33
8×24 PLBOFB‘Finger’
5/3 and 9/7-tap DWT
5.84
29.07 25.99 23.51
8×24 PUFB [6]5.68
30.21 26.59 23.79
5.65
30.25 26.62 23.77
8×24 BOFB [7]8×24 PLPUFB
5.66
30.26 26.58 23.71
5.66
30.21 26.62 23.91
8×24 PLBOFB
Average of 10 test images
5/3 and 9/7-tap DWT
5.31
32.95 30.06 27.62
8×24 PUFB [6]5.32
33.46 30.33 27.68
8×24 BOFB [7]5.29
33.53 30.31 27.65
8×24 PLPUFB
5.29
33.56 30.32 27.62
8×24 PLBOFB
5.29
33.56 30.37 27.70(a)(b)(c)(d)Figure 9: Enlarged image of ‘Barbara’ (Bit rate: 0.25[bpp]):(a)Original image, (b)9/7-tap DWT, (c)8×24 PLPUFB, (d)8×24
PLBOFB.

REFERENCES[1] W. Pennebaker and J. Mitchell, JPEG, Still Image Data Compression Standard, NY: Van Nostrand, 1993.
[2] K. R. Rao and P. Yip, Discrete Cosine Transform Algorithms,Academic Press, 1990.
[3] A. Skodras, C. Christopoulis, and T. Ebrahimi,“TheJPEG2000 still image compression standard,” IEEE Trans.
Signal Process. Mag., vol. 18, no. 5, pp. 36–58, Sep. 2001.
[4] W. Sweldens, “The lifting scheme: a custom-design construction of biorthogonal wavelets,” Appl. Comput. Harmon. Anal.,
vol. 3, no. 2, pp. 186–200, 1996.
[5] 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.

[6] T. Suzuki, Y. Tanaka, and M. Ikehara, “Lifting-based paraunitary filterbanks for lossy/lossless image coding,” in Proc. ofEUSIPCO’06, Florence, Italy, Sep. 2006.
[7] 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.
[8] P. P. Vaidyanathan, Multirate Systems and Filter Banks, Englewood Cliffs, NJ: Prentice Hall, 1992.
[9] T. D. Tran, J. Liang, and C. Tu, “Lapped transform via timedomain pre- and post-filtering,” IEEE Trans. Signal Process.,
vol. 6, no. 6, pp. 1557–1571, June 2003.
[10] X. Gao, T. Q. Nguyen, and G. Strang, “On factorization of Mchannel paraunitary filterbanks,” IEEE Trans. Signal Process.,
vol. 49, no. 7, pp. 1433–1446, Jul. 2001.
[11] 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.

2248