Two-Stage Golomb – Context-Adaptive Binary Arithmetic Coders Coding in Lossless Image Compression

Frydrychowicz, Małgorzata; Ulacha, Grzegorz

doi:10.12913/22998624/191111

Artykuł - szczegóły

Tytuł artykułu

Two-Stage Golomb – Context-Adaptive Binary Arithmetic Coders Coding in Lossless Image Compression

Autorzy

Frydrychowicz Małgorzata , Ulacha Grzegorz

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

DOI

10.12913/22998624/191111

Warianty tytułu

Języki publikacji

Abstrakty

In this paper, a broad view of the individual stages of data modeling and encoding in the field of lossless image compression is presented. The main emphasis was placed on encoding prediction errors with the assumption of its geometric distribution. Basic and less common techniques of predictive data modeling for improving prediction efficiency by better fitting to a one-sided probability distribution are being discussed. Among them, our own mechanism Conditional Move To Front (CMTF), which can be useful for encoding images with high variation of input data, was described. Additionally, an original two-stage mechanism for efficient prediction error encoding (used in three codecs of different computational complexities: Multi-ctx 2, 7-ctx MMAE, and Blend-28), which uses adaptive Golomb code at the initial stage and passes its binary output to context-adaptive binary arithmetic coders (CABAC), is described in detail. We also introduced separate coders for prediction error bit signs and prediction coefficients (often forming large block in header data). In particular, we focused on the important role of correct contextual division, when sections with different characteristics of their nearest neighbourhood are grouped into separate classes to compress the data within each of them as efficiently as possible. From experimental studies, we conclude that the minimum mean absolute error (MMAE) method is superior to the minimum mean square error (MMSE) method in determining linear prediction models, especially for images with low noise level. Connecting mechanisms known from the literature with our ideas in the Blend-28 codec enabled us to increase compression efficiency in comparison to the modern and popular WebP codec by achieving an approximately 11% shorter bit average.

Słowa kluczowe

lossless image compression adaptive arithmetic coding linear prediction context-dependent constant component removing prediction coding

Wydawca

Lublin University of Technology
Polish Society of Ecological Engineering (PTIE), Branch of PTIE in Lublin

Czasopismo

Advances in Science and Technology. Research Journal

Rocznik

2024

Tom

Vol. 18, no 6

Strony

62--85

Opis fizyczny

Bibliogr. 65 poz., fig., tab.

Twórcy

autor

Frydrychowicz Małgorzata

malgorzata.frydrychowicz@zut.edu.pl

Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, ul. Żołnierska 49, Szczecin, 71-210, Poland

autor

Ulacha Grzegorz

Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, ul. Żołnierska 49, Szczecin, 71-210, Poland

https://orcid.org/0000-0002-5726-6251

Bibliografia

1. Scharcanski J. Lossless and Near-Lossless Compression for Mammographic Digital Images. Proceedings of International Conference on Image Processing ICIP’06, Atlanta, GA, USA, 8–11 October 2006, 2253–2256. https://doi.org/10.1109/ICIP.2006.312811.
2. Xie X., Li G., Wang Z. A near-lossless image compression algorithm suitable for hardware design in wireless endoscopy system. EURASIP Journal on Advances in Signal Processing, 2007, 1–13. https://doi.org/10.1155/2007/82160.
3. Kassim A.A., Yan P., Lee W.S., Sengupta K. Motion compensated lossy-to-lossless compression of 4-D medical images using integer wavelet transforms. IEEE Transactions on Information Technology in Biomedicine, March 2005, 9(1), 132–138. https://doi.org/10.1109/TITB.2004.838376.
4. Sanchez V., Nasiopoulos P., Abugharbieh R. Efficient 4D Motion Compensated Lossless Compression of Dynamic Volumetric Medical Image Data. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing ICASSP 2008, Las Vegas, Nevada, USA, 31 March - 4 April 2008, 549–552. https://doi.org/10.1109/ICASSP.2008.4517668.
5. Chen X., Canagarajah C.N., Vitulli R., Nunez-Yanez J.L. Lossless Compression for Space Imagery in a Dynamically Reconfigurable Architecture. in: Proceedings of International Workshop on Applied Reconfigurable Computing (ARC2008). March 2008, LNCS 4943, 336–341. https://doi.org/10.1007/978-3-540-78610-8_38.
6. Lossless Data Compression. Recommendation for Space Data System Standards, CCSDS 120.1-G-1. Green Book. 1. Washington, D.C.: CCSDS, June 2007.
7. Andriani S., Calvagno G., Erseghe T., Mian G.A., Durigon M., Rinaldo R., Knee M., Walland P., Koppetz M. Comparison of Lossy to Lossless Compression Techniques for Digital Cinema. Proceedings of International Conference on Image Processing ICIP’04, Singapore, 24–27 October 2004, 1, 513–516. https://doi.org/10.1109/ICIP.2004.1418803.
8. Sayood K. Introduction to Data Compression. Fifth Edition, Morgan Kaufmann Publ./Elsevier Inc., US, Cambrdge, 2018.
9. Weinberger M.J., Seroussi G. Sapiro G., The LOCOI lossless image compression algorithm: principles and standardization into JPEG-LS. IEEE Transactions on Image Processing, August 2000, 9(8), 1309–1324. https://doi.org/10.1109/83.855427.
10. Wu X., Memon N.D. Context-based, adaptive, lossless image coding. IEEE Trans. on Communications, May 1997, 45(7), 437–444. https://doi.org/10.1109/26.585919.
11. Codec WebP 1.3, https://storage.googleapis. com/downloads.webmproject.org/releases/webp/libwebp-1.3.0-windows-x64.zip (Accessed: 08.04.2023).
12. Meyer B., Tischer P. TMW – a new method for lossless image compression. Proceedings of International Picture Coding Symposium (PCS97), Berlin, Germany, September 1997, 533–538.
13. Meyer B., Tischer P. TMWLego - An Object Oriented Image Modelling Framework. Proceedings of Data Compression Conference 2001, Snowbird, Utah, 504. https://doi.ieeecomputersociety.org/10.1109/DCC.2001.10044.
14. Matsuda I., Ozaki N., Umezu Y., Itoh S. Lossless Coding Using Variable Blok-Size Adaptive Prediction Optimized for Each Image. Proceedings of 13th European Signal Processing Conference EUSIPCO 2005, 4–8 September 2005.
15. Ulacha G., Stasiński R. Context Based Lossless Coder Based on RLS Predictor Adaptation Scheme. Proceedings of International Conference on Image Processing ICIP 2009, Egypt, Cairo, 7–11 November 2009, 1917–1920. https://doi.org/10.1109/ICIP.2009.5413680.
16. Ulacha G., Stasiński R., Wernik C. Extended Multi WLS Method for Lossless Image Coding. Entropy 2020, 22(9), 919. https://doi.org/10.3390/e22090919.
17. Marcellin M., Gormish M., Bilgin A., Boliek M. An Overview of JPEG2000. Proceedings Data Compression Conference, Snowbird, Utah, March 2000, 523–541. https://doi.org/10.1109/DCC.2000.838192.
18. Kiely A., Klimesh M. The ICER Progressive Wavelet Image Compressor. The Interplanetary Network Progress Report 42, November 15, 2003, 155.
19. Rhee H., Jang Y.I., Kim S. Cho N.I. Lossless Image Compression by Joint Prediction of Pixel and Context Using Duplex Neural Networks. IEEE Access, 2021, 9, 86632–86645. https://doi.org/10.1109/ACCESS.2021.3088936.
20. Bai Y., Liu X., Wang K., Ji X., Wu X., Gao W. Deep Lossy Plus Residual Coding for Lossless and Nearlossless Image Compression. arXiv - CS - Computer Vision and Pattern Recognition, September 2022. https://doi.org/10.48550/arXiv.2209.04847.
21. Carpentieri B., Weinberger M.J., Seroussi G. Lossless compression of continuous-tone images. Proceedings of the IEEE, November 2000, 88(11), 1797–1809.
22. Deng G. Transform domain LMS-based adaptive prediction for lossless image coding. Signal Processing Image Communication, February 2002, 17(20), 219–229. https://doi.org/10.1016/S0923-5965(01)00019-4.
23. Hashidume Y., Morikawa Y. Lossless Image Coding Based on Minimum Mean Absolute Error Predictors. Proceedings of SICE Annual Conference 2007, Kagawa University, Japan, September 2007, 17–20, 2832–2836. https://doi.org/10.1109/SICE.2007.4421471.
24. Wang X., Wu X. On Design of Linear MinimumEntropy Predictor. Proceedings of IEEE 9th Workshop on Multimedia Signal Processing, MMSP 2007, Crete, October 2007, 1–3, 199–202. https://doi.org/10.1109/MMSP.2007.4412852
25. Ulacha G., Stasiński R. A New Fast Multi-Context Method for Lossless Image Coding. Proceedings of the 2018 International Conference on Sensors, Signal and Image, Prague, Czech Republic, 12–14 October 2018, 69–72, https://doi.org/10.1145/3290589.3290600.
26. Pinho A.J. On the impact of histogram sparseness on some lossless image compression techniques. Proceedings of International Conference on Image Processing, Thessaloniki, Greece, 2001, 3, 442–445. https://doi.org/10.1109/ICIP.2001.958146.
27. Ulacha G., Łazoryszczak M. Lossless image compression using context-dependent linear prediction based on absolute error minimization. Entropy 2024. In review.
28. Wu X., Zhai G., Yang X., Zhang W. Adaptive Sequential Prediction of Multidimensional Signals With Applications to Lossless Image Coding. IEEE Trans. on Image Processing, 2011, 20(1), 36–42. https://doi.org/10.1109/TIP.2010.2061860.
29. Liu J., Zhai G., Yang X., Chen L. Lossless Predictive Coding for Images With Bayesian Treatment. IEEE Transactions on Image Processing, December 2014, 23(12), 5519–5530. https://doi.org/10.1109/TIP.2014.2365698.
30. Ueno H., Morikawa Y. A New Distribution Modeling for Lossless Image Coding Using MMAE Predictors. Proceedings of the 6th International Conference on Information Technology and Applications, Hanoi, Vietnam, 9–12 November 2009, 249–254.
31. Deng G., Ye H. Maximum likelihood based framework for second-level adaptive prediction, IEEE Proceedings - Vision, Image and Signal Processing, June 2003, 150(3), 193–197. https://doi.org/10.1049/ip-vis:20030381.
32. Masmoudi A., Puech W., Masmoudi A. An improved lossless image compression based arithmetic coding using mixture of non-parametric distributions. Multimed Tools Appl 2015, 74, 10605–10619. https://doi.org/10.1007/s11042-014-2195-8.
33. Kau L.J. Lin Y.P. Least-Squares-Based Switching Structure for Lossless Image Coding. IEEE Transactions on Circuits and Systems I: Regular Papers, July 2007, 54(7), 1529–1541. https://doi.org/10.1109/TCSI.2007.899608.
34. Matsuda I., Ishikawa T., Kameda Y., Itoh S. A Lossless Image Coding Method Based on Probability Model Optimization. Proceedings 26th European Signal Processing Conference EUSIPCO 2018, Rome, Italy, 3–7 September 2018, 156–160. https://doi.org/10.23919/EUSIPCO.2018.8553404.
35. Meyer B., Tischer P. GLICBAWLS - Grey Level Image Compression by Adaptive Weighted Least Squares. Proceedings of Data Compression Conference 2001, Snowbird, Utah, 503. https://doi.ieeecomputersociety.org/10.1109/DCC.2001.10020.
36. Gallager R.G. Variations on a theme by Huffman. IEEE Transactions on Information Theory, November 1978, 24(6), 668–674. https://doi.org/10.1109/TIT.1978.1055959.
37. Kau L.J. Lossless image coding using adaptive predictor with automatic context modelling. 10th IEEE International Conference on Electronics, Circuits and Systems, 2003. ICECS 2003. Proceedings of the 2003, Sharjah, United Arab Emirates, 2003, 1, 116–119. https://doi.org/10.1109/ICECS.2003.1301990.
38. Matsumura S., Maezawa T., Takago D., Kato K., Takebe T. Least-square-based block adaptive prediction approach for lossless image coding. 2007 18th European Conference on Circuit Theory and Design, Seville, Spain, 27–30 August 2007, 188–191. http://doi.org/10.1109/ECCTD.2007.4529568.
39. Deng G. Context-based adaptive arithmetic coding for lossy plus lossless image compression. The IX European Signal Processing Conference, Island of Rhodes, Greece, September 1998, 2317–2320.
40. Matsuda I., Shirai N., Itoh S. Lossless Coding Using Predictors and Arithmetic Code Optimized for Each Image. Lecture Notes in Computer Science, 2003, 2849, 199–207. http://doi.org/10.1007/978-3-540-39798-4_26.
41. Deng G., Ye H. Lossless image compression using adaptive predictor combination, symbol mapping and context filtering. Proceedings of IEEE 1999 International Conference on Image Processing, Kobe, Japan, October 1999, 4, 63–67. https://doi.org/10.1109/ICIP.1999.819520.
42. Aiazzi B., Alparone L., Baronti S. Context modeling for near-lossless image coding. IEEE Signal Processing Letters, March 2002, 9(3), 77–80. https://doi.org/10.1109/97.995822.
43. Motta G., Storer J.A., Carpentieri B. Adaptive linear prediction lossless image coding. Proceedings DCC’99 Data Compression Conference (Cat. No. PR00096), Snowbird, UT, USA, 1999, 491–500. https://doi.org/10.1109/DCC.1999.755699.
44. Ye H., Deng G., Devlin J.C. Parametric Probability Models for Lossless Coding of Natural Image. Proceedings of 11th European Signal Processing Conference EUSIPCO-02, Toulouse, France, 3-6 September 2002, 2, 514–517.
45. Ye H., Deng G., Devlin J.C. A weighted least squares method for adaptive prediction in lossless image compression. Proceedings Picture Coding Symposium, Saint-Malo, France, 2003, 489–493.
46. Avcibas I., Memon N., Sankur B., Sayood K. A progressive Lossless/Near-Lossless image compression algorithm. IEEE Signal Processing Letters, 2002, 9(10), 312–314 (extended version). https://doi.org/10.1109/LSP.2002.804129.
47. Krivoulets A. A method for progressive nearlossless image compression. Proceedings of International Conference on Image Processing ICIP’03, Barcelona, Catalonia, Spain, 14–18 September 2003, 2, 185–188. https://doi.org/10.1109/ICIP.2003.1246647.
48. Bhaskaran V., Konstantinides K. Image and video compression standards – algorithms and architectures. Second Edition, Norwell, MA, USA, Kluwer Academic Publishers, 1997.
49. Salomon D. Data compression. The complete reference, Fourth Edition, New York, SpringerVerlag, 2006.
50. Sugiura R., Kamamoto Y., Harada N., Moriya T. Optimal Golomb-Rice Code Extension for Lossless Coding of Low-Entropy Exponentially Distributed Sources. IEEE Transactions on Information Theory, April 2018, 64(4), 3153–3161. https://doi.org/10.1109/tit.2018.2799629.
51. Xu M., Wu X., Franti P. Context quantization by kernel Fisher discriminant. IEEE Transactions on Image Processing, 15(1), January 2006, 169–177. https://doi.org/10.1109/TIP.2005.860357.
52. Dataset of 45 Images. 2022. Available online: https://kakit.zut.edu.pl/fileadmin/Test_Images.zip (Accessed: 03.05.2024).
53. Ulacha G., Wernik C. A High Efficiency Multistage Coder for Lossless Audio Compression using OLS+ and CDCCR Method. Journal: Applied Sciences-Basel 2019, 9(23), 1–22, 5218. https://doi.org/10.3390/app9235218.
54. Ulacha G., Stasinski R. High performance predictor blending lossless image coder. 2023 Data Compression Conference (DCC), Snowbird, UT, USA, 21–24 March 2023, 366–366. https://doi.org/10.1109/DCC55655.2023.00066.
55. Hsieh F.Y., Wang C.M., Lee C.C., Fan K.C. A Lossless Image Coder Integrating Predictors and Block-Adaptive Prediction. Journal of Information Science and Engineering. September 2008, 24(5), 1579–1591.
56. Dai W., Xiong H. Gaussian Process Regression Based Prediction for Lossless Image Coding. Proceedings of Data Compression Conference, Snowbird, Utah, USA, March 2014, 93–102. https://doi.org/10.1109/DCC.2014.72.
57. Dai W., Xiong H., Wang J., Zheng Y.F., Large Discriminative Structured Set Prediction Modeling With Max-Margin Markov Network for Lossless Image Coding. IEEE Transactions on Image Processing. February 2014, 23(2), 541–554. https://doi.org/10.1109/tip.2013.2293429.
58. Weinlich A., Amon P., Hutter A., Kaup A. Probability Distribution Estimation for Autoregressive Pixel-Predictive Image Coding. IEEE Transactions on Image Processing, March 2016, 25(3), 1382–1395. https://doi.org/10.1109/TIP.2016.2522339.
59. Unno K., Kameda Y., Matsuda I., Itoh S., Naito S. Lossless Image Coding Exploiting Local and Non-local Information via Probability Model Optimization. 27th European Signal Processing Conference (EUSIPCO), A Coruna, Spain, 2–6 September 2019, 1–5. https://doi.org/10.23919/EUSIPCO.2019.8903128.
60. Kojima H., Kita Y., Matsuda I., Itoh S., Kameda Y., Unno K., Kawamura K. Improved Probability Modeling for Lossless Image Coding Using Example Search and Adaptive Prediction, Proceedings of SPIE 12177, International Workshop on Advanced Imaging Technology (IWAIT 2022), April 2022. http://doi.org/10.1117/12.2625972.
61. Kaji K., Kita Y., Matsuda I., Itoh S. Kameda Y. Enhancement of CNN-based Probability Modeling by Locally Trained Adaptive Prediction for Efficient Lossless Image Coding. 2022 Picture Coding Symposium (PCS), San Jose, CA, USA, 2022, 79–83. https://doi.org/10.1109/PCS56426.2022.10018003.
62. Salimans T., Karpathy A., Chen X., Kingma D.P. PixelCNN++: Improving the PixelCNN with Discretized Logistic Mixture Likelihood and Other Modifications. 5th International Conference on Learning Representations (ICLR 2017), April 2017. https://doi.org/10.48550/arXiv.1701.05517.
63. Kojima H., Kameda Y., Kita Y., Matsuda I., Itoh S. Probability model adjustment for the CNN-based lossless image coding method. Proceedings of SPIE 11766, International Workshop on Advanced Imaging Technology (IWAIT 2021), March 2021, 1176605, 13 https://doi.org/10.1117/12.2590982.
64. Kau L.J., Lin Y.P., Lin C.T. Lossless image coding using adaptive, switching algorithm with automatic fuzzy context modelling. IEE Proceeding Vision, Image and Signal Processing, October 2006, 153(5), 684–694. https://doi.org/10.1049/ip-vis:20045256.
65. Kau L.J., Lin Y.P. Least squares-adapted edge-look-ahead prediction with run-length encodings for lossless compression of images. Proceedings of International Conference on Acoustics. Speech and Signal Processing ICASSP 2008. Las Vegas. Nevada. U.S.A. 31 March – 4 April 2008, 1185–1188. https://doi.org/10.1109/ICASSP.2008.4517827.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-8789e21f-2dcc-44d8-bf01-a4718b1c171a