臺灣博碩士論文加值系統

JPEG2000標準中，最吸引人的莫過於它對於各階級影像解析度及影像品質的自由調整能力。其中數位小波轉換（DWT）與EBCOT尤其是兩大功臣，然而，它們也是整個系統當中最花費記憶體、最消耗運算力的部分。
為了減少記憶體需求，分別組合五種DWT運算順序與兩種DWT分解層級順序，來考量它們對緩衝存儲器（buffer）大小的影響。最後，我們選擇level-by-level與optimal-z san的運算順序組合，它不但減少DWT本身所需的buffer大小，同時也考量其與EBCOT之間的buffer。再者，將以stripe為基本單位的EBCOT運算順序運用到整個系統上，則能使DWT與EBCOT間的buffer再減少93.8%，而表現在整個系統上，則是總記憶體需求減少為原來的66%。然而，由於此方法會造成運算時間增加原來的14%，我們提出一個 “全零stripe略過方法”，預先跳過全零的位元平面不做，不但能補救此缺點，還能多減少0.22%的運算時間。
至於減少運算需求上，在DWT方面，兩個方向的一維DWT核心共用同一組加法及乘法器，這使得整個二維DWT的gate count減少三分之一。在EBCOT，則設計為pass-層級的平行處理，能達到傳統作法的三倍速度，並減少三分之二的記憶體存取次數。我們所設計的pass-層級平行的context formation架構，gate count約是其他人的6.8%。
最後提出一個JPEG2000編碼器的實作計畫，它使用一個DWT模組與三套embedded block coder。這個編碼器使用較小的面積與記憶體，能達到55.6Msamples/sec。

The ability to have scalability in resolution as well as image quality is the main attractiveness of JPEG2000. DWT (Discrete Wavelet Transform) and EBCOT (Embedded Block Coding with Optimal Truncation) which are two major technologies enable it, however, are also the parts that demand huge storage and computations.
To reduce memory requirement, we combine five different computing orders of DWT with level-by-level or mixed-level and find that level-by-level optimal-z scan can reduce the temporal buffer in DWT as well as the buffer between DWT and EBCOT. We also adopt the new stripe-based computation order of EBCOT to further reduce 93.8% buffer size between DWT and EBCOT. The total buffer for the JPEG2000 encoder can be reduced to 66% of the original design. However, the stripe-based computing order will increase 14% more computation time. Thus, we proposed the zero-stripe skipping technique to skip the all-zero-bitplane. With this approach, we can eliminate this overhead and reduce 0.22% computation time further.
To reduce the computation complexity, we share the multipliers and adders of the two directional DWT kernels, so that 1/3 of the area of DWT module can be saved. For EBCOT, a pass-level parallelism is adopted to speed up 3 times of the traditional processing time and to reduce 2/3 memory accesses. The gate count of proposed context formation is 6.8% of others.
Finally, we proposed a plan to use one DWT module with three embedded block coders to integrate our JPEG2000 encoding system. It can achieve a throughput of 55.6 Msamples/sec at 100 MHz clock rate with lower cost and less memory requirement.

Contents
CONTENTS V
LIST OF TABLES VIII
LIST OF FIGURES XI
CHAPTER 1 INTRODUCTION 1
1.1 BRIEF OF JPEG2000 AMONG STILL IMAGE COMPRESSION TECHNIQUES 2
1.2 JPEG2000 SYSTEM OVERVIEW 3
1.3 MOTIVATION AND CONTRIBUTION 4
1.3.1 Previous Work 4
1.3.2 Contribution 5
1.3.3 Thesis Organization 6
CHAPTER 2 ANALYSIS AND DESIGN OF DISCRETE WAVELET TRANSFORM (DWT) 7
2.1 ALGORITHM 7
2.1.1 1-D DWT and Lifting Scheme 8
2.1.2 2-D DWT and Decomposition Structure 10
2.1.3 Dead-zone Scalar Quantization 11
2.2 PRECISION ANALYSIS OF FIXED-POINT LIFTING-BASED DWT 12
2.2.1 Environment Assumptions and Problem Formulations 13
2.2.2 Range Expansion 15
2.2.3 Analysis of Number of Fractional Bits 17
2.3 BUFFER REQUIREMENT FOR DIFFERENT SCAN ORDER 22
2.3.1 Overview of the Correlation between Buffer Requirement and the Scan Order 23
2.3.2 Buffer Size Formulation of Several Scan Orders 24
2.3.3 Summary 31
2.4 ARCHITECTURE OF PROPOSED DWT 32
2.4.1 Pipelined DWT with Shared Lifting MACs 33
2.4.2 Timing Analysis of Optimal-Z Scan DWT 34
2.4.3 Memory Arrangement of the Buffers 36
CHAPTER 3 EMBEDDED BLOCK CODER 40
3.1 ALGORITHM OF EBCOT 40
3.1.1 Context Formation 41
3.1.2 MQ-Coder: Context-Based Adaptive Arithmetic Coder 47
3.2 DESIGN OF PASS-PARALLEL CONTEXT FORMATION 50
3.2.1 Parallel Techniques and Memory Considerations 50
3.2.2 Pass-Level Parallelism 53
3.2.3 Solutions of the Pass-Parallel Data Dependencies 57
3.2.4 Architecture of the Proposed Pass-parallel Context Formation 59
3.3 DESIGN OF THE PROPOSED PASS-PARALLEL MQ-CODER 63
3.3.1 Design Issues of Pass-Parallel MQ-Coder 64
3.3.2 Modifications on Original MQ-coder Algorithm 65
3.3.3 Architecture of Pipelined Pass-Parallel MQ-Coder 69
CHAPTER 4 DESIGN OF STRIPE-BASED JPEG2000 SYSTEM 73
4.1 STRIPE-BASED SUB-MODULES 74
4.1.1 Stripe-Based DWT 74
4.1.2 Stripe-Based Context Formation 75
4.1.3 Stripe-Based MQ-Coder 80
4.2 SUMMARY 83
CHAPTER 5 SYSTEM INTEGRATION, HARDWARE IMPLEMENTATION AND EXPERIMENTAL RESULT 86
5.1 SYSTEM INTEGRATION 86
5.1.1 Overview of Proposed JPEG2000 Encoder 87
5.1.2 Word-to-bitplane Conversion 90
5.2 IMPLEMENTATION FLOW AND EXPERIMENTAL RESULTS 93
5.2.1 Implementation Flow 93
5.2.2 Experimental Results 94
CHAPTER 6 CONCLUSION AND FUTURE WORK 99
6.1 CONCLUSION 99
6.2 FUTURE WORK 101
BIBLIOGRAPHY 102
APPENDIX 106

Standard
[1] ISO/IEC JTC 1/SC 29/WG 1 N1646, “JPEG2000 Part I Final Committee Draft Version 1.0,” March 2000.
[2] ISO/IEC JTC 1/SC 29/WG 1 N1894, “JPEG 2000 Verification Model 8.6 (Technical Description),” 2000.
[3] C. Christopoulos, A. Skodras, and T. Ebrahimi, “The JPEG 2000 Still Image Coding System: An Overview,” IEEE Trans. on Consumer Electronics, vol. 46, no. 4, pp.1103-1127, November 2000.
[4] D. Santa-Cruz, and T. Ebrahimi, “An Analytical Study of JPEG 2000 Functionalities.” IEEE International Conference on Image Processing, vol. 2, pp. 49-52, 2000.
[5] S. Athanassios, C. Charilaos, and E. Touradj, “The JPEG 2000 Still Image Compression Standard,” IEEE Signal Processing Magazine , vol. 18 ,no. 5, pp. 36-58, Sep 2001.
[6] R. Majid, and T. Rajan, “An overview of the JPEG 2000 Still Image Compression Standard,” Signal Processing: Image Communication.
[7] C. Christopoulos, A. Skodras, and T. Ebrahimi, “The JPEG2000 Still Image Coding: An Overview,” IEEE Trans. on Consumer Electronics, Vol. 46, No. 4, pp. 1103-1127, Nov 2000.
[8] D. Santa-Cruz, T. Ebrahimi, J. Askelof, M. Larsson, and C. Christopoulos, “JPEG 2000 Still Image Coding Versus other Standards,” ISO/IEC JTC1/SC29/WG1 (ITU-T SG8), July 2000.
[9] D. Taubman, and M. W. Marcellin, JPEG2000 Image Compression Fundamentals, Standards and Practice, Boston, Kluwer Academic Publishers, 2002.

DWT Implementation
[10] B. E. Usevitch, “A Tutorial on Modern Lossy Wavelet Image Compression: Foundations of JPEG 2000,” Proc. IEEE Int. Conf. Image Processing, Vancouver, Canada, Sep. 2000, vol. II, pp. 33-36.
[11] W. Sweldens, “The Lifting Scheme: A Custom-design Construction of Biorthogonal Wavelets,” Appl. Comput. Harmon. Anal., vol. 3, no.15, pp. 186-200, 1996.
[12] C. Chrysafis, and A. Ortega, “Line-based, Reduced Memory, Wavelet Image Compression,” IEEE Trans. Image Processing, vol. 9, no. 3, pp. 378-389, Mar. 2000.
[13] W.-H. Chang, Y.-S. Lee, W.-S. Peng, and C.-Y. Lee, “A Line-based, Memory Efficient and Programmable Architecture for 2D DWT Using Lifting Scheme,” IEEE International Symposium on Circuits and Systems, vol. 4, pp. 330-333, 2001.
[14] P.-C. Tseng, C.-T. Huang, and L.-G. Chen, “Generic RAM-based Architecture for Two-dimensional Discrete Wavelet Transform with Line-based Method,” 2002 Asia-Pacific Conference on Circuits and Systems, APCCAS '02. , vol. 1, pp. 363 -366, Oct. 2002.
[15] G. Lafruit, L. Nachtergaele, J. Bormans, M. Engels, and I. Bolsens, “Optimal memory organization for scalable texture codecs in MPEG-4”, Circuits and Systems for Video Technology, IEEE Trans. on , vol. 9 , 1999.
[16] N. D. Zervas, G. P. Anagnostopoulos, V. Spiliotopoulos, Y. Andreopoulos, and C. E. Goutis, “Evaluation of design alternatives for the 2-D-discrete wavelet transform”, Circuits and Systems for Video Technology, IEEE Tran. on , vol. 11 , 2001.
[17] M.-Y. Chih, K.-B. Lee, and C.-W. Jen, “Optimal Data Transfer and Buffer Scheme for JPEG 2000 Encoder”, SIPS, 2002.
[18] K. Andra, C. Hakrabarti, and T.Acharya, “ A VLSI architecture for lifting-based forward and inverse wavelet transform”, IEEE Tras. on Signal Processing, vol. 50, pp. 966 -977, 2002
[19] 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 Tras. on , vol. 48, pp. 1026 -1032, 2002
[20] V. Spiliotopoulos, N. D. Zervas, Y. Anagnostopoulos, G. Anagnostopoulos, and C. E Goutis, “Quantization effect on VLSI implementations for the 9/7 DWT filters”, ICASSP 2001.
[21] H. Tsutsui, T. Masuzaki, T. Izumi, T. Onoye, and Y. Nakamura, “High speed JPEG2000 encoder by configurable processor”, APCCAS, 2002.
[22] C. K. Hyung, and E. J. Delp, “A comparison of fixed-point 2D 9x7 discrete wavelet transform implementations”, Image Processing. 2002. Proceedings. 2002 International Conference on, vol. 1, 22-25. 2002.

EBCOT Implementation
[23] D. Taubman, “High Performance Scalable Image Compression with EBCOT,” Proc. of IEEE International Conference on Image Processing (ICIP), Kobe, Japan, 1999, vol. 3, pp. 344-348.
[24] D. Taubman, “High Performance Scalable Image Compression with EBCOT,” IEEE Trans. on Image Processing, vol. 9, pp.1158 –1170, July 2000
[25] David Taubman et al., “Embedded Block Coding in JPEG 2000.”
[26] K. Chen, C. Lian, H. Chen, and L. Chen, “Analysis and Architecture Design of EBCOT for JPEG 2000,” ISCAS, 2001.
[27] C.-J. Lian, K.-F. Chen, H.-H. Chen, and L.-G. Chen, “Analysis and architecture design of block-coding engine for EBCOT in JPEG 2000”, Circuits and Systems for Video Technology, IEEE Transactions on , vol. 13, pp. 219 -230, 2003
[28] Y.-T. Hsiao, H.-D. Lin, K.-B. Lee, and C.-W. Jen, “High-speed Memory-saving Architecture for the Embedded Block Coding in JPEG2000,” IEEE International Symposium on Circuits and Systems, vol. 5, pp. 122-136, 2002.
[29] L Yijun, R. E. Aly, B. Wilson, and M. A. Bayoumi, “Analysis and enhancements for EBCOT in high-speed JPEG2000 architectures”, MWSCAS, 2002.
[30] J.-S. Chiang, Y.-S. Lin, and C.-Y. Hsieh, “Efficient pass-parallel architecture for EBCOT in JPEG2000”, IEEE International symposium on Circuits and Systems (ISCAS), vol.1, pp. 26-29, May 2002.
[31] L Yijun; R. E. Aly, M. A. Bayoumi, and S. A. Mashali, “Parallel high-speed architecture for EBCOT in JPEG2000”, ICASSP, 2003.
[32] H.-C. Fang, T.-C. Wang, C.-J. Lian, T.-H. Chang, and L.-G. Chen, “High speed memory efficient EBCOT architecture for JPEG2000”, ISCAS, 2003.
[33] M. Dyer, D. Taubman, and S. Nooshabadi, “Memory efficient pass-parallel architecture for JPEG2000 encoding”, Signal Processing and Its Applications, Proceedings. Seventh International Symposium on , vol. 1, pp. 53 – 56, July 1-4, 2003
[34] M. Tarui, M Oshita, T. Onoye, and I. Shirakawa, "High-Speed Implementation of JBIG Arithmetic Coder," IEEE Tencon, 1999.
[35] K.-K. Ong, W.-H. Chang, Y. –C. Tseng, Y.-S. Lee, and C.-Y. Lee, “A high throughput low cost context-based adaptive arithmetic codec for multiple standards”, Image Processing. 2002. Proceedings. International Conference on , vol. 1 , pp. 22-25, Sept. 2002

JPEG2000 CODEC Implementation
[36] K. Andra, C. Chakrabarti, and T. Acharya, “A High-performance JPEG2000 Architecture”, IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp. 209-218, Mar., 2003.
[37] H.Yamauchi, S. Okada, K. Taketa, T. Ohyama, Y. Matsuda, T. Mori, T. Watanabe, Y. Matsuo, Y. Yamada, T. Ichikawa, and Y. Matsushita, “Image processor capable of block-noise-free JPEG2000 compression with 30 frames/s for digital camera applications”, ISSCC, 2003.
[38] H.Yamauchi, S. Okada, K. Taketa, Y. Matsuda, T. Mori, T. Watanabe, and K. Mochizuki, “A 1440x1080-pixels 30-Frams/s Motion-JPEG2000 Codec for HD Movie Transmission”, ISSCC, 2004.
[39] H.-C. Fang, C.-T. Huang, Y.-W. Chang, T.-C. Wang, P.-C. Tseng, C.-J. Lian, and L.-G. Chen, “81M Samples/s JPEG 2000 Single-Chip Encoder with Rate-Distortion Optimization”, ISSCC, 2004.
[40] Alma Technologies, “JPEG 2000 Encoder Datasheet,” May 2002. Available on http://www.alma-tech.com/products_list.htm.
[41] Amphion products—JPEG2000 encoder, CS6510. Available on http://www.amphion.com/cs6510.html