A new approach is proposed for lossless raster image compression employing interpolative coding. A new multifunction prediction scheme is presented first. Then, interpolative coding, which has not been applied frequently for image compression, is explained briefly. Its simplification is introduced in regard to the original approach. It is determined that the JPEG LS predictor reduces the information entropy slightly better than the multi-functional approach. Furthermore, the interpolative coding was moderately more efficient than the most frequently used arithmetic coding. Finally, our compression pipeline is compared against JPEG LS, JPEG 2000 in the lossless mode, and PNG using 24 standard grayscale benchmark images. JPEG LS turned out to be the most efficient, followed by JPEG 2000, while our approach using simplified interpolative coding was moderately better than PNG. The implementation of the proposed encoder is extremely simple and can be performed in less than 60 lines of programming code for the coder and 60 lines for the decoder, which is demonstrated in the given pseudocodes.

Department of Computer Science and Engineering University of West Bohemia Technická 8 306 14 Plzeň Czech Republic

Faculty of Electrical Engineering and Computer Science University of Maribor Koroška cesta 46 SI 2000 Maribor Slovenia

Zobrazit více v PubMed

Shannon C.E. A Mathematical Theory of Communication. AT&T Tech. J. 1948;27:379–423.

Nelson M., Gailly J.-L. The Data Compression Book. 2nd ed. M&T Books; New York, NY, USA: 1991.

Moffat A., Turpin A. Compression and Coding Algorithms. Kluwer Academic; New York, NY, USA: 2002.

Cover T.M., Thomas J.A. Elements of Information Theory. 2nd ed. Wiley; Hoboken, NJ, USA: 2006.

Salomon D., Motta G. Handbook of Data Compression. 5th ed. Springer; London, UK: 2010.

Sayood K. Introduction to Data Compression. 4th ed. Morgan Kaufman; Waltham, MA, USA: Elsevier; Waltham, MA, USA: 2012.

Richardson I.E.G. H.264 and MPEG-4 Video Compression: Video Coding for Next-Generation Multimedia. Wiley; Chichester, UK: 2003.

Rao K.R., Yip P. Discrete Cosine Transform. Academic Press; Boston, MA, USA: 1990.

Sridhar S., Kumar P.R., Ramanalah K.V. Wavelet Transform Techniques for Image Compression—An Evaluation. Int. J. Image Graph. Sig. Process. 2014;6:54–67. doi: 10.5815/ijigsp.2014.02.07. DOI

Starosolski R. Hybrid Adaptive Lossless Image Compression Based on Discrete Wavelet Transform. Entropy. 2020;22:751. doi: 10.3390/e22070751. PubMed DOI PMC

Qin Q., Liang Z., Liu S., Wang X., Zhou C. A Dual-Domain Image Encryption Algorithm Based on Hyperchaos and Dynamic Wavelet Decomposition. IEEE Access. 2022;10:122726–122744. doi: 10.1109/ACCESS.2022.3212145. DOI

Demaret L., Dyn N., Iske A. Image compression by linear splines over adaptive triangulations. Signal Process. 2020;22:1604–1616. doi: 10.1016/j.sigpro.2005.09.003. DOI

Papamarkos N., Atsalakis A.E., Strouthopoulos C.P. Adaptive color reduction. IEEE Trans. Syst. Man Cybern. 2002;32:44–56. doi: 10.1109/3477.979959. PubMed DOI

Jeromel A., Žalik B. An efficient lossy cartoon image compression method. Multimed. Tools Appl. 2020;79:433–451. doi: 10.1007/s11042-019-08126-7. DOI

Ansari R., Momon N., Ceran E. Near-lossless image compression techniques. J. Electron. Imaging. 1998;7:486–494.

Rahman M.A., Hamada M. Lossless Image Compression Techniques: A State-of-the-Art Survey. Symmetry. 2019;11:1274. doi: 10.3390/sym11101274. DOI

Weinberger M.J., Seroussi G., Sapiro G. The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS. IEEE T Image Process. 2000;9:1309–1324. doi: 10.1109/83.855427. PubMed DOI

Xiaolin W., Memon N. Context-based lossless interband compression-extending CALIC. IEEE Trans. Image Process. 2000;9:994–1001. doi: 10.1109/83.846242. PubMed DOI

Žalik B., Mongus D., Lukač N. Can burrows-Wheeler transform be replaced in chain code compression? Inf. Sci. 2020;525:109–118. doi: 10.1016/j.ins.2020.03.073. DOI

Overview of JPEG LS. [(accessed on 23 January 2023)]. Available online: https://jpeg.org/jpegls/index.html.

Golomb S.W. Run–length encodings. IEEE Trans. Inform. Theory. 1966;12:399–401. doi: 10.1109/TIT.1966.1053907. DOI

Welch T. A Technique for High-Performance Data Compression. Computer. 1984;17:8–19. doi: 10.1109/MC.1984.1659158. DOI

PortableNetwork Graphics. [(accessed on 23 January 2023)]. Available online: http://www.libpng.org/pub/png/

Paeth A.W. In: Image File Compression Made Easy. James A., editor. Academic Press; San Diego, CA, USA: 1991. pp. 93–100. Graphics Gems, 2.

Ziv J., Lempel A. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory. 1977;23:337–343. doi: 10.1109/TIT.1977.1055714. DOI

Huffman D.A. A Method for the Construction of Minimum-Redundancy Codes. Proc. IRE. 1952;40:1098–1101. doi: 10.1109/JRPROC.1952.273898. DOI

Taubman D., Marcellin M.W. JPEG2000: Image Compression Fundamentals Standards and Practice. Kluwer; Boston, MA, USA: 2002.

Le Gall D., Tabatabai A.J. Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques; Proceedings of the ICASSP-88: International Conference on Acoustics, Speech, and Signal Processing; New York, NY, USA. 11–14 April 1988; Piscataway, NJ, USA: IEEE Press; 1988. pp. 761–764.

Ko H.-H. Enhanced Binary MQ Arithmetic Coder with Look-Up Table. Information. 2021;12:143. doi: 10.3390/info12040143. DOI

Ulacha G., Łazoryszczak M. Lossless Image Coding Using Non-MMSE Algorithms to Calculate Linear Prediction Coefficients. Entropy. 2023;25:156. doi: 10.3390/e25010156. PubMed DOI PMC

Moffat A., Stuiver L. Binary interpolative coding for effective index compression. Inf. Retr. 2000;3:25–47. doi: 10.1023/A:1013002601898. DOI

Žalik B., Mongus D., Lukač N., Rizman Žalik K. Efficient chain code compression with interpolative coding. Inf. Sci. 2018;439:39–49. doi: 10.1016/j.ins.2018.01.045. DOI

Žalik B., Rizman Žalik K., Zupančič E., Lukač N., Žalik M., Mongus D. Chain code compression with modified interpolative coding. Comput. Electr. Eng. 2019;77:27–36. doi: 10.1016/j.compeleceng.2019.05.001. DOI

Howard P.G., Vitter J. Fast and efficient lossless image compression; Proceedings of the DC’93: Data Compression Conference; Snowbird, UT, USA. 30 March–2 April 1993; New York, NY, USA: IEEE Computer Society; 1993. pp. 208–215.

Niemi A., Teuhola J. Interpolative coding as an alternative to arithmetic coding in bi-level image compression; Proceedings of the SCC 2015—10th International ITG Conference on Systems, Communications and Coding; Hamburg, Germany. 2–5 May 2015; New York, NY, USA: IEEE; 2015. pp. 1–6.

Strnad D., Kohek Š., Nerat A., Žalik B. Efficient representation of geometric tree models with level-of-detail using compressed 3D chain code. IEEE Trans. Vis. Comput. Graph. 2020;26:3177–3188. doi: 10.1109/TVCG.2019.2924430. PubMed DOI

FLoCIC. [(accessed on 14 March 2023)]. Available online: https://github.com/mitzal/FLoCIC.

IrfanView. [(accessed on 23 January 2023)]. Available online: https://www.irfanview.com/

ImageMagick. [(accessed on 23 January 2023)]. Available online: https://imagemagick.org/

Bodden E., Clasen M., Kneis J. Arithmetic Coding Revealed. McGill University; Montreal, QC, Canada: 2007. Sable Technical Report No. 2007-5.

Marpe D., Scwarz H., Wiegand T. Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard. IEEE Trans. Circuits Syst. Video Technol. 2003;13:620–636. doi: 10.1109/TCSVT.2003.815173. DOI

Overview of JPEG XL. [(accessed on 23 January 2023)]. Available online: https://jpeg.org/jpegxl/

An Image Format for Web. [(accessed on 23 January 2023)]. Available online: https://developers.google.com/speed/webp/

Globačnik T., Žalik B. An efficient raster font compression for embedded systems. Pattern Recogn. 2010;43:4137–4147. doi: 10.1016/j.patcog.2010.07.018. DOI

Špelič D., Novak F., Žalik B. Educational support for computational geometry course—The Delaunay triangulation tester. Int. J. Eng. Educ. 2009;25:93–101.

Krivograd S., Žalik B., Novak F. TriMeDeC tool for preparing visual teaching materials based on triangular networks. Comput. Appl. Eng. Educ. 2002;10:144–154. doi: 10.1002/cae.10031. DOI

State-of-the-Art Trends in Data Compression: COMPROMISE Case Study

A case study on entropy-aware block-based linear transforms for lossless image compression

A New Transformation Technique for Reducing Information Entropy: A Case Study on Greyscale Raster Images