Direction Scalability of Adaptive Directional
Wavelet Transform: An Approach Using
Block-Lifting Based DCT and SPIHT
Yuichi Tanaka, Madoka Hasegawa, Shigeo Kato

Taizo Suzuki, Masaaki Ikehara

Dept. of Information Science
Utsunomiya University
Utsunomiya, Tochigi 321-8585 Japan
Email: {tanaka, madoka, kato}@is.utsunomiya-u.ac.jp

Dept. of Electronics and Electrical Engineering
Keio University
Yokohama, Kanagawa, 223-8522 Japan
Email: {suzuki, ikehara}@tkhm.elec.keio.ac.jp

Abstract— Adaptive directional wavelet transform is an effective alternative of the traditional 2-D wavelet transform for image coding. It
is able to transform an image adaptively along diagonal orientations aswell as conventional vertical/horizontal directions. However, it requires totransmit transform direction information to the decoder side. For image
coding at very low bitrates, the bit budget of the direction information
degrades a reconstructed image quality. In this paper, a method toconstruct a scalable bitstream for transform directions is presented. We
utilize the fact that the matrix yielded by transform direction indices stillcontains the original image characteristics. The matrix is transformed bya block-lifting based DCT, then encoded by SPIHT to yield a scalable
bitstream. Our method is effective for very low bitrate image coding, andis comparable to the non-scalable one for middle-to-high bitrates.

I. I NTRODUCTION
In image and video processing using wavelet transform (WT),
multiresolution decomposition is one of the most important features[1]–[3]. It represents an image by several multiresolution subbands.
Since most images have higher energy in low-frequency subbands
than high-frequency ones, the decomposition is very effective forcompression, denoising, etc.
Traditionally, 2-D WT is based on 1-D filterings along verticaland horizontal directions. However, edges usually exist along various
directions. Those limited transform directions cause poor directional
selectivity in the traditional 2-D WT, especially in compression
where the high-frequency subbands are often quantized coarsely.
Consequently, the reconstructed image has significant blurry artifacts.
Adaptive directional WT with lifting implementation [4], [5] is
one of the most efficient transforms against the directional selectivity
problem, and it yields a multiresolution image fully compatible withthat of the traditional WT. It applies directional lifting in each lifting
step. Prediction and updating steps for directional lifting can be inseveral diagonal orientations as well as traditional vertical/horizontal
ones. Lifting factorization always guarantees perfect reconstruction
even for directional lifting steps. As a result, it is regarded as a goodalternative for the 2-D WT.
The authors have proposed an efficient realization of the adaptive
directional WT based on prefilterings of an original image [6]–[8].
The obtained subbands by the prefilterings are used as “referenceframes” to calculate transform directions. The method succeeds toreduce the computation complexity significantly compared with thatof the previously proposed ones in spite of the comparable image
coding performance and simple framework.
However, the adaptive directional WTs share one problem about
the transform direction information. Especially at very low bitrates,
bitrates for transform directions require high percentage comparedto the target bitrates. Finally, the reconstructed image has a lot of

978-1-4244-5309-2/10/$26.00 ©2010 IEEEFig. 1. Directions for the directional WT. Black pixels correspond a row tobe transformed.

annoying artifacts, or sometimes we cannot spend any bits for image
textures. Rate-dependent direction determination [5] can partly solve
the problem since it provides associated transform direction data fora specific target bitrate. Unfortunately, the bitstream for transform
directions cannot be an embedded one. As a result, the rate-dependent
determination does not provide a good trade-off between the bitrate
for the associated direction information and image textures especiallyat very low bitrate.
In [9], an approach has been proposed to tackle this problem. It
first calculates transform directions for some target bitrates, and thenit merges them to construct a scalable bitstream of the transform
directions. It has a layered or level-unit structure, hence the adaptive
directional WT can be efficiently used from low to high bitrates.
Unfortunately, its structure to yield a scalable bitstream is complex
and it still requires to calculate K transform direction sets for K
quality layers of the directions.
In this paper, we present a very simple approach to represent a
scalable bitstream of transform directions for the adaptive directional
WT. It is based on our prefiltering-based method [6]–[8]. The keyof this work is to recognize the matrix obtained from indices oftransform directions as a small image which preserves original image
characteristics. A block-based integer transform, called block-lifting
based DCT (BL-DCT) [10], is used to transform the direction matrix.
Moreover, SPIHT progressive encoder is employed to yield a scalable
bitstream. In the experimental results, our method shows significant
image quality improvements at very low bitrates compared with thenon-scalable approach.

3044

Fig. 2.

Framework of D1F-WT. The arrowheads in the reference frames represent the main directions of the diagonal lines in them.

II. D IRECTIONAL L IFTING AND A DAPTIVE D IRECTIONALWAVELET T RANSFORM
A. Directional Lifting
In this paper, we consider the directional lifting for integer pixel
positions [4]. Hereafter, we define the notations of the transform
directions of directional lifting as the relative pixel position fromthe pixel to be transformed. Some typical directions are illustrated inFig. 1 where the direction for the separable WT (SWT) is defined as(0, 1).
Let x(m, n) and (l0 , l1 ) denote the pixel value at (m, n) and atransform direction, respectively. A prediction step with the vertical
downsampling is represented ash(m, 2n + 1) = x(m, 2n + 1) − P (m, 2n)(1)where h(m, 2n + 1) represents a highpass branch of the directional
lifting step andP (m, 2n) = pi (x(m+l0 , 2n+1−l1 )+x(m−l0 , 2n+1+l1 )) (2)in which pi is a coefficient for this prediction step. An updating stepis given byl(m, 2n) = x(m, 2n) + U (m, 2n + 1)

directional filtering stage, which transforms an input image before
calculating transform directions. These directional filters extract directional information from the image and resulting subbands are used
as reference frames to calculate transform directions of the adaptive
directional WT since these reference frames indicate the positionsof diagonal lines in the image. Finally, both of the multiresolution
image and the direction data are used for image coding.
The reference frames are only used on the analysis side to calculate
the transform directions. Hence, the synthesis side of this framework
is exactly the same as that of the previously proposed ones [4], [5]. In
this paper, the directional filtering stage simply uses directional WT
highpass filters along two fixed directions (1, 1) and (−1, 1). We callthis adaptive directional WT as D1F-WT, which is the acronym ofDirectional 1-D Filtering [7], [8].
III. B LOCK -L IFTING BASED DCTBlock-lifting based DCT (BL-DCT) is a DCT based integer transform which has an arbitrary block size M (M = 2n , n ∈ N) andachieves higher compression ratio than conventional integer DCTs
since it can merge many rounding operators [10]. M -channel BLDCT type-II is expressed by

(3)

[M ]
CII = P

where l(m, 2n) represents a lowpass branch andU (m, 2n + 1) = ui (h(m + l0 , 2n − l1 ) + h(m − l0 , 2n + l1 )), (4)in which ui is an updating coefficient. Clearly these lifting steps are
perfect reconstruction and can be cascaded with other lifting steps
similar to SWTs. The resulting subbands are compatible with thoseusing the SWTs. Note that the even (odd) row to be transformed
requires neighboring odd (even) rows in each lifting step for perfectreconstruction. Therefore, the directions (1, 2), (-1, 2), etc. cannot
be transformed without interpolating pixels. For more generalized(fractional-pel) representations of directional lifting steps, please referto [5].
B. Adaptive Directional Wavelet Transform with Prefiltering
We have recently proposed an efficient realization of the adaptive
directional WT [6]–[8]. Its analysis side framework is shown in Fig.
2. Different from the other frameworks [4], [5], our scheme has aI00−X3

I0X2I

IX10II0X0I



I00J



(5)
where P and I are a permutation√ [M/2]matrix and the identity√ matrix,[M/2]
respectively, and X0 =2CII− I, X1 = −1/ 2CIII ,√ [M/2]2[M/2][M/2] [M/2]− CIIand X3 = CIV CII . Similarly,
X2 = 2CII
M -channel BL-DCT type-IV is presented by



[M ]

CIV =

V0 V1I 0=0 −I
V1T V2I Y00 I

I 0Y1 I

I Y00 I



where V0 = V0T , V2 = V2T = −V1−1 V0 V1 , Y0 = −V1T and
Y1 = (I − V0 )V1−T . The integer-to-integer transform is obtainedby applying rounding operators for every block-lifting step. Note that(5) is not a complete lifting structure yet due to X3 . We can achieve
[M ]
[M ]
the completeness by iterating lifting factorization of CII and CIV
in X3 shown as Fig. 3. In this paper, the eight-channel BL-DCT isused to transform the direction matrix.

30453028

PSNR (dB)

26
24
22
20

Fig. 3.

M -channel BL-DCT (white circles: rounding operations).

1816(3, 1)(2, 1)(1, 1)(1, 3)(0, 0)(-1, 3)(-1, 1)(-2, 1)(-3, 1)

00.1

0.2

0.3

bpp
24

PSNR (dB)

22(a)
BL-DCT

SWT
D1F-WTsD1F-WT(a)sD1F-WT(b)

20

18
SWT
D1F-WTsD1F-WT(a)sD1F-WT(b)

16

SPIHT

Transform direction matrix
14(b)The D1F-WT calculates its transform directions in a block-based
fashion. They constructs a transform direction matrix whose eachelement contains an index value of the transform direction. Conventionally, a direction vector is obtained by raster scanning of thematrix, and then the vector is encoded by runlength coding [7], [8].
However, the resulting vector does not have a rate-scalable property.
For very low bitrate image coding, the non-scalable direction data
severely affect to a reconstructed image quality since we can spend
very few bits for textures at that rate. We resolve this problem byusing dual SPIHT encoding that one is used for textures and the otherfor transform directions.
A transform direction matrix for Barbara by the D1F-WT isdepicted in Fig. 4(a). Clearly a transform direction corresponds to theimage feature itself. Consequently, the direction matrix is regarded
as a small image. Thus, we simply transform the direction data by
the BL-DCT and the transformed image is encoded by the scalable
encoder SPIHT. The framework of direction matrix transformation isshown in Fig. 4(b).
In the synthesis side, the direction matrix is reconstructed byusing a received scalable bitstream. Indeed a compressed direction
matrix does not match the actual one. Therefore, the advantage ofthe scalable direction is for the very low bitrate case. Additionally,the transform direction matrix is usually very smaller than the original
image. For example, if we determine the directions for every 16 × 16

0.1

0.2

0.3

bpp

Fig. 4.
Transformation of direction matrices. (a) a transform direction
example for Barbara. (b) Framework of scalable encoding of the direction
matrix.

IV. D IRECTION S CALABILITY U SING BL-DCT AND SPIHT

0Fig. 5.

PSNR comparisons. (Top) Barbara. (Bottom) Bike.

block in a 512 × 512 image, the transform direction matrix is of thesize 32 × 32. For such a small image, block-based transform is moresuitable than the normal filter banks (e.g., 9-7 filters) which requires
signal extensions at image boundaries. Moreover, integer transforms
are desired since a transform direction matrix strictly contains onlyinteger values. They are the reason that we apply the BL-DCT to thedirection transformation.
Our BL-DCT based approach requires a simple structure comparedwith the previous layer/level-unit based method [9]. It can be appliedfor tree-based adaptive directional wavelet transform [4], [5] whichconstructs a tree for transform directions by using a cost function with
Lagrangian multiplier λ. The resulting tree is highly rate-dependent,
thus in the scalable transform direction case, optimal trees for some
λ’s are first constructed and then they are utilized to obtain a scalable
bitstream. In contrast to that, we just need to calculate one transform
direction matrix for high bitrates. Then the BL-DCT and SPIHT canconstruct a scalable direction matrix for low bitrates.
V. E XPERIMENTAL R ESULTS
In this section, our proposed approach is applied for image coding
and compared with the SWT and the non-scalable D1F-WT [7]. Bothof the adaptive directional WTs are based on D1F-WT. Two 512 ×
512 images, Bike and Barbara, are used for this experiment. We
tested two scalable D1F-WT; one spends 0.1 bpp for the 32 × 32
transform direction matrix, whereas the other reconstructed the matrix

3046

Fig. 6.

Comparison of reconstructed image qualities. From left to right, SWT, D1F-WT [7], sD1F-WT(a) and sD1F-WT(b).

losslessly. We refer these two cases as sD1F-WT(a) and sD1F-WT(b),respectively.
Fig. 5 shows PSNR comparisons of two images. Clearly in very
low bitrates, sD1F-WT(a) shows comparable performance to theSWT, whereas the D1F-WT and the sD1F-WT(b) are significantly
worse than these two transforms. In 0.1 bpp or higher, the D1FWT and the sD1F-WT(b) present very similar PSNRs and theyoutperforms the SWT and the sD1F-WT(a). The reconstructed visualquality of Barbara image is compared in Fig. 6. It is clear that thereconstructed images of the SWT and the sD1F-WT(a) are better in
0.01–0.02 bpp. Especially in 0.01 bpp, only these two transforms
could reconstruct the image. In contrast to that, the D1F-WT andsD1F-WT(b) preserve textures in the image better than the other twofor 0.1 bpp.
Note that we can estimate an optimal truncation point of thedirection bitstreams by using the similar method to [9]. Therefore, theproposed approach can choose the best one between the sD1F-WT(a)and (b). The bitstream for the direction data is easily embedded intothat for the texture data. As a result, the sD1F-WT can achieve good
performance from very low to high bitrates.
VI. C ONCLUSIONSIn this paper, we propose a simple approach to obtain a scalable
bitstream for transform directions of adaptive directional WT. It
uses the BL-DCT and SPIHT to make a scalable bitstream fromthe viewpoint that the transform direction matrix can be recognized
as a small image. In the experimental results, our method shows apossibility of a flexible bitrates for the direction matrix. Especiallyin very low bitrates, our scalable method presented significant image
quality improvements than the non-scalable one.
R EFERENCES[1] P. P. Vaidyanathan, Multirate Systems and Filter Banks. NJ: PrenticeHall, 1993.
[2] M. Vetterli and J. Kovačevic, Wavelets and subband coding.
NJ:
Prentice-Hall, 1995.
[3] G. Strang and T. Q. Nguyen, Wavelets and Filter Banks. MA: WellesleyCambridge, 1996.
[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, 2007.
[5] W. Ding, F. Wu, X. Wu, S. Li, and H. Li, “Adaptive directional liftingbased wavelet transform for image coding,” IEEE Trans. Image Process.,
vol. 16, no. 2, pp. 416–427, 2007.
[6] Y. Tanaka, M. Hasegawa, and S. Kato, “Highpass-filtering based adaptive
directional wavelet transform,” in Proc. 27th Picture Coding Symposium,2009.
[7] Y. Tanaka, M. Hasegawa, S. Kato, M. Ikehara, and T. Q. Nguyen,“Adaptive directional wavelet transform using pre-directional filtering,”
in Proc. ICIP’09, 2009, pp. 1–4.
[8] ——, “Adaptive directional wavelet transform based on directional
prefiltering,” IEEE Trans. Image Process., accepted, 2010.
[9] T. Xu, C.-L. Chang, and B. Girod, “Scalable direction representation forimage compression with direction-adaptive discrete wavelet transform,”in Proc. Visual Communication and Image Processing, 2007.
[10] T. Suzuki and M. Ikehara, “Design of Block Lifting-Based Discrete
Cosine Transform Type-II and IV,” in Proc. DSP/SPE 2009, 2009, pp.
480–484.

3047