臺灣博碩士論文加值系統

在本篇論文中，主要有兩方面的研究重點，一方面是發展出一套新的運用小波轉換在二維分解上的演算法，另一方面則是設計硬體實現這個新的二維小波分解演算法。
新的二維小波分解演算法當中，其一維的分解主要是以Lifting Scheme的程序完成一維的小波轉換。在新訂定的壓縮標準JPEG2000的報告中，亦是建議使用Lifting Scheme實現一維的小波轉換，此方法將會使運算的複雜度降低並減少對記憶體的需求量。在實現一般的小波轉換中，為了使邊界效應不會影響重建後影像的品質，在執行小波轉換前必須先執行邊界延伸（Boundary Extension）的技術，但相對的，這個方法將會產生大量邊界延伸的個數，以至於增加運算的複雜度，且這些邊界延伸的個數仍需被編碼到位元串（Bit-Stream）內，進而影響壓縮效果。論文中將提出新的離散式橫截小波轉換，這是藉由階梯掃描方式讀取二維影像的資料，再將此資料以一維的方式執行小波轉換，而其主要的優點將會大量減少邊界延伸的個數，並進而減少運算的複雜度。若比較傳統的二維小波分解與離散式橫截小波轉換所需儲存的邊界延伸個數，總數相差將近98%。
本論文的第二部分說明了離散式橫截小波轉換的硬體設計，其設計硬體的主要理由，是在於以小波轉換為主的影像壓縮中，需要先執列運算後，才能執行行運算，以至於需要大量的記憶體需求和頻繁的對記憶體執行資料的存取。這設計主要包含了以Lifting Scheme實現一維的小波轉換架構和離散式橫截小波轉換的架構。這架構亦可被運用在傳統的二維小波轉換，亦比一般的硬體實現方式快。硬體設計以Verilog HDL實現並燒錄在FPGA上以33 MHz的速度做系統模擬驗證，並以640x480大小的灰階影像並執行四層的二維小波轉換為例，可達到每秒完成71張的小波分解。

A novel VLSI architecture for the 2-D Discrete Wavelet Transform﹙DWT﹚ using lifting scheme is presented in this thesis. The advantages of the lifting scheme suggested in JPEG2000 include lower computational complexity, and reduced memory requirement. In conventional DWT implementations, boundary extension is necessary but this increases the number of pixels to be encoded as well as the computation complexity. A new Discrete Traversal Wavelet Transform (DTWT) is proposed to reduce the boundary extension. The DTWT performs the transformation by linking all the image pixels in a 1-D manner. Comparing with conventional approaches, the total number of extended pixels is greatly reduced.
The VLSI design of the DTWT is also presented in the paper. Due to the huge amount of memory requirement, it is necessary to use hardware to implement the wavelet based image compression. The design includes the 1-D DWT architecture based on the lifting scheme and the 2-D DTWT architecture. The new architecture is also faster than the conventional DWT implementation. The corresponding hardware design is realized on a FPGA based system running at 33 MHz. For 640X480 gray-level images, it reaches 71 frames/sec for 4-level DWT decomposition.

CHAPTER 1 1
1.1 MOTIVATION
1.2 RELATED ISSUES
1.2.1 Wavelet-Based Compression
1.2.2 Hardware Implementation
1.3 ORGANIZATION
CHAPTER 2
2.1 WAVELET THEORY AND NOTATION
2.2 WAVELET TRANSFORM FOR MULTI-RESOLUTION DECOMPOSITION
2.2.1 Multi-resolution Decomposition
2.2.2 The Scaling Function
2.2.3 The Wavelet Function
2.2.4 Direct Sum Decomposition
2.3 WAVELETS AND FILTER BANKS
2.3.1 MRA and FWT
2.3.2 Wavelets and Filter Banks
2.4 BI-ORTHOGONAL WAVELET SYSTEM
2.5 THE LIFTING SCHEME
CHAPTER 3
3.1 INTRODUCTION OF THE CONVENTIONAL APPROACHES IN JPEG2000
3.1 BOUNDARY EXTENSION
3.1.1 Boundary Extension in One Dimension
3.1.2 Boundary Extension in 2 Dimensions
3.2 DISCRETE TRAVERSAL WAVELET TRANSFORM
3.2.1 Introduction of the DTWT
3.2.2 Bi-orthogonal wavelet filter
3.2.3 Difference between the conventional approaches and the DTWT
3.2.4 Extension strategies
3.3 COMPARING THE RESULTS BETWEEN THE CONVENTIONAL APPROACHES AND THE DTWT
CHAPTER 4
4.1 DESIGN OF THE INTEGER 5/3 WAVELET CORE BY THE LIFTING SCHEME
4.1.1 Integer 5/3 filter with the lifting scheme
4.1.2 Architecture of integer 5/3 filter
4.1.3 Time scheduling of the current design
4.2 DESIGN OF THE INVERSE INTEGER 5/3 WAVELET CORE BY THE LIFTING SCHEME
4.2.1 Architecture of inverse integer 5/3 filter
4.2.2 Timing of the current design
4.3 DESIGN OF THE 2-D DWT SYSTEM
4.4 MEMORY MANAGEMENT OF THE CONVENTIONAL APPROACHES
4.5 MEMORY MANAGEMENT FOR THE DTWT SYSTEM
CHAPTER 5
5.1 EMBEDDED ZEROTREE WAVELET
5.2 SET PARTITIONING IN HIERARCHICAL TREES
5.4 EMBEDDED BLOCK CODING WITH OPTIMIZED TRUNCATION
CHAPTER 6
6.1 SIMULATING THE NEW ALGORITHM – DTWT
6.2 HARDWARE DESIGN FLOW
6.3 SYNTHESIS RESULT
CHAPTER 7
REFERENCE
APPENDIX

Reference
[1.1]S.Mallat, “A Theory for Multi-resolution Signal Decomposition：The Wavelet Representation,” IEEE Trans. Pattern Anal. And Machine Intell., Vol. 11, no. 7, pp.674-693, July 1989
[1.2]ISO/IEC JTC1/SC29 WG1N 1646R, “Discrete Wavelet Transform of Tile Components, ” 2000
[1.3]M. Vishwanth, “The Recursive Pyramid Algorithm for Discrete Wavelet Transform,” IEEE Trans. On Signal Processing, vol. 42, no. 3, pp.673-676, 1994
[1.4]W.S Peng and C. Y Lee, “An Efficient VLSI Architecture for Separable 2-D Discrete Wavelet Transform” Proc. of IEEE Int. Conf. Image processing, 1999
[1.5]ISO/IEC JTC1/SC29/WGIN 1013, “Low Memory Line–based Wavelet Transform Using Lifting Scheme,” 1998
[2.1]A.N. Akansu, M.V. Tazebay, M.J. Medley and P. K. Das, “Wavelets and Sub-band Transforms：Fundamentals and Communication Applications,” IEEE Communications Magazine, pp. 104-115, Dec. 1997.
[2.2]M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, “Image Coding Using Wavelet Transform”, IEEE Trans. Image Processing, vol. 1, pp. 205-220, Apr. 1992.
[2.3]M. Vetterli and C. Herley, “Wavelets and Filter Banks：Theory and Design,” IEEE Transactions on Signal Processing, vol. 40, pp. 2207-2232, Sep. 1992.
[2.4]S. Mallat, “Multi-frequency Channel Decompositions of Images and Wavelet Models,” IEEE Trans. ASSP, vol. 37, pp. 2091-2110, 1989.
[2.5]S. Mallat, “A Theory for Multi-resolution Signal Decomposition：The Wavelet Representation,” IEEE Trans. Pattern Anal. Machine Intell., vol. 11, pp. 674-693, July 1989.
[2.6]B. Jawerth and W. Sweldens, “An Overview of Wavelet Based Multi-resolution Analysis,” SIAM Rev., vol. 36, pp.377-412, 1994.
[2.7]I. Daubenchies, “Orthonormal Bases of Compactly Supported Wavelets,” Comn. Pure Appl. Math., vol. 41, pp. 906-966, 1988.
[2.8]M. Vetterli, “Filter Banks Allowing Perfect Reconstruction,” Signal Processing, vol. 10, pp. 219-244, April 1986.
[2.9]V.K. Heer and H.E Reinfelder, “A Comparison of Reversible Methods for Data Compression,” in Medical Imaging IV, pp. 354-365, Proc. SPIE 1233, 1990.
[2.10]S. A. Martucci and R. M. Mersereau, “The Symmetric Convolution Approach to the Non-expansive Implementation of FIR Filter Banks for Image,” in Proc. 1993 IEEE Int. Conf. Acoustics, Speech, Signal Processing, Minneapolis, MN, Apr. 1993, pp. V.65-V.68
[2.11]A. Cohen, I. Daubechies, and J.C. Feauveau, “Biorthogonal Bases of Compactly Supported Wavelets,” Commun Pure Appl. Math., pp. 485-500, 1992.
[2.12]W.Sweldens, “The lifting scheme：A New Philosophy in Biorthogonal Wavelet Constructions,” Proc. SPIE Wavelet Application in Signal and Image Processing III, pp 68-79, 1995.
[2.13]W.Sweldens, “The lifting scheme：A Custom-Design Construction of Biorthogonal Wavelets,” Appl. Comput. Harmon. Anal., 3（2）：186-200, 1996.
[3.1]ISO/IEC JTC1/SC29 WG1N 1646R, “Discrete Wavelet Transform of Tile Components, ” 2000
[4.1]W. Sweldens and P. Schröder. “Building Your Own Wavelets at Home.” Technical Report1995:5, Industrial Mathematic Initiative, Department of Mathematics, University of South Carolina, 1995.
[4.2]I. Darbechies and W. Sweldens, “Factoring Wavelet Transforms into Lifting Steps,” tech. Rep., Bell Laboratories, 19
[5.1]J.M. Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients,” IEEE Transactions on Signal Processing, SP-41：3445-3462, December 1993.
[5.2]A. Said and W.A. Pearlman, “A New Fast and Efficient Coder Based on Set Partitioning in Hierarchical Trees,” IEEE Transactions on Circuits and Systems for Video Technologies, pages 243-250, June 1996.
[5.3]D. Taubman, “Directionality and Scalability in Image and Video Compression,” Ph.D. thesis, University of California-Berkeley, May 1994.
[5.4]G.K. Wallace, “The JPEG Still Picture Compression Standard,” Communications of the ACM, 34:31-44, April 1991.