REVERSIBLE NON-EXPANSIVE SYMMETRIC CONVOLUTION FOR
M -CHANNEL LIFTING BASED LINEAR-PHASE FILTER BANKS
Taizo Suzuki

Masaaki Ikehara

EEE Dept., College of Eng., Nihon University
Koriyama, Fukushima 963-8642, Japan
Email: taizo@ee.ce.nihon-u.ac.jp

EEE Dept., Keio University
Yokohama, Kanagawa 223-8522, Japan
Email: ikehara@tkhm.elec.keio.ac.jp

ABSTRACTThis paper presents an effective signal boundary solution in lossyto-lossless image coding which is the unification of lossy and lossless image coding. Although M -channel filter banks (FBs) for lossy
image coding have several effective signal boundary solutions, M channel lifting based FBs (L-FBs) for lossless image coding do nothave such an effective signal boundary solutions due to rounding error in each lifting step. This paper proposes reversible non-expansive
symmetric convolution for M -channel lifting based linear-phase FBs(L-LPFBs) to apply lossy-to-lossless image coding. Our proposal
is validated by comparing with the periodic extension in lossy-tolossless image coding.
Index Terms— M -channel lifting based linear-phase filter bank
(L-LPFB), lossy-to-lossless image coding, reversible non-expansive
symmetric convolution
1. INTRODUCTION
Filter bank (FB) [1] technologies are frequently found in the field of
signal processing applications. Especially, M -channel linear-phase
FBs (LPFBs) [2], include lapped transforms (LTs) [3], are wellknown as one of the most useful transforms for image compression(coding). It is a reason that LPFBs can adopt the symmetric extension [4] to overcome the signal boundary distortion problem. In thisapproach, the input signals are extended symmetrically in order tomaintain the continuity at the signal boundaries. The output signals
are reconstructed without the signal boundary distortion by using
symmetry even if the extended signals are not transmitted. Since
the symmetric extension improves the performance of image coding
applications, most works in the field of FB systems are focused on
LPFBs.
Meanwhile, lifting based LPFBs (L-LPFBs) composed of lifting structures [5] and rounding operations are required for lossy-tolossless image coding, which is the unification of lossy and losslessimage coding, such as JPEG 2000. However, L-LPFBs (M > 2)
generate the signal boundary distortion because the symmetric extension cannot be applied directly to L-LPFBs due to rounding error.
Because of that, the periodic extension is often used for lossy-tolossless image coding even if the FB without rounding operations
has symmetry [6].
In this paper, the signal boundary problem in lossy-to-losslessimage coding is solved by focusing on symmetry in each building
block of a particular class of M -channel L-LPFBs again. The proposed reversible symmetric extension can obtain similar smoothness
to the symmetric extension at the signal boundaries even if rounding operations are used. Moreover, the computational cost is less978-1-4673-2533-2/12/$26.00 ©2012 IEEE

2453

Fig. 1. M -channel FB (↓, ↑ and z −1 means downsampling, upsampling and delay operation, respectively).
due to use of non-expansive convolution [7], i.e., the number of input signals does not increase even temporarily. Our proposal, which
this paper calls the reversible non-expansive symmetric convolution,
is validated by comparing with the periodic extension in lossy-tolossless image coding.
Notations: I, J and {·}T are an identity matrix, a reversal identity matrix and transpose of a matrix, respectively.
2. REVIEW
2.1. Linear-Phase Filter Banks (LPFBs)
The polyphase representation of a typical structure of a FB is shownin Fig. 1. Using the lattice structure, the type-II analysis polyphasematrix E(z) in an M × M K LPFB can be presented as [8]E(z) = E0 G1 (z) · · · GK−2 (z)GK−1 (z)

(1)

where
E0 = Φ0 W, Gk (z) = Λ(z)Ξk = Λ(z)WΦk W,





1 I
I
J
0
Uk
, W= √Φk =, Λ(z) =0Vk0
2 J −I

z

0

−1


I

and Uk and Vk are M/2 × M/2 arbitrary nonsingular matrices
when M is even, respectively. (1) is shown in Fig. 2. Also, Uk is
usually replaced by I when k ≥ 1. If E(z) is invertible, the synthesis
polyphase matrix R(z) can be chosen as the inverse of E(z), i.e.,
perfect reconstruction (PR) R(z) = ET (z −1 ) is achieved.
2.2. Lifting Structure
The lifting structure [5], also known as the ladder structure, is a special type of lattice structure. It is implemented by cascading elementary matrices - identity matrices with a single nonzero off-diagonal
element.

ICIP 2012

Fig. 2. General lattice structure for M × KM LPFB (drawn for M = 8).
vectors. If their reflected signals are JXk,l , symmetry is achieved as



sk,l
 Yk,l
tk,l


Jtk,l
= JYk,lΞk JXk,l = ΞkJsk,lΞk Xk,l = ΞkFig. 3. A lifting structure (white circle: rounding operation).

(2)
(3)

where
Yk,l =


1 Uk (sk,l + Jtk,l ) + JVk (Jsk,l − tk,l ).
2 JUk (sk,l + Jtk,l ) − Vk (Jsk,l − tk,l )Since sk,0 = Jtk,0 when the process is stepping over just signal
boundaries, i.e., l = 0, the input and output signals are expressed as




Jtk,0
Uk Jtk,0= JXk,0 and Yk,0 == JYk,0 ,Xk,0 =tk,0
JUk Jtk,0Fig. 4. Analysis part of the symmetric extension by M × 4M LPFB
(dashed line means signal boundary).

Fig. 3 shows a basic lifting structure. It is expressed byyj (n) = xj (n), yi (n) = xi (n) + round{P xj (n)}zj (n) = yj (n), zi (n) = yi (n) − round{P yj (n)}where round{·} and P are rounding operation and a lifting coefficient, respectively. Thus the lifting structure with rounding operation
can achieve integer-to-integer transform. Also, the lifting matrix andits inverse matrix in this case are represented as


1
0

P
1




and

1
0

P
1



−1
=

1
0



−P
,
1

respectively. In the synthesis part, perfect reconstruction is achievedby using such symmetry without receiving redundant signals. As amatter of course, the symmetric extension is also easily applied tothe opposite signal boundaries. Note that if the output signals ofwhen lifting structures and rounding
the input signals Xk,l are Yk,loperations are used in Ξk , the output signals of the reflected input
due to rounding error, i.e., symmetry
signals JXk,l are NOT JYk,lis not achieved. Hence, the symmetric extension cannot be directly
applied to L-LPFBs.
3. L-LPFBS AND REVERSIBLE NON-EXPANSIVESYMMETRIC CONVOLUTION
3.1. L-LPFBs
This paper presents L-LPFBs based on [8] and [9]. First, a building
block Gk (z) can be represented by
Gk (z) = Λ(z)Ξk  Λ(z)WL Φk WR

respectively.

where
WL = W

2.3. Symmetric Extension
In lossy compression without rounding operations, the symmetricextension for LPFB in (1) can be implemented by using symmetry ineach building block. Fig. 4 shows the analysis part of the symmetricextension in case of K = 4. Let l-th (l ≥ 1) M × 1 input signals
for Ξk be Xk,l = {sTk,l , tTk,l }T where sk,l and tk,l are M/2 × 1

2454

√
WR =

 1
√

2I
0

2

0

I

0
√




=

I
J

− 2I


I
W
=
1
− √2 I
0
0

0
I



1
J
2

I
0


I

− 12 J
I
I
−J




0
.
I

The half top of Fig. 5 shows a building block Ξk of M × KM
L-LPFB. Then, if {ˆ·} means a matrix with rounding operations, ÛkFig. 7. Analysis part of the reversible non-expansive symmetric convolution by M × 4M L-LPFB (dashed line means signal boundary).
Fig. 5. Building blocks of M × KM L-LPFB: (top) Ξk , (bottom)
JΞk J for boundary area.

By the replacement of building blocks on boundary area and(4), the implementation in case of the reflected input signals
JXk,l is similarly expressed as follows:JΞ̂k J · JXk,l = JΞ̂k Xk,l = JYk,lwhere J·J = I. Fig. 5 shows symmetry in building blocks Ξ̂kand JΞ̂k J of M × KM L-LPFB. As a result, it is clear thatsymmetry can be satisfied by a simple matrix manipulationeven if the implementation has rounding operations in case ofl = 0.
Fig. 6. Analysis part of the reversible symmetric extension by M ×
4M L-LPFB (dashed line means signal boundary).
and V̂k mean matrices factorized Uk and Vk into single-row elementary reversible matrices (SERMs) by [9] with the fewest rounding operations. Also, W in the last block E0 is factorized into lifting
structures by lifting factorization of Givens rotation matrix as1





√
√
I
0 I (1 − 2) J I 0
I (1 − 2) J
.
W=
1
√ J I
0 −I
0
I
0
I
2

Case 2 (l = 0) :This case structurally achieves symmetry. Let the input signals Xk,0 be [(Jtk,0 )T , tTk,0 ]T for simplicity. (4) is rewrittenasÛk Jtk,0= Yk,0= JYk,0Ξ̂k Xk,0 =JÛk Jtk,03.2. Reversible Symmetric Extension
The loss of symmetry due to rounding error can be solved by a simple
matrix manipulation. Fig.6 shows a realization of symmetry withrounding operations.
Case 1 (l = 0) :If l-th input signals are Xk,l and rounding operations are considered, it is expressed as= Yk,l .
Ξ̂k Xk,l  Yk,l(4)

According to (2) and (3), Ξk can be represented byΞk = JΞk J.
This means that each building block Ξk for extended signals
can be replaced by JΞk J. This relationship is preserved evenif Ξ̂k is used in place of Ξk , i.e.,Ξ̂k = JΞ̂k J.
1 Although W in E

0 of biorthogonal LPFB (BOLPFB) can be replaced
by WR , this paper uses paraunitary LPFB (PULPFB) for simplicity.

2455

It is clear that symmetry is also satisfied even if the implementation has rounding operations in case of l = 0.
Consequently, the symmetric extension is applicable to LLPFBs in (1) by replacing Ξ̂k at boundary area to JΞ̂k J.
3.3. Reversible Non-Expansive Symmetric Convolution
It is important that the input and output signals for Ξ̂k always havesymmetry as already indicated in Sec. 3.2. Additionally, note that
only half of the output signals processed by Ξ̂k is used in case ofl = 0, i.e., the signal boundaries. Consequently, the reversible symmetric extension in the above subsection can be replaced by the nonexpansive convolution [7] as shown in Fig. 7. This structure, which
this paper calls reversible non-expansive symmetric convolution, hasless computational cost because it does NOT need extension of the
input signals at the signal boundaries temporarily. Also, since Ûk(k = 0) usually adopts I as discussed in Sec. 2.1, JÛk and Ûk J are
replaced by simple J.
4. RESULTS
8 × 16 paraunitary LPFB (PULPFB) and 8 × 24 PULPFB, which−1T
T
have Uk = I (k = 0), U−1
0 = U0 and Vk = Vk , were designed
based on Sec. 3.1 for simplicity. We optimized design parameters byTable 1. Lossy image coding results (PSNR[dB]).
Test
9/7-DWTPULPFB (per.)
PULPFB (prop.)[5]
8 × 16 8 × 24 8 × 16 8 × 24
imagesbit rate: 0.25 [bpp]Barbara
27.28
27.97
28.15
28.09
28.30
Elaine
31.62
31.01
31.08
31.27
31.35
23.52
23.60
23.68
23.63
23.70
Finger
bit rate: 0.50 [bpp]Barbara
30.55
31.58
31.73
31.74
31.92
33.13
32.42
32.56
33.12
33.17
Elaine
26.02
26.44
26.48
26.49
26.53
Finger
bit rate:1.00 [bpp]Barbara
35.16
35.77
35.75
35.95
35.91
Elaine
34.96
34.87
34.82
35.09
35.03
29.15
30.05
30.10
30.09
30.13
FingerFig. 8. Comparison of a particular area of the image Barbara reconstructed by 8 × 24 PULPFBs (bit rate: 0.25[bpp]): (left) the periodic
extension, (right) the proposed method.
5. CONCLUSION
This paper presented the reversible non-expansive symmetric convolution for M -channel lifting based linear-phase filter banks (LLPFBs) to apply lossy-to-lossless image coding. Since the proposed
method has similar smoothness to the symmetric extension at the signal boundaries, it does NOT generate the signal boundary distortioneven if rounding operations are used. Moreover, the computational
cost is less due to non-expansive convolution. As result, it achieved
better coding performance than the periodic extension.

Table 2. Lossless image coding results (LBR [bpp]).
Test
5/3-DWTPULPFB (per.)
PULPFB (prop.)[5]
8 × 16 8 × 24 8 × 16 8 × 24
imagesBarbara
4.87
4.86
4.88
4.83
4.85
Elaine
5.11
5.12
5.12
5.08
5.08
5.84
5.71
5.70
5.70
5.69
Finger

6. REFERENCES
the cost function, which is a weighted linear combination of coding
gain, DC leakage and stopband attenuation [1], and fminunc.m in
Optimization ToolBox of MATLAB. The resulting PULPFBs
were applied to lossy-to-lossless image coding. Integer-to-integertransform can be obtained by using a rounding operation at eachlifting step. To evaluate transform performance fairly, a waveletbased coder EZW-IP [10] was used in the simulation. Also, the reversible non-expansive symmetric convolution and the periodic extension were used for signal boundaries in the designed PULPFBs.
In Table 1, we compared the lossy coding results in peak signal-tonoise ratio (PSNR):2552
PSNR [dB] = 10 log10
MSE
where MSE is the mean squared error, at 0.25, 0.50 and 1.00 bit per
pixel (bpp) for several 512 × 512 8-bit grayscale images as Barbara.
The bolds mean the best PSNRs. 9/7-tap discrete wavelet transform(9/7-DWT) is used in JPEG 2000 lossy mode. Fig. 8 illustrates
the comparison of a particular area of the image Barbara. In signal
boundaries shown in each right side of Fig. 8, it is obvious thatthe proposed non-expansive convolution is better than the periodic
extension.2
Since the proposed PULPFBs are integer-to-integer transforms,
we can also obtain lossless reconstructed images at high bit rate.
Lossless coding performance in lossless bit rate (LBR) [bpp]:
LBR [bpp] =Total number of bits [bit]Total number of pixels [pixel]

is shown in Table 2. The bolds mean the best LBRs. 5/3-tap DWT(5/3-DWT) is used in JPEG 2000 lossless mode. Similar to the lossy
image coding results, the proposed L-LPFBs show the effectivenessfor the images with high frequency components.
2 Fig. 8 shows a particular area of the image Barbara. The left side, top
and bottom of Fig. 8 are NOT boundaries.

2456[1] P. P. Vaidyanathan, Multirate Systems and Filter Banks, Englewood Cliffs, NJ: Prentice Hall, 1992.
[2] T. D. Tran, R. L. de Queiroz, and T. Q. Nguyen, “Linear-phaseperfect reconstruction filter bank: Lattice structure, design, andapplication in image coding,” IEEE Trans. Signal Process., vol.
48, no. 1, pp. 133–147, Jan. 2000.
[3] H. S. Malvar,“Lapped transforms for efficient transform/subband coding,” IEEE Trans. Acoust., Speech, Signal
Process., vol. 38, no. 6, pp. 969–978, June 1990.
[4] M. J. T. Smith and S. L. Eddins, “Analysis/synthesis techniques
for subband image coding,” IEEE Trans. Signal Process., vol.
38, no. 8, pp. 1446–1456, Aug. 1990.
[5] I. Daubechies and W. Sweldens, “Factoring wavelet transforms
into lifting steps,” J. Fourier Anal. Appl., vol. 4, no. 3, pp. 245–
267, 1998.
[6] T. Suzuki and M. Ikehara, “Integer fast lapped orthogonaltransform based on direct-lifting of DCTs for lossless-to-lossy
image coding,” in Proc. of ICASSP’11, Prague, Czech Republic, May 2011, pp. 1525–1528.
[7] T. Nagai, M. Ikehara, M. Kaneko, and A. Kurematsu, “Generalized unequal length lapped orthogonal transform for subband
image coding,” IEEE Trans. Signal Process., vol. 48, no. 12,
pp. 3365–3378, Dec. 2000.
[8] T. D. Tran, “M -channel linear phase perfect reconstruction
filter bank with rational coefficients,” IEEE Trans. Circuits
Syst. I, vol. 49, no. 7, pp. 914–927, July 2002.
[9] P. Hao and Q. Shi, “Matrix factorizations for reversible integer
mapping,” IEEE Trans. Signal Process., vol. 49, no. 10, pp.
2314–2324, Oct. 2001.
[10] 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.