分段摺積與小波轉換

Abstract

離散小波轉換 (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. In 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. The 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. Recently, 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. In 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. In Chap. 1, I will introduce the basic ideas and history of the wavelet transform. In Chap. 2, I will introduce the definition and the computation complexity of the DWT, including the detailed derivation, property. In Chap. 3, I will introduce the applications of the DWT simply. In Chap. 4, I will introduce the EIDWT and compare it to the traditional DWT in computation complexity. In 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. In 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. In Chaps. 7, 8, I will introduce other researches of method to improve the efficiency of DWT May this thesis be helpful for you.