Peculiarities of Adaptation of the LZ77 Dictionary Algorithm to Lossless Image Compression
DOI:
https://doi.org/10.47839/ijc.24.1.3883Keywords:
lossless image compression, dictionary compression methods, LZ77 algorithm schedulesAbstract
The article describes three modifications of the LZ77 dictionary algorithm for lossless image compression in the process of sequential bypass pixels: storing offsets to identical sequences in pixels, not in individual components; performing a search for identical sequences first, starting from adjacent previously processed pixels; performing a search for identical sequences not only in the horizontal but also in the vertical direction. The first of these modifications is shown to improve compression by using smaller values for storing offsets and increasing the dictionary of the LZ77 algorithm threefold. The second modification forms small offsets to adjacent pixels of the previous row. And the third one finds longer identical sequences. Storing offsets in pixels and separately searching for identical sequences from adjacent processed pixels is recommended to use in graphic formats, as they improve compression with almost no impact on encoding and decoding time. The search for identical sequences in two directions is suggested to be used only in archivers, because the implementation of this modification slows down both encoding and decoding, improving the compression of only individual images. On the well-known ACT test set, it is shown that the application of the proposed modifications together with the simultaneous search of the same sequences in three dictionaries makes it possible to reduce image compression coefficients by an average of 0.18 bpb.
References
G. Wallace, “The JPEG still picture compression standard,” Communication of ACM, vol. 34, pp. 30-44. 1991. https://doi.org/10.1145/103085.103089.
J. Miano, Compressed Image File Format: JPEG, PNG, GIF, XBM, BMP, Addison Wesley, New York, 1999, 264 p. ISBN 0201604434.
L. D. Crocker, “PNG: The portable network graphic format,” Dr. Dobb's Journal. vol. 20, no. 232, pp. 36–44, 1995.
A. V. Shportko, A. Ya. Bomba and V. A. Postolatii, “Programming the formation of difference color models for lossless image compression,” Proceedings of the 7th International Conference Computational Linguistics and Intelligent Systems (COLINS 2023), Kharkiv, Ukraine, Apr. 20-21, 2023, vol. 3, pp. 53-68. Available at: http://ceur-ws.org/Vol-3403/paper5.pdf.
X. Li, M. T. Orchard, “Edge-directed prediction for lossless compression of natural images,” IEEE Transaction on Image Processing, vol. 10, issue 6, pp. 813-817, 2001. https://doi.org/10.1109/83.923277.
N. A. N. Azman, A. Samura, R. A. Rashid, F. A. Saparudin, M. A. Sarijari, “A hybrid predictive technique for lossless image compression,” Bulletin of Electrical Engineering and Informatics, vol. 8, no. 4, pp. 1289-1296, 2019. https://doi.org/10.11591/eei.v8i4.1612.
M. U. A. Ayoobkhan, E. Chikkannan, K. Ramakrishnan, S. B. Balasubramanian, “Prediction-based lossless image compression,” Proceedings of the International Conference on ISMAC in Computational Vision and Bio-Engineering 2018 (ISMAC-CVB), Springer, Cham, Jan. 02, 2019, vol. 30, pp. 1749–1761. https://doi.org/10.1007/978-3-030-00665-5_161.
D. Huffman, “A method for the construction of minimum redundancy codes,” Proceedings of the IRE, vol. 40, issue 9, pp. 1098-1101, 1952. https://doi.org/10.1109/JRPROC.1952.273898.
A. Moffat, “Huffman coding,” ACM Computing Surveys (CSUR), vol. 52, pp. 1-35, 2019. https://doi.org/10.1145/3342555.
J. Duda, K. Tahboub, N. J. Gadil and E. J. Delp, “The use of asymmetric numeral systems as an accurate replacement for Huffman coding,” Picture Coding Symposium, Cairns, QLD, Australia, Jul. 30, 2015. https://doi.org/10.1109/PCS.2015.7170048.
A. Gribov, “Optimal Compression of a Polyline with Segments and Arcs,” 2017, 40 p. Available at: https://arxiv.org/pdf/1604.07476.pdf.
J. Rissanen, “Generalized Kraft inequality and arithmetic coding,” IBM Journal of Research and Development, vol. 20, issue 3, pp. 198–203, 1976. https://doi.org/10.1147/rd.203.0198.
J. Rissanen, G. G. Langdon, “Arithmetic coding,” IBM Journal of Research and Development, vol. 23, vol. 2, pp. 149–162, 1979. https://doi.org/10.1147/rd.232.0149.
A. Moffat, R. M. Neal and I. H. Witten, “Arithmetic coding revisited,” ACM Transactions on Information Systems, vol. 16, vol. 3, pp. 256-294, 1998. https://doi.org/10.1145/290159.290162.
I. H. Witten, R. M. Neal and J. G. Cleary, “Arithmetic Coding for Data Compression,” Communications of the ACM, vol. 30, issue 6, pp. 520–540, 1987. https://doi.org/10.1145/214762.214771.
C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, no. 4, pp. 623-656, 1948. https://doi.org/10.1002/j.1538-7305.1948.tb00917.x.
Kh. B. Predko, M. V. Shovheniuk, “Canonical presentation of colour spaces for publishing systems,” Scientific Papers Ukrainian Academy of Printing, vol. 2(16), 2009, pp. 60–73. Available at: http://nz.uad.lviv.ua/static/media/2-16/11.pdf.
P. Deutsch, DEFLATE Compressed Data Format Specification, version 1.3, RFC 1951. Available at: https://www.rfc-editor.org/rfc/rfc1951.
J. Ziv, A. Lempel, “A universal algorithm for sequential data compression,” IEEE Transactions on Information Theory, vol. 23, issue 3, pp. 337-343, 1977. https://doi.org/10.1109/TIT.1977.1055714.
S. Kreft, G. Navarro, “LZ77-like compression with fast random access,” Proceedings of the 2010 IEEE Data Compression Conference. Snowbird, UT, USA, Mar. 24-26, 2010, pp. 239-248. https://doi.org/10.1109/DCC.2010.29.
H. Nagumo, M. Lu, K. Watson, “Image compression with modified LZ77 coding,” Proceedings of the IEEE Third International Conference on Signal Processing (ICSP), Beijing, China, Oct. 14-18, 1996, pp. 1067-1070. https://doi.org/10.1109/ICSIGP.1996.566277.
M. Komar, A. Sachenko, V. Golovko and V. Dorosh, “Compression of network traffic parameters for detecting cyber attacks based on deep learning,” Proceedings of the IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, May 24-27, 2018, pp. 43-47. https://doi.org/10.1109/DESSERT.2018.8409096.
P. Deutsch, J-L. Gailly, ZLIB Compressed Data Format Specification, version 3.3, RFC 1950, Network Working Group, 1996, 10 p. https://doi.org/10.17487/rfc1950.
A. V. Shportko, Rise of efficiency of compression of colored images in the PNG format. Thesis for a candidate’s degree in technical sciences, Rivne State University of the Humanities, Rivne, 2010, 195 p. Available at: https://dspace.megu.edu.ua:8443/jspui/handle/123456789/1665.
A. V. Shportko, “Optimization of the use of static predictors in the process of lossless image compression,” Information extraction and processing, vol. 28, 2008, pp. 82-89.
W. K. Pratt, “Correlation techniques of image registration,” IEEE Transactions on Aerospace and Electronic Systems, vol. AES-10, no. 3, pp. 353-358, 1974. https://doi.org/10.1109/TAES.1974.307828.
ACT – Test Files, 2002, [Online]. Available at: http://www.compression.ca/act/act-files.html.
MinPNG 1.0 – a utility to minimize the size of PNG image files (True Color), 2010, [Online]. Available at: http://apserver.org.ua/peregl.php?d=view&tid=131.
O. Shehata, “Unraveling the JPEG,” Parametric Press, vol. 1, 2019. Available at: https://parametric.press/issue-01/unraveling-the-jpeg.
A. Ya. Bomba, A. V. Shportko and V. A. Shportko, “Development of the HBF-LS graphics format for lossless progressive image compression,” Proceedings of the III scientific and technical conference Computational methods and systems of information transformation, Lviv, Ukraine, Sept. 25-26, 2014, vol. 3, pp. 98-101.
B. Rusyn, O. Lutsyk, Y. Lysak, A. Lukenyuk and L. Pohreliuk, “Lossless image compression in the remote sensing applications,” IEEE Proceedings First International Conference on Data Stream Mining & Processing (DSMP), Lviv, Ukraine, Aug. 1, 2016, pp. 195-198. https://doi.org/10.1109/DSMP.2016.7583539.
H. D. Kotha, M. Tummanapally and V. K. Upadhyay, “Review on lossless compression techniques,” Journal of Physics, vol. 1228, 2019. https://doi.org/10.1088/1742-6596/1228/1/012007.
D. R. Pavithra, Sudarshan Patil Kulkarni, “Investigation of wavelets for representation and compression of skin cancer images,” International Journal of Image, Graphics and Signal Processing (IJIGSP), vol. 15, no. 2, pp. 24-34, 2023. https://doi.org/10.5815/ijigsp.2023.02.03.
Z. Hu, O. Shkurat, K. Przystupa, O. Kochan, M. Ivakhnenko, “Low-light image enhancement technology based on image categorization, processing and retinex deep network,” International Journal of Image, Graphics and Signal Processing (IJIGSP), vol. 16, no. 5, pp. 1-13, 2024. https://doi.org/10.5815/ijigsp.2024.05.01.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
