臺灣博碩士論文加值系統

本論文提出二進制算術編碼法與基於上下文的二進制算術編碼法的解析解，因此，相對於傳統方法，所提出解析解的執行時間有明顯的改進。實驗結果顯示所提出的方法優於目前主流方法，如不用乘法的Q編碼（MQ編碼）與以基於上下文的自適應二進制算術編碼（CABAC）。實驗結果也顯示，在可接受的執行時間下，所提出二進制算術編碼法與基於上下文的二進制算術編碼法的解析解其壓縮率較MQ編碼佳。此外，透過所提出的解析解，原二進制算術編碼法與基於上下文的二進制算術編碼法的執行時間可以分別減少大約16%與27%。相較於原CABAC，在可接受的壓縮率下，所提出的二進制算術編碼法與基於上下文的二進制算術編碼法的執行時間可以分別減少大約73%與66%。所提出之解析解實質地改進了二進制算術編碼法與基於上下文的二進制算術編碼法的編碼速度。

In this thesis, analytic forms of binary arithmetic coding (BAC) and context-based binary arithmetic coding (CBAC) are proposed, with the aim of significantly improving their execution times compared with conventional approaches. The experimental results show that the performances of the proposed methods are comparable to those of state-of-the-art methods, such as the multiplier-free Q-coder (MQ-coding) and context-based adaptive binary arithmetic coding (CABAC). The experimental results also show that, under acceptable execution time, the compression ratios of the proposed analytic forms of BAC and CBAC demonstrate better performance than does MQ-coding. In addition, the execution times of conventional BAC and CBAC are reduced to approximately 16% and 27%, respectively, by the proposed analytic forms. Compared with CABAC, the proposed analytic forms provide a substantial improvement in coding speed, where the execution times are reduced to approximately 73% and 66%, respectively, by the proposed analytic forms of BAC and CBAC with an acceptable compression ratio.

中文摘要 III
Abstract IV
List of Acronyms VII
List of Tables VIII
List of Figures X
Chapter 1 Introduction 1
Chapter 2 Background 3
2.1 Binary Arithmetic Coding 3
2.2 Context-Based Binary Arithmetic Coding 5
2.3 MQ-Coding 8
2.3.1 MQ-Coding Procedure 8
Chapter 3 Proposed Analytic Forms for BAC and CBAC 18
3.1 Proposed BAC Analytic Form 18
3.2 Proposed CBAC Analytic Form 30
Chapter 4 Experimental Results 53
Chapter 5 Conclusions 60
References 61

[1]Bodden, E., MalteClasen, and Joachim Kneis, “Arithmetic Coding revealed-A guided tour from theory to praxis, Sable Technical Report No. 2007-5, pp. 1-60, May 2007.
[2]Brady, N., F. Bossen, and N. Murphy, “Context-based arithmetic encoding of 2D shape sequences, Proceedings of IEEE International Conference on Image Processing, California, USA, pp. 29-32, Oct. 26-29, 1997.
[3]Chiang, J. S., Y. S. Lin, and C. Y. Hsieh, “Efficient pass-parallel architecture for EBCOT in JPEG2000, Proceedings of IEEE International Symposium on Circuits and Systems, Arizona, USA, pp. 773-776, May 26-29, 2002.
[4]Doshi, J., “Improved performance of arithmetic coding by extracting multiple bits at a time, International Journal of Engineering, vol. 1, no.8, pp. 1-7, 2012.
[5]Gonzalez, R. C. and R. Woods. (2008), Digital Image Processing. Boston, MA, USA: Pearson/Prentice Hall.
[6]Hattori, R., K. Sugimoto, Y. Itani, S.-i. Sekiguchi, and T. Murakami, “Fast bypass mode for CABAC, Proceedings of Picture Coding Symposium, Krakow, Poland, pp. 417-420, May 7-9, 2012.
[7]Howard, P. G., “Text image compression using soft pattern matching, The Computer Journal, vol. 40, pp. 146-156, 1997.
[8]Kim, C. H. and I. C. Park, “High speed decoding of context-based adaptive binary arithmetic codes using most probable symbol prediction, Proceedings of IEEE International Symposium on Circuits and Systems, Island of Kos, Greece, pp. 1707-1710, May 21-24, 2006.
[9]Konecki, M., R. Kudelic, and A. Lovrencic, “Efficiency of lossless data compression, Proceedings of the 34th International Convention on Information and Communication Technology, Electronics and Microelectronics, Opatija, Croatia, pp. 810-815, May 23-27, 2011.
[10]Lelewer, D. A. and D. S. Hirschberg, “Data compression, Association for Computing Machinery Computing Surveys, vol. 19, pp. 261-296, 1987.
[11]Lucking, D. and E. Balster, “An increased throughput FPGA design of the JPEG2000 binary arithmetic decoder, International Conference on Digital Image Computing: Techniques and Applications, Sydney, Australia, pp. 400-405, Dec. 1-3, 2010.
[12]Marpe, D., G. Blattermann, G. Heising, and T. Wiegand, “Video compression using context-based adaptive arithmetic coding, Proceedings of IEEE International Conference on Image Processing, Thessaloniki, Greece, pp. 558-561, Oct. 7-10, 2001.
[13]Marpe, D., H. Schwarz, and T. Wiegand, “Context-based adaptive binary arithmetic coding in the H. 264/AVC video compression standard, IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, pp. 620-636, 2003.
[14]Min, B., S. Yoon, J. Ra, and D. S. Park, “Enhanced renormalization algorithm in MQ-coder of JPEG2000, Proceedings of International Symposium on Information Technology Convergence, Jeonju, Korea, pp. 213-216, Nov. 23-24, 2007.
[15]Moffat, A., R. Neal, and I. H. Witten, “Arithmetic coding revisited, Proceedings of IEEE Data Compression Conference, Snowbird, Utah, pp. 202-211, Mar. 28-30, 1995.
[16]Nesamani, I. and C. Vasanthanayaki, “Implementation of simplified architecture of JPEG 2000 MQ coder, Proceedings of International Conference on Control, Automation, Communication and Energy Conservation, Kongu Engineering College, India, pp. 1-6, Jun. 4-6, 2009.
[17]Osorio, R. R. and J. D. Bruguera, “Arithmetic coding architecture for H. 264/AVC CABAC compression system, Proceedings of the Euromicro Symposium on Digital System Design, Rennes, France, pp. 62-69, Aug. 3, 2004.
[18]Saidani, T., M. Atri, and R. Tourki, “Implementation of JPEG 2000 MQ-coder, Proceedings of the 3rd International Conference on Design and Technology of Integrated Systems, Tozeur, Tunisie, pp. 1-4, Mar. 25-27, 2008.
[19]Vitter, J. S. and P. G. Howard, “Arithmetic coding for data compression, Proceedings of the IEEE, pp. 857-865, Jun., 1994.
[20]Witten, I. H., R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression, Communications of the Association for Computing Machinery, vol. 30, pp. 520-540, 1987.
[21]Yang, Y., H. Yan, and D. Yu, “Content-lossless document image compression based on structural analysis and pattern matching, Pattern Recognition, vol. 33, pp. 1277-1293, 2000.