Wavelet Transform (779450), страница 6
Текст из файла (страница 6)
It could be shown that sample values of the wavelet transformcan be computed by means of a PR filter bank, provided the coefficients c ~ ( n )for representing an approximation xo(t) = C, co(n)$(t - n) are known. Forthe sequences d m ( n ) , m > 0, successively computed from co(n), we haddrn(n) = W , (2"n, 2") = (X,$",)L(8.203)CQ-2-tx ( t ) +*(2-"t- n)dt,that is, the values d m ( n ) were sample values of the wavelet transform ofa continuous-time signal. A considerable problem is the generation of thediscrete-time signal c g ( n ) because in digital signal processing the signals tobe processed are usually obtained by filtering continuous-time signals with astandard anti-aliasing filter and sampling. Onlyif the impulse response h(t)ofthe prefilter is chosen such that xo(t) = x ( t ) * h ( t )E VO,we obtain a "genuine"wavelet analysis.If we wish to apply the theory outlined above to "ordinary" discrete-timesignals x ( n ) , it is helpful to discretize the integral in (8.203):w,(2"n, 2") = 2 - tckZ(k) ?)*(2-"/c- n).(8.204)256TransformChapter 8.
WaveletHere, the values $ ~ ( 2 - ~-5n ) , m > 0, 5,n E Z are tobe regarded as samplesof a given wavelet +(t)where the sampling interval is T = 1.Translation Invariance. We are mainly interested in dyadically arrangedvalues according to (8.204). In thisform the wavelet analysis is not translationinvariant because a delayed input signal z ( n - l) leads towz(2"(n-2 - y , 2m)= 2-?C kz ( k= 2-7Xi+)7)*(2-Y-l) 7)*(2-rnlc-n)[n- 2 - T l ) .(8.205)Only if l is a multiple of 2rn, we obtain shifted versions of the same waveletcoefficients.
However, for many applications such as pattern recognition ormotion estimation inthe wavelet domain it is desirable to achieve translationinvariance. This problem can be solved by computing all valuesw2(n,2rn) = 2 - tC+) 7)*(2-rn(lc--n)).(8.206)kIn general, this is computationally very expensive, but when using the B trousalgorithm outlined in the next section, the computation is as efficient as withthe DWT.8.8.1The A Trous AlgorithmA direct evaluation of (8.204) and (8.206) is very costly if the values of thewavelet transform must be determinedfor several octaves becausethe numberof filter coefficients roughly doubles from octave to octave. Here, the so-calledci trous algorithm allows efficient evaluation with respect to computing effort.This algorithm has been proposed by Holschneider et al.
[73] and Dutilleux[48]. The relationship between the B trous and the Mallatalgorithm wasderived by Shensa [132].We start with dyadic sampling accordingto (8.204). The impulse responseof the filter H l ( z ) is chosen to beh1(n) = 2 - i 7)*(-n/2).(8.207)With this filter the output values of the first stage of the filter bankinFigure 8.19 are equal to those according to (8.204), we havewz(2n,2) = @,(2n,2).The basic idea of the B trous algorithm is to evaluate equation (8.204)notexactly, but approximately.
For this, we use an interpolation filter as8.8. The Wavelet Transform of Discrete-Time257Signals-Figure 8.19. Analysis filter bank.B2 (4Figure 8.20. Equivalent arrangements.4 may for instance be a Lagrange halfbandthe analysis lowpass H 0 ( ~ ) .Thisfilter, but in principle any interpolation filter will do. In order to explain thisapproach in more detail let us take a look at the flow graphs shown in Figure 8.20, which both have the transfer function H1(z2) [Ho(z) Ho(-z)].The transfer function & ( z ) is++B z ( z ) = Ho(z)(8.208)H1(z2).If Ho(z)is an interpolation filter, (8.208) can be interpreted as follows: firstwe insert zeros into the impulse responseh1 (n).By convolving the upsampledimpulseresponse h i ( 2 n ) = hl(n), h i ( 2 n + 1) = 0 with the interpolation+filter the values h i ( 2 n ) remainunchanged, while the values h i ( 2 n 1)are interpolated.
Thus, the even numbered values of the impulse responseb2(n) t)B ~ ( zare) equal to the even numbered samples of 2-l$* (-n/4).The interpolated intermediate values are approximately the sample values of2 - l $ * ( - n / 4 ) at the odd positions. Thus, we haveb2(n) M 2-1 $*(-n/4).(8.209)Iteration of this approach yields4The term “A trous” means “with gaps”, which refers to the fact that an interpolationlowpass filter is used.258Chapter 8. WaveletTransformFor the impulse responses b,(n)& ( z ) we gett)The values ul,(2mn,2m) computed with the filter bank in Figure 8.19 aregiven byG, (2%, 2 m ) m W, (2%, 2m).(8.212)Thus, the scheme in Figure 8.19 yields an approximate wavelet analysis.Oversampled Wavelet Series.
Although the coefficients of critically sampled representations containall information onthe analyzed signal, they sufferfrom the drawback that the analysis is not translation invariant. The aim isnow to compute an approximation ofWz(n,2m) = 2 - tC z ( k )@*(2-m(Ic - n ) )(8.213)kby means of the filters bm(n)t)B,(z)&(n, 2m) = 2 - taccording to (8.210):C z(k)b,(n- Ic)(8.214)kWhile the direct evaluation of these formulae meanshigh computational cost,the values 271,(n, 2m) may be efficiently computed by use of the filter bank~ ~ )H ~ ( . z ~m~>) 1,, can be realized inin Figure 8.21.
The filters H O ( . Z andpolyphase structure. The number of operations that have to be carried outis very small so that such an evaluation is suitable for real-time applicationsalso.In many cases the frequency resolution of a pure octave-band analysis isnot sufficient. An improved resolution can be obtained by implementing M8.8.WaveletDiscrete-TimeTransformTheofSignals259octave filter banks in parallel where each bank covers only an Mth partof theoctaves. This concept has been discussed in Section 8.4.2 for the continuoustime case. The application to a discrete-time analysis based on the B trousalgorithm is straightforward.8.8.2The Relationship between the Mallat and A TrousAlgorithmsThe discussion above has shown that the only formal difference between thefilters usedin the Mallat and B trous algorithms liesin the fact that inthe Mallat algorithm the impulse response of the filter H l ( z ) does not, ingeneral, consist of sample values of the continuous-time wavelet.
However,both concepts can easily be reconciled. For this, let us consider a PR twochannel filter bank, where Ho(z) is an interpolation filter and where H1( z )satisfies Hl(1) = 0. Based on the filter bank we can construct the associatedcontinuous-time scaling functions and wavelets. Since Ho(z) is supposed tobe an interpolation filter, we have the following correspondence between theimpulse response of the highpass filter, h l ( n ) ,and the sample values of thewavelet $ ( t ) ,which is iteratively determined from ho(n) and hl(n):h1(n) = 2-i $*(-n/2).(8.215)For the filters B,(z) defined in (8.210) we havembm(n)= 2-?+*(-2-"n),(8.216)and we derive211, (2%,2m)= W, (2%, P ) .(8.217)wavelet transform exactlyThis meansthat theB trous algorithm computes theif Ho(z) and Hl(z) belong to a PR two-channel filter bank while Ho(z) is aninterpolation filter.
Then, all computed wavelet coefficientsW, (2%, 2m), m >0, can be interpreted as sample values of a continuous wavelet transform provided the demandfor regularity is met: wz(2%, 2m) = W , (2%, 2m), m > 0.In order to determine filters that yield perfect wavelet analyses of discretetime signals with 211,(2mlc, 2m) = wz(2%, 2m) we may proceed as follows: wetake an interpolation filter Ho(z) and compute a filter Go(z) such that260TransformChapter 8. WaveletNote that (8.218) is just an underdetermined linear set of equations.
FromHo(z) and Go(z) we can then calculate the filters H l ( z ) and G1 ( z ) accordingto equation (6.22) and can construct thewavelet via iteration. Thesolution to(8.218) is not unique, so that one can choose a wavelet which has the desiredproperties.Example. For the analysis lowpass we use a binary filter with 31coefficients as given in (8.181).
The lengthof the analysis highpass is restrictedto 63 coefficients. The overall delay of the analysis-synthesis system is chosensuch that a linear-phase highpass is yielded. Figures8.22(a) and8.22(b)show the respective scaling function,the wavelet, andthe sample values4(-n/2) = ho(n) and +(-n/2) = h l ( n ) .The frequency responses of Ho(z)and H l ( z ) are pictured in Figure 8.22(c).8.8.3The Discrete-Time MorletWaveletThe Morlet wavelet was introduced in Section 8.2.
In orderto realize a waveletanalysis of discrete-time signals, the wavelet is sampled in such a way thathl(n) = b l ( n ) = ejwon,-P2n2/2,where b l ( n ) isdefined as in (8.210). Inorderadmissible and analytic wavelet we choose243WO(8.219)to obtaina“practically”7r/2.(8.220)In the discrete-time case a further problem arises due to the periodicity ofthe spectra.
In order to ensure that we achieve an analytic wavelet we haveto demand that!@(eJW)= Ofor7r< W 5 27rIn order to guarantee this, at least approximately, the parametersare chosen such thatwo<n-1/2/3is also satisfied [132].WOandp(8.221)2618.9. DWT-Based Image Compression'-0.4-2002t(4-I200.8tSOS-0.6-2002t@)-20t100(c)Qln*1Figure 8.22. Example; (a) scaling function 4(t)and the sample values4(-nT/2) =ho(n); (b) wavelet +(t)and the samplevalues +(-nT/2) = hl(n);(c)frequencyresponses of the analysis filters.8.9DWT-BasedImageCompressionImage compression based onthe DWT is essentially equivalent to compressionbased on octave-band filter banks as outlined in Section 6.8. The strategy isas follows: the image is first decomposed into a set of subband signals by usinga separable5 2-D filter bank.
Then, the subband samples are quantized andfurther compressed. The filters, however, satisfy certain conditions such asregularity and vanishing moments.Togive an example of the discrete wavelet transform of a 2-D signal,5Non-separable 2-D wavelets and filter banks are not considered throughout this book.262Chapter 8. WaveletTransformFigure 8.23. Separable 2-D discrete wavelet transform; (a) original; (b) DWT.Figure 8.23(a) shows an original image and Figure8.23(b) shows its 2-Dwavelet transform.
The squares in Figure 8.23(b) indicate spatialregions thatbelong to thesame region in Figure 8.23(a). Thearrows indicate parent-childrelationships. An important observation can be made from Figure8.23(b),which is true for most natural images: if there is little low-frequency information in a spatial region, then it is likely that there is also little high-frequencyinformation in that region. Thus, if a parent pixel is small, then it is likely thatthe belonging children are also small. This relationship can be exploited inorder to encode the subband pixels in an efficient way.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
