臺灣博碩士論文加值系統

在大部分的資料壓縮演算法當中，熵編碼是其中不可或缺的一環，它可以被用來將複雜的中繼符號轉換成用來儲存的01二元符號。常被使用的熵編碼演算法有像是赫夫曼編碼，算數編碼等，以及最近其的非對稱數值系統。就壓縮率而言，算數編碼在編碼效能上能夠最逼近該數值分布理論上的熵值，因此在近期的研究中被廣泛運用。
在本論文中，我們先提出了改良式漸進算數編碼的研究成果，這之中使用了五樣技術以改進算數編碼的壓縮效能，包括：初始頻率表的設計、漸進式增加的調整幅度、廣域調整、交互學習、暫時／局部的頻率表設計。我們也提供了這些技術應用在許多壓縮演算法中所得到的模擬結果，像是無失真／失真圖片壓縮、文字壓縮。模擬結果也顯示出我們提出的這五項技術確實能使編碼效能更高。此外，由於絕大多數的壓縮演算法都有熵編碼的設計在內。因此，我們提出的這五項技術可以被廣泛運用在各式各樣的壓縮演算法之中。
一直以來，資料壓縮的研究員們試圖將各式各樣的訊號處理技術應用在資料壓縮上。而近年隨著機器學習的興起，以及針對機器學習設計的硬體輔佐，使得在這近一、二十年間使用機器學習理論去做壓縮的演算法技術有逐漸增多的趨勢。然而，由於一些機器學習理論及技術的限制，絕大多數相關的演算法所得到的壓縮效能都無法和其他傳統訊號處理的技術比擬。
在此論文中，我們提出了一個相當有效混合傳統訊號處理及機器學習的壓縮演算法架構。而其中的機器學習技術使用的是一般在該領域相當常見的二元分類問題。 我們將它應用到一個類似於JPEG2000的壓縮演算法之中，首先影像先經過二維的小波轉換並量化。然後，在反量化後的小波係數域中，我們透過鄰近的小波係數以及更高層頻帶的小波係數來預測當前的小波係數是否為0。透過這樣的設計，我們將這個預測結果帶入JPEG2000原先的編碼系統之中，再運用前文參考的算數編碼去做壓縮。這個混合傳統訊號處理以及機器學習的系統可以被應用在各式各樣基於多解析度的壓縮演算法之中。此架構的精髓在於，我們可以基於一個本身就相當不錯的架構，再套用機器學習的技術來加強。如此得到的編碼效能必然會比原先的結果來得好，而不是像近年許多基於機器學習的壓縮技巧用了很多複雜的理論技術但僅能勉強達到「不輸傳統技術太多」的效能。
資料壓縮亦被廣泛使用在生醫訊號的壓縮上，因為像是心電圖之類的生理量測訊號往往是長時間記錄的，因此如果無損儲存的話，會耗費相當大量的存儲資源。在本論文中，我們也提出了一個非常有效的心電圖壓縮技術。首先我們先透過既有的針對節律的切割排序方法，將一維的心電圖轉換成二維的心電圖，再使用一個新穎的頻帶間的預測編碼技術，最後再使用如前段所述混合機器學習的架構去做壓縮。模擬結果顯示，我們提出的心電圖壓縮技術遠勝於早些時候的心電圖壓縮技術，也能夠略勝或可比擬於近期的一些研究成果。

In most compression algorithms, entropy coding, such as Huffman code and arithmetic code is applied as a means for coding the source symbols into bits with respect to their entropy. Arithmetic codes have been proven to be the most efficient, since it could theoretically achieve bitrates arbitrarily close to the entropy.
In this thesis, we propose several efficient techniques that could be applied in arithmetic coding, including table initialization, increasing adjusting step, range adjustment, mutual learning, and the design of local frequency tables. We also provide examples of using the proposed techniques to compress texts, lossless image compression, and lossy image compression. Simulation results show that with these techniques applied, arithmetic coding could have a better coding efficiency. Above all, our proposed techniques on improving arithmetic code could be used in any compression algorithms.
Data compression researchers have been applying various analysis techniques in each domain to further improve their compression efficiency. In recent years, machine learning has been a trending research area that was made available by the growth of hardware infrastructures, and people have been applying it on all kinds of tasks. In the past two decades, there have been several machine learning based compression techniques. However, their performances weren’t relatively promising to other signal processing methods.
In this thesis, we propose an efficient and robust compression framework that uses machine learning based classification. We applied it on a JPEG2000-like image compression algorithm. First, the image is transformed using discrete wavelet transform (DWT) and each subband is quantized individually. For each DWT coefficient, we use its neighboring dequantized coefficients and dequantized coefficients in its higher-level subband to predict whether or not the current quantized coefficient is zero. Then the binary prediction result is emitted as an additional context, and coded along with the final context-based adaptive binary arithmetic coder (CABAC). Even though our framework is based on the JPEG2000 codec, but it could also be applied to any other compression algorithms that uses multilevel decomposition and context based entropy coding. The essence of this proposed framework is that, instead of building a machine learning based coder from scratch and struggle to compete with other traditional codecs, we build it upon an already decent coder. Thus, it guarantees that it could be at least as good as the coder, and be further improved using the machine learning techniques.
Data compression has also been a crucial part in biomedical signals, since signals such as electrocardiogram (ECG), are recorded for a long duration, and could easily overwhelm its storage device if no compression is applied. In this thesis, we also proposed an ECG compression algorithm that aligns the ECG signal into 2D and utilize the framework mentioned previously for image compression with some domain adaptation such as inter-subband DPCM. Results show that our proposed method yields significant improvement over recent works.

口試委員會審定書 #
誌謝 ii
中文摘要 iii
ABSTRACT v
CONTENTS vii
LIST OF FIGURES xi
LIST OF TABLES xv
Chapter 1 Introduction 1
1.1 Background 1
1.2 Theoretical Foundation 2
1.3 Organization 4
Chapter 2 Image and Text Compression 5
2.1 Evaluation 5
2.2 JPEG 8
2.2.1 Color Space Transformation 8
2.2.2 Block-based 2D Discrete Cosine Transform 10
2.2.3 Quantization 12
2.2.4 DC Coefficients: Differential Coding 13
2.2.5 AC Coefficients: Zigzag Scanning and Run-length Coding 13
2.2.6 Symbol Grouping and Huffman Coding 14
2.3 JPEG2000 17
2.3.1 Tile-based 2D Discrete Wavelet Transform 18
2.3.2 Quantization 20
2.3.3 Tier-1 Coding: EBCOT, MQ-Coder 21
2.3.4 Tier-2 Coding: Bitstream Formation 24
2.4 Lossless Image Compression: CALIC 24
2.5 Lossless Image Compression: EDP 26
2.6 Text Compression 27
Chapter 3 Entropy Coding 29
3.1 Introduction 29
3.2 Huffman code 31
3.3 Arithmetic Code 32
3.4 Asymmetric Numeral Systems 35
Chapter 4 Proposed Improved Adaptive Arithmetic Coding: Algorithms 38
4.1 Initialization of the Frequency Table 38
4.2 The Range Adjusting Scheme 39
4.3 Increasing the Adjusting Step Size 43
4.4 Mutual Learning 45
4.5 Local Frequency Table 46
Chapter 5 Proposed Improved Adaptive Arithmetic Coding: Simulation Results
…………………………………………………………………………... 48
5.1 JPEG 48
5.1.1 DC Differences 49
5.1.2 AC Coefficients 51
5.1.3 DC+AC Combined 54
5.2 JPEG2000 55
5.3 Lossless Image Compression: CALIC 59
5.4 Lossless Image Compression: EDP 61
5.5 Text Compression 66
5.6 Guide on Selecting Parameters 68
5.7 Additional Simulation Results 70
5.8 Conclusion 72
Chapter 6 Fundamentals of Machine Learning 73
6.1 Introduction 73
6.2 Training / Inference 75
6.3 Artificial Neural Network 77
6.4 Autoencoder 80
6.5 Generative Adversarial Network 81
6.6 Compression Related works 82
Chapter 7 Proposed Lossy Image Compression Using Machine Learning
Techniques ………………………………………………………………. 85
7.1 Introduction 85
7.2 Framework 86
7.3 Feature Extraction 88
7.4 Model Training 92
7.5 Apply Prediction 95
7.6 Entropy Coder 96
7.7 Simulation Results 98
7.8 Conclusion 104
Chapter 8 Introduction to ECG Compression 105
8.1 Introduction 106
8.2 Evaluation 108
8.3 Related Works 109
Chapter 9 Proposed ECG Compression Using Machine Learning 111
9.1 Introduction 111
9.2 Framework 111
9.3 Beat-Align and Padding 112
9.4 Directed DPCM 114
9.5 Entropy Coder 115
9.6 Simulation Results 116
9.7 Conclusion 117
Chapter 10 Conclusion and Future Work 119
10.1 Conclusion 119
10.2 Future Work 120
REFERENCE 121
PUBLICATIONS 128

[1]Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: From error measurement to structural similarity”, IEEE Trans. Image Process., vol. 13, no. 4, pp. 600-612, Apr. 2004.
[2]G. K. Wallace, “The JPEG still picture compression standard,” Commun. ACM, vol. 34, pp. 30-44, Apr. 1991.
[3]C. Christopoulos, A. Skodras, A. Koike, and T. Ebrahimi, “The JPEG2000 still image coding system: an overview,” IEEE Transactions on Consumer Electronics, vol. 46, issue 4, pp. 1103- 1127, 2000.
[4]T. Acharya and P. S. Tsai, JPEG2000 Standard for Image Compression: Concepts, Algorithms and VLSI Architectures. Wiley, Jan. 2005.
[5]D. Taubman, “High performance scalable image compression with EBCOT,” Proc. IEEE Int. Conference Image Processing, vol. 3, pp. 344-348, Oct. 1999.
[6]X. Wu and N. Memon, “Context based, adaptive, lossless image coding,” IEEE Trans. Commun., vol. 45, issue 4, pp. 437-444, Apr. 1997.
[7]D. A. Clunie, “Lossless compression of grayscale medical images: effectiveness of traditional and state-of-the-art approaches,” Medical Imaging, International Society for Optics and Photonics, pp. 74-84, 2000.
[8]J. Kim and C. M. Kyung, “A lossless embedded compression using significant bit truncation for HD video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, issue 6, pp. 848-860, 2010.
[9]X. Li and M. Orchard, “Edge-directed prediction for lossless compression of natural images,” IEEE Trans. Image Processing, vol. 10, pp. 813-817, 2001.
[10]M. Mahoney, Large text compression benchmark, 2009, [online] Available: http://www.mattmahoney.net/text/text.html.
[11]A. Said and W. A. Pearlman, “A new fast and efficient image codec based on set partitioning in hierarchical trees,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 243-250, June 1996.
[12]R. G. Gallager, “Variations on a theme by Huffman,” IEEE Trans. Inf. Theor. IT-24, vol. 6, pp. 668-674, Nov. 1978.
[13]J. S. Vitter, “Design and analysis of dynamic Huffman Codes,” Journal of the ACM, vol. 34, pp. 825-845, Oct. 1987.
[14]D. Marpe, 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, July 2003.
[15]J. Wang, X. Ji, S. Zhao, X. Xie, and J. Kuang, “Context-based adaptive arithmetic coding in time and frequency domain for the lossless compression of audio coding parameters at variable rate,” EURASIP Journal on Audio, Speech, and Music Processing, vol. 1, pp. 1-13, 2013.
[16]K. Sayood, Lossless Compression Handbook. New York: Academic, 2002.
[17]J. Duda, K. Tahboub, N. J. Gadgil, and E. J. Delp, “The use of asymmetric numeral systems as an accurate replacement for Huffman coding,” 31st Picture Coding Symposium, May 2015.
[18]“Old and new coding techniques for data compression, error correction and nonstandard situations,” class notes for Information Theory, Institute of Computer Science and Computational Mathematics, Jagiellonian University, April, 2016.
[19]Y. W. Huang, “New directions for image compression techniques: less buffer size, weighted adaptive arithmetic coding, and collagen image compression,” MS thesis, National Taiwan University, Taiwan, 2013.
[20]P. G. Howard and J. S. Vitter, “Practical implementations of arithmetic coding,” in Image and Text Compression, J. A. Storer, Ed. Boston, MA: Kluwer, pp. 85–112, 1992.
[21]A. Masmoudi and A. Masmoudi, “A new arithmetic coding model for a block-based lossless image compression based on exploiting inter-block correlation,” Signal Image Video Process., vol. 9, issue 5, pp. 1021–1027, 2013.
[22]A. Masmoudi, W. Puech, and A. Masmoudi, “An improved lossless image compression based arithmetic coding using mixture of non-parametric distributions,” Multimedia Tools and Applications, pp.1–15, 2014.
[23]A. Masmoudi, A. Masmoudi, and W. Puech, “A new semiparametric finite mixture model-based adaptive arithmetic coding for lossless image compression,” Circuits, Systems, and Signal Processing, pp.1-24, July 2015.
[24]M. Powell, the Canterbury Corpus, 2001, [online] Available: http://corpus.canter bury.ac.nz/descriptions/#calgary¬¬¬.
[25]http://djj.ee.ntu.edu.tw/IAAC_distributed.zip.
[26]D. P. Kingma and J. Ba, “Adam: a method for stochastic optimization,” in ICLR, 2015.
[27]T. Tijmen and G. Hinton. Coursera. Class Lecture, Topic: “Neural Networks for Machine Learning, lecture 6.5-rmsprop: divide the gradient by a running average of its recent magnitude,” April 2012.
[28]T. Dozat, “Incorporating nesterov momentum into Adam,” Tech. Rep., Stanford University, 2015, http://cs229.stanford.edu/proj2015/054_report.pdf.
[29]S. Ioffe and C. Szegedy, “Batch normalization: accelerating deep network training by reducing internal covariate shift,” in ICML, 2015.
[30]G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter, “Self-normalizing neural networks,” in arXiv preprint arXiv:1706.02515 [cs.LG], June 2017.
[31]Y. LeCun, “The MNIST database of handwritten digits,” [online] Available: http://yann.lecun.com/exdb/mnist.
[32]A. Torralba, R. Fergus and W. T. Freeman, “80 million tiny images: a large database for nonparametric object and scene recognition,” IEEE PAMI, 2008
[33]J. K. U. Linz, SNNs, GitHub repository, [online] Available: https://github.com/bioinf-jku/SNNs.
[34]P. Vincent, H. Larochelle, Y. Bengio, and P. Manzagol, “Extracting and composing robust features with denoising autoencoders,” in ICML, 2008.
[35]C. Doersch, “Tutorial on variational autoencoders,” in arXiv preprint arXiv:1606.05908 [stat.ML], June 2016.
[36]I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in NIPS, 2014.
[37]S. Reed, Z. Akata, X. Yan, L. Logeswaran, B. Schiele, and H. Lee, “Generative adversarial text to image synthesis,” in ICML, 2016.
[38]G. Toderici, S. M. O''Malley, S. J. Hwang, D. Vincent, D. Minnen, S. Baluja, M. Covell, and R. Sukthankar, “Variable rate image compression with recurrent neural networks,” in ICLR, 2016.
[39]G. Toderici, D. Vincent, N. Johnston, S. J. Hwang, D. Minnen, J.Shor, and M. Covell, “Full resolution image compression with recurrent neural networks,” in arXiv preprint:1608.05148 [cs.CV], July 2017.
[40]L. Theis, W. Shi, A. Cunningham, and F. Huszar, “Lossy image compression with compressive autoencoders,” in ICLR, 2017.
[41]O. Rippel and L. Bourdev, “Real-time adaptive image compression”, in ICML, 2017.
F.Proposed Lossy Image Compression Using Machine Learning Techniques
Proposed Lossy Image Compression Using Machine Learning Techniques
[42]J. J. Ding, H. H. Chen, G. C. Pan, and P. H. Wu, “Improved JPEG 2000 system using LS prediction and grouping context coding scheme,” in IEEE APSIPA ASC, 2012.
[43]G. B. Moody and R. G. Mark, “The impact of the MIT-BIH arrhythmia database,” IEEE Eng. Med. Biol. Mag., vol. 20, no. 3, pp. 45-50, 2001.
[44]S. M. Isa, W. Jatmiko, and A. M. Arymurthy, “3D SPIHT for multi-lead ECG compression,” Proceedings - IEEE International Conference on Robotics and Automation, pp. 488-493, 2014.
[45]M. S. Manikandan and S. Dandapat, “Wavelet-based electrocardiogram signal compression methods and their performance: a prospective review,” Biomedical Signal Processing and Control, vol. 14, pp. 73-107, 2014.
[46]K. M Buckley and H. Lee, “ECG data compression using cut and align beats approach and 2D transforms,” IEEE Trans. Biomed. Eng., vol. 46, no. 5, pp. 556–564, 1999.
[47]Y. N. Iwata and N. Suzumura, “Data compression of the ECG using neural network for digital Holter monitor,” IEEE Eng. Med. Bio1. Mag., vol. 9, no. 3, pp. 53-57, Sep. 1990.
[48]A. J. Pinho and L. B. Almeida, “Biomedical image compression based on artificial neural networks,” Proceedings - 1st European Conf. on Biomed, Nice, France, pp. 90–91, Feb. 1991.
[49]M. Figueredo, J. Nievola, S. Rogal Jr. and A. Neto, “Compression of electrocardiogram using neural networks and wavelets,” Computer and Information Science, vol. 131, pp. 27-40, 2008
[50]C. M. Fira and L. Goras, “An ECG signals compression method and its validation using NNs,” IEEE Trans. Biomed. Eng., vol. 55, no. 4, pp. 1319-1326, Apr. 2008.
[51]A. Bilgin, M. W. Marcellin, and M. I. Altbach, “Compression of electrocardiogram signals using JPEG2000,” IEEE Trans. Consum. Electron., vol. 49, no. 4, pp. 833-840, Nov. 2003.
[52]B. Huang, Y. Wang, and J. Chen, “2-D compression of ECG signals using ROI mask and conditional entropy coding,” IEEE Trans. Biomed. Eng., vol. 56, no. 4, pp. 1261-1263, Apr. 2009
[53]K. Ranjeet, A. Kumar, and R.K. Pandey, “An efficient compression system for ECG signal using QRS periods and CAB technique based on 2D DWT and Huffman Coding,” IEEE Int. Conf. CARE, pp. 1-6, 2013.
[54]Z. Lu, D. Y. Kim, and W. A. Pearlman, “Wavelet compression of ECG signals by the set partitioning in hierarchical trees algorithm,” IEEE Trans. on Biomedical Engineering, vol. 47, pp. 849-856, July 2000.
[55]S. Lee, J. Kim, and M. Lee, “A real-time ECG data compression and transmission algorithm for an e-health device,” IEEE Trans. Biomed. Eng., vol. 58, no. 9, pp. 2448–2455, 2011
[56]S. J. Lee, J. Luan, and P. H. Chou, “A new approach to compressing ECG signals with trained overcomplete dictionary,” EAI 4th Int. Conf. on Wireless Mobile Comm. and Healthcare, pp. 83-86, Nov. 2014.
[57]J. Pan and W. J. Tompkins, “A real-time QRS detection algorithm,” IEEE Transactions on Biomedical Engineering, no. 3, pp. 230–236, 1985.