SPACE-FREQUENCY QUANTIZATION USING DIRECTIONLETS Vladan Velisavljevi 1 , Baltasar Beferull-Lozano2 , Martin Vetterli3,4 c
Deutsche Telekom, Laboratories, Germany, 2 Universidad de Valencia, Spain,
EPFL, Switzerland, 4 University of California, Berkeley, CA

ABSTRACT

In our previous work [1], we proposed a construction of critically sampled perfect reconstruction transforms with directional vanishing moments (DVMs) imposed in the corresponding basis functions along different directions, called directionlets. Here, we combine the directionlets with the space-frequency quantization (SFQ) image compression method, originally based on the standard two-dimensional (2-D) wavelet transform (WT) and proposed in [2]. We show that our new compression method outperforms the standard SFQ as well as the state-of-the-art compression methods, like SPIHT and JPEG2000, in terms of the quality of compressed images, especially in a low-rate compression regime. We also show that the order of computational complexity remains the same, as compared to the complexity of the standard SFQ algorithm.
Index Terms Directional transforms, Directional vanishing moments, Image coding, Wavelet transforms 1. INTRODUCTION
The standard two-dimensional (2-D) wavelet transform (WT) has become very successful in image compression in recent years because it provides a sparse multiresolution representation of natural images due to the presence of vanishing moments in the high-pass (HP) lters (enforced by imposing zeros at = 0) [3]. This transform is conceptually simple and has a low computational complexity because of the simple separable one-dimensional (1-D) ltering and subsampling operations. For these reasons, the 2-D WT has been adopted in the image compression standard JPEG-2000. However, the performance of the 2-D WT is limited by the spatial isotropy of the basis functions and the construction only along the horizontal and vertical directions, which does not provide enough directionality. For this reason, the standard 2-D WT fails to provide a sparse representation of oriented 1-D discontinuities (edges or contours) in images [3]. These features are characterized by a geometrical coherence that is not properly captured by the isotropic wavelet basis functions. Thus, to provide an efcient representation of contours, the basis functions are required to have directional vanishing moments (DVMs) along more than the two standard directions. Several previous approaches, like curvelets [4], contourlets [5] and bandelets [6], have already addressed this non-trivial task. However, these methods have higher complexity than the standard 2-D WT and require non-separable ltering and lter design. Furthermore, these transforms are often oversampled, thus, making it non-trivial to have efcient image compression methods.
Several recently proposed methods use the lifting scheme in image compression algorithms. This scheme is exploited in [7], where transform directions are adapted pixel-wise throughout images. A similar adaptation is used in [8] and [9], but with more different directions (9 and 11, respectively). In addition, the method in [8] uses the pixel values at fractional coordinates obtained by interpolation. However, even though these methods are computationally efcient and provide good compression results, they show a weaker performance when combined with zerotree-based compression algorithms. In our previous work [1], we designed critically sampled anisotropic basis functions with DVMs across any two directions with rational slopes, which we called directionlets. Our basis construction retains the separable processing and the computational simplicity of the standard 2-D WT. We showed that directionlets outperform the standard 2-D WT in non-linear approximation of images while keeping a similar complexity. In [10], we showed that directionlets imrove the performance of the compression method based on the correlation of wavelet coefcients across scales using zerotrees [11]. Here, our main goal is to design and implement a compression method based on the spacefrequency quantization (SFQ) [2] using directionlets instead of the WT. We show that our new method outperforms the standard SFQ as well as the state-of-the-art image coding algorithms, like SPIHT [12] or JPEG-2000. At the same time, our method preserves the same order of computational complexity as the standard SFQ. In Section 2, we briey review the main principles of the standard SFQ method. Then, in Section 3, we present the details of our new compression method, which combines directionlets and the standard SFQ. We compare the results achieved by our method to the results obtained by the standard SFQ, SPIHT and JPEG-2000 in Section 4. Finally, we conclude in Section 5.

2. SPACE-FREQUENCY QUANTIZATION
The SFQ image compression method for images was originally proposed in [2]. Here, because of lack of space, we only briey revisit the basic concept of the SFQ. The main idea behind SFQ is to minimize a mean-square error (MSE) distortion measure of the reconstructed image for a given bit-rate constraint using Lagrangian optimization. The algorithm exploits the multi-scale correlation among wavelet coefcients produced by the standard 2-D WT. The coefcients are structured in multi-scale trees (zerotrees) so that one tree consists of the coefcients from different transform scales at the same spatial location (see Fig. 1). Each tree has a root at the corresponding coefcient from the coarsest scale. The same tree-structure is used in [11],

3. COMPRESSION ALGORITHM

LH1 HH1
LH2 HH2 LH3 HH3 HL2 LL HL3 HL1
Fig. 1. The wavelet coefcients are grouped in zerotrees to exploit the
multi-scale correlation. The zerotrees have originally been proposed in [11].

Entropy coder

data map
R-D based SFQ optimization
Images have geometrical oriented features that vary over space. For that reason, we have to adapt the DVMs of directionlets locally to each neighborhood. Recall that directionlets can have up to 2 DVMs.1 Thus, this implies a need for spatial segmentation as a way of partitioning image into smaller segments with one or a few dominant directions per segment. In our algorithm, we use the quad-tree segmentation, as the simplest method in the sense of encoding efciency. The transform directions (and DVMs) are adapted independently in each spatial segment allowing for more efcient capturing of geometrical information. However, the separate processing of segments may cause some blocking effect in the compressed images, especially noticeable at low bit-rates. Hence, a post-processing is required to remove this effect, as explained in the sequel. Next, we present the basic concept of our compression algorithm (see [13] for detailed explanations). Then, we give a brief overview of the deblocking algorithm originally proposed in [14] for JPEG compressed images and, nally, we analyze the computational complexity of the full method.

3.1. Denition of the Algorithm Fig. 2. The standard SFQ encoding consists of four blocks: the 2-D WT,
SFQ optimization, quantization and entropy coding. The task of the SFQ optimization is to pick the optimal subset of retained transform coefcients in a R-D sense. These coefcients are quantized in the subsequent step. The locations of retained coefcients are transmitted as a side information.
whereas a similar one is exploited in [12]. In the process of the SFQ encoding, a subset of wavelet coefcients is discarded (set to zero), whereas the rest is quantized using a single uniform scalar quantizer. The main tasks of the SFQ are (1) to select the subset of coefcients that should be discarded and (2) to choose which quantization step size should be used to quantize the retained coefcients. In both tasks, Lagrangian optimization is used to select the optimal solution in a rate-distortion (R-D) sense. The locations of the retained coefcients are encoded and sent as a map information, whereas the quantized magnitudes are entropy coded. The block diagram of the encoder is shown in Fig. 2. The optimization process consists of three phases: (a) spacefrequency tree pruning, (b) predicting the map and (c) joint optimization of the quantizers. Notice that, even though the optimal result of the tree pruning is inuenced by the bit-rate spent for predicting and encoding the map in (b), the optimization process in (a) is assumed to be independent and is updated in the subsequent phase. In the rst optimization phase (a), all nodes in the full depth multi-scale tree are checked bottom-up if it is cheaper in a R-D sense to keep or to zero out the descendant nodes. The process is iterated on the resulting pruned multi-scale tree until the convergence is reached, that is, until no new node is pruned. In the second phase (b), the locations of the retained nodes are encoded as a map information using a predictive scheme based on the variance of parent nodes. Finally, in the last phase (c), the previous optimization process (the phases (a) and (b)) is run exhaustively for each value of the quantization step size q from an ad-hoc optimized list {q : q = 7.5 + 0.1 k, k = 1, 2,. , 245} for the scaling and wavelet coefcients and the value that minimizes the Lagrangian cost is chosen as optimal. The quantized coefcients are encoded using an adaptive entropy coder.
Even though the construction of directionlets, as proposed in [1], allows for anisotropy and DVMs along any two directions with rational slopes, we apply two restrictions on the transform: (1) only the isotropic realizations are allowed and (2) the transform direction pairs are taken only from the set D = {(0 , 90 ), (0 , 45 ), (0 , 45 ), (90 , 45 ), (90 , 45 )}. The reason for the rst restriction is in a better compression performance with natural images in the case of isotropic segmentation (like quad-tree). The second restriction is imposed to prevent the constructions of directionlets that lead to more than one coset in the transform, since such constructions result in a less efcient image representation (see [1] for more details). The depth of the multi-scale decomposition in the transform is ad-hoc optimized to 5 levels. The ltering operations are implemented using the 1-D biorthogonal 9-7 lter-bank [15]. Since a wider interval of the target compression bit-rates is allowed, as compared to the standard SFQ, the quantization step size is chosen from an extended list of values. The new extended list is given by Q = {5.0 + 0.5 k, k = 1, 2,. , 245}. The compression algorithm consists of several embedded optimization phases based on minimization of the Lagrangian cost.2 First, spatial segmentation is applied on the entire image in the original domain until a preselected maximal depth is reached and, then, the transform is applied on each segment separately using the transform directions from the list D. For each segment and combination of transform directions, the optimal encoding is found following the same principles as in the standard SFQ optimization phases [2] (referred to in Section 2 as phases (a) and (b)). The best transform

1 For the reasons of lack of space, we do not review the construction of directionlets in detail (see [1] for more details). 2 Notice that directionlets retain orthogonality from the standard WT allowing for conservation of the mean-square error (MSE) in the transform domain. Thus, they can be fully implemented in Lagrangian optimization-based methods. Notice also that, although the conservation of the MSE does not hold exactly for the biorthogonal 9-7 lter-bank used in the experiments, the difference of the MSE is small enough and the optimization process is still valid.
directions that minimize the Lagrangian cost are found for each segment and the spatial quad-tree is pruned bottom-up to the optimal solution. Finally, the optimal quantization step size is chosen from the list Q. The full algorithm is presented next. Step 0: Set Slevel 0, Step 1: If Slevel < maxSlevel, then: Apply quad-tree segmentation in the original domain, For each of the 4 generated segments go recursively to Step 1 with Slevel Slevel + 1, Step 2: For each pair of transform directions from the list D: Apply directionlets to each segment using the isotropic construction and build the zerotrees, Quantize the LP coefcients using all values qLP Q and choose the one that minimizes the Lagrangian cost, For each qHP Q, apply the standard SFQ, compute and record the resulting Lagrangian costs, Choose the best qHP that minimizes the Lagrangian cost, Step 3: Choose the best pair of transform directions that minimizes the Lagrangian cost, Step 4: If Slevel < maxSlevel, then: If the Lagrangian cost of the current segment is smaller than the sum of the Lagrangian costs of its children-segments, then keep only the current segment and discard the childrensegments, Otherwise, keep its children-segments and set the Lagrangian cost of the current segment to be the sum of the Lagrangian costs of the children-segments, Step 5: Encode the quantized coefcients and map information for each segment using an adaptive arithmetic coder. The variable maxSlevel determines the maximal segmentation depth and is chosen a priori. In our experiments, maxSlevel = 3. Notice that the jump in Step 1 is not a loop, but a recursive call, where newly generated smaller segments are forwarded as arguments in each call. The optimal choices of the spatial segmentation, transform directions for each segment and the quantization step sizes are encoded as side information that is added to the output bit stream. The cost of these side information bits is added to the total Lagrangian cost of encoding segments and is used when the optimal segmentation is calculated. (a) (b)

Fig. 3. The optimal segmentation and choice of transform directions in
each segment are found using Lagrangian optimization. These solutions are obtained for compression of the images (a) Lena at the target bit-rate 0.05bpp and (b) Barbara at 0.12bpp.
3.3. Computational Complexity
In [10], we showed that the order of computational complexity (or the order of the number of arithmetic operations) of applying directionlets to an N N image using L-tap 1-D lters is given by O(LN 2 ). Here, we show that our method increases the computational complexity of the standard SFQ only up to a constant and, thus, retains the same order. The increase of the order is generated by two factors: (1) the two additional optimization phases (over spatial segmentation and directions) and (2) the deblocking algorithm. The two optimization phases contribute to the total complexity in the two multiplicative constants. The optimization over spatial segmentation increases the complexity (maxSlevel + 1) times, whereas the optimization over directions contributes in the constant |D|. Notice that these constants have small values in our experiments and do not depend on the image size. The deblocking algorithm carries more multiplication and addition operations because of the implemented forward and inverse overcomplete 2-D WT. However, the computational complexity remains of the order O(N 2 ). Thus, the total computational complexity is equal to the complexity of the standard SFQ multiplied by a constant, which does not depend on the image size.

4. RESULTS

We compare the performance of our compression method to the performance of the standard SFQ and the state-of-the-art methods SPIHT [12] and JPEG-2000 when applied to several standard test images. The comparison is given in terms of both the visual and numerical (PSNR) quality. As explained in Section 3.1, the optimal spatial segmentation and transform directions are found using Lagrangian optimization. Fig. 3 shows a result of this optimization process in the case of the images Lena and Barbara compressed at the bit-rates 0.05bpp and 0.12bpp, respectively. Notice that the chosen directions are aligned to the locally dominant directions in the segments of the image. The results of compression of the images Lena and Barbara using our method, the standard SFQ, SPIHT and JPEG-2000 are compared in Fig. 4. Our method outperforms all these methods in the entire bit-rate interval shown in the graphs. The gain is especially signicant at low bit-rates (up to 0.8dB). The corresponding reconstructions of the two images are shown in Fig. 5 for the compression at the bit-rate 0.1bpp using our method and the standard SFQ. The obtained PSNR factors are 30.92dB and 30.17dB for Lena and

3.2. Deblocking

Because of the separated processing of spatial segments, the compressed images may be affected by a blocking effect, which is visible as sharp articial edges along the segment boundaries. This effect is especially severe in the case of compression at low bit-rates. The same issue appeared in the JPEG standard in the 90s and, since then, there have been many successful deblocking algorithms. We use the algorithm proposed in [14], which is based on thresholding oversampled wavelet coefcients. The visual quality of the reconstructed images is importantly improved (as shown in Fig. 5), even though the impact on the MSE is negligible.
PSNR (dB) 0 0.2 0.4 0.6 bitsperpixel (bpp) 0.Directionlets + SFQ SFQ SPIHT JPEG 2000 PSNR (dB) 0 0.2 0.4 0.6 bitsperpixel (bpp) 0.Directionlets + SFQ SFQ SPIHT JPEG 2000
25.34dB and 24.58dB for Barbara, respectively. Both the numerical and visual quality of the images obtained by our method are better than those obtained by the standard method. Moreover, the artifacts that appear in the low bit-rate compressed images are oriented along locally dominant directions and are, thus, less visually annoying as compared to the standard reconstruction. 5. CONCLUSION We have proposed a novel adaptive image compression algorithm that combines the SFQ method proposed in [2] and directionlets. In our algorithm, image is segmented using the quad-tree segmentation method and transform directions are adapted to dominant directions in each segment. The segmentation and the choice of transform directions are optimized in a R-D sense using Lagrangian optimization. We showed that our method outperforms the standard SFQ and also the state-of-the-art image coding methods, like SPIHT or JPEG2000, with no signicant increase of computational complexity.
6. REFERENCES [1] V. Velisavljevi , B. Beferull-Lozano, M. Vetterli, and P. L. Dragotti, Directionc lets: Anisotropic multi-directional representation with separable ltering, IEEE Trans. Image Processing, vol. 15, pp. 19161933, July 2006. [2] Z. Xiong, K. Ramchandran, and M. T. Orchard, Space-frequency quantization for wavelet image coding, IEEE Trans. Image Processing, vol. 6, pp. 677693, May 1997. [3] S. Mallat, A Wavelet Tour of Signal Processing. San Diego, CA: Academic Press, 1997. e [4] E. J. Cand` s and D. L. Donoho, Curvelets - a surprisingly effective nonadaptive representation for objects with edges, in Curve and Surface Fitting, A. Cohen, C. Rabut, and L. L. Schumaker, Eds. Saint-Malo: Vanderbilt University Press, 1999. [5] M. N. Do and M. Vetterli, The contourlet transform: An efcient directional multiresolution image representation, IEEE Trans. Image Processing, vol. 14, pp. 20912106, Dec. 2005. [6] E. L. Pennec and S. Mallat, Sparse geometric image representations with bandelets, IEEE Trans. Image Processing, vol. 14, pp. 423438, Apr. 2005. [7] O. N. Gerek and A. E. Cetin, A 2-D orientation adaptive prediction lter in lifting structures for image coding, IEEE Trans. Image Processing, vol. 15, no. 1, pp. 106111, Jan. 2006. [8] W. Ding, F. Wu, and S. Li, Lifting-based wavelet transform with directionally spatial prediction, in Picture Coding Symposium (PCS2004), San Francisco, CA, Dec. 2004.

Fig. 4. The numerical comparison of the compression performance in terms
of PSNR. (a) The original images Lena and Barbara. (b) The results obtained by our method, the standard SFQ, SPIHT and JPEG-2000. Our method outperforms the standard SFQ as well as the other two methods.
[9] C.-L. Chang and B. Girod, Direction-adaptive discrete wavelet transform via directional lifting and bandeletization, in Proc. IEEE International Conference on Image Processing (ICIP2006), Atlanta, GA, Oct. 2006. [10] V. Velisavljevi , B. Beferull-Lozano, M. Vetterli, and P. L. Dragotti, Low-rate c reduced complexity image compression using directionlets, in Proc. IEEE International Conference on Image Processing (ICIP2006), Atlanta, GA, Oct. 2006. [11] J. M. Shapiro, Embedded image coding using zerotrees of wavelet coefcients, IEEE Trans. Signal Processing, vol. 41, pp. 34453463, Dec. 1993. [12] A. Said and W. A. Pearlman, A new, fast, and efcient image codec based on set partitioning in hierarchical trees, IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 243250, June 1996. c [13] V. Velisavljevi , B. Beferull-Lozano, and M. Vetterli, Space-frequency quantization for image compression with directionlets, IEEE Trans. Image Processing, to appear. [14] Z. Xiong, M. T. Orchard, and Y.-Q. Zhang, A deblocking algorithm for JPEG compressed images using overcomplete wavelet representations, IEEE Trans. Circuits Syst. Video Technol., vol. 7, no. 2, pp. 433437, Apr. 1997. [15] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, Image coding using wavelet transform, IEEE Trans. Image Processing, vol. 1, no. 2, pp. 205220, Apr. 1992.
Fig. 5. The reconstructions of the two images are obtained by the compression at 0.1bpp using (a) the standard SFQ (30.17dB for Lena and 24.58dB for Barbara) and (b) our method (30.92dB and 25.34dB). Our new method provides better reconstructions than the standard SFQ at the same bit-rate. The artifacts are aligned with the locally dominant directions in the images and are less visually annoying as compared to (a).