近年來，離散小波轉換 (Discrete Wavelet Transform，簡稱DWT)，目前已成功地被應用在各種領域，包括數值分析、信號分析、影像編碼、紋理辨識與生物醫學等。由於離散小波轉換具有極佳能量集中的特質和與生俱來多重解析 (Multiresolution) 的特性，使它在影像及視訊壓縮編碼系統中受到極高的重視。

在多媒體IC硬體中，因為運算上的複雜，使得內部存取的記憶體 (On- chip memory) 變的很佔面積，而JPEG2000壓縮技術中，二維離散小波轉換就有此問題，但離散小波轉換在應用上需要很複雜的運算，而用硬體架構來實現離散小波轉換可以節省運算時間，因此VLSI架構的實現變得相當重要。

在本論文中，我們透過介紹JPEG2000中二維離散小波轉換 (2-D Discrete Wavelet Transform) 之演算法，提出VLSI架構設計與實現，在電路設計上，我們特別考慮到影像邊緣效應的處理，藉由適當的映射硬體電路之設計，可使影像反轉時更接近原始影像，硬體設計以低記憶空間及高工作頻率為目標，為達此目標我們提出了交叉讀取掃瞄演算法 (Interlace Read Scan Algorithm, IRSA)，以平行小波轉換器處理方式達成低記憶空間並減少其時脈週期，據此，我們設計了一個提昇式5/3無失真離散小波轉換器。它可以有更低計算的複雜度，且有規則的資料流，很適合做為VLSI的實現，可應用於JPEG 2000和MPEG- 4的及時影像/視訊處理。

為了驗證設計的架構，我們使用TSMC 0.35.um 1P4M CMOS製程實作晶片。此二維離散小波轉換所用的記憶體容量在計算N×N的二維影像上只需要N的儲存空間，這大約是JPEG2000標準中儲存空間的一半，且工作頻率可達到100MHz。

In the last few years, discrete wavelet transform (DWT) has been widely and successfully used in many fields, such as numerical analysis, signal analysis, image coding, pattern recognition, and biometric. Since DWT has excellent features of energy compaction and inherent Multiresolution, it has been applied extensively in the field of image and video compression.

Usually people 2-dimensional (2-D) DWT to accomplish their applications. However, 2-D DWT needs very intensive computation and massive memory. For real-time applications the 2-D DWT is usually hardwarized. For hardware implementation, to reduce the computation complexity and memory requirement becomes an very important issue.

This thesis tries to find some new algorithms and hardware architectures to improve the 2-D DWT. We present a low memory and high speed VLSI architecture for 2-D lifting-based lossless 5/3 filter discrete wavelet transform. The architecture is based on the proposed interlaced read scan algorithm (IRSA) and parallel scheme processing to achieve low memory size and high speed operation. The proposed lifting-based DWT architecture has the advantages of lower computational complexity. Meanwhile, our architecture can also provide embedded symmetric extension function, and regular data flow, and is suitable for VLSI implementation. It can be applied to real time image/video operating of JPEG 2000 and MPEG- 4 applications.

To verify the performance of our proposed architecture, we designed and simulated a 2-D DWT VLSI chip by TSMC 0.35um 1P4M CMOS technology. In our proposed VLSI architecture, to compute an N×N 2-D DWT using 5/3 filter requires only N storage cells and this memory bandwidth requirement is almost one-fourth of the JPEG 2000 proposal and it can operate at 100MHz clock frequency. The proposed VLSI architectures are designed in Verilog HDL, and syntesized by the Synopsys Design Compiler. Finally, the layout of the design is generated automatically by Avant! Apollo Layout Tools in a TSMC 0.35μm 1P4M CMOS technology.

第一章 緒論………………………………………………………1
1.1 研究背景與動機…………………………………………...1
1.2 JPEG 系統簡介……………..........................3
1.3 JPEG 2000 系統概述……………………………………….5
1.3.1 JPEG 2000之特色……………………………………....8
1.3.2 JPEG2000壓縮系統…………………………………....10
1.4 論文架構…………………………………………………..14

第二章 離散小波轉換………………………………………….15
2.1 JPEG 2000之離散小波轉換演算法……………………….15
2.2 提昇式架構之簡介………………………………………..20
2.2.1 提昇式5/3與9/7離散小波轉換濾波器……………....23
2.2.2 邊界訊號延伸之處理………………………………....26
2.2.3提昇式離散小波反轉換……………….……………... 28

第三章 高效能離散小波轉換之演算法設計…….……………31
3.1 交錯式讀取掃瞄演算法…………………………………..32
3.1.1交錯式讀取掃瞄演算法之演算法索引介紹……….....36

第四章 高效能離散小波轉換之硬體架構設計……………….39
4.1 二維離散小波轉換………………………………………..39
4.1.1 水平拆解運算………………………………………....40
4.1.2 垂直拆解運算………………………………………....41
4.2 高效能二維離散小波轉換架構…………………………..42
4.2.1 前級離散小波轉換…………………………………....42
4.2.2 後級離散小波轉換…………………………………....46
4.2.3 二維離散小波轉換整體架構………………………....48
4.3 新架構之時序分析………………………………………..52

第五章 IC晶片實現…………………………………………….55
5.1 設計流程…………………………………………………..55
5.2 模擬結果…………………………………………………..57
5.2.1功能模擬…………………………………………….....57
5.2.2 邏輯閘層級模擬……………………………………....58
5.3 晶片佈局與規格…………………………………………..60
5.3.1 佈局結果……………………………………………....60
5.3.2 晶片規格……………………………………………....61

第六章 結論…………………………………………………….63
6.1 結果與比較………………………………………………..63

參考文獻…………………………………………………………66

圖目錄
圖1.1 JPEG編碼流程……………………………………………………5
圖 1.2 JPEG與JPEG 2000之壓縮效率比較…………………………...7
圖 1.3 JPEG 2000的應用………………………………………………11
圖 1.4為JPEG2000 Part 1的編碼/ 解碼流程………………………...11
圖 1.5 量化階的示意圖……………………………………………….13
圖 2.1 小波轉換與其他轉換的比較…. ……………………………...17
圖 2.2 經過高通濾波器及低通濾波器的訊號…. …………………...17
圖 2.3 小波分解樹……………………...……………………………..18
圖 2.4 二維離散小波轉換子頻帶分解……………………………….19
圖 2.5 正向提昇式架構……………………………………………….22
圖 2.6 提昇式5/3離散小波轉換演算法……………………………..24
圖 2.7 提昇式9/7離散小波轉換演算法……………………………..25
圖 2.8 提昇式5/3離散小波轉換之邊界延伸處理圖………………...26
圖 2.9 邊界延伸的種類……………………………………………….27
圖 2.10 提昇式5/3濾波器之週期對稱延伸圖………………………28
圖 2.11反向提昇式架構……………………………………………….29
圖 3.1 二維離散小波轉換之示意圖………………………………….31
圖 3.2 交錯式讀取掃瞄演算法輸入之像素圖……………………….33
圖 3.3 以交錯式讀取演算法處理二維離散小波轉換……………….35
圖 3.4 以N= 6，N*N影像階層的方式………………………………36
圖 4.1　二維離散小波轉換之直接架構……………………………...40
圖 4.2　水平拆解運算………………………………………………...41
圖 4.3　垂直拆解運算………………………………………………...42
圖 4.4　單輸入一維離散小波轉換架構……………………………...43
圖 4.5　信號排列單元運作方式說明………………………………...43
圖 4.6 乘加器單元…………………………………………………….44
圖 4.7 邊界延伸下乘加器的資料流向(前級)……………………..…45
圖 4.8 雙輸入一維離散小波轉換架構…………………………….....46
圖 4.9　包含係數整合的信號排列方法……………………………...47
圖 4.10 邊界延伸下MAC的資料流向(後級) ……………………….48
圖 4.11 整體架構方塊圖……………..……………………………….48
圖 4.12 資料輸入順序示意圖………………………………………...49
圖 4.13內部架構方塊圖……………………………………………….50
圖 4.14 二維離散小波轉換流程……..……………………………….50
圖 4.15 提出的二維一階小波轉換架構……………………………...52
圖 5.1 標準元件庫IC設計流程………………………………………56
圖 5.2 二維一階上提式離散小波轉換圖…………………………….57
圖 5.3 我們提出的演算法使用Matlab來模擬低低頻結果…………58
圖 5.4 邏輯閘層級電路描述………………………………………….59
圖 5.5 電晶體層級模擬結果………………………………………….59
圖 5.6 邏輯閘層級模擬結果………………………………………….60
圖 5.7 二維離散小波轉換硬體架構之Apollo佈局圖……………….61
圖 6.1 經過二維離散小波轉換……………………………………….65

表目錄


表 2.1為JPEG 2000中對於這兩個濾波器之邊界延伸的標準………28
表 4.1 8× 8影像之輸入與輸出資料表……………………...………...53
表 5.1 二維離散小波轉換晶片規格表……………………………….61
表 6.1 二維離散小波轉換比較表……………………………………64

[1] Information technology – JPEG 2000 image coding system – Part 1: Core coding system, ISO/IEC 15444-1, December 2000.
[2] ISO/IEC JTC1/SC29/WG1 Wgln 1684, “JPEG 2000 Verification Model 7.0,” 2000.
[3] D. Taubman, M. Marcellin, JPEG2000 image compression fundamentals, standards, and practice, Kluwer Academic Publisher, November 2001.
[4] 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, November 2000.
[5] M. W. Marcellin, M. J. Gormish, A. N. Skodras, “JPEG2000: The new still picture compression standard,” Proceedings on ACM multimedia 2000 workshops, pp. 45- 49, 2000.
[6] G. K. Wallance, “The JPEG still picture compression standard,” Communication of ACM, vol. 34, no.4, pp.31- 44, April 1991.
[7] D. Taubman, “High performance scalable image compression with EBCOT,” IEEE Transactions on Image Processing, vol. 9, no. 7, pp. 1158- 1170, July 2000.
[8] D. Taubman, E. Ordentkich, M. Weinberger, G. Seroussi, I. Ueno, and F. Ono, “Embedded block coding in JPEG2000, “HPL-2001-35, HP Labs, Palo Alto, February 2001.
[9] D.Taubman, E. Ordentlich, M. Weinberger, G. Seroussi, I. Ueno, and F. Ono, “Embedded block coding in JPEG2000,” Proceedings of IEEE International Conference on Image Processing, vol. 2, pp. 33- 36, September 2000.
[10] Kuan-Fu Chen, Chung-Jr Lian, Hong-Hui Chen, and Liang-Gree Chen, “Analysis and architecture design of EBCOT for JPEG-2000,” Proceedings of IEEE International Symposium on Circuits and Systems, vol. 2, pp. 765- 768, May 2001.
[11] M. D. Adams and F. Kossentini, “JasPer: a software-based JPEG-2000 codec implementation,” Proceedings of IEEE International Conference on Image Processing, vol. 2, pp. 53- 56, September 2000.
[12] J. S. Chiang, Y. S. Lin, and C. Y. Hsieh, “Efficient pass-parallel architecture for EBCOT in JPEG2000,” Proceedings IEEE International Symposium on Circuits and Systems, vol. 1, pp. 773- 776, May 2002.
[13] Jen-Shiun Chiang, Chun-Hau Chang, Yu-Sen Lin, Chang-You Hsien, and Chih-Hsien Hsia, “High- Speed EBCOT with Dual Context- Modeling Coding Architecture for JPEG2000, ” Proceedings IEEE International Symposium on Circuits and Systems, vol. 3, pp. 865- 868, May 2004.
[14] Chung-Jr Lian, Kuan-Fu Chen, Hong-Hui Chen, and Liang-Gree Chen, “Analysis and architecture design of lifting based DWT and EBCOT for JPEG2000,” Proceedings of International Symposium on VLSI Technology, Systems, and Applications, pp. 180- 183, April 2001.
[15] D. Santa-Cruz and T. Ebrahimi, “An analytical study of JPEG2000 functionalities,” Proceedings of International Conference on Image Processing, vol. 2, pp. 49- 52, September 2000.
[16] Usevitch. B. E., “A tutorial on modern lossy wavelet image compression: foundations of JPEG 2000,” IEEE Signal Processing Magazine, vol. 18, issue 5, September 2001.
[17] A. Said and W. Pearlman, “A new, fast and efficient image codec based on set partitioning in hierarchical trees,” IEEE Transactions on Circuits and Systems for Video Technology. Pp. 243- 250, June 1996.
[18] D. Santa-Cruz and T. Ebrahimi, “An analytical study of JPEG2000 functionalities,” Proceedings of International Conference on Image Processing, vol. 2, pp. 49- 52, September 2000.
[19] S. Mallat, “Multi-frequency channel decompositions of images and wavelet models,” IEEE Transactions on Acous. Speech and Processing, ASSP-37, 12, pp. 2091- 2110, 1989.
[20] I. Daubechies and Wim Sweldens, “Factoring wavelet transforms into lifting scheme,” The Journal of Fourier Analysis and Applications, vol. 4, pp. 247- 269, 1998.
[21] Wim Sweldens, “The lifting scheme: A custom-design construction of biorthogonal wavelets,” Applied and Computation Harmonic Analysis, vol. 3, pp.186- 200, 1996.
[22] Wim Sweldens, “The lifting scheme: A construction of second-generation wavelets,” Siam Journal of Mathematical Analysis, vol. 29, pp. 511- 200, 1997.
[23] 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.
[24] W. Press et al., Numerical recipes in Fortran, Cambridge University press, New York, 1992.
[25] Bahman Zafarifar, Micro-codable Discrete Wavelet Transform, Delft University of Technology, July 2002.
[26] K. Andra, C. Chakrabarti and T. Acharya, “A VLSI Architecture for Lifting-Based Wavelet Transform,” IEEE Workshop on Signal Processing Systems, pp. 70- 79, October 2000.
[27] C. -J. Lian, K. -F. Chen, H.-H. Chen, and L. -G. Chen, “Lifting based discrete wavelet transform architecture for JPEG2000,” IEEE International Symposium on Circuits and Systems, pp.445- 448, May 2001.
[28] K. Andra, C. Chakrabarti and T. Acharya, “A VLSI architecture for lifting-based forward and inverse wavelet transform,” IEEE Transactions on Signal Processing, vol. 50, No.4, pp. 966- 977, April 2002.
[29] We-Tan Lee, Hug-Ying Chen, Pei-Yung Hsiao and Chia-Chun Tsai, “An Efficient Lifting Based Architecture for 2-D DWT Used in JPEG2000, ” Proceeding of the 2003 VLSI Design/ CAD Symposium, pp. 577- 580, August 2003.
[30] C. Diou, L. Torres and M. Robert, ”An embeded core for the 2-D Wavelet Transform, ” IEEE on Emerging Technologies and Factory Automation Proceedings, vol. 2, pp. 179- 186, 2001.
[31] Shung-Chih Chen and Chung-Cheng Wu, “An Architecture of 2-D 3-Level Lifting-based Discrete Wavelet Transform,” Proceeding of the 2002 VLSI Design/ CAD Symposium, pp. 351- 354, August 2002.
[32] JPEG 2000 Part 1 Final Committee Draft Version 1.0, ISO/IEC JTC1/SC29/WG1N1646R.
[33] Jen-Shiun Chiang, and Chih-Hsien Hsia, “An Efficient VLSI Architecture for 2-D DWT using Lifting Scheme, ” IEEE International Conference on Systems and Signals, pp. 528- 531, April 2005.
[34] Jen-Shiun Chiang, Chih-Hsien Hsia, Hsin-Jung Chen, and Te-Jung Lo, “ VLSI Architecture of Low Memory and High Speed 2-D Lifting-Based Discrete Wavelet Transform for JPEG2000 Applications , ” IEEE International Symposium on Circuits and Systems Conference, pp. 4554- 4557, May 2005.
[35] S. Mallat, “A theory for multi-resolution signal decomposition: The wavelet representation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 7, pp. 674-693, July 1989.
[36] 黃朝宗,陳良基 “離散小波轉換之原理、應用及架構(上), ” IC Application & Design Magazine, vol. 31, pp.50- 60, November 2002.
[37] 黃朝宗,陳良基 “離散小波轉換之原理、應用及架構(下), ” IC Application & Design Magazine, vol. 32, pp. 1- 9, December 2002.
[38] 吳忠政, 二維三階上提式離散小波轉換架構: 南台科技大學電子工程所碩士學位論文, 民國91年7月.
[39] 戴顯權,陳正一, JPEG 2000, 紳藍出版社, 民國91年11月.
[40] 吳炳飛,胡益強, 瞿忠正, 蘇崇彥, JPEG 2000影像壓縮技術, 全華科技圖書股份有限公司, 民國92年4月.
[41] I. Sodagar, H-J Lee, P. Hatrack, and Y.-Q. Zhang. “Scalable wavelet coding for synthetic/natural hybrid images,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 9, pp. 244- 254, March 1999.
[42] Jer Min Jou, Pei-Yin Chen, and Ming-Shiang Liang, “A scalable pipelined architecture for separable 2-D discrete wavelet transform,” Design Automation Conference, vol. 1, pp. 205- 208, 1999.
[43] Tao-Wen Chung, Chu Yu, Guang-Huei Lin, and Sao-Jie Chen, “Design and Implementation of 2-D Discrete Wavelet Transform VLSI Architecture for JPEG2000, ” Proceeding of the 2002 VLSI Design/ CAD Symposium, pp. 363- 366, August 2002.
[44] C.-C. Lin, Y.-H. Shiau, and J. M. Jou, “Design and Implementation of a Progressive Image Coding Chip Based on the Lifted Wavelet Transform,” Proceeding of the 2000 VLSI Design/ CAD Symposium, pp. 49- 52, August 2000.
[45] Chu Yu and Sao-Jie Chen, “VLSI Implementation of 2-D Discrete Wavelet Transform for Real-Time Video Signal Processing, ” IEEE Transactions on Consumer Electronics, vol. 43, No. 4, pp. 1270 - 1279, Nov. 1997.
[46] K. K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation, John Wiley & Sons, 1999.
[47] S. Li, W. Li, “Shape-Adaptive Discrete Wavelet Transforms for Arbitrarily Shaped Visual Object Coding,” IEEE Transactions on Circuit and Systems for Video Technology, vol. 10, No. 5, pp. 725 – 743, August 2000.
[48] Po-Cheng Wu and Liang-Gee Chen, “An Efficient Architecture for Two-Dimensional Discrete Wavelet Transform,” IEEE Transactions on VLSI System, vol. 11, pp. 536- 545, June 2001.
[49] K.C.B. Tan and T. Arslan, “Low power embedded extension algorithm for the lifting based discrete wavelet transform in JPEG2000,” IEE EIectronics Letters, vol. 37, NO. 22, pp.3513- 3516, May 2002.