TWO DIMENSIONAL NON-SEPARABLE ADAPTIVE DIRECTIONAL LIFTINGSTRUCTURE OF DISCRETE WAVELET TRANSFORM
Taichi Yoshida1 , Taizo Suzuki1 , Seisuke Kyochi2 and Masaaki Ikehara1
1 : EEE Dept., Keio Univ., Yokohama, Kanagawa 223-8522, Japan
2 : NTT Cyber Space Laboratories, NTT Corporation, Yokosuka, Kanagawa, 239-0847, Japan
Email: {yoshida, suzuki, kyochi, ikehara} @tkhm.elec.keio.ac.jp
ABSTRACTIn this paper, we propose a two dimensional (2D) non-separable
adaptive directional lifting (ADL) structure of discrete wavelet transform (DWT) and its image coding application. Conventionally, wehave proposed a polyphase representation of a 2D non-separable lifting structure of DWT. We generalize the polyphase representation inthis paper and one structure of the class has been proven to reduce
errors due to the rounding operations and improve a compatibilityof the irreversible 9/7 DWT, compared with a 2D separable lifting structure of DWT. Adding the adaptive directional transforming
property to the generalized structure, our proposed method improves
the lossy image coding performance with maintaining the compatibility.
Index Terms— two dimensional non-separable lifting structure,
discrete wavelet transform, adaptive directional transform, lossy tolossless image coding.
1. INTRODUCTION
The discrete wavelet transform (DWT) has been a fundamental toolfor image and video processing for the last few decades. It is applied
to the JPEG 2000 international image coding standard [1]The irreversible 9/7 DWT utilized by the JPEG 2000 is efficientfor the lossy image coding. However, it can not be applied to thelossless image coding. For the lossless image coding, the lifting
structure of 9/7 DWT has been proposed [2]. It realizes the integerto-integer transform, but it introduces a mismatching error due to therounding operations when the 9/7 DWT is connected to the lifting
structure of 9/7 DWT. Iwahashi et al. have proven that the two dimensional (2D) non-separable lifting structure of 9/7 DWT requires
less rounding operators than the conventional one and improves thecompatibility.
These structures of DWT are efficient for the image coding application. However, since they can only transform images along thevertical and horizontal direction, they fail to provide sparse representation of transforming images when images contain rich directional
high frequency component, such as edges and contours, and the coding efficiency is degraded. To avoid this degradation, an adaptive
directional transform has been proposed [3–5]. The adaptive directional transform can flexibly switch the filtering direction according
to the direction of edges and contours and compression efficiency
is improved. Especially, one dimensional (1D) adaptive directional
lifting (ADL) based wavelet transform [4] achieves high compression efficiency for the lossy image coding. However, since 1D ADLThis work is supported by Global COE Program ”High-Level Global
Cooperation for Leading Edge Platform on Access Space (C12)”

978-1-4577-0539-7/11/$26.00 ©2011 IEEE

has to be applied twice for the separately implementation of 2D signals, it is redundant and provides a degradation of desired filtering
directions due to the downsampling between the first and second
filtering. Therefore, we have proposed the 2D ADL [5]. The 2D
ADL is simpler than the 1D one and can select the filtering directions which are different from 1D ADL. It is efficient for the losslessimage coding, but it is only 5/3 DWT.
In this paper, we propose a 2D non-separable ADL structureof DWT. We generalize the polyphase representation of 2D nonseparable lifting structure of DWT. For the adaptive directional transform, the proposed method is realized by changing the sampling matrix by sub-regions of images. Therefore, with advantages of thenon-separable structure and the adaptive directional transform, theproposed structure improves the performance of the lossy-to-losslessimage coding application. Finally, lossy and lossless image coding
results of the proposed structure are shown to validate the advantageof the proposed structure.
Notations：AT denotes the transpose of the matrix A. I and0 are identity and the null matrices, respectively. M is an 2 × 2
nonsingular integer matrix. ↓ M and ↑ M also represent the downand up-samplers with M, respectively. Using vectors z = [zx , zy ]Tand k = [kx , ky ]T , a multiplication of vectors is defined as zk =kzxkx zy y . diag(·) denotes the block diagonal matrix.

2. REVIEW
The polyphase representation of 1D lifting structure of DWT can be
expressed as follows [2], [6].
  
01
10s 0HL (z)1 Ui (z 2 )=0 1/s
HH (z)z −1
Pi (z 2 ) 10
1i=N −1= E1D (z 2 )d2 (z)(1)
According to the separable implementation, the polyphase representation of the 2D separable lifting structure of DWT can be given by⎤ ⎡⎤ ⎡⎤0HL (zx )HL (zy )HL (zy )HLL (z)(z)(z)H(z)(z)0HHH⎥ HL (zx )⎢ HL ⎥ ⎢ L x H y ⎥ ⎢ H y⎦⎣ H (z) ⎦ = ⎣ H (z )H (z ) ⎦ = ⎣ 0
HL (zy ) HH (zx )LH
H xL yHHH (z)
HH (zx )HH (zy )0
HH (zy )= E(zM )dM (z)
(2)
⎡1529

ICASSP 2011

Fig. 1. 2D separable lifting structure of 9/7 DWT
where
M = diag(2, 2),dM (z) = [z−k0 , z−k1 , z−k2 , z−k3 ]T ,mmmm
zM = [zx 0,0 zy 1,0 , zx 0,1 zy 1,1 ]T ,z = [zx , zy ]T , zx and zy are the vertical and horizontal delay elements, respectively, ki (i = 0, 1, 2, 3) is an integer vector within
Ξ(M), called as a delay vector, k0 is restricted to be [0, 0]T , Ξ(M)is a set of integer vectors, which is defined as
Ξ(M) = {Mx | x ∈ [0, 1)},

Using these matrices, (3) is rewritten asx ∈ [0, 1) denotes a set of 2 × 1 real vectors x whose the ith component satisfies 0 ≤ xi < 1 and mi,j denotes the (i, j) element ofM. The polyphase matrix E(z) is factorized as
E(z) =

Ey1D 00 Ey1D

sI 00 1/sI

one in (2). In this paper, we introduce the generalized polyphaserepresentation. Here, some matrices are defined as follows.

 
sI 0s 0s 0,, Ŝ =,S = diag
0 1/sI0 1/s
0 1/s






1 Uij
1 Uij
I Uij IUji = diag,, Ûji =,(5)0 10 10 I 1 0I 01 0
Pji = diag,, P̂ji =.
Pij 1
Pij I I
Pij 1

 0I Uix I
I 0x0 I
Pi I Ii=N −1(3)where Ey1D , Pij and Uij (j = x, y) denote E1D (zy ), Pi (zj ) andUi (zj ). According to the polyphase matrix, the delay vectors aredecided asdM (z) = [1, zy−1 , zx−1 , zx−1 zy−1 ]TFor example, fig.1 shows the 2D separable lifting structure of 9/7
DWT with rounding operators R in lifting steps. Fig.1 shows thatimages are divided into four sets and transformed with maintaining
an integer.
The pair of scaling factors can be realized as a lifting structure[2]. The scaling is factorized as 
10 1 s−1 1 0s 01 s − s2.
(4)=−1/s 111 10 1/s
01For simplicity, scaling is not represented as the lifting structure inthis paper.
3. 2D NON-SEPARABLE ADL STRUCTURE OF DWT
3.1. Basic structure
In [5], we have proposed the polyphase representation of the 2D nonseparable lifting structure of 5/3 DWT by factorizing the separable

1530

E(z) = S0
{Uyi Pyi } Ŝi=N −10Ûxi P̂xi .

(6)i=N −1Ŝ and Ûxi P̂xi can be moved as follows.
Uyi Pyi Ŝ = ŜUyi Pyi , Uyp Pyp Ûxq P̂xq = Ûxq P̂xq Uyp Pyp .

(7)

where p, q = 0, 1, . . . , N − 1. We have factorized Uyp Pyp Ûxq P̂xq asÊp,q in [5], where⎤⎡
11 Upy Uqx −Upy Uqx
0 ⎥⎢Ppy⎢0 1 0Êp,q = ⎣0 0 10 ⎦⎣ 00 0 010⎤⎡10 0 01 0 0⎥⎢ 0×⎣
00 1 0⎦
Ppy Pqx Pqx Ppy 1⎡⎤⎡0 0 01x1 0 Uq ⎥⎢ 00 1 0 ⎦⎣Pqx
00 0 1⎤0 0 01 0 0⎥
0 1 Upy ⎦0 0 1(8)Using (7) and (8), the any polyphase matrix E(z) of the 2D nonseparable lifting structure of DWT can be realized. For example, inthe case of 9/7 DWT, E(z) is designed asE(z) = S̃Uy1 Py1 Ê0,1 Ûx0 P̂x0(9)where S̃ = SŜ = diag(s2 , 1, 1, 1/s2 ). This structure is shown infig.2. Compared with fig.1, it is shown to require less rounding operators. Therefore, the non-separable structure has better compatibilities to the irreversible 9/7 DWT in the JPEG 2000 than the separable
structure [7].

Fig. 2. 2D non-separable lifting structure of 9/7 DWT
3.2. Directional sampling
By changing the sampling matrix M by sub-regions of images, 2D
non-separable ADL structure of DWT is realized. The arbitrary sampling matrix whose absolute determinant is 4 can be selected. Thefollowing sampling matrices Md (d = 0, 1, . . . , 6) are used in thispaper.
      
2 −42 42 0
2 0
2 −22 2
2 0,,,,,,
0 2
0 2−2 2
2 20 2
0 20 2
With changing the sampling matrix, the delay vectors have to
be changed. For maintaining the linear phase property of filters, wedefine the delay vectors to be symmetry with respect to a point which
is a center of Md . Table 1 shows the delay vectors corresponded toMd and the filtering directions are represented in fig.3. It shows thatthe proposed structure can transform along with various directions
besides vertically and horizontally shown in fig.3(a).

d0123456Table 1. Delay vectors
k1k2k0T[0, 0][0, 0]T[0, 0]T[0, 0]T[0, 0]T[0, 0]T[0, 0]TT[0, 1][1, 1]T[−1, 1]T[0, 1]T[0, 1]T[2, 1]T[−2, 1]TT[1, 0][1, 0]T[1, 0]T[1, 1]T[1, −1]T[1, 0]T[1, 0]Tk3[1, 1]T[2, 1]T[0, 1]T[1, 2]T[1, 0]T[3, 1]T[−1, 1]T3.3. Optimal direction decision
For the image coding application, the optimal directions are decided
according to the energy of highpass subband. Especially, we focus
on the energy of ”HH” subband in this paper. For all the sampling
matrix Md , the HH subband components are described as hd . The
optimal direction Dir(m, n) is chosen such that it minimize the energy of hd (m, n),Dir(m, n) = min |hd (m, n)|.
dFig. 4. Simulation of directional selectivity(10)Practically, the direction information is assigned to not the pixels
but the blocks divided by the quad tree decomposition in order toreduce the side information. For this purpose, R-D optimization isprocessed as in the following. The full quad tree T is constructed byapplying the quad tree decomposition to the image until reaching thepredefined block size. B, D(B) and R(B) are defined as an arbitrary
subtree, a distortion and a rate of bits. The most suitable subtree B ∗with optimal direction is provided by minimizing the cost function
J(B) expressed byτ denotes a node of B, rC (τ ) and rT (v) are defined as the rate of
the entropy encoding high pass coefficients in τ and coding the sideinformation in node in v, respectively. Applying the automatical decision of optimal directions to a simulation image is shown in fig.4.
Along directions of stripes, the filtering directions are selected correctly.

B ∗ = min J(B) = min(D(B) + λR(B))

Here, we apply the proposed structure shown in fig.2 into the lossyto-lossless image coding application and compare the coding efficiency with the conventional one shown in fig.1. The embedded zerotree wavelet based on intraband partitioning (EZW-IP) [8] is usedas the encoder. Since transformed coefficients are integer and encoded images are lossless bit streams, lossy bit streams are produced
by discarding bits in the lower bit plane of the bit streams. The sideinformation is encoded by the arithmetic coding algorithm [9]. AtB

where
D(B) =R(B) =B(11)|hτ,d (m, n)|,rC (τ ) +rT (v),τ
∈B m,nτ ∈Bv∈B1531

4. SIMULATION

Fig. 3. Sampling matrices

Table 2. Image coding results
Lossless [bpp]Conventional Proposed
Entropy
4.81
4.76
Lossy [dB]Rate [bpp] Conventional Proposed
0.25
27.23
27.47
0.5
30.45
30.78
134.8435.16

the lossy image coding application, the peak signal-to-noise ratio(PSNR) is used as a objective function measuring an image qualityof reconstructed images. As a test image, Barbara is used.
Table 2 indicates results of the lossless and lossy image coding application. From the table, the proposed structure improves thelossy-to-lossless image coding application compared with the conventional structure, because of the adaptive directional transform. In
fig.5, the original and reconstructed images are represented, where
the compression rate is 0.25 [bpp]. Compared with the conventionalstructure, the proposed structure can represent various direction besides vertically and horizontally. Especially, stripe textures in fig.5(f)are represented clearly.

(a)Original(b)Enlarged original(c)Conventional(d)Enlarged conventional(e)Proposed(f)Enlarged proposed

5. CONCLUSION
In this paper, we generalize the polyphase representation of the 2D
non-separable lifting structure of DWT and propose ADL of thestructure. With maintaining the advantage of the 2D non-separable
and the adaptive directional transform, the proposed structure achieves
better image coding results than the conventional one.
6. REFERENCES[1] ISO/IEC 10918-1, Information technology - JPEG 2000 image
coding system : Core coding system .
[2] I. Daubechies and W. Sweldens, “Factoring wavelet transforms
into lifting steps,” J. Fourier Anal. Appl., vol. 4, no. 3, pp. 247–269, 1998.
[3] C.-L. Chang and B. Girod, “Direction-adaptive discrete wavelet
transform for image compression,” IEEE Trans. Image Process.,
vol. 16, no. 5, pp. 1289–1302, May. 2007.
[4] W. Ding, F. Wu, X. Wu, S. Li, and H. Li, “Adaptive directional
lifting-based wavelet transform for image coding,” IEEE Trans.
Image Process., vol. 16, no. 2, pp. 416–427, Feb. 2007.

1532

Fig. 5. Original images and reconstructed images[5] S. Kyochi, J. Aoyama, and M. Ikehara, “A directional-adaptive
image coding using two-dimensional direct lifting wavelet transform,” IEEE ICIP’10, pp. 381–384, Sep. 2010.
[6] P. P. Vaidyanathan, Multirate Systems and Filter Banks.
Prentice-Hall, Englewood Cliffs, NJ, 1993.
[7] M. Iwahashi and H. Kiya, “Non separable 2D factorization ofseparable 2D DWT for lossless image coding,” IEEE ICIP’09,
pp. 17–20, Nov. 2009.
[8] Z. Liu and L. J. Karam, “An efficient embedded zerotree wavelet
image codec based on intraband partitioning,” IEEE ICIP’00,
pp. 162–165, Sep. 2000.
[9] P. G. Howard and J. S. Vitter, “Arithmetic coding for data compression,” Proc. IEEE, vol. 82, no. 6, pp. 857–865, Jun. 1994.