prev

next

out of 5

View

0Download

0

Embed Size (px)

Signal-Matched Wavelet Design via Lifting using Optimization Techniques

Naushad Ansari Deptt. of Electronics and Communications Engineering Indraprastha Institute of Information Technology-Delhi

IIIT-D, Delhi, India Email: naushada@iiitd.ac.in

Anubha Gupta Deptt. of Electronics and Communications Engineering Indraprastha Institute of Information Technology-Delhi

IIIT-D, Delhi, India Email: anubha@iiitd.ac.in

Abstract—This paper proposes design of signal-matched wavelets via lifting. The design is modular owing to lifting framework wherein both predict and update stage polynomials are obtained from the given signal. Successive predict stages are designed using the least squares criterion, while the update stages are designed with total variation minimization on the wavelet approximation coefficients. Different design strategies for compression and denoising are presented. The efficacy of matched-wavelets is illustrated on transform coding gain and signal denoising.

Index Terms—Signal-matched wavelet system; lifting scheme; optimization techniques.

I. INTRODUCTION

Design of multirate filterbanks and wavelets is an active research area explored extensively by applied mathematicians and signal processing community. Wavelets have been applied successfully in many areas applications including compres- sion, denoising, pattern matching, watermarking, biomedical signal and image processing, texture analysis, traffic model- ing, etc. Compared to the traditional Fourier-based analysis, wavelet analysis provides an option to choose different basis. Since the basis here is not unique, it is natural to seek a wavelet that is best in a particular context for a given signal.

Design of signal-adapted or signal-matched wavelets has been addressed with lifting in [1-10]. The lifting technique involves alternate predict and update steps. Although it is easy to find the prediction stage filters, finding an update filter offers a real challenge. One of the criteria used in the literature to find the update filters is the minimization of reconstruction error of even and odd indexed samples [1]. In [2,3], the update first structure with adaptation of the update step is used. The update filter is changed based on the local gradient information such that sharp variations in the signal get less smoothened than the more homogenous regions. Similar update method is used in [4]. In [5], a nonseparable lifting is used on images with regularity conditions imposed. In [6], directional interpolation is used with coefficients of interpolation filter to optimize to adapt to statistical property of image. In [7], authors have designed wavelets by minimizing the difference between BWT (Block Wavelet Transform) and KLT (Karhunen-Loève Transform) of signal. In [8], orthogonal IIR (Infinite Impulse Response) filterbank is designed using

allpass filter in the lifting steps. In [9], geometry of the given image is used to design new wavelet via lifting leading to local and anisotropic filters. [10] has designed nonseparable filter- banks which are pixel-wise adapted according to local image feature.

In this paper, we propose to design signal-matched wavelets using lifting wherein both predict and update stage polyno- mials are obtained from a given signal. Successive predict stages are designed using the least squares criterion, while the update stages are designed with total variation minimization on the wavelet approximation coefficients. We propose two design methods. Method-1 designs signal matched filters with no constraint of linear phase property imposed on filters, while method-2 designs linear phase scaling and wavelet filters. We test our design methods on some randomly picked speech and music clips and compare results of designed wavelets with standard wavelets on transform coding gain and signal de- noising. The signal-matched wavelets are designed differently for compression (illustrated via transform coding gain) and denoising.

In [11], nonseparable wavelets are designed for images using lifting using the criterion of variance minimization in the wavelet space for the predict stage. For the update stage, reconstruction error is minimized between the input signal and the output signal after dropping the wavelet subband. The work proposed in this paper is carried out independently of [11], although it is noticed to have some similarity in the design approach. This work differs from [11] in the following ways:

• In this work, we design signal-matched wavelets for 1- D signals with 2-tap update and the predict polynomials in the powers of z and z−1, respectively. This leads to the design of signal-matched 5/3 and 9/7 wavelets with one and two stages of predict-update pairs, respectively. Other variations on number of filter taps or different polynomials in z or z−1 will not lead to these wavelets. On the other hand, [11] designs nonseparable wavelets for images without any such focus.

• We show that signal-matched wavelets designed differ- ently in different applications lead to better designs. Here, a different approach is proposed to design matched wavelet for denoising compared to compression.

• Also, we use total variation minimization constraint in

the update stage, while [11] uses a constraint related to the nonseparable quincunx lattice of the image.

The paper is organized as follows. In section 2, we present a brief review of lifting scheme. Section 3 presents our proposed methods on signal-matched wavelet design. Simulation results are presented in section 4. Some conclusions are presented in section 5.

II. THEORY OF LIFTING IN BRIEF

Lifting, also known as second generation wavelets, is a technique for either factoring existing wavelet filters into a finite sequence of smaller filtering steps or constructing new customized wavelet basis [12]. A general lifting scheme consists of three steps: Split, Predict, and Update (Refer to figure 1).

Split: In the split step, given input signal is split into two disjoint sets, generally even indexed and odd indexed samples, labeled as xe[n] and xo[n], respectively. The original signal can be recovered perfectly by interlacing or combining this even and odd indexed sample stream. The corresponding filterbank structure is also called as the Lazy wavelet system [12] and the related filterbank structure is shown in Fig. 2 with analysis filters labeled as H0(z) = Z{h0[n]}, H1(z) = Z{h1[n]} and the synthesis filters as F0(z) = Z{f0[n]}, F1(z) = Z{f1[n]}.

Predict or Dual Lifting Step: In the predict stage, one of these two disjoint sets is predicted from the other set. For example, in figure 1(a), we predict even samples from the neighboring odd samples by using the predictor P ≡ T (z). Predict stage is equivalent to applying a high-pass filter on the input signal. This step modifies the analysis high-pass and synthesis lowpass filter, without changing other filters according to the following relations:

Hnew1 (z) = H1(z)−H0(z)T (z2). (1)

Fnew0 (z) = F0(z) + F1(z)T (z 2). (2)

Update or Primal Lifting Step: This step modifies the analysis lowpass filter and provides the coarse approximation of the signal. The update step is denoted with the symbol U ≡ S(z). This is also called as the primal lifting step or simply, the lifting step. Update step only modifies the analysis low pass and synthesis high-pass filter according to the following relation:

Hnew0 (z) = H0(z) +H1(z)S(z 2). (3)

Fnew1 (z) = F1(z)− F0(z)S(z2). (4)

One of the major advantages of lifting scheme is that each stage (predict or update) is invertible. Hence, perfect reconstruction (PR) is guaranteed.

III. PROPOSED WAVELET DESIGN

In this section, we propose two methods of designing matched wavelet via lifting. In the first method, we discuss wavelet design without imposing the condition of linear phase (LP) on filters. The second method designs linear phase filters.

d-1[n]

xe[n] d-1[n]

a-1[n] xo[n]

x[n]

(a)

(b)

Interleave/ combine samples from the two input streams

+

- +

+

+ +

Odd/

Even Split

+

+

U≡S(z) -

+

P≡T(z)

+ +

U≡S(z) P≡T(z)

a-1[n]

x[n] ^

Fig. 1: Steps of Lifting: Split, Predict and Update

x[n]

x2[n]

x1[n]

+

+

h0[n]

h1[n]

f0[n]

f1[n]

+

x[n] ^

Fig. 2: Two Channel Biorthogonal Wavelet System

A. Method-1: With no constraint of LP

Let us refer to figure 3 that considers the following filters for the Lazy wavelet:

H0(z) = z −1, H1(z) = z

−2, (5)

F0(z) = z −2, F1(z) = z

−1. (6)

This set of filters gives perfect reconstruction with

x̂[n] = x[n− 3] (7)

Starting from this, we now present our method to design predict and update stages.

1) Design of Predict Stage: The wavelet subband coeffi- cients from the lower branch of figure 3(a) can be written as:

d−1[n] =xe[n]− P1(xo[n]) =x[2n− 2]− t0x[2n− 1]− t1x[2n− 3]

= ∑ k

h1[k]x[2n− k] (8)

where H1(z) = −t0z−1 + z−2 − t1z−3. Assuming that input signal is rich in low frequency content, most of the input signal energy after decomposition should lie in the lowpass band. Hence, predict stage polynomial T (z) = t0 + t1z−1 can be obtained by minimizing the energy of the signal d−1[n] in the high pass band, with the following least squares criterion

t̃ =min t ‖d−1‖22

=min t ‖b− At‖22 (9)