丁建均臺灣大學:電信工程學研究所沈汝川Shen, Nu-ChuanNu-ChuanShen2010-07-012018-07-052010-07-012018-07-052008U0001-0907200818092200http://ntur.lib.ntu.edu.tw//handle/246246/188228離散小波轉換 (discrete wavelet transform)，是大家耳熟能詳的一個數學工具。它被廣泛的應用在工程上，訊號處理上，影像處理上，以及其他許多方面。 這本論文中，我先簡單的介紹離散小波轉換和他的應用，再來我會用我這篇文章所提出的一個方法分段摺積(sectioned convolution)來簡化離散小波的運算複雜度。段摺積是一種摺積運算的快速演算法，將輸入的訊號切割成長度L的大小來做運算。不但可以藉此來解決運算延遲的問題，整體運算的速度和系統的複雜度都可以大幅度的提升。段摺積離散小波轉換(sectioned convolution discrete wavelet transform SCDWT)是一種分段摺積的應用。將傳統離散小波轉換中使用傳統摺積的地方用分段摺積來取代。高效率實作的分段摺積離散小波轉換(efficiency implementation sectioned convolution discrete wavelet transform EISCDWT)它的架構和高效率實作的離散小波轉換(efficiency implementation discrete wavelet transform)相同，並且和分段摺積離散小波轉換一樣，都是將傳統離散小波轉換中使用傳統摺積的地方用分段摺積來取代，藉此來有效的提升運算速度和降低運算複雜度。除了上述提升運算速度和降低運算複雜度這兩個優點外，我們意外的發現它也降低了系統設計的複雜度。這是因為我們將訊號切割成等長每段都是L，這固定了快速離散傅立葉運算的點數，也降低了系統設計的負雜度。年來，關於離散小波轉換的研究，可以說是蓬勃發展。它被廣泛的用在各種不同的應用上。在第三章裡我們有做一些簡單的介紹，我們所提出來的改良方法，相信在這些應用上絕對能提升它們的競爭力。 這本論文中，我將簡單的介紹一下離散小波轉換和它的應用。再來就將重點放在我們所以提出的方法，並且將它和過往的方法做些詳細的比較。第一章，我將介紹離散小波轉換的一些基本概念。第二章，我將詳細的介紹離散小波轉換，對它的推導、性質做分析。第三章，簡單的介紹一些離散小波轉換的應用。第四章，高效能實作的離散小波轉換系統的分析。在這章我比較了高效能實作的離散小波轉換和離散小波轉換運算複雜度的比較。五章，我將仔細的說明分段摺積。並且詳細的比較分段摺積和傳統摺積的差別，從運算速度和運算複雜度這兩方面來進行分析。基於公平性，這章中，所以比較運的模擬都是我們自己寫的，沒有用到任何內建的程式。第六章，我將分析分段摺積運用在離散小波轉換和高效能實作的離散小波轉換上的效能。並且詳細的比較離散小波轉換、分段摺積離散小波轉換和高效率實作的分段摺積離散小波轉換在一階和二階上的運算複雜度。最後我們將利用高效率實作的分段摺積離散小波轉換來做壓縮的JPEG2000和離散餘弦轉換的JPEG作比較。七章和第八章中，我將介紹一些其他改善離散小波轉換效能的方法。第九章，我作個結論。在參考資料 (Reference) 部分，我也對目前相關領域的研究，加以分類整理。 望這本論文對您有幫助。Discrete wavelet transform (DWT) is a very popular mathematical tool. It has been widely applied in engineering, signal processing and image processing, etc. n this thesis, we will introduce the DWT and the application of it and then I will use a method called sectioned convolution that proposed in this thesis to reduce the complexity of the DWT. The sectioned convolution is a fast algorithm of convolution by splitting the input of signal into section by section with sectioned length L, so we do not have to do the convolution until all the signal is received. It not only finds out a way to solve the delay problem but also reduces the computation time and computation complexity very much.he sectioned convolution discrete wavelet transform (SCDWT) is an application of sectioned convolution. It replaces all the traditional convolution computation in the DWT into the sectioned convolution. The efficiency implementation sectioned convolution discrete wavelet transform (EISCDWT) is an efficient way to implement the DWT. Its concept just likes the efficient implementation discrete wavelet transform but we use the sectioned convolution to instead of the traditional convolution. By this replacement, we can reduce the computation complexity and computation time. Beside the advantages that we mention above, there is another advantage that we also reduce the system complexity. Because we split the signal into the same length L, the point of FFT is fixed, the complexity of system is reduced. ecently, there are many research works about the DWT. The DWT has been used for many applications. We believe that the algorithm that we proposed in this thesis can make the DWT more powerful and have a lot of potentiality in the future. n this thesis, I will introduce the research works about the DWT systematically, including the research works of my professor and I and do a detailed comparison to the previous works. n Chap. 1, I will introduce the basic ideas and history of the wavelet transform. n Chap. 2, I will introduce the definition and the computation complexity of the DWT, including the detailed derivation, property.n Chap. 3, I will introduce the applications of the DWT simply.n Chap. 4, I will introduce the EIDWT and compare it to the traditional DWT in computation complexity.n Chap. 5, I will introduce the sectioned convolution and compare it to the traditional convolution on computation time and computation complexity. Considering the fair competition, all the programmings in my thesis are written by myself. n Chap. 9, I will do a detailed analysis of SCDWT and EISCDWT and a comparison between the DWT, SCDWT and EISCDWT. In the end of this chapter, I will compare the JPEG2000 with EISCDWT and JPEG wit DCT. n Chaps. 7, 8, I will introduce other researches of method to improve the efficiency of DWT ay this thesis be helpful for you.ABSTRACT #hapter 1 Introduction 1.1 Basic Ideas 1.2 History of Development of Wavelets 2.3 The Abbreviations Used in This Thesis 3hapter 2 Discrete Wavelet Transform 5.1 Introduction 5.2 Scaling Function 5.3 Multiresolution Analysis (MRA) 6.4 Wavelet Function 6.5 Discrete Wavelet Transform 7.6 The Daubechies Wavelet Transforms 9.7 Symmlets and Coiflets Wavelets 12.8 Two Dimension Discrete Wavelet Transform 12.9 The Computation Complexity of 1-Dimension Discrete Wavelet Transform 15.10 The Complexity of 2-Dimension Discrete Wavelet Transform 17.10.1 The Complexity of 2 Dimension Orthogonal Case 17.10.2 The Complexity of the Biorthogonal Case 19hapter 3 Applications of the Wavelet 23.1 Image compression 23.2 Biorthogonal Wavelets for Waveform Coding in BPSK and QPSK System 24.3 Wavelet Modulation: A Prototype for Digital Communication System 24.4 Face Detection Using Quantized Skin Color Regions Merging and Wavelet Packet Analysis 25.5 Edge Detection of High Resolution Remote Sensing Imagery Using Wavelet 25.6 Video Compression Using 3D Wavelet Transform 26.7 Dynamic Wavelet Feature-Based Watermarking for Copyright Tracking in Digital Movie Distribution System 27hapter 4 Efficient Implementations of The DWT 29.1 Introduction 29.2 Energy Consumption Made by Discrete Wavelet Transform 30.2.1 Computation Energy 30.2.2 Communication Energy 31.3 Computation Complexity of DWT in Direct Way 31.4 Efficient Implement of the DWT 33.5 Computation Complexity of the Efficient Implement DWT 34hapter 5 Sectioned Convolution 39.1 Introduction 39.2 Sectioned Convolution 39.2.1 Overlap-Add Method 40.2.2 Overlap-Saved Method 44.3 The Computation Complexity of Sectioned Convolution with One Dimension Signal 47.4 The Computation Complexity of Sectioned Convolution with Two Dimension Signal 50.5 Simulation Result 53.5.1 Complexity and Computation Time of Sectioned Convolution 53.5.2 Comparing the Computation Complexity of the Sectioned Convolution with Doing Convolution in FFT-Method 54.5.3 Comparing the Computation Time of the Sectioned Convolution with Doing Convolution in FFT-Method 55.6 Conclusion 57hapter 6 Sectioned Convolution DWT and Efficient Implementation Sectioned Convolution DWT 59.1 Introduction 59.2 The Computation Complexity of 1 Dimension Sectioned Convolution DWT and Efficient Implementation Sectioned Convolution DWT 59.2.1 The Computation Complexity of Sectioned Convolution DWT (SCDWT) 60.2.2 The Computation Complexity of Efficient Implementation Sectioned Convolution DWT (EISCDWT) 61.2.3 Efficiency Comparison of 1 Dimension DWT 63.3 The Computation Complexity of 2 Dimension Sectioned Convolution DWT and Efficient Implementation Sectioned Convolution DWT 65.3.1 The Computation Complexity of the SCDWT in 2 Dimension Orthogonal Case 65.3.2 The Computation Complexity of the SCDWT in 2 Dimension Biorthogonal Case 68.3.3 The Computation Complexity of the EISCDWT in 2 Dimension Orthogonal Case 69.3.4 The Computation Complexity of the EISCDWT in 2 Dimension Biorthogonal Case 75.3.5 Efficiency Comparison of 2 Dimension Orthogonal DWT 78.3.6 Efficiency Comparison of 2 Dimension Biorthogonal DWT 81.3.7 Efficiency Comparison of 2 Dimension orthogonal DWT with Different Filter Length 83.4 Comparing the Computation Complexity, Compression Ratio and Compression Quality of the DCT in JPEG and DWT in JPEG 2000 85.4.1 Coding Redundancy 86.4.2 Interpixel Redundancy 86.4.3 Psychovisual Redundancy 87.4.4 Simulation Result 87.5 Conclusion 91hapter 7 Boundary Problems for Implementation 93.1 Introduction 93.2 Decomposition with Lower Compression Ratio 93.3 Reconstruction Problem 99.4 Conclusion 105hapter 8 Other Method to Improve the Efficiency of DWT 107.1 Using Symmetries Property to Reduce the Computation Complexity 107.2 Symmetric Input Signal and Symmetric Filter Coefficient 109.3 Improving the Efficiency of DWT by the DWT Matrix 110hapter 9 Conclusion and Future Work 113.1 Conclusion 113.2 Future Work 114EFERENCE 1151301419 bytesapplication/pdfen-US摺積小波轉換convoluitondiscrete wavelet transformthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188228/1/ntu-97-R95942110-1.pdf