The expediency is substantiated, the way of pixel traversal is given and symmetrical and asymmetric predictors for realization of progressive hierarchical context-independent compression of images without losses are offered. The results of the application of the proposed predictors to reduce the entropy of the images of the ACT set in the process of previous transformations are presented. It is shown that the use of combinations of the proposed progressive hierarchical predictors makes it possible, for example, to reduce the compression coefficients of photorealistic images by an average of 0.08 bpp.
In today's world, images are an integral part of multimedia information, which is often created, stored and stored on digital media and transmitted through communication channels [1]. Compression of the respective files allows us to increase proportionally the speed of information exchange over the network and reduce the amount of disk space usage. All graphic formats on the principle of image compression are divided into two main classes: with losses and lossless. And if for the vast majority of image compression algorithms with losses it can be provided the desired ratio due to deterioration, the level of lossless image compression depends, in fact, only on the color differences of their pixels and the compression algorithm itself, it is not programmatically regulated and averages only 30 – 70%. Today, designers and developers of the websites often save photorealistic images in JPEG format. Discrete-tone and those where losses are unacceptable are saved in PNG format. Processing of brightness of pixels of images in popular graphic formats which carry out compression without losses (including PNG format [2, p. 249-317]), is mostly carried out consecutively on lines from top to bottom, and in each line it is carried from left to right. As a result, you can output a compressed image in these formats only after decoding all the pixels. Decompressing photos or images with millions of pixels in this way can take several seconds, regardless of the area size and resolution of the output device.
Along with this, to accelerate the output of large images in compression formats with losses, graphic formats that use progressive (translational) hierarchical processing of pixels have already been developed [3, p. 176] (for example, wavelets). In the process of applying this method of image processing, the pixels are bypassed in layers, increasing each time the resolution (progressive component). And in the process of sequential processing of the data of the next layer the data of the previous layers is used (hierarchical component). The image from pixels of the next layer is actually a reduced in several times (usually four) copy of the image from the pixels of the previous layer. So, the last layer coincides with the input image. Therefore, during the progressive hierarchical decoding, the details of the image appear gradually. It is possible to stop such decoding after decompression of the layer with the number of pixels, not less than the output area on each of the axes, without waiting for the reproduction of all pixels of the image. Thus, the development of methods and graphic format for lossless image compression using the principles of progressive hierarchical processing, which is the purpose of the study, is an urgent task today. This work, in fact, is a logical continuation of the work [4], as it improves predictors described in it and offers new predictors that provide better compression ratios.
As it is known, lossless image compression in graphic formats often occurs in three stages. During the first step brightness of the pixels are converted using predictors. During the second step contextdependent coding reduces redundancies between such fragments. During the last step contextindependent coding eliminates redundancies between the predominant values of the brightness of the components. Context-sensitive encoding can reduce the compression ratio (the ratio of the size of the compressed to uncompressed image files) several times due to such fragments. But such fragments are rare in photorealistic images, so the only universal step in lossless image compression is contextindependent encoding. The basic principle of such coding: the code length of an arbitrary element with a higher probability should not exceed the code length of any element with a lower probability. With regard to images, this principle is based on the fundamental tenet of information theory, according to which to minimize the length of the sequence code each brightness (for a separate component of each pixel of the image True Color brightness 0, 255) with probability of appearance pbrightness it is expedient to encode by log2 pbrightness bits [5, p. 17]. Therefore, the average code length of the block element after the application of any context-independent algorithm according to the formula of Shannon [5, p. 611; 6], cannot be less than the entropy of the source H
pbrightness log2 pbrightness .
brightness
(
It is known that the entropy of the source decreases with increasing non-uniformity of the distribution of probabilities (frequencies) between the elements [7]. According to our estimates, the use of a context-independent algorithm (for example, Huffman coding or arithmetic coding [2-5; 7-9]) reduces the compression ratio of images by an average of 33%.
To improve the efficiency of this encoding in the process of lossless image compression it can be
used predictors that predict the brightness of each component of the next pixel (for example, for the
most common 24-bit images – the brightness of red, green and blue components written in integers in
individual bytes), using the values of the luminance of the same components of the previously
processed adjacent pixels, because these luminance have the highest degree of correlation [7, p. 675].
In the process of using this approach, it is calculated and further encoded the deviation ij of the
brightness value of the next component of the pixel brightnessij from the predicted value of the
selected predictor predictij , namely
ij brightnessij predictij
(2)
(i and j run accordingly on all lines and columns of the components of pixels of the image). Adjacent
pixels of images often have similar colors. Thus, they have close values of the brightness of the
respective components, so the value of the forecast often coincides with the brightness of the next
component. It is often close to this value and sometimes is significantly different from it (Figure 1).
2500
2000
That is why most values ij are close to zero. Thus, the use of predictors often increases the uneven
distribution of probabilities of brightness values and, as a consequence, reduces entropy (
Why do the brightness values of the pixel components deviate from the values predicted by the predictors? The fact is that these deviations are often due to two objectively existing main factors: "strong" changes – the trend and "weak" background fluctuations – noise. Therefore, two opposite types of models are possible: the contribution of noise is insignificant compared to the contribution of evolution; the contribution of the evolution is insignificant compared to the contribution of noise. In the first case ... we will predict the value of ... based on ... the current trend in the second – as equal to the arithmetic mean ... of the previous elements " [8, p. 59].
0
In addition, during the traditional sequential pixel traversal, predictors can use only the brightness values from the previous lines and on the left in the next line for prediction (Figure 2), which reduces the efficiency of their usage.
With this method of traversing pixels, using the notation of adjacent elements for the element X in accordance with Figure 2, the most common predictors in C today can be implemented as follows: typedef unsigned char ubyte; ubyte LeftPredict(ubyte Left, ubyte Above, ubyte LeftAbove) {return Left;} ubyte AbovePredict(ubyte Left, ubyte Above, ubyte LeftAbove) {return Above;} ubyte AveragePredict(ubyte Left, ubyte Above, ubyte LeftAbove) {return (Left+Above)/2;} ubyte PaethPredict(ubyte Left, ubyte Above, ubyte LeftAbove) {int pp=Left+Above-LeftAbove; int pa, pb, pc; pa=abs(pp-Left); pb=abs(pp-Above); pc=abs(pp-LeftAbove); if (pa<=pb && pa<=pc) return Left; else if (pb<=pc) return Above;
else return LeftAbove;} ubyte MedPredict(ubyte Left, ubyte Above, ubyte LeftAbove) {if (LeftAbove>=max(Left, Above)) return min(Left, Above); else if (LeftAbove<=min(Left, Above)) return max(Left, Above);
else return Left+Above-LeftAbove; }
Predictor LeftPredict predicts the value of the next element that is equal to the value on the left. Predictor AbovePredict predicts the value that is equal to the value above. And predictor AveragePredict predicts the value that is equal to the arithmetic mean of these values. These three predictors belong to the linear static predictors and essentially calculate the arithmetic mean of individual adjacent elements and therefore describe the noise model. The next two predictors belong to nonlinear static predictors and take into account trends relatively to the value predicted in the assumption of equalities of background oscillations of diagonal elements. Therefore, they describe a mixed trend-noise model.
The Paeth predictor PaethPredict calculates the value at point X based on the plane passing through the points Left, Above and LeftAbove in three-dimensional space and predicts one of these three values in the direction of the smallest increment relatively to the calculated value.
The MedPredict predictor tries to adapt to the local horizontal and vertical edges. The Left value is often returned when a horizontal edge is detected. The Above value is returned when a vertical edge is detected. If no edge is detected, the value of the plane above the point X passing in the threedimensional space through the points Left, Above and LeftAbove is returned. The first four of these predictors are used in PNG format, for example. The fourth predictor is used in WinRAR archiver. The last predictor is used in JPEG-LS compression format. A description of other predictors used in the process of sequential pixel traversal can be found in [6].
On the one hand, translational hierarchical compression of images allows to speed up decoding, and on the other – to consider the values of previously processed elements from four, not just from two different sides in the process of using predictors. That is why to achieve the goal of the study we have developed an effective scheme of pixel traversal and appropriate predictors that implement progressive hierarchical compression of images without losses. In particular, for a progressive hierarchical traversal, we propose a scheme in which the pixels of the image are processed sequentially on the first layer, starting from the first, in rows from top to bottom, and in each row from left to right in steps h1 2k , where k is determined from a condition maxminheight; width; 16 1 k log2 , height –the number of lines, width – the number of 15 columns of pixels of image. This step provides processing on the first layer of at least 16 pixels (if any) on each of the axes (as in the icons), if the image is smaller. On the next layers ( l 2, k 1) intermediate pixels of the image are processed in two passes: on the first pass, those of them which are contained on crossing of diagonals of squares with vertices in adjacent pixels of the previous layer with a step hl 2k 2l both on lines, and on columns are processed. And on the second – unprocessed pixels are processed between adjacent pixels of the previous layer and the first pass with the same step on columns and with twice reduced – on lines (Figure 3).
The proposed sequence of traversing the pixels of the image allows not only to speed up decoding when the size of the output area is much smaller than the size of the image, but also to use hierarchical predictors to predict the value of each element of the next pixel (in Figure 4 it is marked as X) on all the layers, starting with the second. To describe these predictors, we denote the values of the brightness of similar components of the nearest (adjacent) previously processed pixels from the previous and next layer or pass using the notation a, b, c, d, ab, bc (Figure 4).
Using these notations, we investigate the principles of forecasting the two main symmetric hierarchical predictors, focused on the basic arithmetic mean (noise component) of the two opposite elements of the next four (a, b, c, d), which differ least (trend component), i.e., most likely belong to the same object in the image. In the case when the brightness of the components of close pixels is more affected by weak background oscillations, we predict the value of the next element using the trend-noise predictor ProgresPredict1, which returns the basic arithmetic mean. In the case when the increments of the nearest opposite elements are the same, this predictor returns the arithmetic mean among a, b, c, d. Predictor ProgresPredict1 performs an average of 3.5 branching operators and the same number of comparison operations to predict the values of individual brightness of each pixel.
If strong fluctuations in the brightness of the pixels predominate, then let us predict the value of the next element using the noise-trend predictor ProgresPredict2. Among four adjacent processed elements a, b, c, d this predictor determines and returns the closest value to the basic arithmetic mean, when such a value is unique. If among the adjacent processed elements there are two closest equidistant values to the basic arithmetic mean, then among them the one around which more brightness is concentrated is returned. When the brightness is scattered, it returns less from the nearest equidistant values to the basic arithmetic mean. The general orientation to smaller values makes it possible to shift the non-zero deviations ij calculated according to (2) towards positive values and thus increase the unevenness of their distribution. The ProgresPredict2 predictor performs an average of 5 branching operators and 6 comparison operations for each prediction.
In C, basic symmetric predictors can be written as follows: ubyte ProgresPredict1(ubyte a, ubyte b, ubyte c, ubyte d) {ubyte pa, pb; if (a>=c) pa=a-c; else pa=c-a; if (b>=d) pb=b-d; else pb=d-b; if (pa<pb) return (a+c)/2; if (pb<pa) return (b+d)/2; return (a+b+c+d)/4; } ubyte ProgresPredict2(ubyte a, ubyte b, ubyte c, ubyte d) {ubyte absac, absbd, maxac, minac, maxbd, minbd, prognozn; if (a<=c) {absac=c-a; maxac=c; minac=a;} else {absac=a-c; maxac=a; minac=c; } if (b<=d) {absbd=d-b; maxbd=d; minbd=b; } else {absbd=b-d; maxbd=b; minbd=d; } if (absac<=absbd) {if (minbd>=minac && minbd<=maxac) return minbd; if (maxbd>=minac && maxbd<=maxac) return maxbd; if (minbd>maxac) return maxac; else return minac; } else {if (minac>=minbd && minac<=maxbd) return minac; if (maxac>=minbd && maxac<=maxbd) return maxac; if (minac>maxbd) return maxbd; else return minbd; }}
Let us describe the mechanism for predicting two additional symmetric hierarchical predictors. The noise predictor ProgresPredict3 returns the arithmetic mean between the average luminance values among a, b, c, d. Thus, it does not consider the largest and smallest values among these four brightness values. To do this, the two minimum and maximum values among the opposite brightness values are calculated first, and then the average between the minimum of the two maxima found and the maximum of the two calculated minima is calculated. This predictor performs an average of 4 branching operators and the same number of comparison operations to predict the brightness values of each pixel. The ProgresPredict3 predictor is effective on the boundaries of the depicted objects.
The trend predictor PrograsPredict4 chooses the one around which the most brightness is concentrated among the two opposite elements, which differ the least from the next four. This predictor is effective in areas of images where the influence of the trend significantly prevails. To predict each brightness value, it uses as many branch operators and comparison operations as PrograsPredict3.
In C, additional symmetric hierarchical predictors can look like this: ubyte ProgresPredict3(ubyte a, ubyte b, ubyte c, ubyte d) {ubyte maxac, minac, maxbd, minbd; if (a<=c) {maxac=c; minac=a; } else {maxac=a; minac=c; } if (b<=d) {maxbd=d; minbd=b; } else {maxbd=b; minbd=d; } return (min(maxac,maxbd)+max(minac,minbd))/2; } ubyte ProgresPredict4(ubyte a, ubyte b, ubyte c, ubyte d) {ubyte absac, absbd, maxac, minac, maxbd, minbd; if (a<=c) {absac=c-a; maxac=c; minac=a; } else {absac=a-c; maxac=a; minac=c; } if (b<=d) {absbd=d-b; maxbd=d; minbd=b; } else {absbd=b-d; maxbd=b; minbd=d; } if (absac<=absbd) {if (b+d>a+c) return maxac; else return minac; } else {if (a+c>b+d) return maxbd; else return minbd; }}
Let us analyze the results of the usage of the proposed symmetric predictors of hierarchical traversal to reduce the entropy of the pixel components of the standard test set Archive Comparison Test (ACT), the image characteristics of which are given in table. 1. This set contains both synthesized (№№ 1 (with noise), 2, 7) and photorealistic (all eost.heYros)u ciamnadgownload TIFF versions of these images, for example, from [10]. 17.83 Continuous-tone, artificial, noisy, several big objects
0.29 Discrete-tone, artificial, one big object 56.56 Continuous-tone, natural, several big objects 19.99 Continuous-tone, natural, one big and several small objects 42.47 Continuous-tone, natural, several big objects 19.26 Continuous-tone, natural, many medium-sized objects
In the table. 2 for comparison, the line NonePredict shows the entropy of the brightness values of the components of the pixels without the usage of predictors, and below – the entropy of the same brightness after using the most common predictors of sequential traversal and symmetric predictors of hierarchical traversal. In the initial passes of the hierarchical pixel traversal, symmetric predictors were not used if they increased entropy.
As it was expected, the usage of noise-trend predictors ProgresPredict2 and ProgresPredict4 proved to be more effective for synthesized images, as they are characterized by sharp differences in the brightness of the processed pixels within the depicted objects (trend influence predominates), and trend-noise predictors ProgresPredict1 and ProgresPredict3 were more effective for photorealistic images, because their adjacent pixels often have similar but different colors (dominated by noise).
The use of symmetric predictors significantly reduces the entropy on the last layers compared to other currently known sequential traversal predictors, as these predictors consider the effect of four equidistant pixels on different sides, not just left and top pixels, as in sequential traversal. In this case, each processed pixel of the next layer in the middle of the image is used to process eight pixels of the next layer (and not for a maximum of three subsequent pixels, as for predictors of sequential traversal).
The level of correlation of the brightness of the components of adjacent pixels on the last layers is significantly higher than the level of correlation of these brightness on the first layers, especially for synthesized images. That is why the use of sequential bypass predictors (and sometimes the refusal to use them) provide less entropy than the use of progressive predictors on the initial layers, although the efficiency of the latter increases with increasing layer number. Therefore, in order not to increase the entropy in general, for the synthesized image № 2 it is advisable to abandon the use of predict both the second and third layers, and for the i–moangethe№first7pass of the second layer.
The noise predictors ProgresPredict1 and ProgresPredict3 provide almost the same compression ratio, but ProgresPredict1 requires fewer operators and comparison operations, so it is chosen as the base. Among the trend predictors ProgresPredict2 and ProgresPredict4, ProgresPredict2 provides much lower entropy, so it is used as a base. In addition, when performing the basic trend predictor ProgresPredict2, on average, 2.5 comparison operations are performed more than the noise predictor ProgresPredict1, so the predictor ProgresPredict1 should be preferred to ProgresPredict2 at the same entropy values after their usage. For comparison: in the process of performing a nonlinear static predictor of sequential traversal of PaethPredict, an average of 5.66 comparison operations are performed. MedPredict predictor performs 5 comparison operations. Thus, the use of the noise predictor ProgresPredict1 even instead of nonlinear sequential bypass predictors significantly speeds up encoding/decoding.
It is possible to increase the efficiency of noise-trend predictors by considering in the first pass of each layer the values of adjacent, previously processed elements on the left and top of the same passage, and in the second pass – the two closest processed diagonal values in the previous line (in Figure 4 they are denoted as ab and bc, respectively). The colors of the pixels of the images are often similar to the colors of close pixels horizontally or vertically, and much less often – to the colors of close pixels diagonally. This (and not only the greater distances to the predicted element) explains much lower efficiency of the use of symmetrical predictors in the first pass relative to the second for each layer of an arbitrary image (see Table 2). It is impossible to consider the values of similar elements on the right and bottom relative to the element X in the first passes, because when applying predictors to this element they have not yet been processed (which is why the predictors described below are asymmetric).
Let us consider the principles of forecasting two asymmetric noise-trend predictors developed by us. The first, ProgresPredict3, returns the closest value to the basic arithmetic mean not only among the four closest adjacent processed elements a, b, c, d as ProgresPredict2, but also additionally among ad and ab, giving them an advantage over other elements at the same distances. To speed up the calculations, the smallest distance to the basic arithmetic mean is determined implicitly, using the fact that the closer to the middle between the points x and y (xy) the point z is, the smaller the difference is y z z x y 2z x .
The second of the asymmetric predictors, ProgresPredict4, determines the smallest absolute diagonal increment relative to the elements ad and ab and returns the value in the direction of this increment relative to the element X, if this increment is less than half of the smaller of the diagonal increments of the nearest elements ( mina c , b d / 2 ). In this case, among two identical diagonal increments, preference is given to that which is associated with a smaller rectilinear increment around the element X. Otherwise, the predictor among the four nearest adjacent processed elements a, b, c, d determines the three closest to the basic arithmetic mean (most likely belonging to one image object) and returns the average value among them.
In C, these asymmetric hierarchical predictors are written as follows: ubyte ProgresPredict5(ubyte a, ubyte b, ubyte c, ubyte d, ubyte ab, ubyte bc) {ubyte absac, absbd, maxac, minac, maxbd, minbd, prognozn, s, mins; if (a<=c) {absac=c-a; maxac=c; minac=a; } else {absac=a-c; maxac=a; minac=c; } if (b<=d) {absbd=d-b; maxbd=d; minbd=b; } else {absbd=b-d; maxbd=b; minbd=d; } if (absac<=absbd) {prognozn=ab; mins=abs(maxac+minac-2*ab); s=abs(maxac+minac-2*bc); if (s<mins) {prognozn=bc; mins=s; } s=abs(maxac+minac-2*minbd); if (s<mins) {prognozn=minbd; mins=s; } s=abs(maxac+minac-2*maxbd); if (s<mins) {prognozn=maxbd; mins=s; } if (minac>=prognozn || prognozn>maxac) return minac; return prognozn; } else {prognozn=ab; mins=abs(maxbd+minbd-2*ab); s=abs(maxbd+minbd-2*bc); if (s<mins) {prognozn=bc; mins=s; } s=abs(maxbd+minbd-2*minac); if (s<mins) {prognozn=minac; mins=s; } s=abs(maxbd+minbd-2*maxac); if (s<mins) {prognozn=maxac; mins=s; } if (minbd>=prognozn || prognozn>maxbd) return minbd; return prognozn; }} ubyte ProgresPredict6a(ubyte a, ubyte b, ubyte c, ubyte d, ubyte ab, ubyte bc) {ubyte absac, absbd, maxac, minac, maxbd, minbd, prognozn, minprD, minprGV, prD, prGV; if (a<=c) {absac=c-a; maxac=c; minac=a; } else {absac=a-c; maxac=a; minac=c; } if (b<=d) {absbd=d-b; maxbd=d; minbd=b; } else {absbd=b-d; maxbd=b; minbd=d; } minprD=abs(ab-a); minprGV=abs(a-d); prognozn=d; prD=abs(ab-b); if (prD<=minprD) {prGV=abs(b-c); if (prD<minprD || prGV<minprGV) {minprD=prD; minprGV=prGV; prognozn=c; }} prD=abs(bc-b); if (prD<=minprD) {prGV=abs(a-b); if (prD<minprD || prGV<minprGV) {minprD=prD; minprGV=prGV; prognozn=a; }} prD=abs(bc-c); if (prD<=minprD) {prGV=abs(d-c); if (prD<minprD || prGV<minprGV) {minprD=prD; minprGV=prGV; prognozn=d; }} if (2*minprD<min(absac, absbd)) return prognozn; return ProgresPredict2(a, b, c, d); } ubyte ProgresPredict6b(ubyte a, ubyte b, ubyte c, ubyte d, ubyte ab, ubyte bc) {UBYTE1 absac, absbd, maxac, minac, maxbd, minbd, prognozn, minpr1, minpr2, pr1, pr2; if (a<=c) {absac=c-a; maxac=c; minac=a; } else {absac=a-c; maxac=a; minac=c; } if (b<=d) {absbd=d-b; maxbd=d; minbd=b; } else {absbd=b-d; maxbd=b; minbd=d; } minpr1=abs(ab-b); minpr2=abs(b-c); prognozn=a; pr1=abs(ab-a); if (pr1<=minpr1) {pr2=abs(a-d); if (pr1<minpr1 || pr2<minpr2) {minpr1=pr1; minpr2=pr2; prognozn=b; }} pr1=abs(bc-b); if (pr1<=minpr1) {pr2=abs(a-b); if (pr1<minpr1 || pr2<minpr2) {minpr1=pr1; minpr2=pr2; prognozn=c; }} pr1=abs(bc-c); if (pr1<=minpr1) {pr2=abs(c-d); if (pr1<minpr1 || pr2<minpr2) {minpr1=pr1; minpr2=pr2; prognozn=b; }} if (minpr1+minpr2<min(absac,absbd)) return prognozn; return ProgresPredict2(a, b, c, d); }
The results of the application of the proposed asymmetric hierarchical predictors to reduce the entropy of the pixel components of the ACT image set are given in table 3. From the data in this table, we see that the use of the asymmetric predictor ProgresPredict5 slightly reduces the entropy of images without noise, and the predictor ProgresPredict6 significantly reduces the entropy of the image № 1 and compresses the rest of thweorisme.agItesis clear that asymmetric predictors are used to predict the values of six rather than four previously processed elements and are therefore are calculated much longer. Such predictors can be used to provide maximum compression, but they are not suitable for graphic formats where fast decoding is required.
The results of the study indicate that predictors should be used only from the passage and the layer when their application begins to reduce entropy, and among the predictors should be chosen the one that provides the lowest entropy after its usage. Moreover, the level of influence and the nature of noise and trends for different fragments of the image may differ, so they may be effective for different hierarchical predictors. We emphasize that the use of predictors should be abandoned for the whole passage, and not for individual fragments, because the values of the brightness of the image components without and after the use of predictors have different nature of uneven distribution (see Figure 1). Therefore, in the process of progressive hierarchical compression for each pass of the next layer, it is advisable first to determine whether the use of predictors generally reduces the entropy of the brightness of its pixel components. Then, if you decide to use predictors, choose for each homogeneous fragment of pixels minimizes its entropy.
We used basic symmetric hierarchical predictors to decide on the use of predictors on each pass of the next layer, as the first of them focuses on photorealistic images and is processed faster than ProgresPredict3, and the second predictor provides significantly better compression for synthesized images than ProgresPredict4. If they reduce the entropy for each row of the next pass, we chose the most efficient among the symmetric predictors and additionally – with each of the asymmetric hierarchical predictors. The results of the usage of these methods of combining hierarchical predictors to reduce the entropy of the pixel components of the ACT image set are given in table 4-6. For comparison, at the beginning of these tables there are the results of a similar application to the same images of combinations of consecutive predictor of PNG format and all consecutive predictors listed above, which provide the lowest entropy for each individual row. The test was performed on a computer with an Intel Pentium 4 processor clocked at 3 GHz and RAM 4 Gb. Let us emphasize that in these experiments, context-dependent algorithms that eliminate repetition between individual fragments of images were not used.
As evidenced by the data of these tables and tables 2-3, the use of combinations of all symmetric hierarchical predictors reduces the entropy relative to the most effective of the individual studied predictors on average by a set of ACT by more than 0.22 bpb mainly due to the synthesized images. The additional use of asymmetric predictors, on average, slows down encoding by 14-17% and decoding by 5%, but reduces entropy by a maximum of 0.1 bpb. Additional application of ProgresPredict5 reduced the entropy of only the synthesized image № 2, but this advantage is offs by the context-dependent algorithm. Therefore, for fast hierarchical compression of images, it is advisable to use a combination of symmetrical hierarchical predictors, and to ensure maximum compression it is better to use an additional combination of symmetrical predictors and asymmetric predictor ProgresPredict6. Sequential predictors of PNG format 1.81 2.37 0.56 0.95 0.56 1.04 0.93 0.98 All sequential predictors 1.99 2.75 0.66 1.21 0.67 1.15 1.09 1.14 Basic symmetric predictors 1.52 2.08 0.55 0.70 0.52 0.83 0.80 0.74 Additional symmetric predictors 1.74 2.57 0.63 0.78 0.66 0.78 1.04 0.78 All symmetrical predictors 1,85 2,42 0,60 0,97 0,58 0,97 0,96 0,96 All symmetric predictors and ProgresPredict5 2.00 2.77 0.70 1.11 0.66 1.11 1.08 1.10 All symmetric predictors and ProgresPredict6 2.06 2.84 0.70 1.15 0.69 1.15 1.13 1.15
The use of hierarchical predictors, although on average provides greater entropy than consecutive ones by 0.13 bpb for synthesized images but achieves the best values for this indicator at 0.08 bpb for photorealistic images. And most importantly: the progressive hierarchical way of traversing pixels allows you to perform decoding much faster than sequential traversal, when the size of the output area is much smaller than the size of images (for example, to fill the output area 128 x 128 pixels (4 layers) such decoding is performed 10 times faster (see Table 6), because the time of hierarchical decoding depends on the smaller among the size of the output area and the size of the image (this was emphasized in [3, p. 175]), and consistent – only on the size of the image. Let us also note that the PNG format should be supplemented with a sequential predictor MedPredict, which will significantly reduce the entropy of photorealistic images (for example, the ACT set – by 0.07 bpp). 6. Conclusions and prospects of subsequent researches 1. In the new versions of graphic formats and new lossless image compression formats, it is advisable to implement progressive hierarchical compression, as this allows you to speed up decoding significantly when the size of the output area is smaller than the image size. 2. Reducing the size of images compressed in a progressive hierarchical manner is achieved mainly on the last layers, because the pixels used in the predictors have the highest level of correlation with the predicted pixel on average relative to other layers. 3. In the process of hierarchical compression to increase the efficiency of symmetrical predictors, which consider the brightness of the previously processed four nearest pixels, possibly by taking into account the brightness of the two nearest adjacent pixels processed in the same pass. 4. During context-independent lossless compression for homogeneous image fragments, it is advisable to choose the predictor from several alternatives that allows to minimize the entropy.
In the future, in order to additionally reduce the size of compressed image files without losses and speed up decoding, we plan to adapt context-sensitive compression methods [4, 11, 12] to the hierarchical traversal of image pixels and increase the efficiency of symmetric and asymmetric predictors using different color models [13].