Implementation Of Orthogonal Wavelet Transfiorms And Their . - TUM
Implementation of Orthogonal Wavelet Transfiormsand their ApplicatioiisPeter Rieder and Josef A. NossekInstitute of Network Theory & Circuit DesignTechnical University of MunichAbstractIn this paperthe eflcient implementation of different types of orthogonal wavelet transformswith respect to practical applications is discussed. Orthogonal singlewuvelet triinsfornis beingbased on one scaling function and one wavelet function are used for denosing of signals.Orthogonal multiwavelets are bused on several scaling filnctions and several wavelets. Sincethey allow properties like regularity, orthogonality and s y t n m e t being impossible in thesinglewavelet case, miiltiwavets are well suited basesfor image compression applications. Withrespect to an eficient implementation of these orthogonal wcrvelet transforms approximatingthe exact rotation angles of the corresponding orthogonal wavelet lattice jilter:; by using veryfbw CORDIC-based elementary rotations reduces the number of shift and add operationssignijicuntly. The performance of the resulting, conipututionully cheap, approximated wavelettransforms with respect to practical applications is discussed in this paper:1 IntroductionIn recent years wavelet transforms have gained a lot of interest in many application fields, wherebyorthogonal wavelet bases have been introduced by examining different possibilj ties for their design[ 11. Orthogonal singlewavelet transforms using one scaling function and one wavelet functionwere designed. Suitable architectures for implementing wavelet transforms are octavfilterbanks,whereby each stage of the filterbank is composed of a lowpass filter G ( z )and the complementaryhighpass filter H ( z ) . Orthogonal lattice filters can be used t o implement these stages, wherebyonly orthogonal 2 x 2-rotations are required [7, 81. Orthogonal singlewavelets are suitable basesfor different types of signals, e.g. images, since they analyse high frequencies with bases of smallcompact support and low frequencies with bases of large support. An important application is thedenoising of images [3]. Thereby, the noisy image is transformed into the wavelet domain. Then,the small coefficients being dominated by the noise are eliminated by setting them to zero. Only theremaining large coefficients are used for reconstructing the image. The result is a denoised imagemainly containing the pure image information.Symmetry of the bases is a desired property for image compr'ession applications [lo], as symmetric bases allow to preserve the signal's phase in the transform domain and an efficient processing atborders. However, with exception of the trivial Hadr bases, it is impossible to delsign orthogonal andsymmetric singlewavelets. Multiwavelet systems based on 2 scaling functions and 2 multiwavletsallow the properties regularity, orthogonality and symmetry, simultaneously 19, 61. This makesmultiwavelets to appropriate bases for image compression algorithms. Also for implementing multiwavelet systems filterbank structures can be used. Thereby, with each stage of the transform thesignal is divided by two lowpass filters GI ( z ) ,Gz( z ) concerning the scaling functions and twohighpass filters H I ( z ) ,H 2( z ) concerning the multiwavelets. For implementing these stages of thetransform lattice structures being composed of orthogonal 2 x 2-rotations were presented in [ 6 ] .1063-6862/97 10.00 0 1997 IEEEAuthorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.489
With respect to image compression two different approaches are possible: With the first approach ainultiresolution of the image is executed and the coefficients of different scale are coded [lo]. Withthe second approach after an 8- or l k h a n n e l filtering (DCT, LOT) of the image the coefficients ofthe different channels are coded [5]. The big advantagz of multiwavelet systems is, that they offergood bases for both approaches.The computational complexity plays an important role not only for image denoising and compression, but also for many other algorithms were wavelet transforms are used. Therefore, anefficient implementation of orthogonal wavelet transforms is desired. Since the basic modules ofthe wavelet lattice filters are orthogonal 2 x 2Zrotations, implementing the orthogonal rotations bya few shift and add operations is equivalent to an efficient implementation of the whole transform.The CORDIC-algorithm offers one possibility to execute elementary rotations, whereby a sequenceof elementary rotations being implementable with a few shift and add operations is used. CORDICbased approximate rotations [4, 8 , 2 ] renounce on the full sequence of elementary rotations by usingonly a few elementary rotations such that the computational complexity is significantly reduced. Inthis paper the influence of this approximation on the performance of the wavelet transform withrespect to the practical applications is discussed. Approximated, orthogonal wavelet systems showing a very simple implementation are presented. With respect to practical applications, like imagedenoising or compression they perform in the same way as exact transforms.2Orthogonal SinglewaveletsOrthogonal singlewavelet systems are based on one scaling function @ ( t )and one waveletfunction Ik(t), which meet the following dilation equations:cn-1n-1a ( t ) g i a (2t - i )i Ohi@( 2 t - i)@ ( t ) i OThe discrete coefficients g i and hi define the discrete wavelet transform and the wavelet filtersG(z) giz? (lowpass) and H ( z ) h i x i(highpass). Wavelet transforms canbe implemented by the filterbank structure of Figure 1, whereby each stage is composed of thecomplementary wavelet filters. Suitable architectures for the implementation of these orthogonalH(zi)72tFigure 1: Filterbank structure implementing a discrete wavelet transformfilters are lattice structures. Figure 2 shows a lattice filter implementing one stage of Daubechies’wavelet transform of length n 4. Obviously, the basic modules are 2 x 2-rotations. By only usingorthogonal rotations, orthogonality of the transform is structurally imposed. For the lattice filter toperform an orthogonal wavelet transform, another property is necessary. This property ensures, thatthe wavelet function is zero mean, what is equivalent with the wavelet having at least one vanishingmoment and the transfer functions G ( z ) and H ( z ) having at least one zero at z 1 and z -1,respectively. In [7, 81 it was used, that these conditions are fullfilled, if the sum of rotation angles490Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
Figure 2: Lattice filter implementing one stage of Daubechies' wavelet transform of length n 4PI; is constant:Cph -45"kTherefore, a lattice filter whose sum of all rotation angles is -45" performs an orthogonal wavelettransform, independent of the angles / ? E .3Orthogonal MultiwaveletsMultiwavelet systems using 2 scaling functions and 2 wavelets are based on 4 dilation equations,that are also represented by the basis matrix W of size 4 x 4m.22m-12Zm-1g1,1 . . . g1,4m-l92,l . ' ' g2,4m-Ih1,o h1,l . ' . k 4 m - 1g1,oQ2,oh2,l&,O.h2,4m-1'In [9] multiwavelets were designed that allow the properties regularity, ortogclnality and symmetry, simultaneously. Thereby, G I (1st row of W )and XPl (3rd row of W )being symmetric, anda2(2nd row of W )and P2 (4th row of W )being antisymmetric, requires a specially structuredwavelet basismatrix W .aoboaibiboa.blalai-bl-bial-boa.Setting 0.009977,0.697129, bo bl -0.083399results in the bases plotted in Figure 3.Also for multiwavelet transforms, filterbanks (Figure 4) and lattice structures offer an efficientimplementation of the multiwavelet filters G , ( z ) Cy:; g W / , H , ( z ) Cy:: h , r i , U E{ 1,2}. Figure 5 shows a lattice structure implementing orthogonal multiwavelet filters. Again,orthogonality is ensured by using only orthogonal rotations, (a wavelet transform (at least onevanishing moment) is guaranteed by the constant sum of rotation angles491Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
-Figure 3: Multiwavelets ofR 4,p 2 and the corresponding scaling functionsstage 1stage 2w,w2mFigure 4: Filterbank for implementing multiwavelet transformationen4Efficient Implementation of Orthogonal RotationsSince in the singlewavelet- as well as in the multiwavelet case the lattice filters are composed oforthogonal 2 X 2-rotations only, in order to get a simple implementation of the filters, an efficientimplementation of the orthogonal rotations is sufficient.An orthogonal 2 x 2-rotation R ( N )is defined as follows:R ( 0 ) cos0[ sin0-sin&COSNIThe CORDIC algorithm is a common method to execute orthogonal rotations by using a sequenceof w 1 protations ( U , being the wordlength): with 2K, n-, being the scaling factor. This corresponds to the representation ofL-1 2-2'iI;cyaskThis representation of an angle in the "arctan 2-I;" basis is also the basic idea of CORDIC-basedapproximate rotations [4], but there we have m k E { - l , O , l}.492Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
Figure 5: Lattice structure implementing mu1 tiwavelet filtersIn [4] double rotations consisting of 2 equal CORDIC elementary rotations were used, whichrotate by the angle 2 a k , i.e. R ( 2 c r h ) R(crk)R(crh)such thatNow, the scaling factor4can be factorized into a sequence of shift & add operations:K,With one (or a few) of these double rotations an approximate rotation can be composed, that issimple to implement, approximates any rotation angle to a certain accuracy (increasing the numberof double rotations increases the accuracy), and is always exactly orthogonal independent of theaccuracy.5Efficiently implemented Singlewavelet transforms for image denoisingIn order to get efficiently implemented singlewavelet transforms, instead of the complete sequenceof elementary rotations only a few CORDIC-based elementary rotations are used in order toapproximate the exact rotations quite well. By always using double rotations (with different signs)the constant sum of rotation angles is not violated and a simple implementation of the scaling factor -60" and Pz 15" are approximated byis possible. For the presented example of n 4 a c t a n 2 -M 14.04". The corresponding scaling -45" - arctan2-' M -59.04" and) the exact rotation angles (dotted line) and for the case of the approximation (solidfunctions @ ( tforline) are plotted in Figure 6 (upper part) together with the zeros of the transfer functions G ( z ) .Theresulting lattice structure is shown in Figure 6 (lower part), whereby only very few shift and addoperations are necessary.The decisive question is, how the performance of the wavelet transform is influenced by theapproximation that allows the very simple implementation. Denoising of images is an importantapplication of orthogonal wavelet transforms. Thereby, according to Figure 7' the noisy imageis transformed into the wavelet domain, the small coefficients being dominated by the noise arethreshholded, before the image is reconstructed by the inverse wavelet transform. In order toimprove the performance of the transform, redundant, time-invariant, undecimated, orthogonalwavelet transforms are often used instead of nonredundant, time-variant, decimated, orthogonalPI493Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
14--0 4 ’1\“‘I123compact suppon45-1-050051realFigure 6: Comparison of Daubechies’ standard scaling function o f length n 4 (dotted line) andthe version showing a simple implementation (solid line)noisysignal*OrthogonalWavelet Transform JInverseWaveletTransformdenoisedsignal/Figure 7: Denoising of signals via wavelet transformFigure 8 (left) shows a Lena image, whose quality is affected by white Gaussian noise of 21.2dB. By wavelet denoising the quality of the image can be improved to 28.4 dB what is documentedin Figure 8 (right). Note, that this application is quite robust with respect to the accuracy of thewavelet transform: There is almost no difference in the performance of the algorithm using theexact or the approximated wavelet filters. Only exact orthogonality -this is guaranted in both casesis important for this application. Note also, that wavelet denoising is not limited to a special kindof noise, different kinds of disturbances, e.g. blockartefacts, can be filtered out of the images.494Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
Figure 8: Noisy (left) and denoised (right) version of Lena6 Efficiently implemented Multiwavelet transforms for irnage compressionIn order to get efficiently implemented multiwavelet transforms, again, we approximate the exactrotation angles by using only a few CORDIC-based elementary rotations. The example of Figure3 requires the angles w1 -w2 6.8", which are approximated by using only one elementaryrotation by i;ll -G2 a c t a n 2 -F 7.1". This results in the lattice structure of Figure 9 andin continuous bases that cannot be distinguished from those of Figure 3. With respect to imageFigure 9: Lattice structure approximating the multiwavelet filters of n 4 and p 2compression one has to choose between two wide-spread algorithms:0Wavelet coder encode the different scales of the image in the multiresoluting wavelet domain.Classical subband coder use the DCT or LOT [5] in order to get the 8 (16) frequency channelsof the image being encoded and compressed.Though both approaches are possible with the presented multiwavelets, here we focus on the subbandcoder showing how multiwavelet packets work as lapped orthogonal transforms. In order to get an495Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
8 channel filterbank, the wavelet packet transform with 2 stages of Figure 10 must be used. Note,that both stages ( W ,, W , )are slightly different because a wavelet-like transform being necessary[9]. Implementing this wavelet packet transform with 2 stages using approximate rotations leads tostage 1stage2Figure IO: %channel wavelet packet structurethe very simple structure of Figure 1 1. The computational costs are reduced to a few shift and addoperations (Note, that only the scaling is not considered in Figure 11. Thereby, the analysis andsynthesis can be combined).Figure 1 1 : Architecture for efficiently implementing the multiwaveletpacket-based lapped orthogonal transformThe decisive question again is, how the multiwavelet-based lapped orthogonal transform showingthe simple implementation performs in comparison to other well tried transforms with respect toimage compression. Figure 12 compares the impulse responses of the transfer functions of the 8channels, whereby the dotted line belongs to the classical LOT designed by Malvar and the solidline belongs to the multiwaveletpacket-based lapped orthogonal transform (there are no visibledifferences between exact and approximated case). Obviously, the curves are similar, in themultiwavelet case the behavior at the borders is even smoother.In order to evaluate the quality of the multiwaveletpacket transform (MWT) in comparison toMalvar's LOT or the DCT, an image compression algorithm according to Figure 13 [ l l ] was used.Figure 14 shows the results obtained for the Lena image, it confirms the similarity of the quality ofMalvar's LOT and the multiwaveletpacket-based lapped orthogonal transform and the improvement496Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
05-0.505io10okvl-051520I5-1520101520OpW-0 505jpw2[-0.5’0I5101520-0 505101521)Figure 12: Impulse response of Malvar’s LOT-filters (dotted lint:) compared to niultiwaveletpacketbased filters (solid line)Coding(LOT,M\NT)USymmetricExtensionFigure 13: Coding procedureof these transforms in comparison to the classical DCT: Depending on the compression (0.1-1 .Obpp) the SNR between reconstructed and original image is analyzed for the DCT, Malvar’s LOT,and the multiwaveletpacket transform. For the most interesting range (0.5 bpp - 1.0 bpp) themultiwaveletpacket transform is even slightly better than Malvar’s LOT.Note, also DCT, LOT or generalized lapped orthogonal transforms can be efficiently implementedby using approximate rotations [2]. However, the presented architecture only requires cornputational cheap orthogonal rotations, whereby other structures use orthortormal rotations additionallyrequiring a scaling procedure per rotation.7ConclusionIn this paper the efficient implementation of orthogonal singlewavelet transforms and symmetricmultiwavelet transforms based on 2 scaling functions was presented. Since both transforms are basedon orthogonal 2 x 2-rotations, their efficient implementation is achieved by using CORDIC-basedapproximate rotations being composed of very few shift and add operations. This approximationdoes not came the loss of the quality of the transform with respect to its properties orthogonality,regularity, frequency behavior. For practical applications, like image denoisirig or compression,497Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
.L- l o0102030405060709OScompressFigure 14: Comparison of different transforms with respect to image compressionwhere the computational complexity is important, the wavelet transforms showing a very simpleimplementation perform quite well.AcknowledgementThe authors would like to thank S. Trautmann and T.Q. Nguyen for making their image compression algorithms being used for the presented work available on the internet.References111 I. Daubechies. Ten Lectut-ex on Wavelets. Notes from the 1990 CBMS-NSF Conference on Waveletsand Applications at Lowell, MA. SIAM, Philadelphia, PA, 1992.[2] E.F. Deprettere, G. Hekstra. and R. Heusdens. Fast VLSI Overlapped Transform Kernel. Preprint.[ 3 ] D.L. Donoho. De-Noising by Soft-Thresholding. ZEEE Trans. Inform. Theor), 41:613-627, 1995[4] J. GZitze and G.J. Hekstra. Adaptive Approximate Rotations for Computing the EVD. In M. Moonenand F. Cathoor, editors, Algorithms urd furallel VLSI Archifectures.Elsevier Science Publishers, 1994.[ 5 ] H.S. Malvar and D.H. Staelin. The LOT: Transform Coding Without Blocking Effects. IEEE Trans. onAcoustics, Speech and Signal Processing. 37(4):553-559, April 1989.[6] P.Rieder. parameterization of Symmetric Multiwavelets. Proc. ZEEE I n f . Con Acoust., Speech andSignal Processing, ICASSP 97, Munich, April 1997.[7] P. Rieder, K. Gerganoff,J . Gotze, and J.A. Nossek. Parameterization and Implementation of OrthogonalWavelet transforms. Proc. IEEE Int. Con Acoust., Speech and Signal Processing, ICASSP 96, Arlantu,111:15 15-1518, Mai 1996.[SI P. Rieder, J. Gotze, J.A. Nossek, and C.S. Burrus. Parameterization of Orthogonal Wavelet Transformsand their Simple Implementation. IEEE Trans. on Circuits and Systems 11, 1997.[9] P. Rieder and J.A. Nossek. Smooth Multiwavelets based on 2 Scaling Functions. Proc. IEEE Int. Symp.on Erne-Frequencyund Time-Scule Analysis, pages 309-3 12, June 1996. Paris.[ I O ] J.M. Shapiro. Embedded Image Coding Using Zerotrees of Wavelet Coefficients. IEEE Transaction onSignal Processing, 41 (12):3445-3462, December 1993.[ 1 I ] S. Trautrnann and T.Q. Nguyen. GenLOT: Design and Application for Transform-BasedImage Coding.Pmc. of the Asilomar Conference, Nov. 1995.498Authorized licensed use limited to: T U MUENCHEN. Downloaded on October 29, 2008 at 06:16 from IEEE Xplore. Restrictions apply.
Implementation of Orthogonal Wavelet Transfiorms and their Applicatioiis Peter Rieder and Josef A. Nossek Institute of Network Theory & Circuit Design Technical University of Munich Abstract In this paperthe eflcient implementation of different types of orthogonal wavelet transforms with respect to practical applications is discussed.
wavelet transform combines both low pass and high pass fil-tering in spectral decomposition of signals. 1.2 Wavelet Packet and Wavelet Packet Tree Ideas of wavelet packet is the same as wavelet, the only differ-ence is that wavelet packet offers a more complex and flexible analysis because in wavelet packet analysis the details as well
Wavelet analysis can be performed in several ways, a continuous wavelet transform, a dis-cretized continuous wavelet transform and a true discrete wavelet transform. The application of wavelet analysis becomes more widely spread as the analysis technique becomes more generally known.
The wavelet analysis procedure is to adopt a wavelet prototype function, called an analyzing wavelet or mother wavelet. Temporal analysis is performed with a contracted, high-frequency version of the prototype wavelet, while frequency analysis is performed with a dilated, low-frequency version of the same wavelet.
aspects of wavelet analysis, for example, wavelet decomposition, discrete and continuous wavelet transforms, denoising, and compression, for a given signal. A case study exam-ines some interesting properties developed by performing wavelet analysis in greater de-tail. We present a demonstration of the application of wavelets and wavelet transforms
3. Wavelet analysis This section describes the method of wavelet analy-sis, includes a discussion of different wavelet func-tions, and gives details for the analysis of the wavelet power spectrum. Results in this section are adapted to discrete notation from the continuous formulas given in Daubechies (1990). Practical details in applying
448 Ma et al.: Interpretation of Wavelet Analysis and its Application in Partial Discharge Detection R&b be (b) Figure 2. Examples of the shape of wavelets.a, db2 wavelet; b, db7 wavelet. signal can be disassembled into a series of scaled and time shifted forms of mother wavelet producing a time-scale
Workshop 118 on Wavelet Application in Transportation Engineering, Sunday, January 09, 2005 Fengxiang Qiao, Ph.D. Texas Southern University S A1 D 1 A2 D2 A3 D3 Introduction to Wavelet A Tutorial. TABLE OF CONTENT Overview Historical Development Time vs Frequency Domain Analysis Fourier Analysis Fourier vs Wavelet Transforms Wavelet Analysis .
The Certificate in Russian Language is six- month programme of 16 Credits. The programme aims at providing beginners with basics of Russian Language. The objective of the programme is to introduce learners to the basics of Russian grammar and phonetics so that they can read, write, listen and speak Russian in an accurate manner. The programme is bilingual (Russian/English) in medium and has .
