Open access peer-reviewed chapter

Adaptive Wavelet Packet Transform

Written By

Zuofeng Zhou and Jianzhong Cao

Reviewed: 04 November 2015 Published: 09 December 2015

DOI: 10.5772/61946

From the Edited Volume

Wavelet Transform and Some of Its Real-World Applications

Edited by Dumitru Baleanu

Chapter metrics overview

2,027 Chapter Downloads

View Full Metrics

Abstract

Two-dimensional over-complete wavelet packet transform can better represent the texture and long oscillatory patterns in natural images.

Keywords

  • Adaptive wavelet packet transform
  • Wiener cost function
  • image denoising

1. Introduction

Wavelet with vanishing moments are very effective for representing piecewise smooth images [1]. However, two-dimensional separable wavelets are ill-suited to represent long oscillatory patterns in images with abundant textures, partly owing to their poor directional selectivity in frequency domain. These oscillatory variations of intensity can only be represented by small-scale wavelet coefficients. In some image-processing applications, such as image denoising or image compression, those small-scale coefficients are quantized to zero in the low bit rate image compression and are thresholded or shrunken to zero in image denoising, which degrades compression and denoising performance significantly. To overcome this circumstance, one way is to find the more suitable image representation techniques such as curvelet, contourlet [2], and ridgelet [3]. But these methods need the researchers to design the new directional compact filter or multichannel filter banks, which is also challenging in filter design area. Another way is to improve the idea of wavelet design method to accommodate the new requirement where the over-complete wavelet packet decomposition is proposed.

Over-complete wavelet packet contains a mass of libraries of waveforms, from which the best wavelet packet base can be selected to efficiently represent long oscillatory patterns given the corresponding criterion. For example, in image compression application, the best wavelet packet base is usually found by pruning the full wavelet packet decomposition given a user predefined cost function. Recently, a large variety of cost function have been proposed, such as Shannon’s entropy cost function and vector entropy cost function, which are used in the rate distortion control strategy. On the other hand, different from finding the best tree structure of the wavelet packet decomposition, some researchers devoted themselves for finding the best wavelet packet decomposition base [4] which is equivalent to find the best filter banks of wavelet packet decomposition.

In image denoising application, due to unknown noiseless image as well as a great diversity of filtering methods in the transform domain, selecting the best wavelet packet base is always a difficult problem. Enlightened by the idea of doubly local Wiener filtering method [5] and spatially adaptive wavelet domain shrinkage image denoising algorithms, the best wavelet packet bases selection method using the local Wiener cost function and its application in image denoising is proposed. In this chapter, we will first give the detail of the best wavelet packet-based selection algorithm and then discuss its application in image denoising.

Advertisement

2. Best wavelet packet base selection

Let ψ0(x),ψ1(x) be the wavelet function and scaling functions, the basic idea of wavelet packet function can be defined as:

ψ2n(x)=2kh(k)ψn(2xk),ψ2n+1(x)=2kg(k)ψn(2xk),for n1E1

where h(k),g(k) are the orthonormal filters, respectively. Given a signal s(n) which is satisfied the Nyquist sampling criterion, subspace V0span{ψ0(xl):l} is usually assumed to be the first-level subspace of signal s(n). The subspace with depth j is defined as Vjnspan{ψj,ln(x)=2j/2ψn(2jxl),l}. To understand this subspace easily, the dynamic interval [2jn,2j(n+1)) can be associated with the subspace Vjn. For example, the interval [0,1) is equivalent to V0.

2.1. Two-dimensional wavelet packet bases

The two-dimensional separable wavelet packet functions are defined as the tensor products of two one-dimensional wavelet packet functions, that are,

V0=span{ψ0(xl)ψ0(yp):(l,p)2}ψm,n(x,y)=ψm(x)ψn(y),m,n0,1,E2

Similar to the one-dimensional case, the subspace

Vjm,nspan{ψj;l,pm,n(x)=2jψm(2jxl)ψn(2jyp),(l,p)2}E3

is referred to as the subspace with depth j and a wavelet packet function ψm,n(x,y). Figure 1 gives the subspace of 2D wavelet packet base diagram. It can be seen that each node is divided into two branches. Let us associate the dyadic square [2jm,2j(m+1))×[2jn,2j(n+1)) with the subspace Vjm,n, for example, V0 associates with the square [0,1)2, V11,0 associates with the rectangle [1/2,1)×[0,1/2), and V11,1 associates with the square [1/2,1)2. It has been proved that: if the squares [2jm,2j(m+1))×[2jn,2j(n+1)), (m,n,j)Ω are a partition of the unit square [0,1)2, then the family of functions {Ψj;l,pm,n(x,y):(l,p)2,(m,n,j)Ω} constitutes an orthogonal wavelet packet base of V0.

Figure 1.

The subspace of 2D wavelet packet base

2.2. Best wavelet packet base selection under wiener cost function

Similar to the tree structure illustrated in Fig. 1, 2D wavelet packet decomposition can be easily expressed by the quad-tree structure with the root node {0,0,0}. Each node (m,n,j) (except the last level node) has four child nodes (2m,2n;j+1),(2m,2n+1,j+1),(2m+1,2n,j) and (2m+1,2n+1,j+1). This quad-tree structure facilitates the best wavelet packet decomposition procedure. Given the image and the noise level σ (if unknown, the noise level can be estimated by the MAD estimator in the wavelet domain), the wavelet packet coefficient at the node (m,n,j) under J-level wavelet packet decomposition is represented as yjm,n(p,q),m,n=0,1,,2j1;j=0,1,,J. For each node, its Wiener cost function is computed by

J(m,n;j)=σ2pq[yjm,n(p,q)]2[yjm,n(p,q)]2+σ2,m,n=0,1,,2j1;j=0,1,,J.E4

Assuming all the node in the quad-tree decomposition forms a set Class(A)={Ω={(m,n,j)}, our task is to find a subset Ω* from set Ω which have the smallest total cost function (the summation of the Wiener cost function at all wavelet packet decomposition node).

Similar to most of the search algorithms of the best wavelet packet base, the best wavelet packet base under Wiener cost function is obtained by pruning a J-level full quad-tree from bottom to top. The searching algorithm can be described as follows:

  1. Let S(m,n,J)={(m,n,J)},m,n=0,1,,2J1 represent 22J leaf nodes in the J-level full quad-tree.

  2. For 0j<J and each node (m,n,j) in the j-th level, calculate the corresponding Wiener cost function

J(m,n;j)=σ2pq[yjm,n(p,q)]2[yjm,n(p,q)]2+σ2E5

as well as the summation of the Wiener cost functions of its four child nodes by

J˜(m,n,j)=J(S(2m,2n,j+1))+J(S(2m,2n+1,j+1))++J(S(2m+1,2n,j+1))+J(S(2m+1,2n+1,j+1))BB1
  1. If J˜(m,n,j)<J(m,n,j), then

S(m,n,j)=S(2m,2n,j+1)S(2m,2n+1,j+1)S(2m+1,2n,j+1)S(2m+1,2n+1,j+1)BB2

otherwise, S(m,n,j)={(m,n,j)}.

  1. Calculate the Wiener cost function of each set S(m,n,j) by

J(S(m,n,j))(u,v,r)S(m,n,j)J(u,v,r),m,n=0,1,,2j1,E6
  1. If j>0, set jj1 and return the step (ii); otherwise, output Ω*=S(0,0,0).

The set Ω* is composed of all leaf nodes of the best quad-tree decomposition structure. In this way, given the input noisy image and the noise level, the optimal orthogonal wavelet packet decomposition structure and the minimal total Wiener cost function can be obtained. Figure 2 shows a demo of best wavelet packet decomposition where Fig. 2(a) is its square representation and Fig. 2 (b) is the corresponding tree structure of this best wavelet packet decomposition.

Figure 2.

A demo of best wavelet packet decomposition

Advertisement

3. Image denoising algorithms based on best wavelet packet decomposition

This section gives two image denoising algorithms based on the best wavelet packet decomposition. In the above section, the optimal wavelet packet decomposition structure is obtained under the Wiener cost function. When computing the Wiener function, the noiseless image and the noise level are assumed as known. In practice, this assumption is unreasonable. It is well known that the noise level can be accurately estimated by the MAD estimator from the input noisy image. The key problem is how to estimate the noiseless image. Enlightened by the empirical Wiener filtering and the doubly local Wiener filtering image denoising algorithms, we first filter the noisy image to get the pilot image, and then the pilot image is used to get the best wavelet packet decomposition structure.

It is well known that undecimated wavelet packet decomposition can achieve better image denoising performance than the decimated wavelet packet decomposition. This is owing to the property that they are shift invariance and robustness. So, the undecimated wavelet packet decomposition can ameliorate some unpleasant phenomenon that appears in the maximally decimated wavelet packet decomposition, such as Gibbs-like ringing around edges and specks in smooth region.

In what follows, we will give the detail of the image denoising algorithm using the undecimated wavelet decomposition. Let x(p,q) be a input noisy image of size 2N×2N, the operator Shiftk,l(x) denotes circularly shifting the input image x(p,q) by k indices in the vertical direction and l indices in the horizontal direction, and the operator Unshiftk,l(x) is a similar operation but in the opposite direction. In the proposed algorithm, we first use the decimated best wavelet packet decomposition algorithm to denoise all possible shift versions of the noisy image to get a set of denoised images and then unshifting these denoised images and average them to get the final denoised image. The new algorithm is referred to as the local Wiener filtering using the best undecimated wavelet packet decomposition (LWF-BUWPD), which can be summarized as follows:

  1. Using the local Wiener filtering image denoising algorithm to each shift of input noisy image shift (x(p,q)) to get a pilot image s^(p,q) ;

  2. Given the pilot image and noise level, the best wavelet packet decomposition structure can be obtained by using the searching algorithm in section 2.

  3. Given the best wavelet packet decomposition structure, the empirical energy distribution of the pilot image can be estimated by

Ejm,n(p,q)={1#W(s,t)Ws^j,m,n2(p+s,q+t)}+,(m,n,j)ΩE7

where W and s^j,m,n(p,q) represent the directional window and the pilot image’s best wavelet packet decomposition coefficients, respectively.

  1. Using the estimated energy distributions and noise level, the local Wiener filtering is operated on the base wavelet packet decomposition coefficients of the noisy image, that is,

s˜jm,n(p,q)=Ejm,n(p,q)Ejm,n(p,q)+σ2yjm,n(p,q),(m,n,j)ΩE8

where yjm,n(p,q) are the best wavelet packet decomposition coefficients of the noisy image in the subspace Vjm,n.

  1. Unshift all the shifted denoised images and average them to obtain the final denoised image s˜(p,q)

s˜(p,q)=122Jk=02J1l=02J1Unshiftk,l(s˜k,l)(p,q)E9
Advertisement

4. Experimental results

We choose the 8-bit 512 × 512 grayscale images “Lena” and “Barbara,” and a 256 × 256 texture image, as the test images. In the proposed image denoising algorithm, the best wavelet packet decomposition structure is varied with different shift noisy images and different noise level. For better illustration, the best wavelet packet decomposition structure for different noise level is shown in Fig. 3 for “Barbara” image.

Figure 3.

The best wavelet packet trees for the “Barbara” image with different noise levels: (a) σ=10 ; (b) σ=15 ; (c) σ=20 ; (d) σ=25.

In Table 1 and Fig. 4, we give the denoising performance of the image denoising algorithms using the undecimated best wavelet packet decomposition. The experimental results show that for images of structural textures, for example, “Barbara” and texture images, the proposed algorithm greatly improves denoising performance as compared with the existing state-of-the-art algorithms.

Test image Boat Fingerprint House
Noise level 10 15 20 25 10 15 20 25 10 15 20 25
DLWFDW 33.43 31.47 30.10 29.09 32.21 30.01 28.51 27.34 35.14 33.21 31.91 30.92
DFB-GSM 33.58 31.70 30.37 29.13 32.45 30.14 28.60 27.45 35.35 33.64 32.39 31.40
LWF-BUWPD 33.58 31.69 30.36 29.36 32.51 30.22 28.66 27.56 35.37 33.65 32.42 31.42
Test Images Lena Barbara Texture
Noise level 10 15 20 25 10 15 20 25 10 15 20 25
DLWFDW 35.3 33.5 32.2 31.2 33.9 31.5 29.9 28.6 33.92 31.68 30.11 29.03
DFB-GSM 35.61 33.90 32.66 31.69 34.03 31.86 30.32 29.13 34.83 32.61 30.95 29.71
LWF-BUWPD 35.60 33.87 32.65 31.66 34.35 32.28 30.80 29.63 34.97 32.92 31.72 30.65

Table 1.

The performance comparison of the LWF-BUWPD and several state-of-the-art image denoising algorithms

Figure 4.

(a) The noiseless image (the left top corner), the noisy image (the right top corner, noise level 20), the denoised image by the DFB-GSM algorithm (the left bottom corner, PSNR = 30.93 dB), and the denoised image by the LWF-BUWPD algorithm (the right bottom corner, PSNR = 31.70 dB); (b). Zoomed local regions of the four images in (a).

References

  1. 1. Shui, P.-L., Zhou, Z.-F., and Li, J.-X., “Image denoising based on adaptive wavelet packets using wiener cost function,” IET Image Processing, 2007, 1(3), pp: 311–318.
  2. 2. Minh, D., and Martin. V., “The contourlet transform: an efficient directional multiresolution image representation,” IEEE Transactions on Image Processing, Dec. 2005, 14(12), pp: 2091–2106.
  3. 3. Zhang, B., Jalal M.F., and Starck J.-L., “Wavelets, ridgelets, and curvelets for poisson noise removal,” IEEE Transactions on Image Processing, 2008, 17(7), pp: 1093–2009.
  4. 4. Mahalakshmi, B.V., and Anand, M.J., “Adaptive wavelet packet decomposition for efficient image denoising by using neighsure shrink method,” International Journal of Computer Science & Information Technology 2014, 5(4), pp: 5003–5007.
  5. 5. Shui, P.-L., “Image denoising algorithm via doubly local Wiener filtering with directional windows in wavelet domain,” IEEE Signal Processing Letters, 2005, 12(10), pp: 681–684.

Written By

Zuofeng Zhou and Jianzhong Cao

Reviewed: 04 November 2015 Published: 09 December 2015