This paper proposes a new string transformation technique called Move with Interleaving (MwI). Four possible ways of rearranging 2D raster images into 1D sequences of values are applied, including scan-line, left-right, strip-based, and Hilbert arrangements. Experiments on 32 benchmark greyscale raster images of various resolutions demonstrated that the proposed transformation reduces information entropy to a similar extent as the combination of the Burrows-Wheeler transform followed by the Move-To-Front or the Inversion Frequencies. The proposed transformation MwI yields the best result among all the considered transformations when the Hilbert arrangement is applied.

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

See more in PubMed

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

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

Liu S., Xu M., Qin Y., Lukać N. Knowledge Graph Alignment Network with Node-Level Strong Fusion. Appl. Sci. 2022;12:9434. doi: 10.3390/app12199434. DOI

Gray R.M. Entropy and Information Theory. 2nd ed. Springer; New York, NY, USA: 2011.

Sabirov D.S., Shepelevich I.S. Information Entropy in Chemistry: An Overview. Entropy. 2021;23:1240. doi: 10.3390/e23101240. PubMed DOI PMC

Vasco-Olmo J.M., Díaz F.A., García-Collado A., Dorado-Vicente R. Experimental evaluation of crack shielding during fatigue crack growth using digital image correlation. Fatigue Fract. Eng. Mater. Struct. 2013;38:223–237. doi: 10.1111/ffe.12136. DOI

Ben-Naim A. Entropy, Shannon’s Measure of Information and Boltzmann’s H-Theorem. Entropy. 2017;19:48. doi: 10.3390/e19020048. PubMed DOI PMC

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

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

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

Ryabko B.Y. Data compression by means of a ‘book stack’. Probl. Pereda. Inform. 1980;16:265–269.

Arnavut Z., Magliveras S.S. Block sorting and compression. In: Storer J.A., Cohn M., editors. Proceedings of the IEEE Data Compression Conference, DCC’97, Snowbird, UT, USA, 25–27 March 1997. IEEE Computer Society Press; Los Alamitos, CA, USA: 1997. pp. 181–190.

Abel J. Improvements to the Burrows-Wheeler Compression Algorithm: After BWT Stages. 2003. [(accessed on 1 November 2023)]. Available online: https://api.semanticscholar.org/CorpusID:16110299.

Bentley J.L., Sleator D.D., Tarjan R.E., Wei V.K. A Locally Adaptive Data Compression Scheme. Commun. ACM. 1986;29:320–330. doi: 10.1145/5684.5688. DOI

Deorowicz S. Improvements to Burrows-Wheeler Compression Algorithm. Softw. Pract. Exper. 2000;30:1465–1483. doi: 10.1002/1097-024X(20001110)30:13<1465::AID-SPE345>3.0.CO;2-D. DOI

Binder E. Distance Coding. 2000. [(accessed on 14 November 2023)]. Available online: https://groups.google.com/g/comp.compression/c/96DHNJgf0NM/m/Ep15oLxq1CcJ.

Albers S. Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 1998;27:682–693. doi: 10.1137/S0097539794277858. DOI

Burrows M., Wheeler D.J. A Block-Sorting Lossless Data Compression Algorithm. Digital Systems Research Center; Palo Alto, CA, USA: 1994. (Technical Report No. 124).

Abel J. Post BWT stages of the Burrows-Wheeler compression Algorithm. Softw. Pract. Exper. 2010;40:751–777. doi: 10.1002/spe.982. DOI

Dorrigiv R., López-Ortiz A., Munro J.I. An Application of Self-organizing Data Structures to Compression. In: Vahrenhold J., editor. Experimental Algorithms, Proceedings of the 8th International Symposium on Experimental Algorithms, SEA 2009, Dortmund, Germany, 3–6 June 2009. Springer; Berlin, Germany: 2009. pp. 137–148. (Lecture Notes in Computer Science 5526).

Žalik B., Lukač N. Chain code lossless compression using Move-To-Front transform and adaptive Run-Length Encoding. Signal Process. Image Commun. 2014;29:96–106. doi: 10.1016/j.image.2013.09.002. DOI

Arnavut Z. Move-To-Front and Inversion Coding. In: Cohn M., Storer J.A., editors. Proceedings of the IEEE Data Compression Conference, DCC’2000, Snowbird, UT, USA, 28–30 March 2000. IEEE Computer Society Press; Los Alamitos, CA, USA: 2000. pp. 193–202.

Adjeroh D., Bell T., Mukherjee A. The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching. 2nd ed. Springer Science + Business Media; New York, NY, USA: 2008.

Lee Y.L., Han K.H., Sullivan G.J. Improved lossless intra coding for H. 264/MPEG-4 AVC. IEEE Trans. Image Process. 2006;15:2610–2615. PubMed

Khademi A., Krishnan S. Comparison of JPEG 2000 and other lossless compression schemes for digital mammograms. IEEE Trans. Image Process. 2005;25:693–695. PubMed

Barina D. Comparison of Lossless Image Formats. arXiv. 20212108.02557

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

Kohek Š., Strnad D., Žalik B., Kolmanič S. Interactive synthesis and visualization of self-organizing trees for large-scale forest succession simulation. Multimed. Syst. 2019;25:213–227. doi: 10.1007/s00530-018-0597-6. DOI

Nong G., Zhang S., Chan W.H. Two efficient algorithms for linear time suffix array construction. IEEE Trans. Comput. 2011;60:1471–1484. doi: 10.1109/TC.2010.188. DOI

Kärkkäinen J., Sanders P., Burkhardt S. Linear work suffix array construction. J. ACM. 2017;53:918–936. doi: 10.1145/1217856.1217858. DOI

Bader M. Space-Filling Curves—An Introduction with Applications in Scientific Computing. Springer; Berlin, Germany: 2013.

Chung K.-L., Huang Y.-L., Liu Y.-W. Efficient algorithms for coding Hilbert curve of arbitrary-sized image and application to window query. Inf. Sci. 2007;17:2130–2151. doi: 10.1016/j.ins.2006.12.003. DOI

Žalik B., Mongus D., Rizman Žalik K., Lukač N. Boolean Operations on Rasterized Shapes Represented by Chain Codes Using Space Filling Curves. J. Vis. Commun. Image Represent. 2017;49:420–430. doi: 10.1016/j.jvcir.2017.10.003. DOI

Lawder J.K., King P.J.H. Using state diagrams for Hilbert curve mappings. Int. J. Comput. Math. 2001;78:327–342. doi: 10.1080/00207160108805115. DOI

Žalik B., Strnad D., Kohek Š., Kolingerová I., Nerat A., Lukač N., Lipuš B., Žalik M., Podgorelec D. FLoCIC: A Few Lines of Code for Raster Image Compression. Entropy. 2023;25:533. doi: 10.3390/e25030533. PubMed DOI PMC

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