1
Prediction of Pixel Component Brightness in the Process of Progressive Hierarchical Lossless Image Compression

A. SHPORTKO1 and A. BOMBA2

1Academician Stepan Demianchuk International University of Economics and Humanities, Rivne, Ukraine,

2National University of Water and Environmental Engineering, Rivne, Ukraine,

1.1. Introduction

As is well known, lossless image compression in archivers and graphic formats often occurs in a maximum of four stages (Shportko and Bomba 2025): at the first stage, context-dependent coding reduces redundancies between identical fragments (Bomba et al. 2024) or fragments with the same structure (reduces inter-fragment redundancy and can be used before the fourth stage); at the second stage, a transition to an alternative color model is performed (Shportko et al. 2023); at the third stage, the brightnesses of pixel components are converted using predictors (Shportko and Postolatii 2021); at the fourth stage, context-independent coding generates codes of elements with lengths depending on their probabilities (works out code redundancy; Shportko et al. 2022). The second and third stages do not compress the image, but increase the unevenness of the brightness distribution and therefore increase the efficiency of the fourth stage, i.e. increase the coded redundancy by reducing the inter-element redundancy. According to Shannon's formula (Shannon 1948), after applying any context-independent algorithm at the fourth stage, the average code length of an element cannot be less than the source entropy

[1.1]

where pi is the luminance of element i. Context-independent coding can even be used instead of context-dependent codes for individual pixel brightnesses if it further reduces the compression ratio (the ratio of the sizes of compressed to uncompressed image files, expressed in bpb, hereafter referred to as the CR; Shportko et al. 2022). In this chapter, we propose predictors (the third stage of compression) for progressive hierarchical lossless image compression and investigate their effectiveness.

We tested all of the algorithms and their modifications proposed in this chapter on the standard Archive Comparison Test (ACT - Test Files 2002, hereinafter ACT) test set, the characteristics of which are given in Table 1.1. This set, unlike other alternative test sets of images, contains both synthesized (No. 1 (with noise), 2, 7) and photorealistic (all other) images. The testing was performed on a computer with an Intel Pentium 4 processor with a clock speed of 3 GHz and 4 Gb RAM.

Table 1.1. Characteristics of ACT set images

File number File name Size, KB Features 1 Clegg.bmp 2101 Continuous-tone, artificial, with noise, several large objects 2 Frymire.bmp 3622 Discrete-tonal, artificial, one large object 3 Lena.bmp 769 Continuous-tone, natural, multiple large objects 4 Monarch.bmp 1153 Continuous-tone, natural, one large and many small objects 5 Peppers.bmp 769 Continuous-tone, natural, multiple large objects 6 Sail.bmp 1153 Continuous-tone, natural, many medium objects 7 Serrano.bmp 1464 Discrete-tonal, artificial, one large fragmented object 8 Tulips.bmp 1153 Continuous tone, natural, multiple large objects Together: 12184

1.2. Problem statement

To increase the efficiency of context-independent coding in the process of lossless image compression, an attempt was made to use predictors (Shportko and Postolatii 2021), which predict the brightness value of each component of the next pixel during the traversal, using the brightness values of the same components of previously processed adjacent pixels, since these brightness data have the highest degree of correlation. In the RGB color model with 8-bit sampling, the color components of each pixel are processed as three separate components. Therefore, for the most common 24-bit images, the components are the luminance of the red, green and blue components of a pixel's color, stored as integers in separate bytes.

In the process of using this approach, the deviation ?ji of the brightness value of the next pixel component brightnessji from the value predicted by the selected predictor predictji is calculated and subsequently encoded, i.e.:

[1.2]

(j and i run along all rows and columns of image pixel components, respectively). The closest processed image pixels often have similar colors, and therefore similar brightness values of the corresponding components, so the prediction value often coincides with the brightness value of the next component, is most often close to this value, and rarely differs significantly from it (see Figure 1.1(b)). That is, most ?ji values are close to zero. Thus, the use of predictors often increases the unevenness of the probability distribution of luminance values and, as a result, reduces entropy [1.1]. For example, for the Lena.bmp image (most often used by researchers to analyze the effectiveness of compression algorithms), as a result of applying combinations of hierarchical predictors, which will be described in section 1.4, the maximum probability of a single value increased from 0.009 (for value 92) to 0.099 (for value 0) and the probabilities of elements close to 0 became close to this maximum value (see Figure 1.1(b)). This increase in the unevenness of the distribution of element probabilities is the reason why the average entropy decreased from 7.59 bpb to 5.34 bpb. According to our estimates, the application of the context-independent algorithm after using the predictors reduces the CR of images by 33% on average.

Why do the brightness values of pixel components deviate from the values predicted by the predictors? The fact is that these deviations are most often caused by two objectively existing main factors: "strong" changes - the trend - and "weak" background fluctuations - noise. As we emphasized in Shportko and Postolatii (2021):

Therefore, two opposite types of models are possible: the contribution of noise is insignificant compared to the contribution of evolution; the contribution of evolution is insignificant compared to the contribution of noise. In the first case [...] we will predict the value of [...] based on the [...] trend, in the second - as equal to the arithmetic mean [...] of the previous elements.

In a traditional pixel-by-pixel traversal, predictors can only use the luminance values from the previous rows and the left of the next row to predict the next row (see Figure 1.2), which reduces their effectiveness.

Figure 1.1. A division of frequencies of values of green components of image Lena.bmp: a) before using the predictor (H=7.59 of bpb); b) after using the left-predictor (H=5.34 of bpb)

Figure 1.2. Marking of adjacent elements to element X in the sequential pixel traversal method

In this way of pixel traversal, using the adjacent element notation for element X in accordance with Figure 1.2, the most commonly used (Memon and Wu 1997) sequential traversal predictors in C++ are written as follows:

The LeftPredict predictor predicts the value of the next element to be equal to the value on the left, the AbovePredict predictor predicts the value on the top and the AveragePredict predictor predicts the arithmetic mean of these values. These three predictors are linear static predictors, which essentially calculate the arithmetic mean of individual adjacent elements and therefore describe a noise model. The next two predictors are nonlinear static predictors, taking into account trends relative to the value predicted under the assumption of equal background fluctuations of the diagonal elements, and therefore describe a mixed trend-noise model.

PaethPredict calculates the value at point X based on the plane passing through the points Left, Above and LeftAbove in a three-dimensional space and predicts one of these three values in the direction of the smallest increase relative to the calculated value.

MedPredict tries to adapt to local horizontal and vertical edges. The value Left is most often returned when a horizontal edge is detected, and Above is returned when a vertical edge is detected. If an edge is not detected, the value of the plane over the point X passing through the points Left, Above and LeftAbove in three dimensions is returned. The first four of these predictors are used, for example, in the PNG format (Miano 1999), the fourth in the WinRAR archiver and the last in the JPEG-LS compression format (Selomon 2002).

According to our estimates, the use of a context-independent...