A case study on entropy-aware block-based linear transforms for lossless image compression Authors: Borut Žalik, David Podgorelec, Ivana Kolingerová, Damjan Strnad, Štefan Kohek Published: 2024 ABSTRACT AbstractData 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.Keywords: Computer science, Information entropy, Prediction, Inverse distance transform, String transformationsSubject terms: Computer science, Software Introduction Storing knowledge and data for future generations is among the most important responsibilities of society. This task has been made easier by today’s advancements in information and communication technologies. However, the amount of data is increasing rapidly due to massive digitalisation and omnipresent sensors. Because the technological advance cannot keep pace with the explosion of modern data generating devices, it remains crucial to store such vast amounts of data in the most efficient way possible, which is why data compression is employed frequently. Data compression is one of the pioneering disciplines in Computer Science, starting with the works of Shannon1, Fano2 and Huffman3. Initially, it was motivated by the limited computer memory, both on-board and in peripheral storage devices. Today, however, the compression is indispensable for data archiving and various computer-supported applications in telecommunications, geographic information systems, environment observation, medicine, wireless sensor networks, engineering, entertainment and other fields. In general, data compression methods can be divided roughly according to two criteria: they can be domain-dependent or independent, and they may be lossless or lossy. Numerous approaches from all categories have been collected in various books4,5 and surveys6–8. Compression of data is achieved by removing redundancies from the input data, which are, typically, considered as raw data. The redundancy in data is related strongly to entropy when the compression is lossless. Entropy is a well-established concept in science, related to disorder, randomness and uncertainty9. The concept of entropy in Computer Science was introduced by Shannon1, who named it information entropy. Let X be the sequence of elements from the input (or raw) data, i.e., X=⟨xi⟩, 0≤i<|X|, where |X| denotes the length of the sequence. X consists of elements from the alphabet Σ={xj}, 0≤j<|Σ|. Each element xj∈Σ can be assigned a probability pj of its appearance in X. The information entropy H(X) is then obtained by Eq. 1. H(X) determines the minimal number of bits required to encode each element xj∈Σ. When applying these codes on the symbols from X, the output sequence Y is obtained, and its length can be calculated by Eq. 2. |Y| can be achieved asymptotically by the classical entropy encoders, such as Huffman or arithmetic coding4. The concept is general, regardless of the type of data being compressed. In contrast to text, some other data, such as images or sounds, may be compressed as either lossy or lossless. Lossy compression typically involves the transformations Tf:xi↦fi, which map the input elements xi∈Σ to the coefficients fi∈R in the frequency space. That enables an elimination of high frequency coefficients, to introduce losses that are difficult for users to notice. Discrete cosine/sine transform10 or various types of wavelet transforms11 are typical examples of Tf. The remaining coefficients fi are then encoded losslessly. On the other hand, the lossless compression, which is the focus of this paper, often applies the concept of predictions. The predictions are also transformations; however, this time they transform the elements xi∈Σ to the domain of integer numbers, i.e., T:xi↦yi, xi∈Σ, yi∈N. The predicted values x^i are subtracted from the actual xi to get the sequence of errors E=⟨ei⟩. If the predictions are adequate, E tends to have many small integer values. In this way, the statistical properties of E differ from those of X, resulting, hopefully, in a smaller information entropy, i.e., H(E)