The method and corresponding algorithm for selecting adaptive difference color models with integer coefficients for improving the efficiency of progressive lossless image compression was proposed. The necessity was reasoned and the displacement of the median differences of the basic components of the R, G, B color model to the middle of the range of possible values was implemented. Fragments of programs in the C++ language for implementing the algorithm for choosing a difference color model from 49 alternatives and the algorithm for determining the median component in linear time by the counting method are given. On the well-known ACT test set, it is shown that the use of difference color models with integer coefficients makes it possible to reduce the compression coefficients of photorealistic images by an average of 0.58 bpb.
As you know, images significantly facilitate and accelerate the perception of information by a person. That is why today they are an integral part of multimedia information, which is most often transmitted by communication channels or stored on electromagnetic media. Therefore, the problem of increasing the efficiency of image compression is relevant today and will be relevant in the nearest future.
All graphic formats and methods used in them are divided into two main classes based on the principle of image data compression: lossy (for example, JPEG) and lossless (for example, PNG) [1]. And if for the vast majority of lossy image compression algorithms it is possible to provide the required compression ratio (the ratio of compressed to uncompressed image file sizes, expressed in bpb, hereinafter – CR) at the expense of quality degradation, then the level of lossless image compression actually depends only on the differences of the colors of their pixels and the compression algorithm itself. It is not adjustable by software and averages only 30-70% [1]. Therefore, the development of alternative graphic formats, such as HBF-LS [2], is an urgent task today.
Any data compression is possible due to reduction or elimination of redundancies [3]. Three main types of redundancies are distinguished in images [4]: visual (consisting in the presence of information that is not perceived by the human visual system), inter-element or spatial (manifested in the correlation of brightness's of adjacent pixels) and coded (revealed when using codes of the same length for elements with different probabilities). It is common knowledge that the more types of redundancies of each type are processed by the graphic format, the more effective the compression is. But in the process of lossless compression, information is not lost, that is why the first type of redundancy is not reduced. Therefore, lossless image compression in archivers and graphic formats most often occurs in a maximum of four stages: firstly, context-dependent coding reduces redundancies between the same fragments or fragments with the same structure (reduces inter-element redundancy). At the second stage, the transition to an alternative color model is performed [5]. On the third – the brightness of the pixel components are transformed using predictors [6] (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). At the fourth stage, context-independent coding forms element codes with lengths dependent on their probabilities (processes code redundancy, for example, with Huffman codes or arithmetic codes [1; 3; 4; 7; 8; 9; 10; 11]). Context-independent coding can even be used instead of context-sensitive codes for individual pixel luminance, if this further reduces CS. For example, in the Deflate format, Huffman codes can be used instead of individual substitutions of the same luminance of the LZ77 dictionary algorithm [7].
Processing of image pixels luminance in popular graphic formats that perform lossless compression is most often carried out sequentially in rows from top to bottom, and in each row – consecutively from left to right. As a result, output of the compressed image in these formats is possible only after decoding is complete. Decompressing pictures or images with millions of pixels with this bypass method can take several seconds regardless of the size of the area or the resolution of the output device. We are developing the HBF-LS [2] format for progressive hierarchical lossless image compression, which will allow you to quickly obtain reduced copies of the image without decoding the entire file.
In the HBF-LS format, a hierarchical scheme is proposed as an alternative to sequential pixel traversal [5; 6], according to which on the first layer the pixels of the image are processed sequentially, starting with the first one in the upper left corner, in rows from top to bottom, and in each row – a sub-row from left to right with a step h1 2k , where k is determined from the condition maxminimage_ row; image_ col;16 1 k log2 , image_row – the number of rows, 15 image_col – the number of columns of image pixels (Figure 1a). This step ensures processing on the first layer at least 16 pixels along each of the axes, if the image is at least as large.
a) b) c) Figure 1: The sequence of pixel bypass in the process of progressive hierarchical processing: a) pixels of the first layer; b) pixels the first passage regular layer; c) pixels the second passage regular layer In the following layers ( l 2, k 1), the intermediate pixels of the image are processed in two passes: in the first, those of them that are located at the intersection of the diagonals of the squares with the vertices in the adjacent pixels of the previous layers are sequentially processed in steps hl 2k 2l both by rows and by columns (see Figure 1b), and on the second, the unprocessed pixels are sequentially bypassed between the adjacent pixels of the previous layers and the pixels of the first pass with the same step in the columns and with a halved step in the rows (see Figure 1c). In Figure 1 the symbol F indicates the pixels of the first layer, the symbol P indicates the pixels of the previous layers, the number 1 – the pixels of the first pass of the next layer, the number 2 – the pixels of the second pass of the next layer. Pixels that were processed earlier and therefore are not processed on the next pass of the layer are highlighted in italics.
In this article, we propose a method and a corresponding algorithm for increasing code redundancy by reducing inter-element redundancy using adaptive difference color models with integer coefficients in the process of progressive lossless image compression.
Difference color models [5], as well as predictors [6] are used to reduce the compression ratio of context-independent coding. The basic principle of such coding can be formulated as follows: the length of the code of an arbitrary element with a higher probability should not exceed the length of the code of any element with a lower probability. With regard to images, this principle is based on the fundamental position of information theory, according to which to minimize the length of the sequence code, each value of the element i (brightness of a separate component brightness (for a separate component of each pixel of images True Color brightness 0, 255) or the value of a contextdependent code) with the probability of occurrence pi it is advisable to code with li log2 pi bits [10], where li is the length of the entropy code element i (here and everywhere else in the work, the logarithm is taken to the base 2). Therefore, the average code length of a block element after applying any context-independent algorithm, according to the formula of Shannon [4], cannot be less than the entropy of the source
H pi log pi . (
i
As it is known, the entropy of the source decreases with increasing unevenness of the distribution of probabilities (frequencies) between elements [6].
Since the average length of a context-independent code is close to entropy (
L N H N logN ni logni . (
To increase the efficiency of context-independent coding in the process of lossless image
compression the help of predictors is used, which during the round predict the value of the brightness
of each component of the next pixel (for the most common 24-bit images, these are the brightness of
the red, green and blue components, written as integers in separate bytes), using the brightness of the
values of the same components of previously processed adjacent pixels [6], since the brightness data
have the highest level of correlation between them. In the process of using predictors, deviations uv
, and the total length of the entropy code of the
of the value of the brightness of the next pixel component brightnessuv from the value predicted by
the selected predictor predictuv , are calculated and further coded. So,
uv brightnessuv predictuv
(
Different color models are also used to reduce entropy. The fact is that, firstly, the color of each pixel in the three-component color model can be represented in the form of coordinates by three linearly independent vectors of any basic colors [5]. Secondly, different image components display sufficiently similar geometrically spatial structure objects (as, for example, in Figure 2).
It is clear that the correlation coefficients between pairs of components in the RGB color model for
different images can differ significantly from each other, and one of the components of a such
arbitrary pair with a strong correlation can be replaced by the difference with another component [5],
if this will reduce the entropy (
Y 77 R 150 G 29 B; 256 256 256
44 87 131 Cb = - R - G + B +128; 256 256 256 131 110 21 Cr = R - G - B +128.
256 256 256
(
Predictors perform decorrelation of the brightness of individual components of the color model, so the transition to alternative difference color models in the process of lossless image compression is performed before the use of predictors [6]. In addition, graphic file formats for lossless image compression must provide both fast encoding and fast decoding, so it is advisable to use difference color models with integer coefficients [5]. Therefore, the purpose of this article is to substantiate the options and algorithm for choosing an adaptive color model for each image to reduce their CR in the process of lossless compression and to provide a software implementation of this algorithm.
As it will be shown below, in order to ensure unambiguous decoding in the image, it is possible to
perform a maximum of two replacements of the values of different components by differences with
other components. Therefore, considering this limitation, in the process of coding for each image
during preprocessing, the problem of choosing one difference color model among alternatives so as to
reduce the CR as much as possible appears. In fact, in the compression process, it is necessary to
evaluate the expediency of replacing the R component values with one of the RG, GR, RB or BR
differences, the G component values with GR, RG, BG or GB differences, and the B component
values with BR, RB, BG or GB differences for each pixel and among these possible differences,
choose a maximum of two that will maximally reduce the predicted length of the entropy code
(
a00 a01 a02 LR LR G LR B
A a10 a11 a12 LG R LG LG B , (
The proposed procedure for calculating the coefficients of matrix A is, in our opinion, effective in simulating the process of lossless image compression. Firstly, the transition to the difference color model is performed, then predictors are applied, and their results are encoded by a contextindependent algorithm. But this approach is focused on the use of linear static predictors. It does not take into account the impact on the compression process of the context-dependent algorithm (which is especially relevant for discrete-tone images) and the cross-correlation of components in the difference color model. It also does not justify the choice of predictor for prediction and does not determine which precisely from two opposite differences (for example, R – G or G – R), which have the same entropy code length after applying the linear predictor should be chosen. In addition, the matrix A allows you to form a difference color model for the entire image but does not indicate ways to fragment it and determine the difference color models for individual fragments. Therefore, we will deal with the elimination of these shortcomings.
Difference color models are used to maximize entropy reduction (
Note that difference color models with integer coefficients can contain no more than two component differences.
To justify this fact, we will use the method of proof from the opposite and the requirement of linear independence of vectors of basic colors of any alternative color model. Let there be a difference color model with three component differences. Firstly, each component must enter at least one difference to ensure a fallback to the RGB color model. Secondly, no difference can contain the same component in the decrement and in the subtractor, because then it will turn to zero, which will violate the requirement of linear independence of the components. Thirdly, any of two differences can not contain two same or opposite components, because then they will be linearly dependent. Fourth, none of the components can be included in all three differences, because otherwise at least two differences of the same or opposite sign will be generated, which will contradict the previous statement (for example, if all differences include the component R, then the components G and B must complement two of these differences, and the third difference must again contain G or B and will contain the same components as one of the other two differences). And, finally, each of the components cannot be included in two differences, because then a linear combination with the sum or subtraction of these differences, which excludes this component, will be linearly dependent with the third difference (for example, if the component R is included in the first difference as the minus, and the second as the minus, then the sum of these differences will create a difference G – B or B – G, which will be the same or opposite in sign to the third difference, which will contradict the requirement of linear independence of the basic color vectors). It turns out that each of the three components must enter the difference color model only once, which makes it impossible to create three differences.
As already mentioned above, in the process of compressing images, a context-dependent algorithm is first performed, and for pixels not processed by this algorithm, a transition to the difference color model is performed, then predictors are applied, and the results of their use and the context-dependent algorithm are coded with a context-independent algorithm. That is, the difference color models increase the efficiency, first of all, of the context-independent algorithm. That is why they are effective primarily for photorealistic images [5]. Among the main symmetric hierarchical predictors for such images, ProgresPredict1 provides the smallest CR [6], therefore, we use this predictor to select a difference color model. In C++, this predictor is written like this: 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; } This predictor returns the arithmetic mean of those two opposite elements from the nearest four (a, b, c, d) that differ the least. If the deviations of the opposite elements are the same, then ProgresPredict1 returns the arithmetic mean of all four values.
If each component of the difference color model were coded into separate Deflate blocks [7] (that
is, there would be no cross-correlation of the components) and the length of the entropy code (
This list of alternative integer-difference color models is constructed from variants of all possible models by discarding opposite-difference models and component-permutation models so that the reduced ones retain the input RGB components. We also classified the RGB color model as differential with having zero subtractors.
We also note that, firstly, the difference color models increase the efficiency of using only the context-independent algorithm. Therefore, we will not consider the brightness of the pixels that are completely included in the replacement of the modified LZ77 algorithm by the adjacent previously processed pixels when determining the parameters of these models.
Secondly, the length of the entropy code (
Thirdly, when calculating the differences in the luminance of the components in cases where the
luminance values of the subtractor insignificantly exceed the luminance values of the reduced one,
negative values of the differences are obtained, which, when stored in unsigned 8-bit components of
the color model, due to overflow, are transformed into values close to 256. And when the luminance
values of the subtractor are slightly smaller than the luminance values of the reduced one, values close
to zero are obtained in the differences. This dispersion of color model difference values negatively
affects the accuracy of ProgresPredict1 prediction and, as a consequence, increases entropy (
Taking into account the above remarks, in the process of progressive hierarchical compression of
lossless images, the following difference color models with integer coefficients can be alternatives:
1. R, G, B;
2. R, G, (R – medR) – (B – medB) + 128;
3. R, G, (G – medG) – (B – medB) + 128;
4. R, (R – medR) – (G – medG) + 128, B;
5. R, (B – medB) – (G – medG) + 128, B;
6. (G – medG) – (R – medR) + 128, G, B;
7. (B – medB) – (R – medR) + 128, G, B;
8. R, G, (B – medB) – (R – medR) + 128;
9. R, G, (B – medB) – (G – medG) + 128;
10. R, (G – medG) – (R – medR) + 128, B;
11. R, (G – medG) – (B – medB) + 128, B;
12. (R – medR) – (G – medG) + 128, G, B;
13. (R – medR) – (B – medB) + 128, G, B;
14. R, (R – medR) – (G – medG) + 128, (R – medR) – (B – medB) + 128;
15. R, (G – medG) – (R – medR) + 128, (G – medG) – (B – medB) + 128;
16. R, (B – medB) – (G – medG) + 128, (B – medB) – (R – medR) + 128;
17. R, (G – medG) – (R – medR) + 128, (B – medB) – (R – medR) + 128;
18. R, (R – medR) – (G – medG) + 128, (B – medB) – (G – medG) + 128;
19. R, (G – medG) – (B – medB) + 128, (R – medR) – (B – medB) + 128;
20. (R – medR) – (G – medG) + 128, G, (R – medR) – (B – medB) + 128;
21. (G – medG) – (R – medR) + 128, G, (G – medG) – (B – medB) + 128;
22. (B – medB) – (R – medR) + 128, G, (B – medB) – (G – medG) + 128;
23. (G – medG) – (R – medR) + 128, G, (B – medB) – (R – medR) + 128;
24. (R – medR) – (G – medG) + 128, G, (B – medB) – (G – medG) + 128;
25. (R – medR) – (B – medB) + 128, G, (G – medG) – (B – medB) + 128;
26. (R – medR) – (B – medB) + 128, (R – medR) – (G – medG) + 128, B;
27. (G – medG) – (R – medR) + 128, (G – medG) – (B – medB) + 128, B;
28. (B – medB) – (R – medR) + 128, (B – medB) – (G – medG) + 128, B;
29. (B – medB) – (R – medR) + 128, (G – medG) – (R – medR) + 128, B;
30. (R – medR) – (G – medG) + 128, (B – medB) – (G – medG) + 128, B;
31. (R – medR) – (B – medB) + 128, (G – medG) – (B – medB) + 128, B;
32. R, (G – medG) – (R – medR) + 128, (R – medR) – (B – medB) + 128;
33. R, (R – medR) – (G – medG) + 128, (G – medG) – (B – medB) + 128;
34. R, (G – medG) – (B – medB) + 128, (B – medB) – (R – medR) + 128;
35. R, (R – medR) – (G – medG) + 128, (B – medB) – (R – medR) + 128;
36. R, (G – medG) – (R – medR) + 128, (B – medB) – (G – medG) + 128;
37. R, (B – medB) – (G – medG) + 128, (R – medR) – (B – medB) + 128;
38. (G – medG) – (R – medR) + 128, G, (R – medR) – (B – medB) + 128;
39. (R – medR) – (G – medG) + 128, G, (G – medG) – (B – medB) + 128;
40. (R – medR) – (B – medB) + 128, G, (B – medB) – (G – medG) + 128;
41. (R – medR) – (G – medG) + 128, G, (B – medB) – (R – medR) + 128;
42. (G – medG) – (R – medR) + 128, G, (B – medB) – (G – medG) + 128;
43. (B – medB) – (R – medR) + 128, G, (G – medG) – (B – medB) + 128;
44. (B – medB) – (R – medR) + 128, (R – medR) – (G – medG) + 128, B;
45. (R – medR) – (G – medG) + 128, (G – medG) – (B – medB) + 128, B;
46. (R – medR) – (B – medB) + 128, (B – medB) – (G – medG) + 128, B;
47. (R – medR) – (B – medB) + 128, (G – medG) – (R – medR) + 128, B;
48. (G – medG) – (R – medR) + 128, (B – medB) – (G – medG) + 128, B;
49. (B – medB) – (R – medR) + 128, (G – medG) – (B – medB) + 128, B.
(
Firstly, the components of difference color models in which R, G or B are included with the same
signs are better correlated with each other than when these signs are opposite. Therefore, such color
models are likely to provide smaller CR. Therefore, with strict limitations on the coding time, the
color model can be chosen not among the 49 alternatives, but only among the first 31, and this will
slightly affect the CR and reduce the compression time. In addition, as it will be shown later,
singledifference color models are effective mainly for discrete-tone images. Therefore, if it is known that
photorealistic images are compressed, then alternative difference color models 2-13 from set (
It is also obvious that among these 49 alternative color models, only one should be chosen
(determine its numberDCM) which will provide the smallest size of the compressed image, that is, the
smallest predicted length of the entropy code (
LDCM numberDCM min LDCM j . (
The length of the entropy code (
The selection of the difference color model according to formulas (
freqCom ponent22
niR niRmedRGmedG128 niRmedRBmedB128 , i 0, 255.(
Frequency arrays freqComponent (
To select the difference color model of the entire image, first let’s determine the medians of its components medR, medG, and medB. Since the median is a value located within a series of sorted values, then, of course, to determine these medians, it would be possible to sort by increasing values of the pixel components that are not included in the long substitutions of the modified LZ77 algorithm, and then choose the average values from the sorted arrays. But the complexity of such an approach would then be Oimage_row image_col logimage_row image_col. We implement an algorithm with linear computational complexity relative to the number of pixels, using the idea of the method of sorting by counting [14, p. 223-226]: for each component, we first count the frequencies of each brightness ni , i 0, 255, after which, using these frequencies, we determine the brightness relative to which the brightness of at least half of the elements is smaller. If the number of pixels for which the median is determined in this way is odd, then this median will be equal to the average value of the sorted array. If it is even, then it will be equal to the value from which the second half of the sorted array begins (the so-called "upper median").
The frequency array, which is additionally created and processed for such determination of medians, contains only 256 elements, which in general is much less than the number of image pixels and indicates the feasibility of applying the idea of the method of sorting by counting. A fragment of a C++ program for determining median components with frequency counts of individual luminances can look like this: step=1; // calculate the brightness frequencies of the components for (l=countShar; l>=2; l--) // loop through all layers except the first {step*=2; // process the pixels of the second pass of the layer startColumn=0; for (j=0; j<image_row; j+=step/2) // cycle by rows {if (startColumn==0) startColumn=step/2; // the first pixel of the first lines else startColumn=0; // the first pixel of the second rows for (i=startColumn; i<image_col; i+=step) // cycle through the columns // if the LZ-decomposition on the nearest processed pixels is not performed // or the next pixel is not included in a long replacement (from six elements) if (!LZReplaceAdjacent || !longAdjacentReplace[j*image_col+i]) {// read the components of the next pixel in the BGR color model b=image[j][i*3]; g=image[j][i*3+1]; r=image[j][i*3+2]; // increase the number of processed pixels and accumulate frequencies countPixelDCM++; freqR[r]++; freqG[g]++; freqB[b]++; }} // similarly process the pixels of the first layer pass for (j=step/2; j<image_row; j+=step) for (i=step/2; i<image_col; i+=step) if (!LZReplaceAdjacent || !longAdjacentReplace[j*image_col+i]) {b=image[j][i*3]; g=image[j][i*3+1]; r=image[j][i*3+2]; countPixelDCM++; freqR[r]++; freqG[g]++; freqB[b]++; }} UBYTE4 halfPixelCM=countPixelCM/2; // half of processed pixels UBYTE4 sumFreq=0; medR=0; // increase the median R until we process half of the frequencies of the elements while (sumFreq<halfPixelCM) sumFreq+=freqR[medR++]; sumFreq=0; medG=0; while (sumFreq<halfPixelCM) sumFreq+=freqG[medG++]; // similarly determine the median of G sumFreq=0; medB=0; while (sumFreq<halfPixelCM) sumFreq+=freqB[medB++]; // similarly determine the median B UBYTE1 medComponent[3]; // store the calculated medians for further complex use medComponent[0]=medR; medComponent[1]=medG; medComponent[2]=medB;
Defined medians of individual components make it possible to accumulate freqComponent (
The function for determining the predicted length of the entropy code (
To save the differences of the color model, we will use the following variables with the numbers
of its components from 0 to 2: cm1 – number of the component of the result of the first difference,
cm11 – number of the component of the reduced first difference, cm12 – number of the component of
the subtractor of the first difference, cm2, cm21, cm22 – similar variables for the second color model
difference. If the denominator of the first or second difference is equal to its denominator, then this
difference is not applied. Having formed the frequency array matrix freqComponent and the
implementation of the function sizeEntropiCode, we now present a fragment of the program for
determining the color model that provides the smallest predicted length of the entropy code (
(c21 != c12 || c22!=c11)) // and no symmetrical to the first differences
{// sum of the frequencies of the components (
Without lines marked with ' ', this program fragment selects alternative difference color models to the RGB model only among models with two differences, that is, it analyzes the effectiveness of using not 49, but 37 color models.
The use of a difference color model as an alternative to RGB, leads to the need to apply its differences to all image pixels that have not been processed by a context-sensitive algorithm, both during encoding and each time during the decoding process. That’s wh,y it slows down these two processes. Although, on the other hand, reducing the size of the compressed image due to the use of difference color models accelerates decoding, as it leads to the processing of compressed data of a smaller volume. Therefore, after determining the differences of the integer color model that provides the minimum predicted entropy code length, we arranged to fall back to the RGB color model if this predicted length decreased by less than 1%. Let's set the indices of the reducible cm11 and the denominator cm12 of the first difference and the indices of the reducible cm21 and the denominator cm22 of the second difference equal to zero: if (lenRGB-minLenDCM<lenRGB/100) {cm11=cm12=cm21=cm22=0; requiredDCM=false; return; } .
Alternative color model differences must be applied to the input components R, G, or B in sequence. Therefore, at the end of choosing a difference color model with integer coefficients, we implement a change in the order of subtraction of components, if the result of the first difference is used in the second difference: // if the second difference is defined and uses the result of the first difference if (cm21!=cm22 && (cm1==cm21 || cm1==cm22)) {i=cm1; cm1=cm2; cm2=i; // change order differences i=cm11; cm11=cm21; cm21=i; i=cm12; cm12=cm22; cm22=i; }
To speed up the application of the differences of the specified color model, we calculate the coefficients alfa1 and alfa2 for the first and second differences: if (cm11!=cm12) alfa1=-medComponent[cm11]+medComponent[cm12]+128; if (cm21!=cm22) alfa2=-medComponent[cm21]+medComponent[cm22]+128;
Then the procedure for applying the differences of the specified color model to any pixel of the image will be written as follows: void codeDCM (int row, int col, UBYTE1 *pixel) {if (cm11!=cm12) // the first subtraction is required pixel[cm1]=pixel[cm11]-pixel[cm12]+alfa1; if (cm21!=cm22) // the second subtraction is required pixel[cm2]=pixel[cm21]-pixel[cm22]+alfa2; }
We return to the RGB color model in the decoder in the reverse order: first we cancel the application of the second, and then the first difference. Therefore, the procedure for returning from the specified color model to the RGB model for each pixel in the decoding process is implemented as follows: void decodeDCM (UBYTE2 row, UBYTE2 col, UBYTE1 * decodeBytePixel) {// if determined, the second subtraction and to DCM components are applied if (cm21!=cm22 && appliedDCMBytePixel[cm2]) if (cm2==cm21) decodeBytePixel[cm2]+=decodeBytePixel[cm22]-alfa2; else decodeBytePixel[cm2]=decodeBytePixel[cm21]-decodeBytePixel[cm2]+alfa2; // if defined, the first subtraction and to DCM components are applied if (cm11!=cm12 && appliedDCMBytePixel [cm1]) if (cm1==cm11) decodeBytePixel[cm1]+=decodeBytePixel[cm12]-alfa1; else decodeBytePixel[cm1]=decodeBytePixel[cm11]-decodeBytePixel[cm1]+alfa1; } .
Let us analyze the results of applying selected from alternative difference color models with integer coefficients to test images of the ACT set [15] (Table 1, 3, 4). We can see that on average for this set due to the use of difference color models with integer coefficients the CR is decreased by 0.36 bpb (second row of Table 1). Moreover, about 19% of this decrease occurred due to the shift of the median difference to the middle of the range of possible values (that is, due to the consideration of alpha, the third line of Table 1).
For different images, the smallest predicted length of the entropy code is provided by different difference color models (Table 2). But the effectiveness of difference color models differs, first of all, for different types of images. If for photorealistic images the CR is decreased by an average of 0.58 bpb, then for discrete-tone images – only by 0.01 bpb, since they have a low level of correlation between components. For image #1, there was even a fallback to the RGB color model, as alternative difference color models reduced the predicted entropy code length by less than 1%.
The choice of difference color models not from the 49th, but from the first 31st with the same
minuends or subtrahends forms models with opposite components in 25% of the images, which
insignificantly increases their compression ratio. On the other hand, this does not lead to a drastic
acceleration of compression, because most of the time in the process of choosing difference color
models is spent on forming a matrix of component frequency arrays and their differences
freqComponent (
If we choose a difference color model from only 16 alternatives (
Difference CM from 49 alternatives Difference CM from 49 alternatives without alpha Difference CM from the first 31st alternative Difference CM from 16 alternatives according to A Difference CM from 49 alternatives according to A
RGB (R, R-G, B) B-R, G-B, B R, R-G, G-B RGB (R, R-G, B) B-R, G-B, B R, R-G, G-B 4 R, B-G, B-R R, R-G, R-B RGB (R, R-G, B) B-R, B-G, B R, G-R, G-B
R, B-G, B-R RGB (R, R-G, B) R-B, G-B, B R, G-R, B-G
R, G-B, B-R RGB (R, R-G, B) B-R, G-B, B R, R-G, G-B
R, G-B, R-B 5 G-R, G, G-B G-R, G, G-B G-R, G, G-B R-G, G, B-G G-R, G, G-B
G-R, G, G-B G-R, G, G-B
7 R-G, B-G, B R-G, B-G, B
8 R, R-G, B-G
R, R-G, B-G G-R, G, G-B
R-G, B-G, B
R, R-G, B-G R-G, G, B-G
R-G, G-B, B
R, G-R, B-G G-R, G, G-B
R-G, B-G, B
R, G-R, G-B
In general, the use of difference color models significantly (on average by more than 13% according to Table 3) slows down encoding not only due to the need to choose such a model from among alternatives, but also due to the orientation to a context-independent algorithm that encodes individual literals. However, the time of image decoding due to the use of these color models is increased by only a tenth of a second (9.3%, second row of Table 4), which, together with a significant reduction in CR, makes it possible to use them effectively in practice.
In the future, with the aim of further reducing the file sizes of lossless compressed images in the
process of progressive hierarchical traversal and speeding up decoding, we plan to increase the
efficiency of using symmetric and asymmetric predictors [6] by applying difference color models
with integer coefficients to image fragments. We are working on an algorithm for dividing images
into large rectangular pieces with different adaptive difference color models by analyzing their
median differences.
9. Conclusions
1. It is possible to reduce the CR of images in three-component color models not only due to the
data decorrelation of individual components, but also with the help of inter-component
decorrelation by switching to difference color models. Inter-component decorrelation should be
performed in such a way as to enhance the properties of the image used by the algorithms of
prepressing and direct compression of the selected graphic format, for example, to minimize the
predicted length of the entropy code (