信号处理07b

 Properties

nkk1,), kZ nn22Scaling:Inclusion:Density:Maximality:f(t)Vnf(2t)Vn1VnVn1foreachnnZVnL2(R)nnZV{0}Basis:(tk),kZisanorthonormalbasisinV

7.4.2.Spaces Wn and Properties Wnspan22(2ntk),kZn2nwhereisanorthonormalbasisinWn

 Properties

Vn1VnWn2n(2tk),kZforeachnL2(R)limVnnlimVn1Wn1nnlimVn2Wn2Wn1 WnnZ不仅是简单的叠加，而是重组，合成向量 Daubechies小波产生的Wn比Haar的要好

Note:Vn and Vm are not orthonormal; But

WnWmAndVnWn

17

7.4.3.Wavelet Decomposition of Signals From the second property on last section, one concludes that

2n2(2ntk),kZ,nZ is an orthonormal basis in L2(R).

Hence for any f(t) L2(R),

nkˆn,k(t)ˆn,k(t)(732)f(t)f(t),

nn2ˆwhere n,k(t)2(2tk) (Haar basis)

For many practical signals, there often are many small wavelet

coefficients. So that the signal can be represented with trancated wavelet series with fewer terms than its Fourier series requires. [see the above example on 7.2.2 s(t)=exp(-10t)sin(100t)]

 Haar Basis for L2[0,1)

The Haar basis n,k given on 7.4.3 is for L2(R). They can be used to defined periodic wavelets:

n~n,k(t)22(2n(tj)k)(733)

jZ~nTheorem Functions 1 and n,k with n0, k = 0,1, ...,2-1 form

an orthonormal basis for L2[0,1).

 Similarly, periodic scaling functions can be generated as

n~n,k(k)22(2n(tj)k)(734)jZ

for n0, and k = 0,1, ...,2n-1.

7.4.4.Fast Haar Transform Consider a signal f(t)VnVn1Wn1. We want to decompose f(t) into items in Vn-1 and Wn-1. This is to say: Given

f(t)and

(n)kn,k(t)kZˆ , we want to compute (n1)k such that

ˆf(t)(n1)k(n1)kn1,kkZ(t)kZ(n1)kˆn1,k(t)(735)

18

n22ˆˆ2(2tk),2(2tk) n,kwhere n,kˆn1,k,kZˆn1,k,kZ forms an Note nnnorthonormal basis for Vn. Therefore,

(n1)kf(t),2(n1)2(2tk),n1(n1)kf(t),2(n1)2t(2tk)n1The DE and WE lead to a beautiful set of relations between these coefficients. Recall

(t)(2t)(2t1)(t)(2t)(2t1)(DE)

(WE)

 (平移)

 (伸缩)

(tk)(2t2k)(2t(2k1)) (tk)(2t2k)(2t(2k1))

(2tk)(2t2k)(2t(2k1))

(2n1tk)(2nt2k)(2nt(2k1))

n1n2n(2tk)2(2t2k)22(2nt(2k1))2n1n1nn

 (长度归一化)

2(n1)22

(n1)nn1nn222(2tk)2(2t2k)2(2t(2k1))2n1

ˆn1,k121ˆˆn,2k2n,2k1

1ˆ1ˆˆn1,k2n,2k2n,2k1

19

 故有如下迭代公式

(n1)kˆf,n1,k1212ˆf,n,2k12ˆf,n,2k1

(n)2k12(n)2k1(n1)k12(n)2k121212(n)2k1

Now we obtain (n1)1k2(n1)1k2(n)2k(n)2k1212(n)2k1(736a)

(n)2k1(736b)

此即S.Mallat 19年给出的多分辨率分析的方程(MRA)或为

(n1)k(n1)k1212(n)2k(n)(737) 2k1 W

此处的W为正交矩阵，即(MRA)矩阵形式，它阐明了正交双方的可逆计算。

A Filter-Bank Implementation of MRA If we refer index 2k+1 as “the present time instant”, then 2k is an index representing the “immediate past”. So, the equations (MRA see the last section) can be implemented as follows:

20

The MRA can be carried out with n levels for signals of length N=2n.

This decomposition process is “reversible”:

,,,to One can use . reconstruct the original signal (0)(0)(n1)(n)perfectly

Again, we use the (DE) and (WE) to accomplish the

reconstruction:

(n)kˆn,kkˆn1,kk(n1)ˆn1,kk(n1)kk111(n1)1ˆn,2kˆn,2k1)k(ˆn,2kˆn,2k1)(2222kkIf k=even:(比较相同基函数的系数应相等)

(n1)k(n)k12(n1)k/212(n1)k/2121)k(n/2121)[12k(n/2120][(n1)(k1)/20](738a)(n1)(k1)/2 If k=odd:



(n)k[01212][01212](738b)21

此处相当于补零形成向量，再通过高、低通滤波器得更精确的系数。

This suggests a filter-bank implementation for the reconstruction: first  and  are up-sampled by padding a zero between each pair of samples the up-sampled  and  are then fed into a lowpass and a highpass FIR filters, respectively, and the filtered sequences are combined to generate

(n1)(n1)(n1)(n1).

(n)

★The impulse response of H0(z) and H1(z) match the coefficients if (DE) and (WE), respectively;

★The filters H0(z) and F0(z), and the filters H1(z) and F1(z) are mirror-image symmetric.

The n-level MRA is now complete with a decomposition phase

and a reconstruction phase:

22

§7-5. Improved Wavelets: A Filter-Bank Approach 7.5.1.Wavelets via Dilation Equations To discover new and improved wavelets, let us suppose

(t) is a better scaling function. Using MRA, we relate (t) to the spaces Vn:

that

Vnspan2(2tk),kZ(739)

2nnSince V0V1,(t)can be expressed as :

k(t)2ck(2tk)(DE)

As W0V1,we should have

k(t)2dk(2tk)(WE)

Here we consider the case when only finite number of

ck'sand dk'sare nonzero:

(t)2ck(2tk)(DE)

k0KK(t)

2dk(2tk)(WE)

k023

If we require

{(tk)} orthonormal, then

(m)(t)(tm)dt2[c(2tk)][c(2tl)]dt

cc,m0,1klklkk2mkIn addition, we impose the “alternating flip” assumption on

dk's:

dk(1)cKk,k0,1,,K

kSince

(t)dt0

Kkk0We obtain

0(t)dt2(1)cKk(2tk)dt12kk(1)k0KkcKk

ccKk0k2m(m),m0,11

k(1)cKk0(2) Example-1(K=1 case)

In this case one has only two nonzero coefficients: c0 and c1 satisfying

24

22c0c111c1c00c1c0(HaarWavelet)

2Example-2(K=3 case)

In this case, nonzero coefficients are: c0 c1 c2 and c3 satisfying

2222c0c1c2c31(a)c0c2c1c30(b)c3c2c1c00(c)

One can impose one more condition on kmake the wavelet more “regular”(smooth):

c'sin order to

t(t)dt0

Kkk0kdwhich leads to

0(d')

c22c13c00(d)

Here is how (d’):

25

0t(t)dt2dkt(2tk)dtk1dk2t(2tk)dt2k1dkt(tk)dt22k1dk[(tk)k](tk)dt22k 1dk(1k2)[1t(t)dt,21(t)dt]22k122d2kkkk22kd2kk[dk0]k2kd2Solving equations(a)—(d), we obtain:

c0,c1,c2,c314412123,33,33,13d0,d1,d2,d313,33,33,13

which is the well-known Daubechies orthogonal filter D4. Once

{ck,k0,1,,K}are obtained, the scaling function

(t)2(2tk)i0,1,2,

(i)k0(0)can be obtained using the CASCADE algorithm:

(i1)K1,0t1(t)with 0,elsewhere

26

(t) has a

support on [0,K]. Once (t) is found, the wavelet (t)can

We can show(by using the cascade algorithm) that

be obtained using (WE). The figure below displays the

Daubechies scaling and wavelet functions with K=3.

7.5.2.Orthogonal Filter Banks and MRA structure of a two-channel Orthogonal Filter Bank

where

KKC(z)ckz,C:zC(z)cKkzkTk1k0k0KKk

D(z)dkzk(1)kcKkzk(alternatingflip)

k0k0

27

k1D(z)(z)C(z) ) (i.e.

The input-output relationship in this filter bank is given by

x(z)1[F0(z)H0(z)F1(z)H1(z)]x(z)21[F0(z)H0(z)F1(z)H1(z)]x(z) 21kz[C(z)C(z1)C(z)C(z1)]x(z)zkx(z)2This is perfect reconstruction requirement,so C(z) must

C(z)C(z1)C(z)C(z1)2satisfiedi.e.C()2C()22

This is the condition which makes the filter bank “orthogonal”. Examples:

◎ With c0,c112,12 the filter bank is orthogonal:

C()122212ej21cos2C()122122ej()1cos

C()C()2

◎ One can also verify the D4(Daubechies-4) correspords

to an orthogonal filter bank. ◎ As a matter of fact, one can show:

Orthogonalconditionckck2m(m)

kA multiresolution analysis can start from na orthogonal

28

filter bank as a building block, DSP algorithm can be applied to each “sub-signal” between the analysis and synthesis banks. Here is a 3-level example:

7.5.3.High-Order Daubechies Orthogonal Wavelets Here we present an easy-to-use method for generating high-order Daubechies orthogonal wavelets. Step1. Given an even length N=2, form polynomial

p

B(z)zp1pk11zkk02p1-1

k1z21k

Step2. Factorize B(z) as

B(z)czp1R(z)R(z1)

Where R(z) is a polynomial in z with all zeros insize

z1; and c is a positive constant.

1pC(z)(1z)R(z) Step3. Construct

with

2[2R(0)]

29

pImportant properties of the Daubechies orthogonal wavelet Let (t) be the wavelet generated by C(z) of length N from the algorithm above, then

(t)(and the associated scaling function) has support

on [0,N-1].

(t)has the maximum number of vanishing moments:

Nt(t)dt0fork0,1,,1 2kThe figure below shows the Daubechies orthogonal wavelets of length 4,6,8 and 10. Note that the smoothness of (t) increases with length.

30

§7-6. Wavelet-Based Signal Denoising 7.6.1.Basic Idea and System Structure

Suppose we have a discrete-time signal {x(n)} that is contaminated with noise:

X(n)S(n)W(n),n0,1,,N1

S(n) is signal, W(n) is noise.

Assumptions:N is Large, W(n) is white with

W(n)N(0,1),andN2(Normal distribution with variance

2p

2and mean 0.)

Problem is to process {x(n)} to get an improves approximation of {S(n)}. Such a problem is referred to as

31

“Noise Reduction”. System structure:

DWT(Discrete Wavelet Transform) and IDWT(Inverse Discrete Wavelet Transform)

are usually implemented using filter bank discussed above The soft-Thresholding as applied to y ,”shrinks” these wavelet coefficients according to a “preset” threshold that is determined chiefly by the noise variance. 7.6.2.Shrinkage and Thresholding Polices Hard shrinkage

x(t),ifx(t)yhard(t) 0,ifx(t)Soft shrinkage

sign[x(t)](x(t)),ifx(t)ysoft(t) 0,ifx(t)“Hyperbolic” shrinkage (“Almost Hard”)

32

22sign[x(t)]x(t),ifx(t)yhyper(t)0,ifx(t)Example:x=0:1:9, x 0 1 2 3 xhar0 0 2 3 d Xsoft 0 0 1 2 Xhyper 0 1

4 5 4 5 3 4 6 6 5 7 7 6 8 9 8 9 7 8 0 1.7321 2.8284 3.8730 4.90 5.9161 6.9282 7.9373 8.9443 From the table you see why the hyperbolic shrinkage is “almost hard” shrinkage. A critical issue in wavelet-based denoising is how to determine the value of

(the threshold)

Determination of threshold 

1. Universal Threshold(Donoho and Johnstone 1993) ˆ 2log(N)where N is the length of the noise-contaminated sequence,

ˆ2is the estimated noise variance. An effective way to estimate ˆ2is to use the detail subsignal at highst resolution. Let N=2p, 2ˆcan be obtained by then an estimate of 12ˆ(dd)p,i(N21)i12N2

the detail signal at

where

{dp,i,i1,,N2}is

highst resolution,

dmean(dp)

33

2. Cross-validation method (Nason 1994) p{y,i1,,N2}. We difine two Given a sequence isequence from it as follows:

yoddiy2i1y2i1,i1,,N2;yN1yN1

2y2iy2i2y,i1,,N2;yN2yN

2For each fixed ,we define function M()as

eveniodd2M()[Tsoft(deven,)dj,kj,k]j,ksoftoddeven2[T(d,)dj,kj,k]j,k

where

{devenj,k}are the wavelet coefficients of yeven generated iodd{dfrom the noise-corrupted signal, and j,k} are the wavelet

coefficients of

yodd. iTsoft(y,) is a sequence obtained by

. It turns out that M() is a

*convex function of . Let be the minimizer of M(), then

soft-shrinkage of y with threshold

the cross-validation based threshold is given by

log212(1)

logN*

34

35

36