IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.10 OCTOBER 2011

1920

PAPER

Two Dimensional Non-separable Adaptive Directional Lifting
Structure of Discrete Wavelet Transform
Taichi YOSHIDA†a) , Student Member, Taizo SUZUKI†† , Seisuke KYOCHI† , and Masaaki IKEHARA† , Members

SUMMARY
In this paper, we propose a two dimensional (2D) nonseparable adaptive directional lifting (ADL) structure for discrete wavelet
transform (DWT) and its image coding application. Although a 2D nonseparable lifting structure of 9/7 DWT has been proposed by interchanging
some lifting, we generalize a polyphase representation of 2D non-separable
lifting structure of DWT. Furthermore, by introducing the adaptive directional filteringingto the generalized structure, the 2D non-separable ADL
structure is realized and applied into image coding. Our proposed method
is simpler than the 1D ADL, and can select the diﬀerent transforming direction with 1D ADL. Through the simulations, the proposed method isshown to be eﬃcient for the lossy and lossless image coding performance.
key words: two dimensional non-separable lifting structure, discrete
wavelet transform, adaptive directional filtering, lossy and lossless image
coding1.

Introduction

The discrete wavelet transform (DWT) has been a fundamental tool for image and video processing for the last few
decades. It is applied to image coding standard, JPEG 2000
[1], and high quality digital cinema [2]. Despite its success,
DWT has a serious disadvantage. Since they can only transform images along the vertical and horizontal directions byseparable implementation, they fail to provide sparse representation of transforming images which consist of various
angles of directionally-oriented textures except vertical andhorizontal directions. Therefore, if DWT is applied to images which contain a rich directional high frequency component, such as edges and contours, the coding eﬃciency isseverely degraded.
To avoid this degradation, an adaptive directional filtering based on a lifting structure has been proposed [3]–[9].
The adaptive directional filtering can flexibly switch the filtering direction according to the direction of edges and contours, and compression eﬃciency can be improved. Especially, an one dimensional (1D) adaptive directional lifting(ADL) based wavelet transform [5] achieves high compression eﬃciency for the lossy image coding. However, since
1D ADL has to be separately applied twice for two dimensional (2D) signals, it is redundant and produces a distortion of desired filtering directions due to the down-sampling
Manuscript received January 13, 2011.
Manuscript revised May 17, 2011.
†
The authors are with the Department of Electronics andElectrical Engineering, Keio University, Yokohama-shi, 223-8522
Japan.
††
The author is with the College of Engineering, Nihon University, Koriyama-shi, 963-8642 Japan.
a) E-mail: yoshida@tkhm.elec.keio.ac.jp
DOI: 10.1587/transfun.E94.A.1920

between the vertical and horizontal filtering. In this paper,
hence, we propose the 2D direct and adaptive directional filtering based on DWT, called a 2D non-separable ADL structure of DWT.
The proposed structure is realized by introducing an
adaptive directional filtering framework into a 2D direct lifting structure based on DWT. The lifting structure of DWT
has been proposed for the integer-to-integer transform [10].
For 2D signals such as images, a 2D separable lifting structure of DWT is realized by applying the 1D lifting structure
to images twice, vertically and horizontally. Iwahashi et al.
have proposed the 2D direct lifting structure based on 9/7
DWT, by interchanging and merging some lifting in the 2D
separable lifting structure of 9/7 DWT [11], [12]. The new
structure is called a 2D non-separable lifting structure of
9/7 DWT. The non-separable structure requires less rounding operators than the separable one, and is suitable for the
lossless image coding application. In this paper, we generalize the polyphase representation of 2D non-separable lifting
structure based on 2-channel 1D filter banks (FBs) such as
DWT. It contains the class of the 2D non-separable lifting
structure of 9/7 DWT [12]. Our proposed structure can design various 2D non-separable lifting structures.
Furthermore, to improve the eﬃciency of image coding, we develop the generalized polyphase representation
for the adaptive directional filtering. Changing the sampling matrix of the proposed structure, we can change thedirection of the transform. The proposed adaptive directional filtering is realized by changing the sampling matrix
by sub-regions of images, according to feature directions of
the sub-regions. With advantages of the 2D non-separable
structure and the adaptive directional filtering, the proposed
structure improves the performance of the lossy-to-losslessimage coding application. The proposed method is simpler
than the 1D one and can select the filtering directions which
are diﬀerent from 1D ADL. Finally, lossy and lossless image coding results of the proposed structure are shown tovalidate the advantage of the proposed structure.
Section 2 summarizes FB and show a polyphase representation of the 2D separable lifting structure and 1D ADL
structure of DWT. We propose the generalized polyphaserepresentation of the 2D non-separable lifting structure of
DWT in Sect. 3, and its adaptive directional filtering in
Sect. 4. Section 5 shows some image coding results and conclusions are presented in Sect. 6.
Notations: Vectors are denoted by boldfaced lowercase characters, whereas matrices are denoted by boldfacedc 2011 The Institute of Electronics, Information and Communication Engineers
Copyright YOSHIDA et al.: 2D NON-SEPARABLE ADL STRUCTURE OF DWT

1921

uppercase characters. AT and A−1 denote the transpose andthe inverse of the matrix A, respectively. I and 0 are identity
and the null matrices, respectively. M is a 2 × 2 nonsingular
integer matrix. An absolute determinant of the factor M is
described as M = |det(M)|. ↓ M and ↑ M also represent the
down- and up-samplers of M, respectively. Using vectors
z = [z x , zy ]T and k = [k x , ky ]T , a multiplication of vectors
kis defined as zk = zkxx zyy . diag(·) denotes the block diagonal
matrix as⎤⎡⎢⎢⎢A0 0 · · · 0 ⎥⎥⎥⎢⎢⎢⎢ 0 A1 · · · 0 ⎥⎥⎥⎥⎥diag(A0 , A1 , · · · , An ) = ⎢⎢⎢⎢⎢ ..
..
.. ⎥⎥⎥⎥ .
..
⎢⎢⎢ .
.
.
. ⎥⎥⎥
⎦
⎣
0
0 · · · An

2.

Review

2.1 Polyphase Representation of FB
The 1D maximally decimated FB with M-channel can bealso represented by polyphase matrices. E(z) and R(z)are the type-I polyphase matrix of the analysis bank andthe type-II polyphase matrix of the synthesis bank [13].
These polyphase matrices are related to Hk (z) and Fk (z)(k = 0, 1, · · · , M − 1) which denote analysis filters and synthesis filters as
H(z) = [H0 (z), H1 (z), · · · , H M−1 (z)]T= E(z M )d M (z),F(z) = [F0 (z), F1 (z), · · · , F M−1 (z)]T= dTM (z−1 )R(z M ),(1)

where d M (z) = [1, z−1 , z−2 , · · · , z−(M−1) ]T . If the polyphasematrices satisfy the condition as E(z)R(z) = z−n I, the result
is said to be the perfect reconstruction, where n is an orderof the FB. Hence, the synthesis matrix R(z) is designed asz−n E−1 (z−1 ). For simplicity, the synthesis bank is omitted inthis paper.
In a similar way to 1D FB, the 2D maximally decimated FB with M is represented by the polyphase matrixasH(z) = E(zM )dM (z),x ∈ [0, 1) denotes a set of 2 × 1 real vectors x whose theith component satisfies 0 ≤ xi < 1 and mi, j denotes the (i, j)element of M.
2.2 2D Separable Lifting Structure of DWT
1D DWT is classified into 2-channel FB. Its lifting structure
can be expressed in the polyphase representation as follows[10], [13].

HL (z)= Ê(z2 )d2 (z)HH (z)



(3)
0
1 0
s 0
1 Ui (z)Ê(z) =
0 1
Pi (z) 1
0 1/s
i=N−1

This structure with N = 2 is shown in Fig. 1, where R denotes a rounding operator. This figure shows that 1D signals
are divided into even samples and odd samples, sample istransformed with the other sample, and even and odd samples are conclusively output as lowpass and highpass coefficients, respectively. In general, down-arrows from evensignals to odd signals are called a prediction step, and uparrows are called an update step.
The pair of scaling factors can be realized as a lifting
structure [10]. The scaling factors are factorized as





s 0
1 0 1 s−1 1 0
1 s − s2
=
.
(4)
0 1/s
−1/s 1 0 1
1 1
01
Figure 2 show the lifting realization of scaling factors,
where s0 = s − 1, s1 = −1/s and s2 = s − s2 . The lifting structure with rounding operators can transform signals
from integer to integer. Note that scaling parts can also beconstructed by lifting steps.
According to the separable implementation, the 2D
separable lifting structure of DWT can be given by(2)

where M is referred to as a sampling matrix, z = [z x , zy ],z x and zy are the vertical and horizontal delay elements, respectively,

Fig. 1

9/7 DWT.

dM (z) = [z−k0 , z−k1 , · · · , z−kM−1 ]T ,mmmmzM = [z0 0,0 z1 1,0 , z0 0,1 z1 1,1 ]T ,ki is an integer vector of a set Ξ(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)},

Fig. 2

Lifting realization of scaling.

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.10 OCTOBER 2011

1922

Fig. 3

2D separable lifting structure of 9/7 DWT.

⎡
⎤ ⎡⎤⎢⎢⎢ HLL (z) ⎥⎥⎥ ⎢⎢⎢ HL (z x )HL (zy ) ⎥⎥⎥⎢⎢⎢ H (z) ⎥⎥⎥ ⎢⎢⎢ H (z )H (z ) ⎥⎥⎥H(z) = ⎢⎢⎢⎢ HL ⎥⎥⎥⎥ = ⎢⎢⎢⎢ L x H y ⎥⎥⎥⎥⎢⎢⎣ HLH (z) ⎥⎥⎦ ⎢⎢⎣ HH (z x )HL (zy ) ⎥⎥⎦HHH (z)
HH (z x )HH (zy )⎤⎡0 ⎥⎥ 
⎢⎢⎢ HL (zy )⎥⎢⎢⎢H (z )0 ⎥⎥⎥⎥
H (z )⎥× L x= ⎢⎢⎢⎢ H y
HL (zy ) ⎥⎥⎥⎥⎦ HH (z x )⎢⎢⎣ 00
HH (zy ) 2Ê(zy ) 00d2 (zy )=Ê(z2x )d2 (z x ),0d2 (zy )0 Ê(z2y )(5)xwhere d̂2 (zy ) = diag(d2 (zy ), d2 (zy )). From the above relationships (6), (5) is rewritten as 2Ê(zy ) 0
H(z) =
0 Ê(z2y )



0
I
0
sI 0
I Ui (z2x )I×
0 1/s I
0I
Pi (z2x )I I
i=N−1

× d̂2 (zy )d2 (z x ).

(7)
Consequently, the polyphase representation of the above 2D
separable structure is described as
H(z) = E(zM )dM (z), yÊ 0 sI 0
E(z) =
0 Êy 0 1/s I

0

i=N−1
−1 −1 −1 T
dM (z) = [1, z−1
y , z x , z x zy ] ,I Uix I I 0
0 I Pix I I

Lifting direction of 1D ADL.

diag(2, 2). For example, Fig. 3 shows the 2D separable lifting structure of 9/7 DWT. This figure shows that images are
divided into four sets and transformed while maintaining integers.

for the four subband filters, HLL (z), HHL (z), HLH (z) andHHH (z). To define the polyphase matrix of 2D separable
structure, we introduce the relationships as


⎧
⎪
s
0
sI
0
⎪
⎪
⎪
(z
)
=
d̂2 (zy ),
d̂
2 y
⎪
⎪
0
1/s
0
1/sI
⎪
⎪
⎪


⎪
⎪
⎪
1 Ui (z2x )I Ui (z2x )I
⎨
(6)
(z
)
d̂
=
d̂2 (zy ),
⎪
2
y
⎪
⎪
0
1
0
I
⎪
⎪


⎪
⎪
⎪
⎪
1
0
I
0
⎪
⎪
⎪
⎩ d̂2 (zy ) Pi (z2 ) 1 = Pi (z2 )I I d̂2 (zy ),x

Fig. 4,(8)

where Ê j , Pij and Uij ( j : x or y) denote Ê(z j ), Pi (z j ) andUi (z j ). Since the 2D FB is realized by the separable implementation of 1D FB, the decimation matrix M should be

2.3 1D ADL Structure of DWTBased on the lifting structure of 1D DWT, 1D ADL is realized by permitting the other directions of the transform
except horizontal and vertical [5].
Figure 4 illustrates a 2D signal x(n), where n =[n x , ny ]T , and n x and ny are defined as vertical and horizontal indices in 2D signals. In the lifting structure of 1D DWT,
the input signals are divided into even samples xe and odd
samples xo as follows.
xe (n) = x([n x , 2ny ]T )xo (n) = x([n x , 2ny + 1]T )(9)In the prediction step, odd samples xo (n) are predicted fromthe neighboring even samples xe (n) asx̂o (n) = xo (n) + pe (n),(10)

where pe (n) is expressed as




n x − tan θdn x + tan θdpe (n) = pi xe
,
+ xe
ny
ny + 1
pi is a coeﬃcient of filter and θd is arbitrary direction offiltering. Figure 4 shows θd = {π/2, π/4, −π/4}. Next, in the
update step, even samples xe (n) are updated from the newneighboring odd samples x̂o (n) asx̂e (n) = xe (n) + uo (n),(11)

where uo (n) is expressed as




n x − tan θdn x + tan θduo (n) = ui x̂o+ x̂o,ny − 1ny

YOSHIDA et al.: 2D NON-SEPARABLE ADL STRUCTURE OF DWT

1923

⎤
⎡
⎤⎡
y
y
⎢⎢⎢1 U p Uqx −U p Uqx ⎥⎥⎥ ⎢⎢⎢ 1y 0 0 0 ⎥⎥⎥⎥⎢⎢⎢⎢0 1 0
0 ⎥⎥⎥⎥ ⎢⎢⎢⎢P p 1 0 Uqx ⎥⎥⎥⎥⎥⎥⎥ ⎢⎢ x
G p,q (z) = ⎢⎢⎢⎢y⎥0 ⎥⎥⎦ ⎢⎢⎢ Pq 0 1 U p ⎥⎥⎥⎥⎢⎢⎣0 0 1
⎦
⎣
0 0 0
1
0 0 0 1⎤⎡0 0 0⎥⎥
⎢⎢⎢ 1
⎥
⎢⎢⎢ 0
1 0 0⎥⎥⎥⎥⎥.
× ⎢⎢⎢⎢
0 1 0⎥⎥⎥⎥
⎢⎢⎣ 0
⎦
y
y
P p Pqx Pqx P p 1

ui is a coeﬃcient of filters. This set of lifting operations isrepeated and conclusive samples are produced as lowpass
and highpass coeﬃcients.
3.

Polyphase Representation of 2D Non-separable Lifting Structure of DWT

3.1 Generalized Structure
In this paper, we introduce the generalized polyphase representation of the 2D non-separable lifting structure of DWT.
Here, some matrices are defined as follows.




sI 0
s 0
s 0
, Ŝ =,
S = diag,
0 1/sI
0 1/s 0 1/s
1 Uij 1 Uij
I Uij I,
, Ûij =, (12)
Uij = diag
0 1
0 1
0 I




1 0
I 0
1 0
,
,
P̂ij = j.
Pij = diagPij 1 Pij 1
Pi I I
By using these matrices, (8) is rewritten as
0E(z) = S{Uyi Pyi } Ŝi=N−1

{Ûix P̂ix }.

0E(z) = S̃

(13)

(19)

where S̃ = SŜ = diag(s2 , 1, 1, 1/s2 ).
In this section, we propose the generalized polyphaserepresentation of 2D non-separable lifting structure of DWT
by using the relationships (14) and the non-separating factorization (18). We show some examples in the next section.

The generalized polyphase representation is proposed in theprevious section. In this section, we present its examples
based on 5/3 and 9/7 DWT. These DWTs are well known tobe applied to the JPEG 2000.
From (19), the polyphase matrix of 2D non-separable
lifting structure of 5/3 DWT is described as
E(z) = G0,0 (z).

(14)

where p, q = 0, 1, . . . , N − 1. These relationships mean thatsome matrices can be moved, and (13) is rewritten as{Uyi Pyi Ûix P̂ix }.

(15)

i=N−1

G p,q (z) = Uyp Pyp Ûqx P̂qx ,(16)

where p and q are arbitrary integers, substituting (12) in(16), G p,q (z) is consequently described as
U ypGqx
Gqx
U yp Pqx
Pqx

Gyp Uqx
Pyp Uqx
Gyp
Pyp⎤
U yp Uqx ⎥⎥⎥⎥Uqx ⎥⎥⎥⎥⎥,
U yp ⎥⎥⎥⎥⎥
⎦
1

(20)

On the other hand, in the case of 9/7 DWT, the polyphasematrix is factorized from (19), asE(z) = S̃G1,1 (z)G0,0 (z).

(21)

However, the other polyphase matrix can be designed fromthe relationships (14) and the non-separating factorization(18). From (13) with N = 2, the other polyphase matrix isdesigned as
E(z) = SUy1 Py1 Uy0 Py0 × ŜÛ1x P̂1x Û0x P̂0x
= SŜ × Uy1 Py1 × Uy0 Py0 Û1x P̂1x × Û0x P̂0x
= S̃Uy1 Py1 G0,1 (z)Û0x P̂0x .

Some matrices are merged with each other and factorized
into the non-separable structure. If G p,q (z) is defined a product of matrices as⎡ y x⎢⎢⎢G pGq⎢⎢⎢⎢ PypG x
G p,q (z) = ⎢⎢⎢⎢ y qx⎢⎢⎢G p Pq⎣ y x
P p Pq

Gi,i (z),i=N−1

3.2 5/3 and 9/7 DWT

i=N−1

⎧
y y
y y
⎪
⎪
⎪
i Pi Ŝ = ŜUi Pi ,
⎨ y U
y x x
x x y y⎪⎪⎪⎩U p P p Ûq P̂q = Ûq P̂q U p P p ,E(z) = SŜThis non-separating factorization achieves to reduce rounding operators through merging some matrices. Substituting(18) in (15), the generalized polyphase representation of 2D
non-separable lifting structure of DWT is defined as0

Without a loss of generalities, the following relationships are satisfied.

0

(18)

(22)

This structure has been proposed in [14], and is shown in
Fig. 5. Compared with Fig. 3, it is shown to require lessrounding operators. Therefore, it is proven that the nonseparable structure has better compatibilities to the conventional 9/7 DWTs in the JPEG 2000 than the separable structure [14]. In that sense, we design the polyphase matrix of
2D non-separable lifting structure of 9/7 DWT as (22).

(17)

where Gkj = 1 + Pkj Ukj ( j : x or y, k : p or q). Consequently,
G p,q (z) can be factorized into a lifting structure as

4.

2D Non-separable ADL Structure of DWT

4.1 Realization
In this section, we propose the 2D non-separable ADL struc-IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.10 OCTOBER 2011

1924

Fig. 5

2D non-separable lifting structure of 9/7 DWT.
Table 1

Fig. 6

Lifting direction of 2D ADL.

ture of DWT based on the 2D non-separable lifting structureof DWT shown in Sect. 3. The ADL structure can transforma sub-region of images along its direction. Therefore, thestructure eﬃciently reduces the entropy of transformed coeﬃcients and achieves better image coding performance.
By changing the sampling matrix M depending on subregions of images, the ADL structure is realized. Figure 6
shows one lifting operation, where these sampling matrices
are defined as


2 0
2 2
, M1 =
.
(23)
M0 =
0 2
0 2
These dots are pixels, and black dots are transformed withneighbor white dots along arrows. This figure shows thatneighbor pixels used for the lifting operation are changed
by changing the sampling matrix in the sub-region. In otherwords, the direction of the transform can be changed bychanging the sampling matrix.
The arbitrary sampling matrix whose absolute determinant is 4 can be selected. The following sampling matrices
Md (d = 0, 1, . . . , 6) are used in this paper.
Md =







2 0 2 2 2 −2 2 0 2 0 2 4 2 −4
,
,
,
,
,
,
0 2 0 2 0 2 2 2 −2 2 0 2 0 2With changing the sampling matrix, the delay vectors have

Delay vectors.

d

k0

k1

k2

k3

0
1
2
3
4
5
6

[0, 0]T[0, 0]T[0, 0]T[0, 0]T[0, 0]T[0, 0]T[0, 0]T[0, 1]T[1, 1]T[−1, 1]T[0, 1]T[0, 1]T[2, 1]T[−2, 1]T[1, 0]T[1, 0]T[1, 0]T[1, 1]T[1, −1]T[1, 0]T[1, 0]T[1, 1]T[2, 1]T[0, 1]T[1, 2]T[1, 0]T[3, 1]T[−1, 1]T

to be changed. For maintaining the linear phase property offilters, we define the delay vectors to be symmetrical withrespect to a point which is a center of Md . Table 1 shows
the delay vectors corresponding to Md and the directions of
the transform are represented in Fig. 7. It shows that the
proposed structure can transform along various directions
besides vertical and horizontal shown in Fig. 7(a). Since 2D
signals are transformed by E(z) after down-sampling with
Md and some delays, in this proposed structure, a sampling
matrix can share the same transformed system produced by
the polyphase matrix E(z) as the others.
4.2 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 at a index n are described as hd (n). Practically, thedirectional information is assigned to not the pixels but theblocks divided by the quad tree decomposition in order toreduce the side information. For this purpose, R-D optimization is processed as in the following. The full quad tree
T is constructed by applying the quad tree decomposition to
the image until reaching the predefined block size. B, D(B)and R(B) are defined as an arbitrary subtree, a distortion anda rate of bits. The most suitable subtree B∗ with optimal
direction is provided by minimizing the cost function J(B)expressed by
B∗ = min J(B) = min(D(B) + λR(B)),
B

B

(24)

YOSHIDA et al.: 2D NON-SEPARABLE ADL STRUCTURE OF DWT

1925

Fig. 7
Table 2

Add.
Mult.
Round.

where
D(B) =
R(B) =

Sampling matrices.

Reduced numbers of computational costs.
Direction decision
5/3
9/7

Image Transformation
5/3
9/7(1/2)DL(1/2)DTDL−2L(−1/2)LL(3/2)DL(5/4)DL
2DL

L(7/4)L
(17/4)L|hτ,d (n)|2 ,rC (τ) +rT (v),

τ∈B n∈Nτ

τ∈B

v∈B

τ denotes a node of B, Nτ is a support region in images at
a node τ, |hτ,d (n)| is |hd (n)| at a node τ, rC (τ) and rT (v) aredefined as the rate of the entropy encoding highpass coefficients in τ and coding the side information in node in v,
respectively.
4.3 Comparison of Computational Costs
In Table 2, we show the diﬀerences of the computationalcosts between the 1D ADL structure and the proposed 2D
ADL of 5/3 and 9/7 DWTs by subtracting 2D ADL from
1D ADL. “Add.”, “Mult.”, “Round.”, “5/3” and “9/7” mean
addition, multiplication, rounding, 5/3 DWT and 9/7 DWT,
respectively. These numbers depend on the size L of input
images and their lifting steps. Additionally, the numbers
D of direction candidates for lifting should be taken into
account for the lifting direction decision.
Table 2 shows that the proposed structure is simpler
than the 1D ADL in terms of the computational costs. For
the adaptive directional filtering, we need at least three directions which are vertical or horizontal, diagonal from top
left to bottom right, and diagonal from top right to bottom
left. Hence, by substituting D = 3 and adding the numbers of the directional decision and image transformation,
total numbers of the reduced addition and multiplication are(−1/2)L and L, in the case of the 5/3 DWT. The multiplication has more loads in the computation and implementation
than the addition. Therefore, the both proposed structures
are considered to be simpler than the 1D ADL structures.

5.

Simulation

We apply the proposed ADL structure of 5/3 and 9/7 DWTs
into the lossy and lossless image coding application andcompare the coding eﬃciency with the conventional structure of 5/3 and 9/7 DWTs.
For the comparisons, we use the 2D separable lifting
structure of DWT in (8), the 2D non-separable lifting structure of DWT in (20), and the 1D ADL structure of DWTshown in Sect. 2.3. In this section, for simple notations,these conventional structures and the proposed structure aredenoted as 1D DWT, 2D DWT, 1D ADL and 2D ADL, respectively. The 1D and 2D DWTs are applied to images
with 6-level octave decomposition. In cases of the 1D and
2D ADLs, the 1D and 2D DWTs are applied to images at thesecond to sixth levels after the 1D and 2D ADL structuresof DWT are applied at only the first level, respectively† .
For reducing the side information and computationalcosts, the candidate directions are restricted three and sevenin the 5/3 and 9/7 DWTs, respectively. There exists a tradeoﬀ between better compression rate and less computationalcosts. These restrictions are experimentally decided for thevalid comparison.
The embedded zerotree wavelet based on intraband
partitioning (EZW-IP) [15] is used as the encoder. Sincetransformed coeﬃcients are integer and encoded images are
lossless bit streams, lossy bit streams are produced by discarding the backward bits of the bit streams. The side information is encoded by the arithmetic coding algorithm [16].
At the lossy image coding application, the peak signal-tonoise ratio (PSNR) is used as an objective function measuring an image quality of reconstructed images. The PSNR isformulated as
PSNR = 10 log10

2552
,
MSE

(25)

where MSE means the mean square error.

†
The 1D ADL is applied at an only vertical direction in thefirst level for fairy comparison. In that case, the number of sideinformation bits is equal to case of the 2D ADL.

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.10 OCTOBER 2011

1926
Table 3
Zone plate
Barbara
Lena

Image coding results of 5/3 DWT [bpp].
1D DWT

2D DWT

1D ADL2D ADL

6.78
4.87
4.50

6.78
4.86
4.49

6.73
4.84
4.49

6.12
4.78
4.48

Table 4

Zone plate

The 2D non-separable ADL structure of 5/3 DWT is applied
into the lossless image coding. The 2D ADL is realized by
imposing the directional selectivity on the 2D non-separable
lifting structure of 5/3 DWT described in (20), as shown in
Sect. 4. For reducing the side information, the selected directions are experientially-restricted to be three in this paper.
θd in Sect. 2.3 is selected as {π/2, π/4, −π/4} in the 1D ADL
structure of DWT, and Md (d = 0, 1, 2) is selected in the
2D ADL. They are not correctly same directions due to thedown-sampling, but considered to be a reasonable comparison.
Table 3 indicates results of the lossless image coding
application. These values are entropies of compressed images described in bit-per-pixel (bpp), and the entropy of 1D
ADL and 2D ADL includes the encoded side information.
In the case of Zone plate and Barbara, the 2D ADL is eﬃcient for images having rich directional components becauseof the small number of rounding operators and the adaptive
directional filtering. On the other hand, the proposed structure is slightly eﬀective for images whose energy is concentrated on the low frequency region such as Lena.

Lossless [bpp]
1D DWT
2D DWT
6.11
6.08
4.84
4.81
4.54
4.51

1D ADL
4.93
4.81
4.54

2D ADL
5.33
4.75
4.51

Rate

Lossy [dB]
1D DWT
2D DWT

1D ADL2D ADL

0.25
0.5
1
0.25
0.5
1
0.25
0.5
1

12.01
15.19
19.98
27.24
30.46
34.85
32.52
35.52
38.39

13.32
17.91
24.56
27.43
30.82
35.14
32.54
35.60
38.44

13.48
17.50
22.94
27.60
30.94
35.28
32.54
35.52
38.38

Zone plate
BarbaraLena

5.1 5/3 DWT for Lossless

Barbara

Lena

Image coding results of 9/7 DWT.

12.02
15.19
19.98
27.23
30.45
34.84
32.50
35.48
38.34

5.2 9/7 DWT for Lossy-to-Lossless
In a similar way to the 5/3 DWT, the 2D ADL structure of
9/7 DWT is applied into the lossy and lossless image coding.
The 2D ADL is based on (22), with Md (d = 0, 1, · · · , 6),
and tan θd = {0, 1, −1, 2, −2, 0.5, −0.5} in the 1D ADL.
Table 4 indicates results of the lossy and lossless image
coding application. In the lossy, these numbers are PSNR ofreconstructed images in dB, and rates are described in bpp.
The proposed structure improves image coding applicationin the lossy and lossless for the same reason of 5/3 DWT.
Compared with the 1D and 2D DWTs, the 2D ADL shows
more eﬃcient image coding results because of fewer rounding operations and adaptive directional filtering. However,
the adaptive directional filtering is considered to be slightly
eﬀective for some images such as Lena due to the same reason as the 5/3 DWT, as in the discussion in Sect. 5.1. On theother hand, compared with 1D ADL, some coding resultsof the 2D ADL show worse performance because the 1D
and 2D ADLs are not in a same class of the adaptive directional filtering. However, it is an advantage that the structureof the 2D ADL is the simpler than one of the 1D ADL. In
this methods, the image coding performance depends on thedecided directions for sub-regions. In a future work, there
exists a better optimal directional decision for the 2D ADL.

Fig. 8

Original images and reconstructed images.

In Fig. 8, the original and reconstructed images are represented, where the compression rate is 0.25 [bpp]. Compared with the conventional structure which does not havean adaptive directional selectivity, the proposed structure
can represent various directions besides vertical and horizontal. Especially, stripe textures in Fig. 8(f) are represented
clearly.

YOSHIDA et al.: 2D NON-SEPARABLE ADL STRUCTURE OF DWT

1927

6.

Conclusion

In this paper, we generalize the polyphase representation of
the 2D non-separable lifting structure of DWT and propose
ADL of the structure. With maintaining the advantage of the
2D non-separable and the adaptive directional filtering, theproposed structure achieves eﬃcient image coding results.

Taichi Yoshidareceived the B.E. and M.E.
degrees in electrical engineering from Keio University, Yokohama, Japan, in 2006 and 2008,
respectively. He is currently a Ph.D. candidate
at Keio University, Yokohama, Japan, under thesupervision of Prof. Masaaki Ikehara. His research interests are in the field of filter bank design and its image coding application.

Acknowledgments
This work was supported by Global COE Program “HighLevel Global Cooperation for Leading-Edge Platform on
Access Spaces (C12)”.
References[1] ISO/IEC 10918-1, Information technology — JPEG 2000 image
coding system: Core coding system.
[2] A. Descampe, F.O. Devaux, G. Rouvroy, J.D. Legat, J.J. Quisquater,and B. Macq, “A flexible hardware JPEG 2000 decoder for digital
cinema,” IEEE Trans. Circuits Syst. Video Technol., vol.16, no.11,
pp.1397–1410, Nov. 2006.
[3] Ömer N. Gerek and A.E. Çetin, “A 2-D orientation-adaptive prediction filter in lifting structures for image coding,” IEEE Trans. Image
Process., vol.15, no.1, pp.106–111, Jan. 2006.
[4] 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.
[5] 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.
[6] W. Dong, G. Shi, and J. Xu, “Adaptive nonseparable interpolation
for image compression with directional wavelet transform,” IEEE
Signal Process. Lett., vol.15, no.1, pp.233–236, 2008.
[7] Y. Liu and K.N. Ngan, “Weighted adaptive lifting-based wavelet
transform for image coding,” IEEE Trans. Image Process., vol.17,
no.4, pp.500–511, April 2008.
[8] G. Quellec, M. Lamard, G. Cazuguel, B. Cochener, and C. Roux,“Adaptive nonseparable wavelet transform via lifting and its application to content-based image retrieval,” IEEE Trans. Image Process.,
vol.19, no.1, pp.25–35, Jan. 2010.
[9] Y. Tanaka, M. Hasegawa, S. Kato, M. Ikehara, and T.Q. Nguyen,“Adaptive directional wavelet transform based on directional prefiltering,” IEEE Trans. Image Process., vol.19, no.4, pp.934–945,
April 2010.
[10] I. Daubechies and W. Sweldens, “Factoring wavelet transforms into
lifting steps,” J. Fourier Anal. Appl., vol.4, no.3, pp.247–269, 1998.
[11] M. Iwahashi, “Four-band decomposition module with minimum
rounding operations,” IET Electronics Lett., vol.43, no.6, pp.27–28,
March 2007.
[12] M. Iwahashi and H. Kiya, “Reversible 9–7 DWT compatible to irreversible 9–7 DWT of JPEG 2000,” IEICE Techical Report, IE2008257, March 2009.
[13] P.P. Vaidyanathan, Multirate Systems and Filter Banks, PrenticeHall, Englewood Cliﬀs, NJ, 1993.
[14] M. Iwahashi and H. Kiya, “Non separable 2D factorization of separable 2D DWT for lossless image coding,” IEEE ICIP’09, pp.17–20,
Nov. 2009.
[15] Z. Liu and L.J. Karam, “An eﬃcient embedded zerotree wavelet image codec based on intraband partitioning,” IEEE ICIP’00, pp.162–
165, Sept. 2000.
[16] P.G. Howard and J.S. Vitter, “Arithmetic coding for data compression,” Proc. IEEE, vol.82, no.6, pp.857–865, June 1994.

Taizo Suzuki
received the B.E., M.E.
and Ph.D. degrees in electrical engineering from
Keio University, Yokohama, Japan, in 2004,
2006 and 2010, respectively. He joined Toppan
Printing Co., Ltd., Tokyo, Japan, from 2006 to
2008. From 2008 to 2011, he was a Research
Assistant (RA) of Global Center of Excellence(G-COE) at Keio University. Also, he was a Research Fellow of the Japan Society for the Promotion of Science (JSPS) from 2010 to 2011.
Moreover, he was a Visiting Scholar at the University of California, San Diego (Video Processing Group supervised by
Prof. T. Q. Nguyen) from 2010 to 2011. He is currently an Assistant Professor at College of Engineering, Nihon University. His current research interests are M-channel filter bank design and its application for image/video
signal processing.

Seisuke Kyochi
received the B.S. degree inmathematics from Rikkyo University, Toshima,
Japan in 2005 and the M.E. and Ph.D. degrees
from Keio University, Yokohama, Japan in 2007
and 2010, respectively. He is currently with theVideo Coding Group of NTT Cyber Space Laboratories. His research interests in the areas ofwavelets, filter banks and their application to image and video coding.

Masaaki Ikehara
received the B.E., M.E.
and Dr.Eng. degrees in electrical engineeringfrom Keio University, Yokohama, Japan, in
1984, 1986, and 1989, respectively. He was Appointed Lecturer at Nagasaki University, Nagasaki, Japan, from 1989 to 1992. In 1992, hejoined the Faculty of Engineering, Keio University. From 1996 to 1998, he was a visiting researcher at the University of Wisconsin, Madison, and Boston University, Boston, MA. He iscurrently a Full Professor with the Department
of Electronics and Electrical Engineering, Keio University. His researchinterests are in the areas of multirate signal processing, wavelet image coding, and filter design problems.