臺灣博碩士論文加值系統

離散小波轉換( Discrete Wavelet Transform )是一種分析資料的方法，當影像資料經過小波轉換後，會產生不同重要性的資料，根據這些重要性的差異，便能依其特性做最佳的處理，而達到更好的壓縮效果。因此，離散小波轉換相當受到重視，也已被廣泛運用在許多領域上。
在本篇論文中，我們提出一些高效率的二維離散小波轉換線型架構。首先提出的架構為長度可調之上提式二維離散小波轉換架構，利用管線化與合併乘法器係數的方法來提升硬體使用率，再來是使用一個4輸入訊號/4輸出訊號的架構直接實現二維離散小波轉換，此架構對一張N×N的影像執行1階層的分解時，大約只需花費(N×N)/4的內部工作時脈。根據此4輸入訊號/4輸出訊號的架構，我們另外提出一個管線式架構，其能執行多階層的二維離散小波轉換，而對一張N×N的影像執行完整的二值分解時，大約也只需花費(N×N)/4的內部工作時脈。從效能分析與比較結果中可以證明我們提出的架構具有較快的資料輸出率、較佳的效能以及較高的硬體使用率。最後以Verilog HDL描述我們提出的電路架構，經過編譯模擬完成後，再利用Xilinx的元件庫設計。然後，我們使用Xilinx FPGA元件Spartan II XC 2S200-6PQ208C來模擬實現。

The discrete wavelet transform (DWT) is one kind of data analysis approaches. Image signals can be decomposed into different frequency bands by the DWT. It can be achieved better performance of compression to process these frequency bands appropriately. Thus the DWT is attached great importance. Moreover, it has been popularly used in many applications.
In this thesis, we present some high-efficiency line-based architectures for two-dimensional discrete wavelet transform (2-D DWT). A scalable architecture for lifting-based 2-D DWT which is a pipelined and merged architecture is first proposed by us. Then we present a four-input/four-output architecture for direct 2-D DWT that 1-level decomposition of a N×N image could be performed in approximately (N×N)/4 intra-working clock cycles (ccs), where the parallelism among 4 sub-bands transforms in lifting-based 2-D DWT is explored. By using this four-input/four-output architecture, we propose a novel pipelined architecture for multi-level 2-D DWT that can perform a complete dyadic decomposition of N×N image in approximately (N×N)/4 ccs. Performance analysis and comparison results demonstrated that, the proposed architectures have faster throughput rate and good performance in terms of production of throughput rate and hardware cost, as well as hardware utilization.
At last the proposed architectures are designed and simulated by using Verilog HDL as well as it is verified by Xilinx tools. Then, we implement them on a FPGA device of Spartan II XC 2S200-6PQ208C.

中文摘要 V
英文摘要 VI
誌謝 VII
目錄 VIII
表目錄 XI
圖目錄 XIII
第一章 緒論 1
1.1 研究動機 1
1.2 相關研究 2
1.3 章節概要 5
第二章 離散小波轉換 7
2.1 前言 7
2.2 一維離散小波轉換 8
2.2.1 傳統濾波器離散小波轉換 8
2.2.2 上提式離散小波轉換 11
2.3 二維離散小波轉換 16
2.4 線型離散小波轉換 18
2.5 相關技術 21
2.5.1 金字塔演算法 21
2.5.2 遞迴金字塔演算法 22
2.5.3 心跳式架構設計 25
第三章 長度可調之上提式離散小波轉換硬體架構 28
3.1 前言 28
3.2 5/3濾波器之上提式離散小波轉換硬體架構 29
3.3 長度可調之上提式二維離散小波轉換硬體架構 32
3.4 效能比較 40
第四章 上提式二維離散小波轉換之線型架構 41
4.1 前言 41
4.2 一階二維離散小波轉換之線型架構 41
4.3 多階二維離散小波轉換之線型架構 45
4.3.1 二維遞迴式架構 47
4.3.2 管線式架構 49
4.4 硬體效能分析與比較 50
4.4.1 硬體複雜度與控制複雜度 51
4.4.2 計算時間與輸出延遲 52
4.4.3 硬體使用率 52
4.4.4 系統功率消耗 53
第五章 設計流程與模擬結果驗證 57
5.1 設計流程 57
5.2 模擬結果比較 59
5.2.1 Case 1：使用9/7濾波器係數 65
5.2.2 Case 2：使用5/3濾波器係數 67
5.3 FPGA硬體實現效能比較 69
第六章 結論與未來展望 73
參考文獻 75
附錄 79
教育性晶片下線報告(94年度) 80
教育性晶片測試成果報告(94年度) 90

表目錄
表2.1 硬體資源比較表 15
表3.1 一階一維離散小波轉換時序排程表 36
表3.2 8×8影像之二維離散小波轉換時序表 38
表3.3 離散小波轉換之輸入資料和輸出係數表 39
表3.4 硬體效能比較表 40
表4.1 降低4倍工作頻率後管線式架構所節省的功率消耗估算表 54
表4.2 管線式架構與遞迴式架構[31]模擬結果(N =128) 55
表4.3 管線式架構與遞迴式架構[31]模擬結果(N =256) 55
表5.1 不同的二維離散小波轉換摺疊式架構效能比較 62
表5.2 不同的多階二維離散小波轉換架構效能比較(1) 63
表5.3 不同的多階二維離散小波轉換架構效能比較(2)(接續表5.2) 64
表5.4 不同的二維離散小波轉換摺疊式架構效能比較(9/7濾波器) 65
表5.5 不同的多階二維離散小波轉換架構效能比較(9/7濾波器)(1) 66
表5.6 不同的多階二維離散小波轉換架構效能比較(9/7濾波器)(2) 66
表5.7 不同的二維離散小波轉換摺疊式架構效能比較(5/3濾波器) 67
表5.8 不同的多階二維離散小波轉換架構效能比較(5/3濾波器)(1) 68
表5.9 不同的多階二維離散小波轉換架構效能比較(5/3濾波器)(2) 68
表5.10 Lifting與Flipping量化後係數對照表 70
表5.11 使用兩種不同的量化係數之PSNR值(Ours) 71
表5.12 使用兩種不同的量化係數之PSNR值(Marino [17]) 71
表5.13 使用兩種不同的量化係數之PSNR值(Liao [31]) 72

圖目錄
圖2.1 輸入資料與高低頻係數的關係 10
圖2.2 一階一維離散小波轉換之正、反轉換架構圖 10
圖2.3 上提式離散小波正轉換架構 12
圖2.4 上提式離散小波反轉換架構 14
圖2.5 一階二維離散小波正轉換架構圖 16
圖2.6 一階二維離散小波反轉換架構圖 18
圖2.7 四階二維線型離散小波轉換示意圖 19
圖2.8 RPA應用於一維離散小波轉換之三層解析度的資料排程 23
圖2.9 RPA應用於二維離散小波轉換之三層解析度的資料排程 24
圖2.10 心跳式系統基本原理示意圖 25
圖2.11 資料相依圖 27
圖2.12 根據圖2.11所描繪出的心跳式架構圖 27
圖3.1 上提式離散小波轉換架構 29
圖3.2 5/3濾波器之上提式離散小波轉換硬體架構 30
圖3.3 改良後5/3濾波器之上提式離散小波轉換硬體架構 30
圖3.4 使用直接法實現上提式一階二維離散小波轉換架構 31
圖3.5 使用一個上提式模組來完成一階二維離散小波轉換架構 32
圖3.6 長度可調之上提式二維離散小波轉換硬體架構 33
圖3.7 列方向小波轉換示意圖 34
圖3.8 行方向小波轉換示意圖 34
圖3.9 管線化5/3濾波器之上提式離散小波轉換硬體架構 35
圖3.10 合併預測與更新模組後之硬體架構 35
圖4.1 一階二維離散小波轉換之線型架構示意圖 42
圖4.2 正規化單元(SNU)架構圖 43
圖4.3 使用D4小波濾波器的一維架構流程圖 44
圖4.4 二維離散小波轉換摺疊式架構圖 46
圖4.5 上提式多階二維離散小波轉換摺疊式架構圖 46
圖4.6 改良後的上提式多階二維離散小波轉換遞迴架構 47
圖4.7 SNU架構示意圖 48
圖4.8 多階二維離散小波轉換管線式架構 50
圖5.1 不同層級的電路示意圖 58
圖5.2 電路架構設計流程圖 59
圖5.3 電路模擬環境流程示意圖 60
圖5.4 不同架構在不同的分解階層中的硬體使用率 62

[1] ISO/IEC ISO/IEC 15444-1 “Information Technology JPEG 2000 Image Coding System,” 2000.
[2] S. G. Mallat, “Multi-frequency channel decompositions of images and wavelet models,” IEEE Trans. on Acous. Speech and Proc. ASSP-37, 12, pp. 2091-2110, 1989.
[3] G. Beylkin, R. Coifman, and V. Rokhlin, “Wavelets in numerical analysis,” New York: Jones and Bartlett, 1992.
[4] A. N. Akansu and R. A. Haddad, Multi-resolution signal decomposition: transforms, subbands and wavelets, ACADEMIC PRESS, second edition, 1992.
[5] M. A. Stoksik, R. G. Lane, D. T. Nguyen, “Accurate synthesis of fractional Brownian motion using wavelets,” Electronic Letters, vol.30, no.5, pp.383-384, Mar 1994.
[6] D. Taubman, “High performance scalable image compression with EBCOT,” IEEE Trans. on Image Processing, vol.9, pp.1158-1170, July 2000.
[7] I. Sodagar, H. J. Lee, P. Hatrack, and Y. Q. Zhang, “Scalable wavelet coding for synthetic/natural hybrid images,” IEEE Trans. on Circuits and Systems for Video Technology, vol.9, pp.244-254, Mar 1999.
[8] R. Kronland-Martinet, J. Morlet, and A. Grossman, “Analysis of sound patterns through wavelet transform,” Int’l J. Pattern Recognition and Artificial Intelligence, vol.1, no.2, pp.273-302, 1987.
[9] K. K. Parhi and T. Nishitani, “VLSI architectures for discrete wavelet transforms,” IEEE Transaction on VLSI System, vol.1, no.6, pp.191–202, 1993.
[10] C. Chakrabarti, M. Vishwanath, “Efficient realizations of the discrete and continuous wavelet transforms: from single chip implementations to mappings on SIMD array computers,” IEEE Trans. on Signal Processing, vol.43, no.3, pp.759-771, 1995.
[11] S.G. 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, 1989.
[12] A. S. Lewis and G. Knowles, “VLSI architecture for 2-D Daubechies wavelet transform without multipliers,” Electronics Letter, vol.27, pp.171–173, Jan. 1991.
[13] C. Chakrabarti and M. Vishwanath, “Architectures for wavelet transforms: A survey,” J. VLSI Signal Processing, vol.14, pp.171–192, 1996.
[14] J. C. Limqueco and M. A. Bayoumi, “A VLSI architecture for separable 2-D discrete wavelet transforms,” J. VLSI Signal Processing, vol.18, pp.125–140, 1998.
[15] P. Wu and L. Chen, “An efficient architecture for two-dimensional discrete wavelet transform,” IEEE Transactions on Circuits and Systems for Video Technology, vol.11, no.4, pp.536-545, 2001.
[16] F. Marino, “Two fast architectures for the direct 2-D discrete wavelet transform-Signal Processing,” IEEE Transactions on Signal Processing, vol.49, no.6, pp.1248-1259, 2001.
[17] F. Marino, “Efficient high-speed/low-power pipelined architecture for the direct 2-D discrete wavelet transform,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol.47, no.12, pp.1476-1491, 2000.
[18] T. Park and S. Jung, “High speed lattice based VLSI architecture of 2D discrete wavelet transform for real-time video signal processing,” Consumer Electronics, IEEE Transactions on Consumer Electronics, vol.48, no.4, pp.1026-1032, 2002.
[19] M. Week and M. Bayoumi, “Discrete wavelet transform: architectures, design and performance issues,” Journal of VLSI Signal Processing Systems - portal.acm.org, vol.35, no.2, pp.155-178, 2003.
[20] C. Chrysafis, and A. Ortega, “Line-based, reduced memory, wavelet image compression,” IEEE Transactions on Image Processing, vol.9, no.3, pp.378-389, 2000.
[21] I. Daubechies and W. Sweldens, “Factoring wavelet transforms into lifting schemes,” J. Fourier Anal. Appl., vol. 4, pp. 247–269, 1998.
[22] W. Sweldens, “The lifting scheme: A new philosophy in biorthogonal wavelet constructions,” in Proc. SPIE, vol.2569, pp. 68–79, 1995.
[23] A.R. Calderbank, I. Daubechies, W. Sweldens, and B.L. Yeo, “Wavelet transform that map integers to integers,” Applied and Computational Harmonic Analysis (ACHA), vol.5, no.3, pp.332-369, 1998.
[24] H. Meng, Z. Wang, “Fast spatial combinative lifting algorithm of wavelet transform using the 9/7 filter for image block compression,” Electronics Letters, vol.36, no.21, pp.1766-1767, 2000.
[25] W. Jiang and A. Ortega, “Lifting factorization-based discrete wavelet transform architecture design,” IEEE Trans. Circuits Syst. Video Technol., vol.11, no.5, pp. 651–657, May 2001.
[26] 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, 2002.
[27] L. Liu, X. Wang, et al, “A VLSI architecture of spatial combinative lifting algorithm based 2-D DWT/IDWT,” Asia-pacific Conference on Circuits and System, vol.2, pp.299-304, 2002.
[28] P.-C. Tseng, C.-T. Huang, L.-G Chen, “Generic RAM-based architecture for two-dimensional discrete wavelet transform with line-based method,” Asia-pacific Conference on Circuits and System, vol.2, pp.363-366, 2002.
[29] G. Dillen, B. Georis, J. D. Legat and O. Cantineau, “Combined line-based architecture for the 5-3 and 9-7 wavelet transform of jpeg2000,” IEEE Trans. on Circuits and Systems for Video Tech., vol.13, no.9, pp.944-950, 2003.
[30] H. Yammauchi, S. Okada, et al, “Image processor capable of block-noise-free JPEG2000 compression with 30 frame/s for digital cameral applications,” in IEEE International Solid-State Circuits Conference Digest of Technical Papers, vol.1, pp.46-477, 2003.
[31] H. Liao, M.K. 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, 2004.
[32] C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Memory analysis and architecture for two dimensional discrete wavelet transform,” Proceeding in IEEE International Conference on Acoustics, Speech, and Signal Processing, vol.5, pp.13-16, May 2004.
[33] C. Chrysafis, and A. Ortega, “Line-based, reduced memory, wavelet image compression,” IEEE Trans. on Image Processing, vol.9, no.3, pp.378-389, 2000.
[34] K. K. Parhi, “VLSI digital signal processing systems design and implementation,” Beijing: China Machine Press, 2003.
[35] J.-M. Jou, P.-Y. Chen, M.-S. Liang, “A scalable pipelined architecture for separable 2-D discrete wavelet transform,” Design Automation Conference, vol. 1, pp.205-208, 1999.
[36] M. Ferretti, D.Rizzo, “Handling borders in systolic architectures for the 1-D discrete wavelet transform for perfect reconstruction,” IEEE Transactions on Signal Processing, vol. 48, no. 5, pp.1365-1378, May 2000.
[37] M. Vishwanath, R. M. Owens and M. J. Irwin, “VLSI architectures for the discrete wavelet transform”, IEEE Transactions on Circuits and Systems, vol. 42, no. 5, pp.305-316, 1995.
[38] Aleksander Grzeszczak, Mrinal K. Mandal, Sethuraman Panchanathan, “VLSI implementation of discrete wavelet transform”, IEEE Transactions on VLSI System, pp.421-433, Dec. 1996.
[39] M. Vishwanath, “The recursive pyramid algorithm for the discrete wavelet transform”, IEEE Transactions on Signal Processing, vol. 42, no. 3, pp.673-677, 1994.
[40] C.T. Huang, P.C. Tseng, L.G. Chen, “Flipping structure: an efficient VLSI architecture for lifting-based discrete wavelet transform”, IEEE Asia-Pacific Conference on Circuits and Systems, vol. 1, 2002, pp.383-388.
[41] Peter Pirsch, Architectures for Digital Signal Processing. Chichester, John Wiley & Sons, 1998.
[42] 吳炳飛、胡益強、瞿忠正、蘇崇彥、林重甫，JPEG 2000影像壓縮技術，全華科技圖書股份有限公司，2005。
[43] 鄭信源，Verilog硬體描述語言數位電路 --- 設計實務，儒林圖書公司，2004。
[44] 黃英叡、黃稚存，Verilog硬體描述語言(第二版)，全華科技圖書股份有限公司，2005。
[45] 林灶生、劉紹漢，Verilog FPGA晶片設計，全華科技圖書股份有限公司，2004。
[46] 鄭群星，FPGA/CPLD數位晶片設計入門 -- 使用Xilinx ISE發展系統，全華科技圖書股份有限公司，2005。
[47] 簡弘倫，Verilog晶片設計，文魁資訊股份有限公司，2005。
[48] 古頤榛，Visual C++ 6教學範本，�眳p資訊股份有限公司，2005。
[49] 張智星，MATLAB程式設計與應用，清蔚科技，2000。