Wavelet Transform and Fast Fourier Transform for Sig Nal Compression: A Comparative Study

Wavelet Transform and Fast Fourier Transform for Sig Nal Compression: A Comparative Study

Subramanian K.A., Karthigeyan R. Karpagam College of Engineering

Abstract Wavelet and Fourier transform are the commonmethods used in signal and image compression. Wavelet transform (WT) are very powerful compared to Fourier transform (FT) because its ability to describe any type of signals both in time and frequency domain simultaneously while for FT, it describes a signal from time domain to frequency domain. Because of that, the performance of FT is outperformed by the impressive ability of WT for most type of signals (stationary or non- stationary). In this paper, we will discuss the use of Fast Fourier Transform (FFT) and Discrete Wavelet Transform (DWT) for signal compression. We do the numerical experiment by considering three types of signals and by applying FFT and DWT to decompose those signals. For DWT, various wavelet filters such as Haar (2 filters) and Daubechies (up to 10 filters) are used. All the numerical results were done by using Matlab programming.

KeywordsFFT, DWT, compression, filters, threshold

1. INTRODUCTION

   From day to day, the technology is increasing rapidly. This led to the demand of faster, greater and more efficient for any kind of works. Same goes to signal processing field. Signal with better quality, minimum size and lowest data rate is really demanded. Thus, the data compression is highly required in order to achieve that. Data compression is the process of reduction in size of data in order to save transmission time and storage [1]. For example, storage and transmission of uncompress data would be extremely costly and impractical if we are dealing with huge size of data. Without data compression, a 10 Gb of data would take couple of hours to fully transmitted. So, what is the best method for signal compression? As explained above, WT and FT are the method that can be used to decompose and compress the signal.

   In [1], the author discussed the use of WT (up to 10 filters) for speech compression. Speech compression is a process of converting human speech signals into efficient encoded representation that can be decoded back to produce a close approximation of the original signals. The input signal used is a 8 kHz 8-bit speech. Based on PSNR, SNR, NRMSE and compression ratio, they concluded D10 wavelet filter gives higher SNR and better speech quality with compression ratio up to 4.31 times and reduced the bit rate from 64 kbps to 13 kbps. In [4], the authors use wavelets to compress speech signal. They used spoken English speech to be analysed by D20 wavelet filter. The

   plot of SNR vs Compression Ratio (CR) was made and showed as CR goes higher, SNR gets lower. In [6], the author did the speech compression using Battle-Lemarie wavelet, Haar and Daubechies (up to 20 filters). The analysis was done by using voiced and unvoiced speech and the results shows Battle- Lemarie wavelet is the best while the other filters almost comparable except Haar. The numerical results were based on percentage of energy concentrated. While in [7], they analysed the effect of different compression schemes on speech signal. They used D4, D8, D10 and D20 and their input is Arabic speech signal (digit 0 and 8). Based on SNR, PSNR and Normalized RMSE (NRMSE), they found that, by using smooth wavelets like D10, the percentage of truncated coefficients decreased and gives better SNR. For unsmooth wavelet, it gives better compression ratio but with low SNR. Last but not least, in [10], the authors evaluated audio compression by using WT (up to 10 filters). Their main objective is to achieve transparent coding of audio and speech signal at the lowest possible data rate. Based on the numerical results, the found that D10 is the best wavelet filter with the lowest SNR and highest compression ratio (CR=1.88).

   In this paper, it is quite different where the comparison will be made for signal compression using Fast Fourier

   Transform (FFT), Haar and Daubechies (up to 10 filters). k=f(x) jk(x)dx (5)

   Furthermore we do numerical comparison for all method and we also show the analysis starting level 1 for DWT.

   The analysis that we have done is more concrete and Those two coefficients 0k and jk are called scaling reliable. We also showed all the statistical measurement

   with the plots of RMSE versus level of compression for all wavelet filters length. All the results will be discussed

   more detail in result and discussion section.

2. FOURIER TRANSFORM

   Fourier Transform (FT) is one of the methods for signal and image compression. FT decomposes a signal defined on infinite time interval into a -frequency

   component where can be either real or complex number

   function and wavelet function (where

   j

   jk(x)=22(2jxk),j,k< Z (6)

   In this paper, we use Haar (2 filters) and Daubechies N (D N) where N is the filter length such as D4, D6, D8 and etc. Some properties of the Daubechies wavelets are asymmetric in particular for low values of N, orthogonal

   [2]. Since Daubechies (1988) and Mallat (1989) have with compact support, the regularity increases with order introduced compactly supported orthonomal wavelets of N and the analysis is orthogonal. By looking at Haar with fast algorithm, Wavelet Transform (WT) has been scaling and wavelet function, we already can guess what using in signal processing successfully [8]. FT is actually type of signal that Haar is the best to do the compression is a continuous form of Fourier series. In this paper, we process. Because of a step or block function, Haar is only are focusing on Discrete Fourier Transform (DFT) since powerful for block or step type of signal. If we have sine we are dealing with discrete data. To be specific, we will or cosine type of signal, Haar obviously be the worst and use FFT because it is an efficient algorithm to compute we can see clearly that FFT outperformed the Haar

   the DFT and its inverse. The definition for DFT is: method. . For wavelets, it decomposes a signal into high

   frequency (details) and low frequency (approximation) of

   N 1 i2 n

   k N coefficients. That could be possible because of high pass

   X k=X n e where k=0,……….,N-1 (1) and low pass filter in wavelets function. Then, the signal

   n=0 can be compressed and reconstructed to recover the original signal where we will get almost the same type,

   We can compress a signal by taking its FFT and then discard the small Fourier coefficients [15]. For example if we have 1024 sampled signal and we apply the FFT to transform the signal into frequency domain, we can decide the percentage of coefficients that we want to zero them. That is how we determine the compression ratio for signal compression using FFT.

3. WAVELET TRANSFORM

   Wavelet transform is the latest method of compression where its ability to describe any type of signals both in time and frequency domain [3], [11] & [12]. That makes WT becomes the most needed tool in signal and image processing area. Wavelet is defined from its scaling

   function (father wavelet) and wavelet function (mother wavelet) [5] & [16]. Wavelet is compactly supported

   orthonomal where the function is

   shape, characteristics of the original signal.

   Figure 1: The decomposition of the signal

   (t)=2j2(2jtk),j,k< z (2)

4. DATA COMPRESSION AND THRESHOLDING

   Wavelet series can be defined as below To compress a signal, it involves the conversion of

   data from one format into different format which requires

   f (x=kkok(x)+jkjk(x) (3) less time to analyse. There are two algorithm process j =0 k used in this paper where it is for FFT and DWT respectively. For FFT, we apply FFT and decide the

   The components of and are the coefficients percentage of coefficients that we want to eliminate. defined by Unlike FFT, DWT is more complex. After we

   decompose the signal via multiresolution analysis, we

   k=f(x)0k(x)dx (4)

   will select threshold values. There exist various choices

   of threshold selection. In data compression, all

   coefficients will set to be zero when they fall below the threshold values. We may apply threshold either as global or level dependent. In this paper we will use global thresholding (universal threshold) for all level. Eq. (7) gives formula for global threshold value

   =2log2(N) (7)

   where N is total of data. For more detail on thresholding selection and data compression, the reader are refer Mallat (2009) and Karim et al. (2010b).

5. RESULT AND DISCUSSION

   In this section, the application of FT and WT will be discussed more detail using numerical observation and analysis. For comparison purpose, three types of signal (Block,Heavy Sine andMishmash) will be used. Fast Fourier Transform (FFT) and Discrete Wavelet Transform (DWT) (up to 10 filters) will be using to compress those data. The main reason to have those three types of signal is to observe which type of compression method is the best for each type of signals. The elimination of high frequency coefficients is the keyword for FFT while for DWT, the thresholding value will determine the percentage of zeroes that can be reduced but will not affect the signal characteristics. Figure 2 shows the approximations for wavelet decomposition of original signal 1(Block), up to level 5 by using D4. Meanwhile, Figure 3a, 3b and 3c show the original signal 1, compressed signal 1 by using FFT and compressed signal by using Daubechies 4 respectively.

   The compression process for FFT is done by determining the percentage of high frequency coefficients that will be removed. For DWT, we need to find the threshold value. This is done by using global thresholding and automatically all the levels will be set up to same value of threshold. For different type of signals, the optimum level is slightly different.

   Figure 2: Signal 1 approximation (left) and details (right) using D4

   Figure 3a: Original Signal 1

   Figure 3b: Compressed Signal 1 using FFT

   68

   1

   INTERFACE ECE T14

   Figure 3c: Compressed Signal 1 using D4

   From Figure 2, we notice that a signal is decomposed into approximation and details parts. The details consist of the high frequency coefficients while the approximation consists of low frequency coefficients. From Figure 2b, the d1 part shows the most high frequency in a signal. At it goes up to d5, the frequency is getting lower. We want to remove the high frequency coefficients as high as we can but maintaining the characteristics of the signal by looking at the approximation part. For example, for signal 1, a2 is the most acceptable approximation signal because a3 gives quite weak signal accuracy. So, we can threshold that signal up to d2.

   In this paper, only decomposition using D4 are shown while for decomposition using D2 (Haar), D6, D8 and D10, the readers can refer to [9] and [14] where all the details are there including numerical comparison. . In this paper we show the overall result for the compression all the three types of signals by using FFT and Daubechies wavelet (D2 until D10). The overall comparison will answer the objective of the paper where it will give which method (FFT, Haar and DN) will perform better for each signal. Even though we knew that wavelet is the best method of compression; it is not a reason to deny the power or ability of FFT function. There is certain type of signals where FFT perform better than DWT. Table 1 shows the statistical analysis of the results.

   compression ratio (CR). A good compression process will have a high compression ratio. As highlighted in yellow, all of them have the highest compression ratio possible compared to other types of filter. Normally, this paramete will be looking after other parameters (MSE, RMSE, RE and NOZ) have been considered. Bear in mind, a very high compression ratio sometimes gives a bad recovered signal and for that reason all the parameters are interrelated and need to be considered.

   From the Table 1, Haar is the best method for Signal 1 compression. Theoretically, if we look at Haar filter diagram it is a step function where logically for sure it is the bes method to compress type 1 signal which is Block function Moreover, for Signal 2 (Heavy Sine), FFT gives the best result compare to Daubechies and Haar. If we look at function of Signal 2, we simply can say sine or cosine type o signal can best be compressed by using FFT. Lastly Daubechies 8 is the best for Signal 3 (Mishmash compression. So,the results have proved that different type method of compressions give different analysis and result fo different type of signals.

   The other parameter that is quite important in the analysis is

   r

   ,

   t

   .

   f

   ,

   )

   r

   1 2 3 4 5 6 7 8 9 10

   compression level

   compression level

   169

   INTERFACE ECE T14 INTRACT INNOVATE – INSPIRE

   	Signal 1 (Block)		Signal 2 (Heavy Sine)	Signal 3 (Mishmash)
   Haar	CR	17:1	18:1	4:1
   	MSE	0	0.0272	0.3369
   	RMSE	0	0.1649	0.5804
   	RE (%)	99.99	99.70	76.82
   	NOZ (%)	94.04	94.34	72.46
   D4	CR	13:1	30:1	3:1
   	MSE	0.0215	0.0207	0.1834
   	RMSE	0.1468	0.1439	0.4283
   	RE (%)	99.74	99.77	87.34
   	NOZ (%)	92.19	96.64	60.83
   D6	CR	14:1	39:1	3:1
   	MSE	0.0457	0.0186	0.1468
   	RMSE	0.2137	0.1364	0.3831
   	RE (%)	99.48	99.77	89.92
   	NOZ (%)	92.97	97.43	61.88
   D8	CR	11:1	41:1	3:1
   	MSE	0.0326	0.0180	0.1280
   	RMSE	0.1805	0.1342	0.3577
   	RE (%)	99.67	99.73	88.38
   	NOZ (%)	90.88	97.55	63.39
   D10	CR	10:1	35:1	3:1
   	MSE	0.0415	0.0214	0.1314
   	RMSE	0.2038	p>0.1463	0.3625
   	RE (%)	99.60	99.72	90.93
   	NOZ (%)	90.08	97.11	61.62
   FFT	CR	10:1	10:1	10:1
   	MSE	0.1395	0.0062	0.5546
   	RMSE	0.3735	0.0787	0.7447
   	NOZ (%)	90	90	90

   Table 1: Overall Comparison (FFT versus DWT)

   Figure 4 shows the performance of wavelet filters for each level. As in the Table 1, Haar give the best performance where it goes down to 0 (RMSE) for level 9 and 10. It is very clear that other filters could not compete with the ability of Haar. From Figure 5, all filters except Haar show a quite similar performance for signal 2 compression. Haar did not give a good result for most levels and for signal 2, FFT

   actually is the best. (Refer Table 1). The comparison is made

   for wavelet filters to see the performance of them. From Figure 6, we can noticed that, Haar is obviously incomparable with other filters due to a very bad result. Again, the performance of all filters except Haar is quite similar but D8 and D10 are a bit better.

   CONCLUSION

   The main idea of data compression via FT and WT is to transform a signal or data into a new domain which can easily be computed, analyzed and can be transmitted with less storage but with no accuracy degradation. In this paper, we have discussed the signal by using FFT, Haar and Daubechies (up to 10 filters) . We do the numerical comparison on MSE, RMSE and CR between FFT and DWT. The results indicated Haar is the best for signals with step or block function. For sine or cosine based signal, FFT gives a quite impressive result and Daubechies give a good result for Mishmash type of signal. Roughly, all methods give a good result in term of MSE, RMSE and compression ratio (CR). For future research, we will consider more type of signals and to categorize them in different method of compression. We will report the result in our forthcoming papers.

   170

   INTERFACE ECE T14 INTRACT INNOVATE – INSPIRE

6. REFERENCES

1. A. M. M. A. Najih, A. R. Ramli, V. Prakash & A. R. Syed, Speech Compression Using Discreet Wavelet Transform, NCTT 2003 Proc. 4th National Conference on Telecommunication Technology, pp. 1-4, 14-15, Jan. 2003.

2. A. Boggess and F. J. Narcowich, A First Course in Wavelets withFourier Analysis, 2nded., John Wiley & Sons, Inc. Hoboken,New Jersey, 2009.

3. C. K. Chui, An Introduction to Wavelets, Academic Press, New York, 1992.

4. H. Elaydi, M. I. Jaber & M. B. Tanboura, Speech Compression Using Wavelets, The International Arab Conference on Information Technology, pp. 1-8, 2003.

5. I. Daubechies, Ten Lectures on Wavelets, Vol 61, CBMS-NSF Reg. Con. Ser. Appl. Math.,Society for Industrial Applied Maths (SIAM), Philadelphia, PA, 1992.

6. J. I. Agbiny, Discrete Wavelet Transform Techniques in Speech Processing, IEEE TENCON-Digital Signal Processing Application, pp. 514-519, 1996.

7. J. Karam and R. Saad, The Effect of Different Compression Schemes on Speech Signals, International Journal of Biomedical Sciences, Vol.1 No.4, pp: 230-234, 2006.

8. Mallat, Wavelet Tour of Signal Processing 3rd Ed. Academic Pres, San Diego, California, 2009.

9. M. H. Kamarudin, On the use of Daubechies Wavelets for Signal and Image Compression: Some Numerical Evaluation, Bachelor Thesis (Hons), Universiti Teknologi PETRONAS,, 2010..

10. O. O. Khalifa, S. H. Harding, & A. H. A. Hashim, Audio Compression using Wavelet Transform, International Journal of Security, ISSN: 1985-2320, Computer Science Journals, Vol. 2, No. 5, pp. 17-26, September, 2008.

11. S. A. A. Karim, M. T. Ismail, B. A. Karim, M. K. Hassan, and

    J. Sulaiman, Compression KLCI Time Series Data Using Wavelet Transform, World Engineering Congress 2010, 2nd 5th August 2010, Kuching, Sarawak, Malaysia Conference on Engineering and Technology Education. In CD, 2010.

12. S. A. A. Karim, B. A. Ismail, M. T. Hasan, and J. Sulaiman, Applications of Wavelet Method in Stock Exchange Problem, Proceedings of International Conference on Fundamental and Applied Sciences (ICFAS 2010), 15-17 June 2010, Kuala Lumpur Convention Center, 2010. In CD, 2010a.

13. S. A. A. Karim, B. A. Karim, M. T. Ismail, M. K. Hasan, and J. Sulaiman. Compression of Temperature Data by using Daubechies Wavelets. Proceedings of International Conference on Mathematical Sciences (ICMS2 2010), 30 November 3 December 2010, PWTC Lumpur , 2010. pp. 726-734, 2010b

14. S. A. A. Karim, and M. H. Kamarudin, Signal Compression using Fast Fourier Transform (FFT) and Discrete Wavelet Transform (DWT): Some Numerical Comparison, Preprint, 2010.

15. The Scientist and Engineers Guide to Digital Signal Processing (Chapter 12), 1997. Retrieved March 2010, from http://www.dspguide.com/cp2/2.htm.

16. Y. Meyer, Wavelet and Operators, Cambridge University, Cambridge, 1992.

171