過去二十年，小波轉換在氣象學、地球物理學、聲音訊號處理及資料壓縮等領域已變成了一種標準的處理技術。這些應用所處理的往往都是取樣後的訊號，因此離散小波轉換已成為一廣泛被採用的計算工具。離散小波轉換的快速歸功於Mallat演算法，雖然如此，它仍擁有龐大的計算複雜度。DWT的另一個實現方式是由Swelden所提出的上提式架構。後者與Mallat演算法不同的是它以純粹時域的方式來計算離散小波轉換。可是上提式架構也有兩個缺點，一是架構會隨著小波基底的改變而改變，並非永遠固定；另一是在軟體的實現上等待時間太長。

本論文結合short-length演算法及poly-phase演算法來平衡Mallat演算法及上提式架構的缺點，並提出一新的poly-short-length演算法。由於short-length演算法具有減少乘法數的優點，而poly-phase演算法能解決Mallat演算法中升、降率取樣子所帶來的問題，因此新演算法不但大幅減少了原有的計算複雜度，對於降低乘法數更有顯著的成效。同時，本論文所提出的演算法擁有非常規則的架構，不但更換小波基底不會影響演算法本身的結構，更具有正向轉換與反向轉換架構完全相同的優點。

本論文的實驗分析比較一張512*512大小的靜態影像做離散小波轉換所需要的計算複雜度。以乘法數來計，並使用Daubechies 9/7小波基底，我們演算法的正向小波轉換與Mallat演算法、Short-length演算法及poly-phase演算法相比，只需42.23%、49.27%、75.32%的乘法數；反向小波轉換則只需42.41%、50.01%、75.40%。如果選擇Daubechies 4小波基底，正向轉換只需36.78%、50.00%、75.29%；反向轉換只需37.54%、49.95%、75.29%。與上提式架構相比，雖然我們的演算法在計算複雜度上不如它，但沒有更換小波基底不方便及在軟體實現等待時間太長的缺點。

Over the past twenty years, the wavelet transform has become a standard technique in many fields such as meteorology, geophysics, audio signal processing, and data compression. In these applications, the signals to be processed are usually sampled, so the discrete wavelet transform (DWT) is used extensively. When it comes to DWT algorithm, we always associate it with the Mallat algorithm. Although it is the most famous DWT algorithm, its intensive computational complexity is a big weakness when we practice it. On the flip side, the lifting scheme, proposed by Swelden, is another framework for computing DWT. It provides an entirely spatial-domain interpretation. Its special structure can reduce huge computational complexities. Nevertheless, there are two weaknesses of the lifting scheme. The structure of lifting scheme is not fixed with respect to wavelet bases; that means changing the wavelet basis is not convenient. The other weakness is the waiting time is too long in the software implementation.

This thesis proposes the poly-short-length algorithm, combining the short-length algorithm with the poly-phase algorithm, to balance the Mallat algorithm and the Swelden algorithm. Due to the short-length algorithm having the advantage of decreasing the number of multiplications and the poly-phase algorithm resolving the problem of sampling operations in the Mallat algorithm, the proposed algorithm can reduce massive computational complexities, especially for multiplications (Mults). At the same time, the proposed algorithm possesses wonderful regular construction; it not only can adapt easily to the change of the wavelet basis, but also has the same implementation for both the forward and the inverse DWT.

The experiments in this thesis analyze the computational complexities of a 512*512 still image. When compared to the Mallat, the short-length, and the poly- phase algorithms with the basis Daubechies 9/7, the proposed algorithm requires only 42.23%, 49.27% and 75.32% Mults in the forward transform; and 42.41%, 50.01%, 75.40% Mults in the inverse transform. With the basis Daubechies 4, the proposed algorithm requires 37.68%, 50.00%, and 75.29% Mults in the forward transform; and 37.54%, 49.95%, 75.29% Mults in the inverse transform. When compared to the lifting scheme, although the computational counts (multiplications and additions) of our proposed algorithm are more than that of the lifting scheme, the latter has the inconvenience of changing basis and requires long waiting time in software implementation.

[1] K. Andra, C. Chakrabarti, and T. Acharya, “A VLSI Architecture for Lifting-Based Forward and Inverse Wavelet Transform,” IEEE Trans. on Signal Processing, Vol. 50, No. 4, pp. 966-977, April 2002.

[2] A. R. Calderbank, I. Daubechies, W. Sweldens, and B.-L Yeo, “Wavelet Transforms That Map Integers to Integers,” Applied and Computational Harmonic Analysis, Vol. 5, No. 3, pp. 332-369, July 1998.

[3] P. Y. Chen, “VLSI Implementation for One-Dimensional Multilevel Lifting-Based Wavelet Transform,” IEEE Trans. on Computers, Vol. 53, No. 4, pp. 386-398, April 2004.

[4] I. Daubechies and W. Sweldens, “Factoring Wavelet Transforms into Lifting Steps,” J. Fourier Anal. Appl., Vol. 4, No. 3, 1998, preprint.

[5] A. Graps, “An Introduction to Wavelets,” IEEE Computational Science and Engineering, Vol. 2, No. 2, pp. 50-61, June 1995.

[6] B. Jawerth and W. Sweldens, “An Overview of Wavelet Based Multiresolution Analyses,” SIAM Review, Vol. 36, No. 3, pp. 377-412, September 1994

[7] H. Liao, M. K. Mandal, and B. F. Cockburn, “Efficient Architectures for 1-D and 2-D Lifting-Based Wavelet Transforms,” IEEE Trans. on Signal Processing, Vol. 52, No. 5, pp. 1315-1326, May 2004.

[8] S. G. Mallat, “A Theory for Multiresolution Signal Decomposition : The Wavelet Representation,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, No. 7, pp. 674-693, July 1989.

[9] S. G. Mallat, “Multifrequency Channel Decompositions of Images and Wavelet Models,” IEEE Trans. on Acoustics, Speech, and Signal Processing, Vol. 37, No. 12, pp. 2091-2110, December 1989.

[10] Z. J. Mou, and P. Duhamel, “Short-Length FIR Filters and Their Use in Fast Nonrecursive Filtering,” IEEE Trans. on Signal Processing, Vol. 39, No. 6, pp. 1322-1332, June 1991.

[11] A. V. Oppenheim, R. W. Schafer and J. R. Buck, Discrete-Time Signal Processing, 2nd, NJ: Prentice Hall, 1999.

[12] O. Rioul and P. Duhamel, “Fast Algorithms for Discrete and Continuous Wavelet Transform,” IEEE Trans. on Information Theory, Vol. 38, No. 2, pp. 569-586, March 1992.

[13] O. Rioul and P. Duhamel, "Fast Algorithms for Wavelet Transform Computation," chapter 8 in Time-frequency and Wavelets in Biomedical Signal Processing, IEEE Press Series on Biomedical Engineering, pp. 211-242, October 1997.

[14] E. Salajegheh and A. Heidari, “Time History Dynamic Analysis of Structure Using Filter Banks and Wavelet Transforms,” Computers and Structures, Vol. 83, No. 1, pp. 53-68, January 2005.

[15] G. Strang and T. Nguyen, Wavelets and Filter Banks, New York: Wellesley- Cambridge Press, 1997.

[16] W. Sweldens, “The Lifting Scheme: A Custom-Design. Construction of Biorthogonal Wavelets,” Applied and Computational Harmonic Analysis, Vol. 3, No. 2, pp. 186-200, April 1996.

[17] B. E. Usevitch, “A Tutorial on Modern Lossy Wavelet Image Compression: Foundations of JPEG 2000,” IEEE Signal Processing Magazine, Vol. 18, No. 5, pp. 22-35, September 2001.

[18] P. P. Vaidyanathan, “Multirate Digital Filters, Filter Banks, Polyphase Networks, and Applications: A Tutorial,” Proceedings of the IEEE, Vol. 78, No.1, pp. 56-93, January 1990.

[19] M. Vetterli and C. Herley, “Wavelets and Filter Banks: Theory and Design,” IEEE Trans. on Signal processing, Vol. 40, No. 9, pp. 2207-2232, September 1992.