臺灣博碩士論文加值系統

在現代人的日常生活中，我們獲取資訊的途徑可能是透過文字，亦可能是藉由圖片。不得不說，有時候圖片所傳達的訊息量甚至高過文字。不過二者對比之下，圖片所需的記憶體空間往往大上許多。因此開發一套具備高效能的影像壓縮技術有其必要性。
提到影像壓縮的方式，最知名的莫過於由聯合影像專家小組在1992年所制定的JPEG。因其架構簡單，容易實現，所以至今仍受到廣泛的使用。不過隨著我們對高解析度圖片的追求，將它們壓縮成JPEG格式可能不是最有效率的方式。在JPEG標準中，會將圖片經由離散餘弦轉換(DCT)產生相應的直流與交流係數。而於此篇論文中，我們以可適性算術編碼為根基，提出了能夠更有效處理這些係數的編碼方式。
對於直流係數，我們並不直接對其數值進行編碼，而是會先預測它的值後再記錄二者之間的殘差。此操作的目的是為了降低鄰近區域間的空間冗餘。接著，我們從直流係數中萃取適合的特徵，並將之用於建立前文模型上。隨後將所建立的前文模型配合可適性算術編碼的使用來處理直流殘差。
另一方面，針對每個8x8 DCT塊內的63個交流係數，會透過斜向掃描將它們進一步表示成遊程編碼的形式。此外，我們利用所收集的圖片來研究這63個係數的統計特性，並把觀察到的結果作為編碼交流係數的先備知識。
最後，我們提出了一種新穎的前文模型建構方式。此方式是受到k-平均演算法的啟發。一開始，我們將特徵空間切割成許多細小的子空間，並且依照資料(直流係數與交流係數)的特性，將它們分配到對應的子空間。藉由把k-平均演算法的核心技術套用在這些子空間上，前文模型將會隨著疊代的進行而逐漸成形。將此方式所產生的前文模型搭配之前所提出的編碼架構，可以將直流項與交流項整體的編碼效率再向前推進。

In the daily life of the modern world, the information may come from text or images. Compared to text, the data size of an image is quite larger. Therefore, an image compression technique with high performance is necessary.
The most famous method of image compression is JPEG, which was created by the Joint Photographic Experts Group in 1992. It is still widely used today due to that it is easy to implement. Nevertheless, for an image with very large size, the JPEG format may not be sufficient to handle it. In this thesis, more effective methods based on adaptive arithmetic coding (AAC) are proposed to encode the DC and AC coefficients of images after performing the discrete cosine transform (DCT).
For the DC coefficients, instead of encoding the values directly, a prediction is first applied to generate the residues, which helps us to reduce the spatial redundancy between the neighboring regions. Next, several features of DC coefficients are extracted to exploit the correlation among residues. Finally, the context models constructed from these features are used in conjunction with the AAC to process DC residuals.
For the AC coefficients, there are 63 elements in a single 8-by-8 DCT block and these elements are recorded by zigzag-scanning technique and the zero-run-length form. We first investigate the distribution of these 63 values based on the collected images, which will be served as the basis for coding the AC coefficients.
At last, a novel context model construction method inspired by k-means clustering is proposed. We first divide the feature space into several subspaces, and assign data to them according to the characteristics of each data. By applying the techniques in k-means-clustering to these subspaces, the context models will gradually take shape in the iterative process. These context models can further improve the coding efficiency of DC and AC terms.

口試委員審定書 #
ACKNOWLEDGMENTS (誌謝) i
MANDARIN ABSTRACT (中文摘要) ii
ABSTRACT iv
CONTENTS vi
LIST OF FIGURES xi
LIST OF TABLES xv
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Contribution of this Thesis 2
1.3 Thesis Organization 3
Chapter 2 Data Compression Overview 4
2.1 Spatial Redundancy Reduction 6
2.1.1 Difference Pulse-Code Modulation 6
2.1.2 Karhunen-Loève Transform 8
2.1.3 Discrete Cosine Transform 9
2.1.4 Walsh-Hadamard Transform 10
2.2 Temporal Redundancy Reduction 11
2.2.1 Motion Estimation 12
2.2.2 Motion Compensation 15
2.3 Perceptual Redundancy Reduction 16
2.3.1 Color Space Conversion 16
2.3.2 Quantization 18
2.4 Statistical Redundancy Reduction 19
2.4.1 Huffman Coding 20
2.4.2 Shannon-Fano Coding 21
2.4.3 Shannon-Fano-Elias Coding 22
2.4.4 Arithmetic Coding 23
2.4.5 kth Order Exponential-Golomb Coding 25
2.5 Summary 26
Chapter 3 Still Image Codec Review 27
3.1 JPEG 27
3.1.1 Color Space Conversion, 2D DCT, and Quantization 27
3.1.2 DC Term Coding 29
3.1.3 AC Term Coding 31
3.2 JPEG 2000 34
3.2.1 Preprocessing 35
3.2.2 Wavelet Transform 37
3.2.3 Block Coding 39
3.3 Summary 42
Chapter 4 Proposed DC Term Coding Algorithm 43
4.1 Problem Statement 43
4.2 Arithmetic Coding Revisited 44
4.2.1 Renormalization 44
4.2.2 Adaptability and Context Model 46
4.3 Predictor Selection 49
4.3.1 LOCO-I Prediction 49
4.3.2 Direct-Left Prediction 51
4.3.3 Edge-Directed Prediction 52
4.3.4 Performance Evaluation 56
4.4 Feature Selection 57
4.4.1 Gradient-Based Feature 58
4.4.2 Linear-Prediction-Error-Based Feature 60
4.4.3 Predictor-Based Feature 61
4.5 Context Model Construction 63
4.6 Experimental Evaluation 66
4.6.1 Coding Architecture 66
4.6.2 Simulation Results 67
4.7 Summary 70
Chapter 5 Proposed AC Term Coding Algorithm 71
5.1 Background 71
5.2 Context Model Determination 72
5.2.1 Observation 72
5.2.2 Model Index 74
5.3 Context Model Construction 78
5.3.1 Initialization of T1 for Each Context Model 78
5.3.2 Initialization of T2 for Each Context Model 79
5.4 Alternative Coding Scheme – Three-Stage Version 80
5.5 Experimental Evaluation 84
5.5.1 Coding Architecture 85
5.5.2 Simulation Results 85
5.6 Summary 90
Chapter 6 Proposed k-Means-Based Context Model Construction 91
6.1 Framework Overview 91
6.2 k-Means Clustering 93
6.3 Architecture 95
6.3.1 Feature Determination 95
6.3.2 Data Classification 99
6.3.3 Probability Initialization 102
6.3.4 k-Means-Based Context Model Generation 104
6.3.5 Additional Frequency Table for AC Coefficients 106
6.4 Experimental Evaluation 108
6.4.1 Coding Process 109
6.4.2 Discussion 110
6.5 Summary 119
Chapter 7 Conclusion and Future Work 120
7.1 Conclusion of the Thesis 120
7.2 Future Work 121
REFERENCES 122

[1]T. Zhang and S. Mao, "An Overview of Emerging Video Coding Standards," GetMobile: Mobile Computing and Communications, vol. 22, no. 4, pp. 13-20, 2019.
[2]G. K. Wallace, "The JPEG still picture compression standard," in IEEE Transactions on Consumer Electronics, vol. 38, no. 1, pp. xviii-xxxiv, Feb. 1992.
[3]“Information technology — Digital compression and coding of continuous-tone still images: Requirements and guidelines,” International Standard ISO/IEC IS-10918-1, Feb. 1994.
[4]I. M. Pu, Fundamental Data Compression, Oxford, MA, USA: Butterworth-Heinemann, 2006.
[5]K. Sayood, Introduction to Data Compression, Boston, MA, USA: Elsevier, 2006.
[6]F. Alajaji and P. -N. Chen, An Introduction to Single-User Information Theory, Springer Singapore, July 6, 2018.
[7]戴顯權 編著，“資料壓縮”，旗標，2012。
[8]酒井善則、吉田俊之 共著，白執善 編譯，“影像壓縮技術”，全華，2004。
[9]W. K. Pratt, J. Kane and H. C. Andrews, "Hadamard transform image coding," in Proceedings of the IEEE, vol. 57, no. 1, pp. 58-68, Jan. 1969.
[10]S. E. Ghrare and A. R. Khobaiz, "Digital image compression using Block Truncation Coding and Walsh Hadamard Transform hybrid technique," 2014 International Conference on Computer, Communications, and Control Technology (I4CT), pp. 477-480, 2014.
[11]M. Tang, X. Chen, J. Wen and Y. Han, "Hadamard Transform-Based Optimized HEVC Video Coding," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 29, no. 3, pp. 827-839, March 2019.
[12]T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra, "Overview of the H.264/AVC video coding standard," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560-576, July 2003.
[13]H. Kalva, "The H. 264 video coding standard," IEEE multimedia, vol. 13, no. 4, pp. 86-90, 2006.
[14]G. J. Sullivan, J. Ohm, W. Han and T. Wiegand, "Overview of the High Efficiency Video Coding (HEVC) Standard," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 12, pp. 1649-1668, Dec. 2012.
[15]B. Bross, J. Chen, J. -R. Ohm, G. J. Sullivan and Y. -K. Wang, "Developments in International Video Coding Standardization After AVC, With an Overview of Versatile Video Coding (VVC)," in Proceedings of the IEEE, pp. 1-31, Jan. 2021.
[16]J. Youn, M.-T. Sun, and C.-W. Lin, “Motion vector refinement for high-performance transcoding,” IEEE Trans. Multimedia, vol. 1, no. 1, pp. 30–40, Mar. 1999.
[17]A. Barjatya, “Block matching algorithms for motion estimation,” IEEE Transactions Evolution Computation, vol. 8, no. 3, pp. 225-239, 2004.
[18]P. G. Howard and J. S. Vitter, "Arithmetic coding for data compression," in Proceedings of the IEEE, vol. 82, no. 6, pp. 857-865, June 1994.
[19]D. Marpe, H. Schwarz and T. Wiegand, "Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 620-636, July 2003.
[20]M. W. Marcellin, M. J. Gormish, A. Bilgin and M. P. Boliek, "An overview of JPEG-2000," Proceedings DCC 2000. Data Compression Conference, 2000, pp. 523-541.
[21]A. Skodras, C. Christopoulos and T. Ebrahimi, "The JPEG 2000 still image compression standard," in IEEE Signal Processing Magazine, vol. 18, no. 5, pp. 36-58, Sept. 2001.
[22]A. Moffat, R. M. Neal, and I. H. Witten, “Arithmetic coding revisited,” ACM Transactions on Information Systems (TOIS), vol. 16, no. 3, pp. 256-294, July 1998.
[23]G. A. Triantafyllidis and M. G. Strintzis, "A context based adaptive arithmetic coding technique for lossless image compression," in IEEE Signal Processing Letters, vol. 6, no. 7, pp. 168-170, July 1999.
[24]D. Marpe, G. Blattermann, G. Heising and T. Wiegand, "Video compression using context-based adaptive arithmetic coding," Proceedings 2001 International Conference on Image Processing (Cat. No.01CH37205), 2001, pp. 558-561 vol.3.
[25]B. Aiazzi, L. Alparone and S. Baronti, "Context modeling for near-lossless image coding," in IEEE Signal Processing Letters, vol. 9, no. 3, pp. 77-80, March 2002.
[26]N. Kuroki, T. Manabe and M. Numa, "Adaptive arithmetic coding for image prediction errors," 2004 IEEE International Symposium on Circuits and Systems (IEEE Cat. No.04CH37512), 2004, pp. III-961.
[27]M. J. Weinberger, G. Seroussi and G. Sapiro, "LOCO-I: a low complexity, context-based, lossless image compression algorithm," Proceedings of Data Compression Conference - DCC '96, 1996, pp. 140-149.
[28]I. Schiopu, Y. Liu and A. Munteanu, "CNN-based Prediction for Lossless Coding of Photographic Images," 2018 Picture Coding Symposium (PCS), 2018, pp. 16-20.
[29]X. Li and M. T. Orchard, "Edge-directed prediction for lossless compression of natural images," in IEEE Transactions on Image Processing, vol. 10, no. 6, pp. 813-817, June 2001.
[30]“Stunning Free Stock Photos for Download,” https://pixabay.com/photos/, accessed: 2020-12-09.
[31]S. D. Kim and J. B. Ra, “An efficient motion vector coding scheme based on minimum bitrate prediction,” in IEEE Transactions on Image Processing, vol. 8, no. 8, pp. 1117-1120, Aug. 1999.
[32]“Public-Domain Test Images for Homeworks and Projects,” https://homepages.cae.wisc.edu/~ece533/images/, accessed: 2020-12-25.
[33]“The Miscellaneous volume,” http://sipi.usc.edu/database/database.php?volume=misc&image, accessed: 2020-12-25.
[34]J. Ding, I. Wang and H. Chen, “Improved Efficiency on Adaptive Arithmetic Coding for Data Compression Using Range-Adjusting Scheme, Increasingly Adjusting Step, and Mutual-Learning Scheme,” in IEEE Transactions on Circuits and Systems for Video Technology, vol. 28, no. 12, pp. 3412-3423, Dec. 2018.
[35]S. Ray, and R. H. Turi, “Determination of number of clusters in k-means clustering and application in colour image segmentation,” in Proceedings of the 4th international conference on advances in pattern recognition and digital techniques, pp. 137-143, Dec. 1999.
[36]N. Dhanachandra, K. Manglem, and Y. J. Chanu, “Image segmentation using K-means clustering algorithm and subtractive clustering algorithm,” Procedia Computer Science, vol. 54, pp. 764– 771, 2015.
[37]S. Zhang, H. Wang, W. Huang, and Z. You, “Plant diseased leaf segmentation and recognition by fusion of superpixel, K-means and PHOG,” Optik-Int. J. Light Electron Opt., vol. 157, pp. 866–872, Nov. 2017.
[38]L. Theis, W. Shi, A. Cunningham, and F. Huszar, “Lossy image compression with compressive autoencoders,” arXiv preprint arXiv:1703.00395, 2017.
[39]Z. Cheng, H. Sun, M. Takeuchi and J. Katto, "Deep Convolutional AutoEncoder-based Lossy Image Compression," 2018 Picture Coding Symposium (PCS), 2018, pp. 253-257.
[40]S. Ma, X. Zhang, C. Jia, Z. Zhao, S. Wang and S. Wang, "Image and Video Compression With Neural Networks: A Review," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 30, no. 6, pp. 1683-1698, June 2020.
[41]N. Krishnaraj, M. Elhoseny, M. Thenmozhi, M. M. Selim, and K. Shankar, “Deep learning model for real-time image compression in Internet of Underwater Things (IoUT),” Journal of Real-Time Image Processing, vol. 17, no. 6, pp. 2097-2111, Dec. 2020.
[42]L. F. R. Lucas, N. M. M. Rodrigues, L. A. da Silva Cruz and S. M. M. de Faria, "Lossless Compression of Medical Images Using 3-D Predictors," in IEEE Transactions on Medical Imaging, vol. 36, no. 11, pp. 2250-2260, Nov. 2017.
[43]M. U. A. Ayoobkhan, E. Chikkannan, K. Ramakrishnan, and S. B. Balasubramanian, “Prediction-based Lossless Image Compression,” in International Conference on ISMAC in Computational Vision and Bio-Engineering, Springer, Cham, vol. 30, pp. 1749-1761, May, 2018.
[44]I. Schiopu, H. Huang and A. Munteanu, "CNN-Based Intra-Prediction for Lossless HEVC," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 30, no. 7, pp. 1816-1828, July 2020.
[45]I. Schiopu and A. Munteanu, "Deep-Learning-Based Lossless Image Coding," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 30, no. 7, pp. 1829-1842, July 2020.