RU2579966C1 - Method of image compressing (versions) - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: invention relates to image processing and specifically to image compression without losses due to use of data coding. Invention represents a method of images compressing. According to the method for each pixel of the input image an error value is determined, a pair of values: prediction error modulus and value of the prediction error sign. Further, the method consists in displaying error modulus of each pixel of the whole image into a binary sequence unary code. Obtained set of binary sequences is presented as set of binary levels, formed from binary values, whose ordinal position in code match the number of corresponding binary level.

EFFECT: high efficiency of encoding images by implementation of context simulation for values of prediction errors and values of prediction error sign in their original view.

23 cl, 12 dwg

Description

FIELD OF TECHNOLOGY

The invention relates to the field of image processing, more specifically to lossless image compression using data encoding.

BACKGROUND OF THE INVENTION

The most well-known lossless image compression methods are JPEG-LS, JPEG-2000 and the CALIC image compression algorithm.

LOCO-I algorithm from JPEG-LS standard ("lnformation Technology Lossless and Near-lossless Compression of Continuous-Tone Still Images: Baseline," ISO / IEC, ISO / IEC 14495-1: 1999), also described in patent applications US 5764374 publ. 06/09/1998 and US 5680129, publ. 10.21.1997, contains the following operations: selection of a pixel coding mode based on neighbor values, adaptive prediction, series length coding mode, context modeling of prediction error values, procedure for selecting parameters of Golomb codes. The adaptive prediction used in the LOCO-I algorithm can be used to generate prediction errors in the claimed method, but the procedure for encoding the prediction errors themselves in the claimed method is significantly different from that presented in the LOCO-I algorithm. In particular, the error values in the inventive method are represented as pairs of module values and the sign of the prediction error with subsequent coding, in the LOCO-I algorithm, the range of values is reduced using modular arithmetic, and the values themselves are mapped to the positive half-plane before encoding.

The lossless compression algorithm CALIC according to the application US 5903676, publ. 05/11/1999, contains operations: predicting the value of the current pixel by environment, context classification, context modeling of the prediction error and its correction, as well as entropy coding of the corrected prediction error. The CALIC invention was developed for compressing 8-bit single-component images, thus, at present, its scope is very limited.

The proposed coding scheme contains a similar set of operations, but has fundamental differences in their execution. In the proposed prediction scheme, there are no operations of multiplication and division, which positively affects the performance of the scheme. Context modeling in the proposed scheme is performed using binary data of bit planes and strictly according to prediction errors, while the CALIC invention uses both prediction error values and image pixel values in their original representation for modeling. In the proposed invention there is no procedure for clarifying prediction errors. In the proposed scheme, the coding of signs and prediction error modules is performed independently, which radically distinguishes it from the sequence of operations proposed in the CALIC invention, where the coding of error modules and signs is performed together.

Closest to the claimed invention is the standard JPEG-2000 ("Information Technology JPEG 2000 image coding system: Core coding system," ISO / IEC 15444-1: 2004, Dec. 2009), which contains a description of the image compression method having a special mode for compression lossless, consisting of the following operations: procedures for representing encoded values in the form of bit planes and layer-by-layer entropy encoding of values from bit layers, which uses context modeling and a binary arithmetic encoder - MQ encoder. The concept of representing values in the form of binary layers with subsequent encoding is similar to the encoding procedure from the claimed compression method. But, unlike the compression algorithm from the JPEG-2000 standard, in the claimed image encoding method, the described method of representing values in the form of binary layers allows the use of data from previously processed layers when performing context modeling for values of prediction error modules to increase the degree of compression of the processed data.

Despite the fact that significant success has been achieved in image compression, the task of developing new methods of image compression remains urgent.

SUMMARY OF THE INVENTION

The claimed inventions are connected by a single inventive concept.

The technical result of the claimed first invention is a lossless image compression method with a high compression ratio.

The first image compression method is characterized in that initially, for each of the pixels of the input image, a prediction error value is determined, which is then generated as a pair of values: the value of the prediction error modulus and the value of the prediction error sign. Then, the error modulus value of each of the pixels of the entire image is displayed in a binary sequence in accordance with the unary code. The resulting set of binary sequences is represented as a set of binary levels formed from binary values whose ordinal positions in the code coincide with the number of the corresponding binary level. At each binary level, contextual modeling is performed for each bit, using the bit values of the display of the values of the error modules of neighboring pixels at this and the previous binary level of the unary code. Next, contextual modeling is performed for the error sign values of each pixel of the image, using the values of the prediction error signs of neighboring pixels. And then generated using context modeling performed for the values of the modules and signs of the prediction errors, the binary streams are processed by compression with a binary arithmetic encoder.

In the particular case, when generating the value of the prediction error sign, the value of the prediction error modulus for the same pixel is taken into account. When the value of the module equal to "0", the value of the sign is not encoded.

When displaying the value of the error modulus of each of the pixels in a unary code, a binary sequence is formed in which the number “0” corresponds to the value of the error modulus and the service value “1” at the end of the sequence of “0”.

They also process values from binary levels, one level after another, starting from a level formed from binary values selected from the first ordinal position of the unary code of the prediction error module for each pixel.

In addition, they process values from the binary level only at those positions where binary values of the prediction error module are present. Thus, at binary levels located above the binary level at which “1” was in this position, this position will not be processed.

In particular, information about the positions at which the processed values are located is transmitted from the previous processed binary level.

In context modeling performed for each bit subjected to coding at the current level, in one case, bits are used to display the error modulus values of the four nearest pixels from the current binary level, which are located to the left and above the current position, as well as the four nearest pixels from the previous binary level, which are located to the right and below the current position.

In contextual modeling performed for each bit subjected to coding at the current level, in another case, bits are used to display the error modulus values of the ten nearest pixels from the current binary level, which are located to the left and above the current position, as well as the ten nearest pixels from the previous binary level, which are located to the right and below the current position.

In context modeling performed for the values of the signs of the prediction errors, in one case, the values of the signs of the four nearest already processed prediction errors are used.

In context modeling performed for the sign values of the prediction errors, in another case, the sign values of the six closest prediction errors already processed are used.

The technical result of the claimed second invention is to increase the encoding speed without loss of image compared to the first invention with minor changes in the degree of image compression, especially when processing images with a large dynamic range in brightness.

The second image compression method is characterized in that initially, for each of the pixels of the input image, a prediction error value is determined, which is then generated as a pair of values: the value of the prediction error modulus and the value of the prediction error sign. Next, the error modulus value of each of the pixels of the entire image is displayed in a binary sequence in accordance with a unary code. The resulting set of binary sequences is represented as a set of binary levels formed from binary values whose ordinal positions in the code coincide with the number of the corresponding binary level. Next, contextual modeling is performed for each bit, using the values of the bits for displaying the values of the error modules of neighboring pixels at this and the previous binary level of the unary code for those binary levels for which the value of the image prediction error module does not exceed a certain threshold. At the other binary levels, the raw values are converted into binary code and contextualized for the values of the resulting binary code. Context modeling is performed for the prediction error sign values for each image pixel, taking into account the prediction error sign values of neighboring pixels. And then generated using context modeling performed for the values of the modules and signs of the prediction errors, the binary streams are processed by compression with a binary arithmetic encoder.

In the particular case, when generating the value of the prediction error sign, the value of the prediction error modulus for the same pixel is taken into account. When the value of the module equal to "0", the value of the sign is not encoded.

When displaying the value of the error module of each of the pixels in a unary code, a binary sequence is formed in which the number “0” corresponds to the value of the error module and the service value “1” at the end of the sequence of “0”.

They also process values from binary levels, one level after another, starting from a level formed from binary values selected from the first ordinal position of the unary code of the prediction error module for each pixel.

In addition, they process values from the binary level only at those positions where binary values of the prediction error module are present. Thus, at binary levels located above the binary level at which “1” was in this position, this position will not be processed.

In particular, information about the positions at which the processed values are located is transmitted from the previous processed binary level.

In contextual modeling performed for the error modulus values of each pixel, in one case, bits are used to display the error modulus values of the four nearest pixels from the current binary level, which are located to the left and above the current position, as well as the four nearest pixels from the previous binary level, which are located to the right and below the current position.

In context modeling performed for the error modulus values of each pixel, in the other case, the bits of the error modulus values of the ten nearest pixels from the current binary level, which are located to the left and above the current position, as well as the ten nearest pixels from the previous binary level, which are located to the right, are used and below the current position.

In context modeling performed for the sign values of the prediction errors of each pixel, in one case, the sign values of the four nearest already processed prediction errors are used.

In context modeling performed for the sign values of the prediction errors of each pixel, in the other case, the sign values of the six closest already processed prediction errors are used.

In addition, the said threshold when performing contextual modeling is determined in advance and is considered a parameter set by the user in order to control the speed of the compression algorithm.

In this case, the values from binary levels composed of the values of the unary code, whose sequence numbers in the code exceed the specified threshold, are displayed in binary sequences in accordance with the uniform code.

In contextual modeling performed for the values of the obtained binary code, information about the position of the binary value in the uniform code is used.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is illustrated by drawings.

In FIG. 1 shows a general block diagram of an image compression method.

In FIG. 2 shows a diagram for generating a prediction error modulus and a prediction error sign.

In FIG. 3 is a flowchart of processing values of prediction error moduli according to the first invention.

In FIG. 4 is a flow diagram of processing values of prediction error units in the second invention.

In FIG. 5 is a drawing explaining the process of generating a set of binary levels from the values of the prediction error modules.

In FIG. 6 is a drawing explaining the processing order of binary levels.

In FIG. 7 is a diagram showing a set of available values in context modeling.

In FIG. 8 is a context modeling diagram for prediction error sign values according to a first embodiment of context modeling.

In FIG. 9 is a contextual modeling diagram for prediction error sign values according to a second embodiment of contextual modeling.

In FIG. 10 is a context modeling diagram for binary values according to a first embodiment of context modeling.

In FIG. 11 is a context modeling diagram for binary values according to a second embodiment of context modeling.

In FIG. 12 is a context modeling diagram for binary values according to a third embodiment of context modeling.

MODES FOR CARRYING OUT THE INVENTION

This method can be applied to images consisting of a single component, for example, black and white images, or from several components 1, 2, 3 in the case of color images (Fig. 1). For RGB images, these components will be green, red, and blue, respectively. In this method, sets of prediction errors generated by different color components are compressed independently.

The method for the first implementation of the invention is as follows.

The image consists of individual pixels. Initially, for each pixel, 4 (Fig. 1) is formed of a prediction error value, which is the difference between the value of the brightness component of the pixel and the predicted value. As a procedure for generating prediction errors, the technique described in one of the known image compression standards can be used (see, for example, MED prediction from the lossless JPEG-LS image compression standard).

Next, the second part is performed - coding of prediction errors 5. Initially (Fig. 2) using a multiplexer 6, a pair of values is formed from each prediction error: the value of the prediction error modulus and the value of the prediction error sign. When generating the value of the prediction error sign, the value of the prediction error modulus for the same pixel is taken into account. When the value of the module equal to "0", the value of the sign is not encoded. Further processing of the prediction error modules 7 and processing of the signs of the prediction error 8 is performed separately.

When processing the values of the prediction error modules, the value of the error module of each of the pixels of the entire image is initially displayed in a binary sequence in accordance with the unary code (Fig. 3). In FIG. Figure 5 shows an example of mapping error module values into a unary code. In the resulting binary sequence, the number “0” corresponds to the value of the prediction error modulus. In addition, at the end of the sequence of "0" is written service value "1". The obtained sequences are presented in the diagram in the form of columns.

, содержащихся на 5 (пятом) уровне двоичного кода, где k - индекс двоичного уровня, (i,j) - координаты значения в двоичном уровне. А значения '-', выделенные серым цветом, показывают отсутствие двоичного значения для данного двоичного уровня на указанной позиции. Производят обработку значений (контекстное моделирование) из двоичного уровня только на тех позициях, на которых присутствуют значения двоичного кода модулей ошибок предсказания. «Пустые» пиксели, выделенные серым цветом, обработке не подвергаются.The resulting set of binary sequences is represented as a set of binary levels 10 formed from binary values, whose ordinal positions in the code coincide with the number of the corresponding binary level. Further processing of values from binary levels is carried out by levels, one after another, starting from the level formed from binary values selected from the first ordinal position of the unary code of the prediction error module for each pixel. This procedure is shown schematically in FIG. 6. At the bottom of the figure, binary sequences from 1 (first) to 5 (fifth) level are shown. At the top of the figure of FIG. 6. shows binary sequences from 6 (sixth) to 14 (fourteenth) level. An example of values is also provided. $$\left(l_{i,j}^{\left(k\right)}\right)$$

contained at the 5th (fifth) level of the binary code, where k is the index of the binary level, (i, j) are the coordinates of the value in the binary level. And the '-' values highlighted in gray indicate the absence of a binary value for a given binary level at the specified position. The values are processed (context modeling) from the binary level only at those positions at which the binary code values of the prediction error modules are present. "Empty" pixels, grayed out, are not processed.

Context modeling involves dividing the original data stream into sub-streams, which will be further processed independently. In context modeling performed for a binary level value at the “X” position, adjacent binary values from the positions shown in FIG. 7 may be used as the context of the pixel at position “X”. In FIG. 7 the positions of binary values taken from the current binary level are highlighted in white, and gray from the previous level. The context model for the processed value is determined by the identification number, calculated as the number of zero neighbors in the context of the current processed value. The context model identification number is calculated using the following formula:

,

,

where N _{i, j} is the set of neighboring positions, the values of which are used as context;

I (.,.) - the following indicator function:

In the first embodiment of the context modeling performed for the value of the prediction error modulus of each pixel, bits of the mapping of the values of the error moduli from the positions highlighted in gray in FIG. 10. In FIG. 10 positions of adjacent values of n, m are replaced by letter representations: N _{i, j} ∈ {A, B, C, D, E, F, G, H}.

In a second embodiment of the context modeling performed for the value of the prediction error modulus of each pixel, bits for displaying the values of the error moduli from the positions highlighted in gray in FIG. 11. What does the following mean:

N _{i, j} ∈ {A, B, C, D, E, F, G, H, NN, NNE, NEE, EE, SEE, SSE, SS, SSW, SWW, WW, NWW, NNW}.

определяется используемый набор контекстных модель. А после этого на основе контекста $$N_{i,j}^{\left(2\right)}$$

определяется используемая контекстная модель из выбранного набора. В качестве контекста для определения используемого набора контекстных моделей используют биты отображения значений модулей ошибок с позиций, выделенных светло-серым цветом на Фиг. 12. В качестве контекста для определения контекстной модели из выбранного набора моделей используют биты отображения значений модулей ошибок с позиций, выделенных темно-серым цветом на Фиг. 12. Что означает следующее:In a third embodiment of the context modeling performed for the value of the prediction error unit of each pixel, a two-level context modeling scheme is used, i.e. based on context first $$N_{i,j}^{\left(\mathrm{one}\right)}$$

the used set of contextual models is determined. And then based on context $$N_{i,j}^{\left(2\right)}$$

the used context model from the selected set is determined. As a context for determining the used set of context models, bits are used to display error module values from the positions highlighted in light gray in FIG. 12. As a context for determining the context model from the selected set of models, bits for displaying error modulus values from the positions highlighted in dark gray in FIG. 12. Which means the following:

As mentioned above, the value of the prediction error sign of each pixel is processed regardless of the value of the prediction error modulus of the same pixel. (Fig. 2, Fig. 3). In the context modeling performed for the sign values of the prediction errors 12, the sign values of the nearest pixels already processed are used as the context. The identification number of the context model is determined by the placement of adjacent signs of the prediction errors and is calculated by the following formula:

,

,

where | Sign | - the power of the set of values of the signs of the prediction error (equal to three);

sign (.,.) - value of the sign of the prediction error at the position

z (.,.) is an index indicating the position of the value used in the context.

In one embodiment of the context modeling performed for the value of the prediction error modulus of each pixel, the sign values of the four nearest already processed pixels from the positions highlighted in gray in FIG. 8. Which means the following: N _{i, j} ∈ {A, B, C, D}

In another embodiment of the context modeling performed for the value of the prediction error modulus of each pixel, the sign values of the six nearest pixels already processed from the positions highlighted in gray in FIG. 9. Which means the following: N _{i, j} ∈ {A, B, C, D, WW, NN}

Next, the binary streams generated by context modeling using the values of the moduli and the signs of the prediction errors are processed (Fig. 3) by compression by the arithmetic encoder 13. This operation is performed by known methods. As an example of using this technique to compress data streams generated using contextual modeling, we can consider encoding procedures (methods) from the JPEG-2000 still image compression standard ("Information Technology JPEG 2000 image coding system: Core coding system," ISO / IEC 15444-1: 2004, Dec. 2009) and the H.264 video sequence compression standard ("The H.264 Advanced Video Compression Standard", lain E. Richardson, ISBN: 978-0-470-51692-8, 2010).

A second embodiment of the invention is shown in FIG. 4. The present invention differs from the first only in that the context modeling procedure 101 is performed only for binary levels formed from binary values of a unary code whose ordinal positions in the code do not exceed a predetermined threshold. When performing context modeling, the mentioned threshold is determined in advance and is considered a parameter set by the user in order to control the speed of the compression algorithm. At the remaining binary levels, the raw values are converted to binary code 102 and contextualized for the values of the resulting binary code 103.

In this case, the values from binary levels composed of the values of the unary code, whose sequence numbers in the code exceed the specified threshold, are displayed in binary sequences in accordance with the uniform code.

In contextual modeling performed for the values of the obtained binary code, information about the position of the binary value in the uniform code is used.

Next, the binary streams generated by context modeling by the values of the moduli and the signs of the prediction errors are processed by compression by an arithmetic encoder, by analogy with the first implementation of the invention.

INDUSTRIAL APPLICABILITY

The invention can be used to compress images in various fields of technology, including compression of still images and video sequences. The most effective application of these methods for compressing naturalistic and medical images.

Claims (23)

1. An image compression method, characterized in that initially, for each of the pixels of the input image, a prediction error value is determined, a pair of values is formed: a prediction error modulus value and a prediction error sign value;
- display the value of the error modulus of each of the pixels of the entire image in a binary sequence of a unary code;
- the resulting set of binary sequences is represented as a set of binary levels formed from binary values whose ordinal positions in the code coincide with the number of the corresponding binary level;
- contextual modeling is performed at each binary level for the values of the prediction error modules of each pixel, using the values of neighboring prediction error modules at the given and previous binary level of the unary code;
- make contextual modeling for the values of the error signs for each image pixel, using the values of the error signs of the prediction of neighboring pixels;
- and then generated using context modeling performed for the values of the modules and the signs of the prediction errors, the binary streams are processed by compression with a binary arithmetic encoder. 2. The method according to claim 1, characterized in that when generating the value of the prediction error sign, the value of the prediction error modulus for the same pixel is taken into account, when the value of the prediction error modulus is “0”, the sign value is not encoded. 3. The method according to claim 1, characterized in that when displaying the value of the prediction error module of each of the pixels in a unary code, a binary sequence is formed in which the number “0” corresponds to the value of the error module and the service value “1” at the end of the sequence from “0 ". 4. The method according to claim 1, characterized in that they process the values from the binary levels, one level after another, starting from the level formed from the binary values selected from the first ordinal position of the unary code of the prediction error module for each pixel. 5. The method according to p. 1, characterized in that they process the values from the binary level only at those positions where the values of the binary code of the prediction error module are present. 6. The method according to p. 5, characterized in that information about the positions at which the processed values are transmitted from the previous processed binary level. 7. The method according to claim 1, characterized in that in the context modeling performed for the error modulus values of each pixel, bits are used to display the error modulus values of the four nearest pixels from the current binary level, which are located to the left and above the current position, as well as the four nearest pixels from the previous binary level, which are located to the right and below the current position. 8. The method according to claim 1, characterized in that in the context modeling performed for the values of the prediction error modules of each pixel, bits are used to display the values of the prediction error modules of the ten nearest pixels from the current binary level, which are located to the left and above the current position, and ten nearest pixels from the previous binary level, which are located to the right and below the current position. 9. The method according to claim 1, characterized in that in the context modeling performed for the sign values of the prediction errors of each pixel, the sign values of the four nearest already processed pixels are used. 10. The method according to p. 1, characterized in that in context modeling performed for the values of the signs of the prediction errors of each pixel, use the values of the signs of the six nearest pixels already processed. 11. An image compression method, characterized in that initially, for each of the pixels of the input image, a prediction error value is determined, a pair of values is formed: a prediction error modulus value and a prediction error sign value;
- display the value of the error modulus of each of the pixels of the entire image in a binary sequence of a unary code;
- the resulting set of binary sequences is represented as a set of binary levels formed from binary values whose ordinal positions in the code coincide with the number of the corresponding binary level;
- make contextual modeling for the values of the error prediction modules of each pixel, taking into account the values of neighboring pixels at a given and previous binary level of a unary code for binary levels formed from binary values of a unary code whose ordinal positions in the code do not exceed a predetermined threshold;
- on the remaining binary levels, the raw values are converted into binary code and contextual modeling is performed for the values of the resulting binary code;
- make contextual modeling for the values of the signs of the prediction error for each image pixel, taking into account the values of the signs of the prediction error of neighboring pixels;
- and then generated using context modeling performed for the values of the modules and the signs of the prediction errors, the binary streams are processed by compression with a binary arithmetic encoder. 12. The method according to p. 11, characterized in that when generating the value of the prediction error sign, the value of the prediction error modulus for the same pixel is taken into account, when the module value is “0”, the sign value is not encoded. 13. The method according to p. 11, characterized in that when displaying the error modulus values of each of the pixels in accordance with the unary code, a binary sequence is formed in which the number “0” corresponds to the value of the error modulus and the service value “1” at the end of the sequence from “ 0 ". 14. The method according to claim 11, characterized in that they process the values from binary levels, one level after another, starting from a level formed from binary values selected from the first ordinal position of the unary code of the prediction error module of each pixel. 15. The method according to p. 11, characterized in that they process the values from the binary level only at those positions where the values of the binary code of the prediction error module are present. 16. The method according to p. 15, characterized in that information about the positions at which the processed values are transmitted from the previous processed binary level. 17. The method according to claim 11, characterized in that in context modeling performed for the error modulus values of each pixel, bits are used to display the error modulus values of the four nearest pixels from the current binary level, which are located to the left and above the current position, as well as the four nearest pixels from the previous binary level, which are located to the right and below the current position. 18. The method according to p. 11, characterized in that in the context modeling performed for the error modulus values of each pixel, bits are used to display the error modulus values of the ten nearest pixels from the current binary level, which are located to the left and above the current position, as well as the ten nearest pixels from the previous binary level, which are located to the right and below the current position. 19. The method according to claim 11, characterized in that in context modeling performed for the sign values of the prediction errors of each pixel, the sign values of the four nearest pixels already processed are used. 20. The method according to p. 11, characterized in that in the context modeling performed for the sign values of the prediction errors of each pixel, the sign values of the six nearest pixels already processed are used. 21. The method according to p. 11, characterized in that the said threshold when performing context modeling is determined in advance and is considered a parameter set by the user in order to control the speed of the compression algorithm. 22. The method according to p. 11, characterized in that the values of the binary levels composed of the values of the unary code, whose sequence numbers in the code exceed a predetermined threshold, are displayed in binary sequences in accordance with a uniform code. 23. The method according to p. 22, characterized in that in context modeling performed for binary values of a uniform code, information about the position of the binary value in the uniform code is used.

Images