LIFTING-BASED PARAUNITARY FILTERBANKSFOR LOSSY/LOSSLESS IMAGE CODING
Taizo Suzuki, Yuichi Tanaka, and Masaaki Ikehara
Keio University
Department of Electronics and Electrical Engineering
Yokohama, Kanagawa, 223-8522 Japanemail: {suzuki, ytanaka}@tkhm.elec.keio.ac.jpx(n)ABSTRACT

H0(z)

ωM

H1(z)

ωM

HM-1(z)

ωM

x(n)
z -1

ωM

z -1

ωM

E(z)

(1)

where e(z) = [1,z−1 ,··· ,z−(M−1) ]. If E† (z−1)E(z) = I and R(z) =E† (z−1 ), where .† stands for the conjugate transpose, the FBs arecalled paraunitary filterbanks (PUFBs). PUFBs are efficiently designed and implemented by the lattice structure. Recently, the complete and minimal lattice structure of PUFBs has been proposed by
Gao et al. [7]. However its structure is still redundant, thus a simpler structure is developed [10]. Though PUFBs present good coding results for lossy image coding, they are not applied to losslessone.
In this paper, by reducing the redundant parameters in Householder matrix, we derive a novel lifting structure for PUFBs which
has less implementation costs similar to [10]. The proposed PUFBs
are not only applied to lossless image coding but lossy image coding. Our PUFBs with lifting structures are called Lifting-Based
PUFBs (LBPUFBs). We show that the LBPUFBs is more superior
results than 9/7-tap and 5/3-tap wavelet transforms (WTs) adopted
in JPEG2000 [8].
Notations: I, M(N) and M† are the indetity matrix, the N ×
N square matrix andthe conjugate transpose of a matrix, respecT2tively. And  m = ∑N
i=1 | mi | where m = [m1 ,m2 ,·· · ,mN ] .

z -1Processing[H0 (z) H1 (z) ··· HM−1 (z)]T = E(zM )e(z)T[F0 (z) F1 (z) ··· FM−1 (z)] = e(z)R(zM )

χM

F0(z)

χM

F1(z)

χM

FM-1(z)y(n)Figure 1: An M-channel filterbank.

1. INTRODUCTION
Filterbanks (FBs) have been found many applications such asspeech, audio and video compression, statistical signal processing,discrete multitone modulation and channel equalization [2, 4]. Fig.
1 shows an M-channel maximally decimated FB, where Hk (z) andFk (z) are the k-th (for k = 0,··· ,M − 1) analysis and synthesis filter,respectively. Also Fig. 2 shows a polyphase structure of FB. The
analysis and synthesis filters are represented by using the polyphasematrices E(z) and R(z) as follows:

Processing

This paper introduces one of the image transform methods using
M-channel paraunitary filterbanks (PUFBs) based on Householder
matirx. First, redundant parameters of PUFB are eliminated by using the fact that they can be factorized into Givens rotation matices. Next, we propose an eliminating redundant parameters method
based on Householder matrix using relationship between Givens rotation and Householder matrices. In addition, PUFBs are factorized
into the lifting structure for lossless image coding, and we call themas lifting-based PUFBs (LBPUFBs). LBPUFBs based on Householder matrix have less number of rounding operators than Givens
rotation matrix version, since proposed structure is efficiency for
lossless image coding. Finally, we show some exsamples to validate our method in lossy/lossless image coding.
Index Terms — Paraunitary filterbank, householder matrix, redundant parameters, lifting structure, lossless image coding.

R(z)

ωM

χMz -1

χMz -1

χMz -1y(n)Figure 2: A polyphase structure of a filterbank.

2. PARAUNITARY FILTERBANKS BASED ON GIVENSROTATION MATRIX
2.1 Lattice Structure
In this paper, we consider PUFBs where the number of channels isM (even), all filter lengths are MK (K ∈ N), and we set L = K − 1.
The polyphase matrix E(z) of the PUFBs is represented as [7]E(z) = XL ΛL (z)··· X1 (z)Λ1 (z)X0(2)where
Λk (z) =I(M−γk )00
z−1 I(γk )(3)and Xk s are M × M arbitrary orthogonal matrices. Although γk isarbitrary integer 1 ≤ γk < M, in this paper we set γk = M/2 forsimplicity. Thus Λk (z) is denoted as Λ(z).
2.2 Givens Rotation Matrix Factorization
An M × M orthogonal matrix X is factorized into a product ofM(M − 1)/2 rotation angles Θi, j [1]M−1X= ∏M∏ Θi, ji=1 j=i+1(4)x(0)where⎧1⎪⎪⎪⎨ cos θi, j− sin θi, j
Θi, j k,l =⎪⎪⎪ sin θi, j⎩
0: k = l = i or j: k = l = i or j
: k = i and l = j .
: k = j and l = i: otherwise

x(1)

(5)

x(2)
x(3)

Here notes that an order of the Givens rotation angles is arbitrary. This means that an orthogonal matrix is represented as manykinds of structures whose the order of Givens rotation angles aredifferent.
2.3 Simple Structure for PUFBs

H[p2]

H[p1]

H[p0]

Figure 3: Relationship between Givens rotation andHouseholder matrices (M = 4).

In [10], it is shown a lattice structure which has less implementation
costs than that in [7]. The lattice structure in [10] is represented as1E(z) =∏ Xk Λ(z) X0(6)k=LFirstly, we show the Householder matrix factorization until
H [pM−3 ] in (11) to find out a relationship between Givens rotationand Householder matrices.

whereM/2

Xk = ∏M∏3.2 Relationship between Givens Rotation and HouseholderMatrices

Θi, j .

(7)

i=1 j=M/2+1

The above equation corresponds to separate M/2 paths with delayand M/2 paths without delay and construct the Givens rotation matrix from each path with delay to each path without delay.
Also the matrix X0 is an arbitrary M ×M orthogonal matrix andincludes M(M −1)/2 free parameters. On the other hand, the matrix
Xk except for X0 includes (M/2)2 free parameters. Therefore thenumber of free parameters of [10] is (K − 1)M2 /4 + M(M − 1)/2
and the same as [7]. However the number of adder and multiplication is less than [7].

X(M) = H [p0 ]··· H [pM−3 ]An M ×M orthogonal matrix is factorized into (M −1) Householdermatrices [1]. A Householder matrix is represented as(8)

where p = [p0 , p1 ,··· , pM−1 ]T and (H [p])−1 = H [p].
Any orthogonal matrices can be always factorized into cascading Householder matrices. In addition, H [p0 ] which satisfies following equation is exists [1]: (1)0I(9)
H [p0 ] X(M) =0X(M−1)
where X(M−1) is (M − 1) × (M − 1) orthogonal matrix. By calculating recursively like (9), we can derive the relationship
H [pM−2 ]··· H [p1 ] H [p0 ]X= I.

(10)

X(M) = H [p0 ] H [p1 ]··· H [pM−2 ].

(11)Hence, X(M) can be factorized into
Note that the vectors pi have the following form:⎡⎤
× 0 ··· 0. ⎥ ⎢
⎢ × × . . . .. ⎥||⎢⎥⎥.. . .
p0 ··· pM−2 = ⎢⎢ ..
. 0 ⎥.
⎢ .
⎥||⎣ × × ··· × ⎦× × ··· ×
where each × denotes an arbitrary value.

0X(2)

(13)

To compare with (11) and (13) and use Givens rotation matrix factorization for X(2) , H [pM−2 ] is rewritten as⎡
H [pM−2 ] = ⎣I(M−2)
00cos θ1 − sin θ1
sin θ1cos θ1

3.1 Householder Matrix Factorization(M)

I(M−2)
0

⎤
⎦.

(14)

Secondly, we also show the Householder matrix factorization
until H [pM−4 ].

3. PARAUNITARY FILTERBANKS BASED ON
HOUSEHOLDER MATRIX

H [p] = I − 2pp† where  p = 1

X(M) = H [p0 ]··· H [pM−4 ]I(M−3)00X(3)

(15)To compare with (11), (14) and (15) and based on Givens rotation
matrix factorization of X(3) , H [pM−3 ] is rewritten asM

H [pM−3 ] =∏ ΘM−2, j .

(16)

j=M−1

Finally, a relationship between Givens rotation and Householder
matrices is represented as
H [pi] =M∏ Θi+1, j .

(17)

j=i+2

3.3 Elimination of Redundant Parameters(12)

For simplicity, we consider the case of M = 4. A relationshipbetween Givens rotation and Householder matrix factorization isshown in Fig. 3. In this figure, Two redundant Givens rotation
angles are drawn as dotted lines. Of course they can be removed,
thus simpler Householder matrices can be calculated. The process
is presented as follows:(i) H [p2 ] is rewritten as H [p2 ] = I, because the Givens rotation
angle can be removed.
(ii) H [p0 ] does not use x(1). Therefore, p0 becomes p0 =T

p0,1 ,0, p0,3 , p0,4 .

We can generalize its structure to the M-channel case easily, so(12) is rewritten as⎤⎡
× 0 ··· 0⎢. ⎥.
⎢ 0 × . . .. ⎥⎥⎤ ⎢⎡⎥⎢ . . .
||⎢ .. . . . . 0 ⎥⎥⎣ p0 ··· pM/2−1 ⎦ = ⎢(18)⎢ 0 ··· 0 × ⎥ .
⎥⎢||⎢ × × ··· × ⎥⎥⎢⎥⎢ . . .
. . ... ⎦⎣ .. ..
× × ··· ×X0

H[p0,1]

X1

H[p0,0]H[p1,1]H[p1,0]

z -1

z -1

H[p0,2]z -1

H[p2,1]

H[p2,0]

z -1

(a)

z -1

However p0 in the first block of PUFBs is same as (12). Hence, thenumber of free parameters of this novel structure is (K − 1)M2 /4 +M(M − 1)/2, same as [10]. We use this structure for the lifting
factorization described next section.

XL

z -1

z -1

(b)

z -1

4. LIFTING-BASED PARAUNITARY FILTERBANKS
4.1 Lifting Factorization of PUFBs
It is well-known that a Givens rotation matrix is factorized into alifting structure as [5] 
1 01 α1 αcos θ − sin θ(19)=sin θcos θ0 1β 10 1
where α = (cos θ − 1)/sin θ , β = sin θ . Hence PUFBs based on
Givens rotation matrix can be factorized into the lifting structuresby using (19).
On the other hand, a Householder matrix is also factorized into
a lifting structure as [9]
⎤
⎡
1..
⎥⎢
⎥
⎢.
⎥⎢
⎥
⎢
1
⎥
⎢
H [p] = ⎢ α1 ··· αr−1 1 αr+1 ··· αM ⎥⎥
⎢
1⎥⎢
⎥
⎢..
⎦⎣
.
1⎤
⎡
β11..
..
⎥⎢⎥
⎢.
.
⎥⎢
⎥⎢
1 βr−1⎥⎢−1× ⎢⎥⎥⎢
βr+1 1⎥
⎢
⎥
⎢.
..
⎦⎣..
.
βM1⎤⎡
1..
⎥⎢⎥
⎢.
⎥⎢⎥
⎢1⎥
⎢
× ⎢ α 1 ··· α r−1 1 α r+1 ··· α M ⎥ .
⎥⎢1⎥⎢
⎥
⎢..
⎦⎣
.
1(20)
Where αk , βk and α k are αk = pk /pr , βk = −2pk pr and α k = −αk ,respectively. And r = i + 1 in (12), (18). Since PUFBs based on
Householder matrix can be factorized into the lifting structures using (20).
4.2 Reducing of Rounding Operators
The number of rounding operators should be as small as possible
for lossless image coding. For this motivation, we change the position of the Givens rotation angles and merge rounding operators.

z -1

z -1

z -1

(c)

z -1

Figure 4: Lattice structures of LBPUFB (M = 4):(a)Householder matrix factorization, (b)Lifting factorization,(c)Reducing of rounding operators.

The Householder factorization is also a minimal structure of an orthogonal matrix, since we change the position of the Householder
matrices and merge rounding operators. Fig. 4 shows its structure.
The number of reduced rounding operators is shown in Table 1.
It is obvious that LBPUFBs based on Householder matrices always
have less number of rounding operators than Givens rotation matrix
ones. Therefore, we use LBPUFBs based on Householder matrix as
our proposed method.
5. RESULTS
5.1 Filterbank Design
In this paper, we focus on image coding applications, thus the costfunction is a weighted linear combination of coding gain CCG , stopband attenuation CSTOP , DC leakage CDC and a new function Cabs.
First three functions are very common [1], and Cabs is the sum of absolute values of parameters to obtain better compression efficiency.
C = −w1CCG + w2CST OP + w3CDC + w4Cabs .

(21)

We designed 4 × 8, 4 × 12, 4 × 16, 8 × 16, 8 × 24 and 8 × 32
LBPUFBs. Their frequency responses are depicted in Fig. 5.
5.2 Application to Lossless Image Coding
In this subsection, our LBPUFBs are applied to lossless image coding by using rounding operators in each lifting structure. For the faircomparison against WT, we adopted the periodic extention and avery common wavelet-based coder EZW-IP [6]. The coding results
are compared by entropy [bpp]=(Total number of bits [bit])/(Totalnumber of pixels [pixel]). Table 2 shows the comparison between
LBPUFBs and 5/3-tap WT [8]. In this table, it is obvious that ourLBPUFBs denote better results on the entropy than 5/3-tap WT.
5.3 Application to Lossy Image Coding
In this subsection, our LBPUFBs are applied to lossy image coding
without using rounding operators. As well as lossless image coding,we adopted the periodic extention and EZW-IP. The coding results
are compared by PSNR [dB]=10log10 (2552 /MSE) where MSE is
the mean squared error. Fig. 6 and Table 3 show the part of theTable 1: The number of reduced rounding operators in LBPUFBs ((·) is the number of rounding operators before reducing).
4×84 × 12
4 × 168 × 168 × 248 × 32LBPUFBs based on Givens rotation matrix 23 (30) 31 (42) 39 (54) 95 (132) 127 (180) 159 (229)
18 (30) 24 (42) 30 (54) 62 (132)82 (180)102 (229)
LBPUFBs based on Householder matrix

Table 2: Comparison of lossless image coding (Entropy [bpp]).
5/3-tap
4×8
4 × 12
4 × 168 × 168 × 24WTLBPUFB LBPUFB LBPUFB LBPUFB LBPUFB
4.87
4.88
4.79
4.79
4.88
4.81
5.10
5.14
5.10
5.09
5.16
5.13
5.11
5.17
5.12
5.11
5.12
5.06
5.84
5.82
5.74
5.72
5.70
5.68
5.60
5.63
5.50
5.47
5.48
5.43
6.06
6.11
6.07
6.06
6.07
6.05

00-10

-10

-10

-20

-30

-40

-50-20-30

-40

-50

00.2

0.4

0.6

0.8

-60

1-20

-30

-40

-50

00.2

0.4

0.6

0.8-601

0.4

0.6(a)(b)(c)-10-10-10-20-30-40-50

Magunitude Response [dB]0-20-30-40-50

0.2

0.2

Normalized Frequency

000

Normalized Frequency

0-608 × 32
LBPUFB
4.83
5.15
5.07
5.68
5.43
6.06

Normalized Frequency

Magunitude Response [dB]

Magunitude Response [dB]-60

Magunitude Response [dB]0

Magunitude Response [dB]

Magunitude Response [dB]

Test image(512×512)
BarbaraBoatElaine
FingerFinger2
Grass

0.4

0.6

0.8

1-60

0.8

10.81-20-30-40

-50

00.2

0.4

0.6

0.8

1-60

00.2

0.4

0.6

Normalized Frequency

Normalized Frequency

Normalized Frequency(d)(e)(f)

Figure 5: Frequency responses of LBPUFBs: (a)4 × 8, (b)4 × 12, (c)4 × 16, (d)8 × 16, (e)8 × 24 and (f)8 × 32 LBPUFB.

Figure 6: Barbara (Bit rate: 0.25 [bpp]): (left)Original, (middle)9/7-tap WT, (right)8×32 LBPUFB.

Test image(512×512)
BarbaraBoat
ElaineFingerFinger2
Grass
Test image(512×512)
BarbaraBoatElaine
FingerFinger2
Grass
Test image(512×512)
BarbaraBoat
ElaineFingerFinger2
Grass

Table 3: Comparison of lossy image coding (PSNR [dB]).
Bit rate: 1.0 [bpp]9/7-tap
4×84 × 12
4 × 168 × 168 × 24WTLBPUFB LBPUFB LBPUFB LBPUFB LBPUFB
34.91
35.15
35.71
35.91
35.84
36.33
34.63
34.57
34.79
34.89
34.65
34.84
34.89
34.59
34.94
35.01
35.10
35.52
29.04
29.30
29.74
29.83
30.13
30.36
31.26
29.70
30.83
31.51
32.09
32.52
28.68
28.85
29.04
29.11
29.14
29.23
Bit rate: 0.5 [bpp]9/7-tap
4×84 × 12
4 × 168 × 168 × 24WTLBPUFB LBPUFB LBPUFB LBPUFB LBPUFB
30.47
30.66
31.21
31.45
31.56
32.03
31.44
31.15
31.34
31.45
31.27
31.44
33.05
32.71
33.02
33.08
33.04
33.43
25.96
25.68
26.08
26.22
26.50
26.60
27.55
25.68
26.58
26.91
27.15
27.72
26.11
26.11
26.26
26.34
26.37
26.47
Bit rate: 0.25 [bpp]9/7-tap
4×8
4 × 12
4 × 168 × 168 × 24WTLBPUFB LBPUFB LBPUFB LBPUFB LBPUFB
27.23
27.10
27.62
27.85
27.97
28.40
28.47
28.09
28.32
28.39
28.32
28.44
31.57
30.98
31.32
31.39
31.11
31.40
23.50
22.87
23.19
23.32
23.65
23.84
24.17
22.51
23.32
23.67
23.84
24.65
24.36
24.17
24.34
24.41
24.48
24.58

enlarged images of Barbara and the comparison of PSNRs between
LBPUFBs and 9/7-tap WT [8], respectively. In this table and figure, it is obvious that our LBPUFBs denote better results on thePSNR against 9/7-tap WT and the high frequency region of the recnstructed image using the LBPUFB is well-approximated.
6. CONCLUSION
We proposed a novel lattice structure of PUFBs based on the Householder factorization without redundant parameters. This class ofFBs, called LBPUFBs, could be factorized into the lifting structures. Our LBPUFBs have less number of rounding operators thanthe Givens rotation ones and this property is useful for lossless image coding. Furthermore, our LBPUFBs presented superior coding
results on the entropy and the PSNR against 9/7- and 5/3-tap WTs
to both lossy/lossless image coding, respectively.
REFERENCES[1] P. P. Vaidyanathan, “Multirate Systems and Filter Banks,” Englewood Cliffs, NJ: Prentice Hall, 1992.
[2] E. S. Malvar and D. H. Staelin, “The LOT: Transform coding without blocking effects,” IEEE Trans. Acoustics, Speech,
Signal Process., vol. 37, pp. 553–559, no. 4, Apr. 1989.
[3] A. K. Soman, P. P. Vaidyanathan, and T. Q. Nguyen, “Linearphase paraunitary filter banks: Theory, factorizations and designs,” IEEE Trans. Signal Process., vol. 41, pp. 3480–3496,
no. 12, Dec. 1993.
[4] R. L. De Queiroz, T. Q. Nguyen, and K. R. Rao, “The GenLOT: generalized linear-phase lapped orthogonal transform,”
IEEE Trans. Signal Process., vol. 44, no. 3, pp. 497–507, Mar.
1996.
[5] Y.-J. Chen, S. Oraintara, and T. Q. Nguyen, “Integer discretecosine transform (IntDCT),” in Proc. 2nd Int. Conf. Inform.
Commun. Signal Process., Singapore, Dec. 1999. Invited paper.

8 × 32LBPUFB
36.33
34.82
35.50
30.60
32.56
29.23
8 × 32LBPUFB
32.07
31.44
33.41
26.68
27.90
26.47
8 × 32LBPUFB28.4228.43
31.37
23.75
24.57
24.57

[6] Z. Liu and L. J. Karam, “An efficient embedded zerotree
wavelet image codec based on intraband partitioning,” in Proc.
Int. Conf. Image Process., vol. 3, pp. 162–165, Sept. 2000.
[7] 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.
[8] A. Skodras, C. Christopoulis, and T. Ebrahimi, “TheJPEG2000 still image compression standard,” IEEE Trans.
Signal Process. Mag., vol. 18, no. 5, pp. 36–58, Sept. 2001.
[9] Y.-J. Chen and K. S. Amaratunga, “M-channel lifting factorization of perfect reconstruction filter banks and reversible Mband wavelet transforms,” IEEE Trans. Circuits Syst. II, vol.
50, pp. 963–976, Dec. 2003.
[10] M. Ikehara and Y. Kobayashi, “A novel lattice structure of Mchannel paraunitary filter banks,” in Proc., IEEE Int. Symp.
Circuits Syst., pp. 4293–4296, 2005.