翻译原文3.pdf

1、Signal Processing 69 (1998) 177182 Remarks on the unsubsampled wavelet transform and the lifting scheme Alexander Stoff el* Fachhochschule Ko (ln, Fachbereich Nachrichtentechnik, Betzdorfer Strae 2, D-50679 Ko (ln, Germany Received 10 November 1997; received in revised form 5 May 1998 Abstract The l

2、ifting scheme, which is known to be a very useful tool for the wavelet transform, is adapted to the calculation of the unsubsampled wavelet coeffi cients. It is shown that as in the subsampled case the two-band transform for each FIR fi lter pair without common zeros can be performed by a fi nite nu

3、mber of lifting steps. Inverting each step, one gets a perfect reconstruction equivalent to the arithmetic mean of the result of two diff erent reconstruction fi lters. Because of this easy inversion, the lifting scheme off ers a great fl exibility in treating boundary conditions in the case of fi n

4、itely many data. ( 1998 Elsevier Science B.V. All rights reserved. Zusammenfassung Das Lifting-Schema, das als ein sehr nu tzliches Werkzeug fu r die Wavelet-Transformation bekannt ist, wird an die Berechnung der Wavelet-Koeffi zienten ohne “Subsampling” angepat. Es wird gezeigt, da wie im Fall mit

5、Subsamp- ling fu r jedes FIR-Filterpaar ohne gemeinsame Nullstellen die Zwei-Band-Transformation mit einer endlichen Zahl von Lifting-Schritten durchgefu hrt werden kann. Indem man jeden Schritt invertiert, erha lt man eine perfekte Rekon- struktion, die a quivalent ist zum arithmetischen Mittel des

6、 Ergebnisses zweier unterschiedlicher Rekonstruktionsfi lter. Aufgrund dieser einfachen Invertierung bietet das Lifting-Schema eine groe Flexibilita t bei der Behandlung von Randbedingungen im Fall endlich vieler Daten. ( 1998 Elsevier Science B.V. All rights reserved. Re sume Le sche ma du soule ve

7、ment (lifting scheme), qui est connu comme un outil tre s utile pour la transformation dondelettes, est adapte au calcul des coeffi cients dondelettes sans sous-e chantillonnage. Il est de montre que comme dans le cas du sous-e chantillonnage pour chaque paire de fi ltres FIR sans ze ros communs, la

8、 transformation en deux sous-bandes peut e tre eff ectue e par un nombre fi ni de pas de soule vement (lifting). En invertissant chaque pas de soule vement, on obtient une reconstruction parfaite qui est e quivalente a la moyenne arithme tique de deux fi ltres de reconstruction diff e rents. Gra ce

9、a cette inversion facile, le sche ma du soule vement off re une grande fl exibilite pour le traitement de conditions aux limites au cas dun nombre fi ni de donne es. ( 1998 Elsevier Science B.V. All rights reserved. Keywords: Wavelet; Filter bank; Lifting scheme; Finite length signals *Tel.: #492218

10、2752431; fax: #4922182752836; e-mail: stoff elnebsy.nt.fh-koeln.de. 0165-1684/98/$ see front matter ( 1998 Elsevier Science B.V. All rights reserved. PII: S0 1 6 5 -1 68 4 (9 8 ) 00 0 9 9- 1 1. Introduction Only wavelets constructed in the framework of a multiresolutionanalysis (MRA) withscaling fun

11、c- tion u will be considered here. We fi x the normaliz- ation condition +hk1, such that the two-scale relation reads u(x)2+ k|Z hku(2x!k),(1) and the wavelet fulfi lls t(x)2+ k|Z gku(2x!k).(2) Let f be a signal. We shall study here the redundant coeffi cients ri(k)2iPf(x)t(2ix!2ik)dx,(3) si(k): 2iP

12、f(x)u(2ix!2ik)dx,(4) which fulfi ll the following recursion formulae: si(k)+ l|Z hlsi1(k#2i1l), (5) ri(k)+ l|Z glsi1(k#2i1l). Their advantage is a simple behaviour, if the signal is translated (usually referred as translation invari- ance). We shall denote the z-transform of a sequence by the corres

13、ponding capital letter as for example Si(z): + k|Z si(k)zk.(6) The above recursion formulae then read Si(z)H(z2i1)Si1(z), (7) Ri(z)G(z2i1)Ri1(z). If we have recursion fi lters H I (z) and G I (z) satisfying the following condition of perfect reconstruction: H I (z)H(z1)#G I (z)G(z1)1,(8) Fig. 1. Per

14、fect reconstructionfi lter bank (withoutsubsampling). the coeffi cients may be successively reconstructed by Si1(z)H I (z2i1)Si(z)#G I (z2i1)Ri(z).(9) For i1, this is visualised in Fig. 1. It is well known that, given any FIR (Finite Impulse Response) fi lters H(z) and G(z) with no common zeros, Euc

15、lids algorithm always furnishes FIR fi lters H I (z) and G I (z) fulfi lling Eq. (8). The reconstruction fi lters are not unique, we have the following proposition. Proposition 1. Suppose that a particular solution H I 0-$(z) and G I0-$ (z) of Eq. (8) for a fi xed pair of analy- sis fi ltersH(z) and

16、 G(z) is given. hen, using any FIR fi lter (z), we always get new reconstruction fi lters by H I /%8(z)H I0-$(z)#(z)G(z1), (10) G I /%8(z)G I0-$(z)!(z)H(z1), (11) and any FIR reconstruction fi lters may be construc- ted in this way, starting from a given pair H I 0-$(z) and G I 0-$(z). That H I /%8(

17、z) and G I/%8 (z) fulfi ll Eq. (8) is elemen- tary, conversely the Laurent polynomial (z) may be constructedanalogouslyto the proof of Proposi- tion 2. 2. Lifting scheme The lifting scheme is a very powerful tool for the wavelet transform with subsampling, see 1,57. It is shown in this section, how

18、it may be adapted to the unsubsampled case. As the analog of 1, (Theorem 3) we get the following proposition. 178A. Stoffel / Signal Processing 69 (1998) 177182 Proposition2(lifting).Givenanysolution H0-$(z), G0-$(z), H I 0-$(z), G I0-$(z) of Eq. (8), then for any new solution fulfi lling H I /%8(z)

19、H I0-$(z) and G/%8(z)G0-$ (z), there is an FIR fi lter (z) with H/%8(z)H0-$(z)!(z1)G0-$(z),(12) G I /%8(z)G I0-$(z)#(z)H I0-$(z). (13) Conversely, any FIR fi lter (z) defi nes a new solu- tion by the above equations. Proof. Let (z): H/%8(z)!H0-$(z), (14) R(z): G I /%8(z)!G I0-$(z). Subtracting the c

20、ondition Eq. (8) for the new fi lters and for the old ones furnishes H I 0-$(z)(z1)#R(z)G0-$(z1)0. (15) Because of Eq. (8), the greatest common divisor of H I 0-$(z) and G0-$(z1) is a Laurent polynomial of degree zero (i.e. of the form c)zk, k3Z). Therefore H I 0-$(z) divides R(z), and we may constr

21、uct a Laur- ent polynomial with the desired properties by the division algorithm (z): R(z) H I 0-$(z) .(16) The converse statement may be verifi ed by elemen- tary calculations.h The following proposition, which corresponds to 1 (Theorem 4), may be proved analogously. Proposition 3 (dual lifting). G

22、iven any “old” solution ofEq. (8),forany“new”solution fulfi lling H/%8(z)H0-$(z) and G I /%8(z)G I0-$(z), there is an FIR fi lter (z) with H I /%8(z)H I0-$(z)#(z)G I0-$(z), (17) G/%8(z)G0-$(z)!(z1)H0-$(z).(18) Conversely, any FIR fi lter (z) defi nes a new solu- tion by the above equations. We shall

23、 now describe the modifi cations of the factoring algorithm in 1, which allow to express the transform by an arbitrary FIR fi lter pair H(z), G(z) without common zeros (except possibly at zero or infi nity) as a product of lifting and dual lifting steps. Thereby one starts from a particular simple f

24、i lter pair which in the unsubsampled case is connected with the “lazy” wavelet. Here, the “lazy” transform we propose corresponds to the trivial fi lters HL(z)GL(z)H I L(z)G IL(z)1/J2. (19) Those factors can be put together in a fi nal factor 1 2 after the addition step as is shown in the scheme of

25、 Fig. 2. In our description we shall suppose that the degree of the Laurent polynomial H(z) is greater than or equal to the degree of G(z) (if this is not the case, one has simply to reverse the role of the two fi lters). Euclids algorithm has to be performed, starting with A0(z): H(z1) and B0(z): G

26、(z1). Then Qi1 (z) is defi ned by the division algorithm as the quotient polynomial of Ai(z) by Bi(z), and Bi1(z) as the remainder, such that Ai(z)Bi(z)Qi1(z)#Bi1(z),(20) and such that the degree of the remainder Bi1(z) is smaller than that of Bi (z). Furthermore, we defi ne Ai1(z): Bi(z),andthisisc

27、ontinueduntil Bi (z)0. Let ni be the fi rst index i when this happens (except for taking capitals, we kept the notation of 1). With V(z): 1 i/nC 01 1!Qi(z)D, (21) we have C An(z) 0DV(z)C A0(z) B0(z)DV(z)C H(z1) G(z1)D. (22) Fig. 2. “Lazy” transform in the unsubsampled case. A. Stoffel / Signal Proce

28、ssing 69 (1998) 177182179 By hypothesis, the greatest common divisor An(z) has degree zero, and the division may be performed such that this is a constant,i.e. An(z)c. We denote the matrix elements of V(z) by ij(z). Because of Eq. (22), we get a reconstruction fi lter pair by H I 0(z): 1 c11(z), G I

29、 0(z): 1 c12(z). (23) Using Eq. (22) furnishes for the z-transform of the coeffi cients C S1(z) R1(z)DV1(z)C c)S0(z) 0D, (24) where V1(z) denotes the inverse matrix of V(z). The matrix V1(z) has to be factored as in 1, but here the last factor has to be changed. In the case of even n, we introduce W

30、e(z) as an abbreviation for the fi rst n!2 factors of V1(z): We(z): n1 i/1 C 1Q2i1(z) 01DC 10 Q2i(z)1D (25) (and We(z): I, the 22 identity matrix, if n2). We get the following factorization in lifting and dual lifting steps: C S1(z) R1(z)D We(z)C1 Qn1(z) 01DC 10 Qn(z)!11DC cS0(z) cS0(z)D. (26) In th

31、e case of odd n, one has to proceed analog- ously. The above considerations prove as the analog of 1, Theorem 7 the following proposition. Proposition 4. Given any FIR fi lter pair H(z) and G(z) without common zeros (except possibly at zero or infi nity), the calculation of the coeffi cients S1(z) a

32、nd R1(z) by Eq. (7) can always be done composing a fi nite number of lifting and dual lifting steps of the form (26). This means that the left-hand side of Fig. 1 may in the case of an even number of factors obtained by Euclids algorithm be replaced by the scheme shown in Fig. 3 (the modifi cation f

33、or the odd case is obvious). As C 1Q(z) 01D 1C1!Q(z) 01D, (27) the reconstruction using the lifting scheme becomes trivial. We simply have to reverse the sign of all the Laurent polynomials, and to multiply the fi nal re- sult by c1 (to balancethe constant) and 1 2 (from the lazy transform), in orde

34、r to get the reconstructed signal. This is shown in Fig. 4. Therefore, the factorization of the analysis fi lters into lifting steps immediately furnishes reconstruc- tion fi lters. One may put the lifting and dual lifting steps of Fig. 4 together, and express them by recon- struction fi lters H I (

35、z) and G I (z), as it corresponds to the right-hand side of Fig. 1. Let us have a closer look, which reconstruction fi lters one gets by this procedure. If we take the inverses of the matrices of the right-hand side of Eq. (26), only the fi rst factor diff ers from the product, which defi nes the ma

36、trix V(z) in Eq. (21). A little calculation furnishes for even n C S0(z) S0(z)D 1 cC 10 11DV(z)C S1(z) R1(z)D, (28) Fig. 3. Calculating the unsubsampled wavelet coeffi cients using the lifting scheme (in the case of an even number of factors obtained by Euclids algorithm). Fig. 4. Reconstruction wit

37、h the lifting scheme (in the case of an even number of factors obtained by Euclids algorithm). 180A. Stoffel / Signal Processing 69 (1998) 177182 and for odd n C S0(z) S0(z)D 1 cC 11 10DV(z)C S1(z) R1(z)D. (29) In both cases we get a vector whose two compo- nents agree. Comparison of the two diff er

38、ent ex- pressionsfor the componentson the righthand side for even and odd n shows, that they are just inter- changed. It turns out that one component is cal- culated by the reconstruction fi lters furnished by Euclids algorithm (23). The other is calculated by the following new reconstruction fi lte

39、rs: H I 1(z)H I0(z)# 1 c21(z), (30) G I 1(z)G I0(z)# 1 c22(z). (31) Our choice of the lazy transform in Fig. 2 means that we take the arithmetic mean of the data recon- structed by the two diff erent fi lters (with index 0 and 1). This might have some stabilizing eff ect, if a manipulation of the co

40、effi cients takes place (for instance in the case of denoising). The resulting equivalent fi lter bank is shown in Fig. 5. However, to save calculation time, one may simply take 1/c times one of the terms before the last summation in Fig. 4, and gets s0(k) as well. The lifting scheme has a remarkabl

41、e property for fi lters satisfying H(z)#G(z)1.(32) Examples of such fi lters are explicitly given by 4, (Eq. (5.75), their properties and advantages in fea- ture extraction are described in 2,3. For those Fig. 5. Filter bank equivalent to the reconstruction by the lift- ing scheme in Fig. 4. Fig. 6.

42、 Analysis and reconstruction with the lifting scheme in the case of fi lters satisfying Eq. (32). fi lters the factorization into lifting steps is trivial. We always get n2, c1, Q1(z)!1 and Q2(z)1!H(z1). The correspondinglifting steps for analysis and reconstruction are shown in Fig. 6. This scheme

43、furnishes the reconstruction fi lters H I 0(z)G I0(z)1, H I1(z)H(z1) and G I1(z) H(z1)#1. A similar investigation as in 1 shows, that in our case there is no reduction of calculation cost using lifting. The main advantage of lifting in the unsubsampled case will be its great fl exibility to adopt bo

44、undary conditions in the case of fi nitely many data, which is discussed in the next section. Until now in this section, all considerations were restricted to the calculation of S1(k) and R1(k), i.e. to the fi rst step in scale. Because of Eq. (7), lifting can also be applied to the general case. Fo

45、r the steps i1, one simply has to replace all the factors Qk(z) by Qk(z2i1). 3. How to treat fi nite length signals As the wavelet transform is linear, we shall de- scribe it in this subsection by matrices. Instead of the sequences si(k) and ri(k), we consider vectors siand ri3RN and identifys0(x0,x

46、1,2,xN1) with the N original data points. We may put the vectors s1and r1together to a single vector in R2N. Con- volution operators described by matrices, as they appear on the right hand side of (25), which correspond to lifting or dual lifting steps, will here become2N2Nmatrices. Theyhavea blocks

47、truc- ture of the following form (I denotes the NN identity matrix): C I0 QID respectively C IQ 0ID. A. Stoffel / Signal Processing 69 (1998) 177182181 In the infi nite case, the operator Q corresponds to a convolution with a sequence q(k) whose z-trans- form is Q(z), i.e. it can be considered as an

48、 infi nite matrix with matrix elements Qikq(i!k).(33) As C IQ 0ID 1CI!Q 0ID, (34) we have total freedom, in choosing a fi nite matrix here again denoted by Q to replace the original convolutionoperator.And at the sametime, perfect reconstruction is maintained. Thus in the fi nite case, Q will be an

49、NN matrix with the following structure: Q QLLQLI0 QILQIIQIR 0QRIQRR .(35) The matrix elements of all the inner submatrices satisfy Eq. (33), as they should agree with the infi - nite case. We have only to change the boundary matricesQLLand QRR. Indeed,we may choose them arbitrarily.One of the simple

50、st choices would be, to let all the matrix elements satisfy Eq. (33), which corresponds to zero padding with subsequent pro- jection to RN (note that this does not correspond to zero padding for the whole wavelet transform, as can be easily seen by calculating examples). For an even number of steps

51、in Euclids algo- rithm, the wavelet transform using lifting now has the form C s1 r1DcC IQ1 0IDC I0 Q2ID2C I0 Qn!IIDC s0 s0D (36) (with an obvious modifi cation in the case of odd n). Practically, this means that using lifting, we may choose any boundary condition we want even diff erent ones for di

52、ff erent lifting steps as far as we take exactly the same boundary condition in the corresponding inverse lifting step for reconstruc- tion. The above formula concerns the calculation for the scale step i1. For general i1, the size of the boundary matrices QLLand QRRwill be increased by a factor 2i1

53、. We have to fi ll in 2i1!1 zeros between the matrix elements, and each row has to be repeated 2i1 times, each time shifted by one position to the right. To obtain perfect reconstruc- tion, one has only to replace the whole block sub- matrix Q by !Q (respectively Q!I by !Q#I). The lifting scheme makes it therefo