近十幾年來，離散小波轉換已被廣泛地應用在各個研究領域，包
括信號分析、影像壓縮、視訊壓縮、圖形辨識以及數值分析等等。由於離散小波轉換具有極佳能量集中的特質和與生俱來多重解析的特性，使它在影像及視訊壓縮編碼系統中受到極高的重視。傳統離散小波轉換是以濾波器為主，然而其運算複雜度非常龐大，因此現今大都使用提升式架構來降低運算複雜度，而且又易於實現，不過對於二維提升式離散小波轉換而言，除了運算複雜度之外，還有著硬體成本上的問題－龐大內部的記憶體。
因此，在本論文中，我們提出了二維提升式離散小波轉換之有效
記憶體架構應用於Motion-JPEG2000，此架構包括一維的行處理器、
內部記憶體與一維的列處理器，此架構不僅支援無失真與失真的兩種模式，而且處理的速度相當快，最主要的優點是大大地減少內部記憶體的容量。例如，以一張N x N 的影像而言，如果要進行一階的二維的離散小波轉換，對於5/3 濾波器只需要2N 記憶體的容量，而9/7濾波器也只需要4N 記憶體的容量。
與其它同為二維提升式離散小波轉換架構的比較之下，我們所提
出的架構對於改善記憶體的貢獻是相當出色的，而且硬體架構的實現
並不難，也可支援其它即時的應用裝置，不管是影像還是視訊上。

In the last few years, discrete wavelet transform (DWT) has been used for a wide range of applications including image coding and compression, speech analysis, pattern
recognition, and computer vision. DWT can be viewed as a multi-resolution decomposition of a signal. This means that it decomposes a signal into several components in different frequency bands. It always needs a large amount of computations and memory to perform the DWT. In order to achieve the real-time processing, reducing of memory
and computational complexity and increasing the efficient hardware utilization are necessary. Therefore, we propose a memory-efficient architecture of lifting based two-dimensional discrete wavelet transform (2-D DWT) for motion-JPEG2000. The proposed 2-D DWT architecture consists of a 1-D row processor, internal memory, and a
1-D column processor.
The main advantage of this 2-D DWT is to reduce the internal memory requirement significantly. For an N×N image, only 2N and 4N sizes of internal memory are required for the 5/3 and 9/7 filters, respectively, to perform the one-level 2-D DWT decomposition. Moreover, it supports both lossless and lossy operation for 5/3 and 9/7 filters with high operation speed.
The proposed 2-D DWT surpasses the existed lifting-based designs in the aspects of low internal memory requirement. It is suitable for VLSI implementation and can support
various real-time image/video applications such as JPEG2000, motion-JPEG2000, MPEG-4 still texture object decoding, and wavelet-based scalable video coding.

TABLE OF CONTENTS

1 INTRODUCTION……………………………………...…………………………………1
1.1 Motivation…………………………………………………………………………1
2 OVERVIEW OF JPEG2000………………………………………………………………5
2.1 Pre-Processing…………………………………..…………………………………6
2.2 Component Transform…………………………..…………………………………7
2.3 Discrete Wavelet Transform…………………….…………………………………8
2.3.1 Wavelet Transform…………………………………………………………9
2.3.2 Multi-Resolution Analysis………………………………………………12
2.3.3 Advantages of Using Wavelets……………………………………………17
2.4 Quantization……………………………………...………………………………18
2.5 Entropy Coding......………………………………………………………………19
2.6 Motion-JPEG2000……………………..…………………………………………22
3 DISCRETE WAVELET TRANSFORM……………………………………...…………24
3.1 Discrete Wavelet Transform by Lifting-Based………………………..………….24
3.1.1 Lifting-Based 5/3 and 9/7 DWT Standard………………………...………26
3.1.2 Boundary Extension Treatment…………………………………..…….…30
3.2 Hardware Issues for DWT……………………………………………………..…33
4 PROPOSED ONE-LEVEL 2-D DWT ARCHITECTURE…………………………...…34
4.1 Proposed VLSI Architecture……………………………………………………..35
4.2 Row Processor……………………………………………………………………36
4.3 Internal Memory….………………………………………………………………38
4.4 Column Processor...………………………………………………………………42
4.5 DFG of Row and Column Processor…………………………………………..…44
4.6 Reduction of Hardware Cost for 5/3 and 9/7 Filter……………..………………51
4.6.1 Integer 9/7 Filter………………………………...………...………………51
4.6.2 Combination of 5/3 and 9/7 Filter…………………………...……………52
5 EXPERIMENTS AND COMPARISON………………………………………………54
6 CONCLUSION AND FUTURE WORK……………………………………………..…58
6.1 Conclusion……………………………………………………………………..…58
6.2 Future Work………………………………………………………………………58

LIST OF FIGURES

Figure1.1 The comparison of compression performance between JPEG and JPEG2000. (a) Original image 512 ´ 512. (b) JPEG bit-rate = 0.03bpp. (c) JPEG2000 bit-rate = 0.03bpp...........................................................................................................................3
Figure 1.2 Profile of JPEG2000 encoding timer……………………………………………4
Figure 2.1 Block diagram of JPEG2000. (a) Block diagram of encoder. (b) Block diagram of decoder…………………………………………………...…………………………6
Figure 2.2 Pre-processing sub-stage…………………………………………………...……7
Figure 2.3 Prototype wavelet. (a) Translations. (b) Dilations..……………………………12
Figure 2.4 Original image for 2-D one-level decomposition………………………...……13
Figure 2.5 Three popular wavelet decomposition structures on image. (a) Mallat. (b) Spacl. (c) Packet……………………………………………………………………..………14
Figure 2.6 2-D DWT decomposition………………………………………………………14
Figure 2.7 2-D One-level 2-D DWT image decomposition………………………….……15
Figure 2.8 Time-frequency plane. (a) DWT. (b) FT………………………………………16
Figure 2.9 Deadzone quantizer structure……………………………………………..……18
Figure 2.10 Example calculation of the quantized value…………………………….……19
Figure 2.11 Structure of the EBCOT algorithm……………………………………...……20
Figure 2.12 Particular scan order in each bit-plane of a code-block………………………21
Figure 3.1 Block diagram of the forward lifting-based DWT………………………..……25
Figure 3.2 Lifting-based 5/3 DWT algorithm………………………………………..……28
Figure 3.3 Lifting-based 9/7 DWT algorithm………………………………………..……29
Figure 3.4 Dependence graph of the 5/3 lifting-based DWT………………………...……31
Figure 3.5 Techniques of various signal extensions. (a) Zero-padding extension. (b) Replication extension. (c) Periodic symmetric extension. (d) Circular extension. (e) Double symmetric extension……………………………...………………………….32
Figure 3.6 Periodic symmetric extension of discrete signal…………………………….…33
Figure 4.1 Architecture of DWT. (a) Traditional architecture. (b) Proposed architecture...34
Figure 4.2 One-level 2-D DWT architecture………………………………………………35
Figure 4.3 Inner of row processor…………………………………………………………36
Figure 4.4 Architecture of row processor element…………………………………...……37
Figure 4.5 Input sequence order of row processor…………………………………...……38
Figure 4.6 Inner of internal memory………………………………………………………39
Figure 4.7 4 x 6 matrix for 5/3 filter……………………………………………………….40
Figure 4.8 Memory operation for 5/3 filter. (a) Write signals into buffers. (b) Read signals from buffer and write signals into buffer……………………………………….……41
Figure 4.9 Memory operation for 9/7 filter……………..……………………………........41
Figure 4.10 Inner of column processor……………………………………………………42
Figure 4.11 Architecture of column processor element……………………………………43
Figure 4.12 Input sequence of column processor…………………………………….……44
Figure 4.13 DFG of row processor…………………………………………………...……46
Figure 4.14 DFG of column processor……………………………………………….……47
Figure 4.15 8x8 matrix for 9/7 filter operation of row processor…………………….……49
Figure 4.16 8x4 matrix for 9/7 filter operation of column processor………………...……50
Figure 4.17 Four coefficients of 9/7 filter. (a) α. (b) β. (c) γ. (d) δ...............………………52
Figure 4.18 Combination of α and β. (a) Modified α. (b) Modified β….…………………53


LIST OF TABLES

Table 1.1 Storage and transmission needs for various types of uncompressed image and video……………………………………………………………….……………2
Table 1.2 Practical execution times of 2-D LDWT approaches…………………………….4
Table 3.1 Boundary extension to the left and to the right…………………………………33
Table 5.1 Hardware specification of three main components……………..………………54
Table 5.2 Hardware cost and performance comparisons of 2-D DWT architecture for 9/7 filter……………………………………………………………………………55
Table 5.3 Design specifications of the proposed 2-D DWT……………….………………56

[1] Information technology – JPEG2000 image coding system – Part 1: Core coding
system, ISO/IEC 15444-1, Dec. 2000.
[2] ISO/IEC JTC1/SC29/WG1 Wgln 1684, JPEG2000 Verification Model 7.0, 2000.
[3] Information technology – coding of audio-visual objects – Part 2: visual, ISO/IEC
14496-2, Mar. 1999.
[4] G. K. Wallance, “The JPEG still picture compression standard,” Communication of
ACM, vol. 34, no.4, pp.31- 44, Apr. 1991.
[5] C.Christopoulos, A. Skodras, and T. Ebrahimi, “The JPEG2000 still image coding
system: An overview,” IEEE Transactions on Consumer Electronics, vol.46, no. 4, pp.
1103-1127, Nov. 2000.
[6] M. W. Marcellin, M. J. Gormish, A. N. Skodras, “JPEG2000: The new still picture
compression standard,” ACM Workshops on Multimedia, pp. 45- 49, Oct. 2000.
[7] D. Taubman, M. Marcellin, JPEG2000 image compression fundamentals, standards,
and practice, Kluwer Academic Publisher, Nov. 2001.
[8] S. Saha, “Image Compression – from DCT to Wavelets: A Review,” ACM Crossroads
Student Magazine, vol. 6.3, Spring 2000.
http://www.acm.org/crossroads/xrds6-3/sahaimgcoding.html
[9] H. Muta, M. Doi, H. Nakano, and Y. Mori, “Multilevel parallelization on the cell/B.E.
for a motion JPEG 2000 encoding server,” ACM Workshops on Multimedia, pp.
942-951, Sept. 2007.
[10] C.-H. Hsia, J.-M. Guo, J.-S. Chiang, and C.-H. Lin, “A novel fast algorithm based on
SMDWT for image applications,” IEEE International Symposium on Circuits and
Systems, pp. 762-765, May 2009.
[11] C. Christopoulos, A. Skodras, and T. Ebrahimi, “The JPEG2000 still image coding system: an overview,” IEEE Transactions on Consumer Electronics, vol. 46, no. 4, pp.
1103-1127, Nov. 2000.
[12] S. Mallat, “Multifrequency channel decompositions of images and wavelet models,”
IEEE Transactions on Acoustics, Speech, and Processing, vol. 37, no. 12, pp.
2091-2110, Dec. 1989.
[13] I. Daubechies and Wim Sweldens, “Factoring wavelet transforms into lifting scheme,”
The Journal of Fourier Analysis and Applications, vol. 4, no. 3, pp. 247-269, May
1998.
[14] D. Taubman, “High Performance Scalable Image Compression with EBCOT,” IEEE
Transactions on Image Processing, vol. 9, no. 7, pp. 1158-1170, July 2000.
[15] D.Taubman, E. Ordentlich, M. Weinberger, G. Seroussi, I. Ueno, and F. Ono,
“Embedded block coding in JPEG2000,” IEEE International Conference on Image
Processing, vol. 2, pp. 33-36, Sept. 2000.
[16] M. Boliek, C. Christopoulos, and E. Majani, JPEG2000 Part I Final Draft
International Standard (ISO/IEC FDIS15444-1), ISO/IEC JTC1/SC29/ WG1 N1855,
Aug. 18, 2000.
[17] M. W. Marcellin, M. Gormish, A. Bilgin, M. Boliek, “An Overview of JPEG2000,”
IEEE Data Compression Conference, pp. 523-541, Mar. 2000.
[18] Official JPEG2000 Homepage http://www.jpeg.org/jpeg2000/index.html
[19] T. Fukuhara, K. Katoh, S. Kimura, K. Hosaka, and A. Leung, “Motion-JPEG2000
Standardization and Target Market,” IEEE International Conference on Image
Processing, vol. 2, pp. 13-24, Sept. 2000.
[20] Wim Sweldens, “The lifting scheme: A custom-design construction of biorthogonal
wavelets,” Applied and Computation Harmonic Analysis, vol. 3, pp.186-200, Apr. 1996.
[21] Wim Sweldens, “The lifting scheme: A construction of second-generation wavelets,”
Siam Journal of Mathematical Analysis, vol. 29, no. 2, pp. 511-546, Mar. 1998.
[22] K.C.B. Tan and T. Arslan, “An embedded extension algorithm for the lifting based
discrete wavelet transform in JPEG2000,” IEEE International Conference on
Acoustics, Speech, and Signal Processing, vol. 4, pp. 3513-3516, May 2002.
[23] K.C.B. Tan and T. Arslan, “Low power embedded extension algorithm for the lifting
based discrete wavelet transform in JPEG2000,” IEE Electronics Letters, vol. 37, no.
22, pp. 3513-3516, May 2002.
[24] M. Vishwanath, R. M. Owens, and M. J. Irwin, “VLSI architecture for the discrete
wavelet transform,” IEEE Transactions on Circuits and Systems II, vol. 42, no. 5, pp.
305-316, May 1995.
[25] C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Efficient VLSI architecture of
lifting-based discrete wavelet transform by systematic design method,” IEEE
International Symposium on Circuits and Systems, vol. 5, pp. 26-29, May 2002.
[26] Z. Guangjun, C. Lizhi, and C. Huowang, “A simple 9/7-tap wavelet filter based on
lifting scheme,” IEEE International Conference on Image Processing, vol. 2, pp.
249-252, Oct. 2001.
[27] David B. H. Tay, “A class of lifting based integer wavelet transform,” IEEE
International Conference on Image Processing, vol. 1, pp. 602-605, Oct. 2001.
[28] M. Martina, and G. Masera, “Folded multiplierless lifting-based wavelet pipeline,”
IET Electronics Letters, vol. 43, no. 5, pp. 27-28, Mar. 2007.
[29] B.-D. Choi, K.-S. Choi, M.-C. Hwang, J.-K. Cho, S.-J. Ko, “Real-time DSP
implementation of motion-JPEG2000 using overlapped block transferring and parallel-pass methods,” Real-Time Imaging, vol. 10, no. 5, pp. 277-284, Oct. 2004.
[30] R. Jain, P. R. Panda, “An efficient pipelined VLSI architecture for lifting-based
2D-discrete wavelet transform,” IEEE International Symposium on Circuits and
Systems, pp. 1377-1380, May 2007.
[31] M. Maamoun, M. Neggazi, A. Meraghni, and D. Berkani, “VLSI design of 2-D
discrete wavelet transform for area-efficient and high-speed image computing,” World
academy science, engineering and technology, vol. 35, pp. 539-544, Nov. 2008.
[32] A. Bellaouar, M. I. Elmasry, Low-power digital VLSI design circuits and systems,
Kluwer Academic Publishers, 1995.
[33] C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Flipping structure: an efficient VLSI
architecture for lifting-based discrete wavelet transform,” IEEE Transactions on
Signal Processing, vol. 52, no. 4, pp. 1080-1089, Apr. 2004.
[34] C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Generic RAM-based architecture for
two-dimensional discrete wavelet transform with line-based method,”IEEE
Transactions on Circuits and Systems for Video Technology, vol. 15, no. 7, pp.
910-920, July 2005.
[35] C. Xiong, J. Tian, and J. Liu, “Efficient architectures for two-dimensional discrete
wavelet transform using lifting scheme,” IEEE Transactions on Image Processing,
vol. 16, no. 3, pp. 607-614, Mar. 2007.
[36] H. Liao, M. Kr. Mandal, and B. F. Cockburn, “Efficient architectures for 1-D and 2-D
lifting-based wavelet transforms,” IEEE Transactions on Signal Processing, vol. 52,
no. 5, pp. 1315-1326, May 2004.