Data compression algorithms tend to reduce information entropy, which is crucial, especially in the case of images, as they are data intensive. In this regard, lossless image data compression is especially challenging. Many popular lossless compression methods incorporate predictions and various types of pixel transformations, in order to reduce the information entropy of an image. In this paper, a block optimisation programming framework Φ is introduced to support various experiments on raster images, divided into blocks of pixels. Eleven methods were implemented within Φ , including prediction methods, string transformation methods, and inverse distance weighting, as a representative of interpolation methods. Thirty-two different greyscale raster images with varying resolutions and contents were used in the experiments. It was shown that Φ reduces information entropy better than the popular JPEG LS and CALIC predictors. The additional information associated with each block in Φ is then evaluated. It was confirmed that, despite this additional cost, the estimated size in bytes is smaller in comparison to the sizes achieved by the JPEG LS and CALIC predictors.

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

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

Zobrazit více v PubMed

Shannon, C. E. A mathematical theory of communication. AT &T Tech J.27(3), 379–423 (1948).

Fano R. M. The Transmission of Information. Technical Report No. 65, Cambridge, MA, USA (1949).

Huffman, D. A. A method for the construction of minimum-redundancy codes. Proc. IRE40(9), 1098–1101 (1952).

Salomon, D. & Motta, G. Handbook of Data Compression 5th edn. (Springer, 2010).

Sayood, K. Introduction to Data Compression 4th edn. (Morgan Kaufman, 2012).

Lelewer, D. A. & Hirschberg, D. S. Data compression. ACM Comput. Surv.19(3), 261–296 (1987).

Jayasankar, U., Thirumal, V. & Ponnurangam, D. A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications. J. King Saud. Univ.-Com.33, 119–140 (2021).

Chiarot, G. & Silvestri, C. Time series compression survey. ACM Comput. Surv.55(10), 1–32 (2023).

Cover, T. M. & Thomas, J. A. Elements of Information Theory 2nd edn. (Wiley, 2006).

Rao, K. R. & Yip, P. Discrete Cosine Transform (Academic Press, 1990).

Taubman, D. & Marcellin, M. W. JPEG2000: Image Compression Fundamentals Standards and Practice (Kluwer, 2002).

Furht, B. A survey of multimedia compression techniques and standards. Part I: JPEG Stand. Real-Time Imaging1(1), 49–67 (1995).

Wu, X. & Memon, N. Context-based, adaptive, lossless image coding. IEEE Trans. Commun.45(4), 437–444 (1997).

Weinberger, M. J., Seroussi, G. & Sapiro, G. The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS. IEEE T Image Process.9(8), 1309–1324 (2000). PubMed

Ulacha, G., Stasiński, R. & Wernik, C. Extended multi WLS method for lossless image coding. Entropy22(9), 919 (2020). PubMed PMC

Ulacha, G. & Łazoryszczak, M. Lossless image coding using non-MMSE algorithms to calculate linear prediction coefficients. Entropy25(1), 156 (2023). PubMed PMC

Portable network graphics (PNG) specification, 2nd Edn. https://www.w3.org/TR/2003/REC-PNG-20031110/. Accessed 5 July 2024.

Paeth, A. W. Image file compression made easy. In Graphics Gems 2 (ed. James, A.) 93–100 (Academic Press, 1991).

Starosolski, R. Simple fast and adaptive lossless image compression algorithm. Softw. Pract Exp.37, 65–91 (2007).

Alakuijala, J. Specification for WebP Lossless Bitstream. https://developers.google.com/speed/webp/docs/webp_lossless_bitstream_specification. Accessed 31 May 2024.

Žalik, B. et al. A new transformation technique for reducing information entropy: A case study on greyscale raster images. Entropy25(12), 1591 (2023). PubMed PMC

Ryabko, B. Y. Data compression by means of a book stack. Probl. Inf. Transm.16(4), 265–269 (1980).

Bentley, J. L., Sleator, D. D., Tarjan, R. E. & Wei, V. K. A locally adaptive data compression scheme. Commun. ACM29(4), 320–330 (1986).

Arnavut, Z., Magliveras, S. S. Block sorting and compression. in Proceedings of the IEEE Data Compression Conference, DCC’97, Snowbird, Utah, USA, pp. 25–27 (1997)

Burrows, M., Wheeler D. J. A Block-Sorting Lossless Data Compression Algorithm. Technical report No. 124, Digital Systems Research Center (1994).

Deorowicz, S. Improvements to Burrows–Wheeler compression algorithm. Softw. Pract. Exper.30(13), 1465–1483 (2000).

Albers, S. Improved randomized on-line algorithms for the list update problem. SIAM J. Comput.27(3), 682–693 (1998).

Žalik, B. et al. FLoCIC: A few lines of code for raster image compression. Entropy25(3), 533 (2023). PubMed PMC

Arun, P. V. A comparative analysis of different DEM interpolation methods. Egypt J. Remote Sens Space Sci.16(2), 133–139 (2013).

Li, J. & Heap, A. D. A. Review of Spatial Interpolation Methods for Environmental Scientists (Geoscience Australia) (2008).

Mortenson, M. E. Geometric Modeling (Wiley, 1985).

Smolik, M. & Skala, V. Large scattered data interpolation with radial basis functions and space subdivision. Integr. Comput. Aided Eng.25(1), 49–62 (2018).

Keller, W. & Borkowski, A. Thin plate spline interpolation. J. Geod.93, 1251–1269 (2019).

Skala, V. & Mourycova, E. Meshfree interpolation of multidimensional time-varying scattered data. Computers12(12), 243 (2023).

Shepard, D. A two-dimensional interpolation function for irregular-spaced data. in Proceedings of the 1968 ACM National Conference, ACM’68, New York, USA 27–29 (1968)

[Image: see text] prototype implementation. https://gemma.feri.um.si/blockbased.zip. Accessed 05 July 2024.

Test images. https://gemma.feri.um.si/BlockTest_Images.zip. Accessed 05 July 2024.

Jeromel, A. & Žalik, B. An efficient lossy cartoon image compression method. Multimed. Tools Appl.79, 433–451 (2020).

Cressie, N. & Wikle, C. Statistics for Spatio-temporal Data (Wiley, 2011).

Cressie, N. & Moores, M. T. Spatial statistics. in Encyclopedia of Mathematical Geosciences. Encyclopedia of Earth Sciences Series (eds Daya Sagar, B. S. et al.) (Springer, 2023).

Sun, J., Zhao, Y., Wang, S. & Wei, J. Image compression based on Gaussian mixture model constrained using Markov random field. Signal Process.183, 107990 (2021).