JPH0865523A - Method for encoding binary pseudo gradation image - Google Patents

Abstract

PURPOSE: To improve encoding efficiency of picture quality. CONSTITUTION: A predicting state calculating part 11 executes gradation value estimation for a given pixel (m) based on the symbol pattern of a reference image R close to the pixel (m) and a threshold matrix (Dxy) being binary structure and finds out a distance between the estimated gradation value and a threshold at the time of preparing a binary pseudo gradation image for the pixel (m) as a predicting state of the pixel (m). A Markov probability estimating part 12 estimates the symbol appearance probability ps of the picture element (m) in a predicting state discriminated by an index. When the symbol appearance probability ps of the pixel (m) is smaller than a 1st previously set value ε and a distance value is smaller than a 2nd previously set value η, a binary symbol changing part 14 inverts the symbol of the pixel (m) stored in a binary pseudo gradation image buffer part 1. An arithmetic encoder 13 encodes the symbol appearance probability ps as an encoding parameter.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of encoding a binary pseudo gradation image composed of binary symbols created by using a threshold matrix for a multi-value gradation image.

[0002]

2. Description of the Related Art Conventionally, techniques in such a field include:
For example, some documents were described in the following documents. Reference: Hiroshi Yasuda, 1991, "International Standard for Multimedia Coding", Maruzen multi-value gradation image is created as follows by using a threshold matrix {Dxy}.

[0003]

[Equation 1] FIG. 2 is a block diagram of an encoder for implementing the encoding method of the binary pseudo gradation image created by the procedure described in the above-mentioned document.

As shown in FIG. 2, this encoder is a binary pseudo gradation image buffer 1 for storing a binary pseudo gradation image binarized by a threshold value {Dxy} of a multi-value gradation image IN. , Markov probability estimation unit 2 and arithmetic code construction unit 3. On the output side of the binary pseudo image buffer 1, a Markov probability estimation unit 2 for obtaining the symbol appearance probability p _s of the pixel of interest m, and an arithmetic code construction unit 3 for creating an arithmetic code are connected. An arithmetic code construction unit 3 is connected to the output side of the Markov probability estimation unit 2. The arithmetic code C is output from the arithmetic code construction unit 3. Next, a conventional method of encoding a binary pseudo gradation image will be described with reference to FIG. In the Markov probability estimation unit 2, the target pixel m is stored for each symbol state of the pixels of the template t, which is a set of reference pixels near the target pixel m stored in the binary pseudo-tone image buffer 1.
The symbol appearance probability p _s is calculated and the symbol appearance probability p _s is output to the arithmetic code construction unit 3. The arithmetic code construction unit 3 obtains the arithmetic code C based on the symbol appearance probability p _s of the pixel of interest m and the symbol of the pixel of interest m, and outputs it to the transmission path or the storage medium.

[0005]

However, the conventional method for encoding a binary pseudo gradation image has the following problems. If the size M × M of the threshold matrix is set to be large with respect to the correlation distance, which is the distance between pixels having a correlation,
Since the periodic structure does not appear in the value pseudo-gradation image, the symbol appearance probability p _s of the symbol value of the pixel of interest _m becomes small and the arithmetic coding length becomes long, which causes a problem that the coding efficiency decreases. there were. In order to solve the above-mentioned problems, the present applicants have described in the specification of Japanese Patent Application No. 6-22235 (hereinafter referred to as the above-mentioned proposal) a binarized threshold matrix {D
xy} structure is traced back to the tone value of the binarized original image as a symbol appearance prediction state, and the prediction state is input to obtain the symbol appearance probability by the Markov probability estimator. The coding efficiency is improved by using the bias of the symbol appearance probability that does not appear explicitly. However, in the previous proposal, coding the symbol in the pixel to be coded significantly lowers the coding efficiency, but coding the symbol using the inverted symbol does not lower the coding efficiency, There are some that have little effect on the quality of the image, and they are not satisfactory in terms of coding efficiency with respect to the image quality.

[0006]

In order to solve the above-mentioned problems, the present invention provides a binary image created by binarizing a multi-value gradation image by a threshold matrix of m × n (m and n are natural numbers). In the encoding method of a binary pseudo gradation image composed of
The following processing is executed in order. That is, the gradation value of the target pixel is estimated from the symbol pattern in the vicinity of the target pixel to be encoded and the threshold matrix, and the binarized threshold value is associated with the estimated gradation value and the coordinates of the target pixel. A prediction state calculation process that calculates a distance between the target pixel and the prediction state of the pixel of interest, a Markov probability estimation process that estimates binary symbol appearance probabilities for each prediction state, and a symbol of the pixel of interest. The value symbol appearance probability is smaller than the first preset value, and the prediction state distance of the pixel of interest is the second value.
When it is smaller than the preset value of, the symbol value of the pixel of interest is inverted, and a binary symbol change process in which the inverted symbol value is the symbol value of the pixel of interest, the symbol appearance probability and the symbol value of the pixel of interest And an arithmetic code configuration process for creating an arithmetic code of a binary symbol based on the above. Then, the gradation of the pixel of interest is estimated from the already decoded symbol pattern near the pixel of interest to be decoded and the threshold matrix, and the binary value corresponding to the estimated gradation value and the coordinates of the pixel of interest is binarized. Calculated distance from the threshold,
A prediction state calculation process that uses the distance as the prediction state of the pixel of interest, a Markov probability estimation process that estimates each binary symbol appearance probability of the pixel of interest that is decoded for each prediction state, and the arithmetic code. Arithmetic decoding processing for decoding the symbol of the pixel of interest based on the symbol appearance probability of the pixel of interest is executed.

[0007]

According to the present invention, since the coding method of the binary pseudo gradation image is configured as described above, the prediction state calculation process is performed to focus on the symbol pattern and the threshold matrix in the vicinity of the target pixel to be coded. The gradation value of the pixel is estimated, the distance between the estimated gradation value and the binarized threshold value corresponding to the coordinates of the pixel of interest is calculated, and this distance is set as the prediction state of the pixel of interest. By the Markov probability estimation process, the symbol appearance probability of the pixel of interest is obtained from the predicted state of the pixel of interest. Since the prediction state is calculated based on the state that has been traced back to the tone value of the original image, the symbol appearance probability reflects the bias of the symbol appearance probability that does not appear explicitly in the image signal. When the symbol appearance probability of the symbol value of the pixel of interest is smaller than the first preset value and the distance of the prediction state of the pixel of interest is smaller than the second preset value by the binary symbol changing process, Invert the value of the pixel symbol. Comparing the symbol appearance probability with the first preset value is
In order to prevent the coding efficiency from decreasing due to the low symbol appearance probability of the pixel of interest, the symbol appearance probability (1
-Probability of symbol appearance before inversion) is increased. The comparison between the threshold value of the pixel of interest, the estimated gradation value distance, and the second preset value is for preventing the quality of the decoded image from deteriorating.
By the arithmetic code configuration processing, a binary symbol arithmetic code is created based on the symbol appearance probability after inversion (1-the symbol appearance probability before inversion) and the value of the symbol of the pixel of interest. The prediction state calculation process estimates the gradation of the pixel of interest from the already decoded symbol pattern near the pixel of interest to be decoded and the threshold matrix, and corresponds to the estimated gradation value and the coordinates of the pixel of interest. Then, the distance from the binarized threshold value is calculated, and the predicted state of the pixel of interest is calculated from the distance. The Markov probability estimation process estimates the symbol appearance probability of the pixel of interest to be decoded from the prediction state calculated by the prediction state calculation process. By the arithmetic decoding process, the symbol of the target pixel is decoded based on the arithmetic code and the symbol appearance probability of the target pixel. Therefore, the above problem can be solved.

[0008]

EXAMPLE In this example, first, the outline (I) and the problem (II) of the previously proposed binary pseudo gradation image encoding method will be described, and then the problem will be solved. An embodiment (III) of the encoding method of the binary pseudo gradation image of the present invention will be described. (I) Embodiment of Encoding Method of Previously Proposed Binary Pseudo-tone Image FIG. 3 is a block diagram of an encoder for implementing the previously proposed encoding method of a binary pseudo-tone image. is there. This encoder has a binary pseudo gradation image buffer 1 for storing the binary pseudo gradation image created by the threshold matrix {Dxy} of the multi-value gradation image IN. To the output side of the binary pseudo gradation image buffer 1, a probability model unit 10 and an arithmetic code construction unit 13 are connected. The probability model unit 10 includes a prediction state calculation unit 11 connected to the output side of the binary pseudo gradation image buffer 1.
And a Markov probability estimation unit 12 connected to the output side of the prediction state calculation unit 11. An arithmetic code construction unit 13 is connected to the output side of the Markov probability estimation unit 12. The arithmetic code C is output from the arithmetic code configuration unit 13. m is a target pixel, and R is a reference pixel in the vicinity of the target pixel m for calculating the prediction state of the target pixel m. Two
The value pseudo-gradation image buffer 1 has a value of 2 before the pixel of interest m.
The value pseudo gradation image is held for the area referred to by the prediction state calculation unit 11. The prediction state calculation unit 11 estimates the gradation value of the pixel of interest m from the symbol pattern in the vicinity of the pixel of interest m to be encoded and the threshold matrix {Dxy}, and uses the estimated gradation value and the coordinates of the pixel of interest m as coordinates. Correspondingly, the distance from the binarized threshold value is calculated and the distance is set as the prediction state of the pixel of interest m.
The Markov probability estimation unit 12 determines the pixel of interest m in each prediction state.
Estimate the symbol appearance probability of. Arithmetic code construction unit 13
Is 2 with the symbol appearance probability p _s as an encoding parameter.
Create the arithmetic sign of the value symbol.

Next, the previously proposed method for encoding a binary pseudo gradation image will be described with reference to FIG. The binary pseudo gradation image to be encoded is input to the prediction state calculation unit 11 through the binary pseudo gradation image buffer unit 1. The prediction state calculation unit 11 estimates the gradation value of the pixel of interest m from the symbol pattern of the reference image R near the pixel of interest m to be encoded and the structure of binarization, that is, the threshold matrix {Dxy}. 2 corresponding to the estimated gradation value and the coordinates of the pixel of interest m
The distance from the binarized threshold value is obtained as the prediction state of the pixel of interest m. Estimation of the gradation value of the target pixel m is the n _max the number of gradations of the threshold matrix {Dxy}, pixels near the target pixel m R
Of n _max uniform gradation images having the same gradation value of, when binarization is performed with each threshold of the threshold matrix {Dxy} corresponding to each coordinate in the vicinity of the pixel of interest m. The estimated gradation value is determined by setting the symbol pattern in the vicinity of the pixel of interest m that most closely matches the symbol pattern of the pseudo gradation image to be encoded. The measure of symbol pattern matching is

[Equation 2] And

Here, R is the coordinate (x, y) of the pixel m of interest.
It is a reference pixel area of the pixel of interest m including earlier pixels, and (x ', y') = (x + Δx, y + Δy), d (x ', y') is uniform at coordinates (x ', y'). The binary symbol of the gradation image and the binary pseudo gradation image (x ', stored in the binary pseudo gradation image buffer 1
A variable that takes 1 when the symbols of y ') match and 0 when they do not match, C _x'y' is a weighting coefficient. For example, the closer to the pixel m of _interest , the larger the value. It is determined that the larger the matching scale is, the higher the matching level is. The distance between this estimated gradation value and the threshold value of the target pixel m is obtained as the prediction state of the target pixel m. Each prediction state is identified by an index, and the index of the pixel of interest m is output to the Markov probability estimation unit 12. The Markov probability estimation unit 12 estimates the symbol appearance probability p _s of the pixel of interest m in the prediction state identified by the index, and outputs this symbol appearance probability p _s to the arithmetic encoder 13. The symbol appearance probability p _s is calculated for each prediction state as the ratio of the number of appearances of each of the symbol “0” and the symbol “1” to the number of appearances of the prediction state. Here, _assuming that the appearance probability of the symbol “0” is p _s (0), the appearance probability p of the symbol “1” is p
_s (1) becomes 1- _ps (0). The arithmetic encoder 13 adopts, from the symbol value of the pixel of interest m in the binary pseudo gradation image buffer 1, the symbol appearance probability p _s of the symbol value. Then, the arithmetic encoder 13 creates an augent from the adopted symbol appearance probability p _s and the symbol value of the pixel of interest m, and encodes the left end point coordinate of this augent to output the arithmetic code C.

(II) Problems of the above proposal However, in the encoding method of the above proposal, the symbol appearance of the symbol value of the pixel of interest m estimated by the Markov probability estimation unit 12 may occur depending on the binary pseudo gradation image. Probability p _s
May be low, which may result in a significant decrease in coding efficiency. On the other hand, if a symbol whose probability of symbol appearance becomes low is inverted and the inverted symbol is encoded, not only the coding efficiency is not lowered, but also the decoded image quality is almost the same as the non-inverted image quality. There were cases like this. That is, the encoding method proposed above is not satisfactory in terms of encoding efficiency with respect to image quality. (III) Embodiment of the present invention FIG. 1 is a block diagram of an encoder for carrying out an encoding method showing an embodiment of the present invention, in which elements similar to those of the previous proposal of FIG. It is attached with a code. The encoder of this embodiment is different from the previously proposed encoder in that the symbol appearance probability p _s of the symbol of the pixel of interest m estimated by the Markov probability estimation unit 12 is smaller than the first preset value. And the distance of the prediction state of the pixel of interest m is the second preset value η
When it is smaller than the above, the binary symbol changing unit 14 for inverting the value of the symbol of the pixel of interest m is provided. As shown in FIG. 1, this encoder is provided with a binary symbol changing unit 22. The binary symbol changing unit 22
It is connected to the input / output side of the binary pseudo gradation image buffer 1 and the output side of the Markov probability estimation unit 21.

FIG. 4 is a block diagram of a decoder for decoding the code encoded by the binary pseudo gradation image encoding method according to the embodiment of the present invention. As shown in FIG. 4, this decoder comprises a probability model unit 20, an arithmetic decoding unit 23, and a binary pseudo gradation image buffer 24. The probability model unit 20 includes a prediction state calculation unit 21 that calculates a prediction state and a symbol appearance probability p _{s of the} pixel of interest m to be decoded that is connected to the output side of the prediction state calculation unit 21.
And a Markov probability estimation unit 22 for calculating The arithmetic decoding unit 23 is provided on the output side of the Markov probability estimation unit 22.
Is connected to the output side of the arithmetic decoding unit 23, and
A value pseudo gradation image buffer 24 is connected. The binary pseudo-tone image buffer 1 predicts the binary pseudo-tone image decoded before the pixel of interest m to be decoded by the prediction state calculation unit 2.
The area referred to in 1 is retained. The prediction state calculation unit 21 estimates the gradation value of the pixel of interest m from the symbol pattern in the vicinity of the pixel of interest m to be decoded and the threshold matrix {Dxy}, and uses this estimated gradation value and the coordinates of the pixel of interest m as coordinates. Correspondingly, the distance from the binarized threshold value is calculated and the distance is set as the prediction state of the pixel of interest m. The Markov probability estimation unit 22 estimates the symbol appearance probability of the pixel of interest m in each prediction state. The arithmetic decoding unit 23 creates a binary symbol arithmetic code using the symbol appearance probability p _s as an encoding parameter.

Next, the encoding method according to the embodiment of the present invention will be described with reference to FIG. The binary pseudo gradation image to be encoded is input to the prediction state calculation unit 11 through the binary pseudo gradation image buffer unit 1. In the prediction state calculation unit 11, the symbol pattern of the reference image R in the vicinity of the pixel of interest m to be encoded and the threshold matrix {Dxy} which is a binary structure.
Then, the gradation value of the pixel of interest m is estimated, and the distance between the estimated gradation value and the threshold at the time of creating the binary pseudo gradation image of the pixel of interest m is obtained as the prediction state of the pixel of interest m. And
In the prediction state calculation unit 11, each prediction state can be identified by an index, and the index of the pixel of interest m is output to the Markov probability estimation unit 22. Estimation of the gradation value of the target pixel m is the n _max the number of gradations of the threshold matrix {Dxy}, the uniform tone of equal gradation values of the pixels in the vicinity of n _{ma x-number} of the target pixel m Among them, the estimated gradation value is the one whose symbol pattern in the vicinity of the pixel of interest m, which is binarized with a threshold value in the vicinity of the pixel of interest m, most closely matches the symbol pattern of the pseudo gradation image to be encoded. To do.

The Markov probability estimating unit 12 estimates the symbol appearance probability p _s at the pixel of interest m in the prediction state identified by the index, and outputs the index and the symbol appearance probability to the binary symbol changing unit 21. The binary symbol changing unit 14 refers to the symbol of the target pixel m of the binary pseudo gradation image buffer 1 and adopts the symbol appearance probability p _s of the symbol of the target pixel m. Then, the binary symbol changing unit 14 refers to the symbol appearance probability p _s of the symbol of the pixel of interest m and the prediction state identified by the index, that is, the value of the distance, and the appearance probability p of the symbol value of the pixel of interest m. _{If s} is smaller than the first preset value ε and the distance value is smaller than the second preset value η, the symbol of the pixel of interest m in the binary pseudo gradation image buffer unit 1 is inverted. Here, in comparing the symbol appearance probability p _s of the symbol of the pixel of interest m with the first preset value ε, the symbol appearance probability is increased by inverting the symbol of the pixel of interest m to improve the coding efficiency. This is to allow it. Also, the comparison between the distance value and the second preset value η is
This is because the image quality is not deteriorated. Arithmetic encoder 13
Then, the symbol appearance probability p _s of the symbol value of the pixel of interest m in the binary pseudo image buffer 1 is adopted. At this time, if the symbol of the pixel of interest m is inverted, the inverted larger symbol appearance probability is adopted. Then, in the arithmetic encoder 13, the symbol appearance probability p _s and the pixel of interest m
The symbol is used to create an augent, the coordinates of the left end point of this augent are encoded, and the arithmetic code C is output.
The pixel of interest m is moved from left to right and from top to bottom in the scanning order of the image, and all pixels are encoded.

Next, referring to FIG. 4, a method of decoding the code encoded by the above encoding method will be described.
The binary pseudo gradation image decoded by the arithmetic decoding unit 23 is input to the prediction state calculation unit 21 through the binary pseudo gradation image buffer 24. Similar to the case of encoding, the prediction state calculation unit 21 calculates the floor of the pixel of interest m from the symbol pattern of the reference image R near the pixel of interest m to be decoded and the threshold matrix {Dxy} which is a binarization structure. Tone value estimation is performed, and the distance between the estimated gradation value and the threshold value when the binary pseudo gradation image of the pixel of interest m is created is obtained as the prediction state of the pixel of interest m. The Markov probability estimation unit 22 estimates the symbol appearance probability p _s of the pixel of interest m in this prediction state, as in the case of encoding. The calculation decoding unit 23 decodes the binary symbol from the arithmetic code C using the symbol appearance probability p _s of the pixel of interest m as a decoding parameter, and outputs it.
The pixel of interest m is moved from the left to the right and from the top to the bottom in the order of the scanning line of the image, and the decoding of all the pixels is executed. When the reference pixel R exists outside the image, the uniqueness of the decoding is guaranteed by setting a common boundary condition for the encoding and the decoding.

Simulation Results Next, the simulation results of the encoding method of the binary pseudo gradation image of this embodiment will be shown. 5A and 5B are coded images (300 dp) showing the results of the simulation experiment.
(i, 2 times enlargement), FIG. 7A is an encoded image by the previously proposed encoding method, and FIG. 7B is an encoded image by the encoding method in the simulation. is there. FIG. 6 is a diagram showing reference images in a simulation experiment used by the prediction state calculation units 11 and 21. [Simulation conditions] Image: SCID (Standard Color Image Data) No. Two
Part of (8 bits) (512 × 512) (shown in FIG. 6) First preset value ε = 0.05 Second preset value η = 16 Reference image in gradation value estimation: Shown in FIG. . Size of threshold matrix {Dxy}: 64 × 64 Maximum of gradation values of threshold matrix {Dxy} n _max = 16 Markov probability estimation unit 12, 22: Markov probability estimation unit of QM-Coder Arithmetic code configuration unit 13: QM Arithmetic code constituent part of -Coder Weighting coefficient C _{x'y '} : 1 for all pixels [Simulation result] 11.2% without deterioration of image quality as shown in FIG.
The code amount could be reduced. As described above, in this embodiment, after the pixel to be encoded, the pixel symbol s thereof is encoded to significantly reduce the encoding efficiency, and even if the pixel symbol s is inverted, the image quality is hardly affected. There is an advantage that it is possible to improve the coding efficiency without degrading the image quality by detecting the missing one and inverting the symbol of the pixel. The present invention is not limited to the above embodiment, and various modifications can be made. The following are examples of such modifications. (1) This embodiment is a facsimile, a DTP system, etc., and can be used in a data compression encoding unit for the purpose of reducing transmission / storage costs. (2) The size of the threshold matrix {Dxy} may be different vertically and horizontally.

[0017]

As described above in detail, according to the present invention, a binary symbol created by binarizing a multi-value gradation image by a threshold matrix of m × n (m and n are natural numbers) is created. In the method of encoding a binary pseudo gradation image, the gradation value of the pixel of interest is estimated from the symbol pattern near the pixel of interest to be encoded and the threshold matrix, and the estimated gradation value and the pixel of interest are estimated. A prediction state calculation process that calculates a distance from a binarized threshold value corresponding to the coordinates, and uses this distance as the prediction state of the pixel of interest; a Markov probability estimation process that estimates the symbol appearance probability for each prediction state; When the symbol appearance probability of the pixel of interest is smaller than the first preset value and the distance of the prediction state of the pixel of interest is smaller than the second preset value, the value of the symbol of the pixel of interest is inverted and then inverted. The symbol value is the symbol of the pixel of interest. Since to perform the binary symbol changing process for a, it is possible to improve the encoding efficiency for image quality.

[Brief description of drawings]

FIG. 1 is a configuration diagram of an encoder for implementing a method of encoding a binary pseudo gradation image according to an embodiment of the present invention.

FIG. 2 is a configuration diagram of an encoder for implementing a conventional binary pseudo gradation image encoding method.

FIG. 3 is a configuration diagram of an encoder for implementing the previously proposed binary pseudo-tone image encoding method.

FIG. 4 is a configuration diagram of a decoder for carrying out a binary pseudo gradation image encoding method according to an embodiment of the present invention.

FIG. 5 is a diagram of a coded image (300 dpi, double magnification) showing the results of a simulation experiment.

FIG. 6 is a diagram of a reference image in a simulation experiment.

[Explanation of symbols]

 1,24 Binary pseudo gradation image buffer 10,20 Probability model part 11,21 Prediction state calculation part 12,22 Markov probability estimation part 13 Arithmetic code construction part 14 Binary symbol changing part 23 Arithmetic decoding part

Claims (1)

[Claims] 1. A coding method for a binary pseudo-gradation image composed of binary symbols created by binarizing a multi-value gradation image by a threshold matrix of m × n (m and n are natural numbers), The gradation value of the pixel of interest is estimated from the symbol pattern near the pixel of interest to be encoded and the threshold matrix, and the estimated gradation value and the binarized threshold value corresponding to the coordinates of the pixel of interest. A prediction state calculation process of calculating a distance and using the distance as a prediction state of the pixel of interest, a Markov probability estimation process of estimating binary symbol appearance probabilities for each of the prediction states, and a symbol value of the pixel of interest. When the symbol appearance probability is smaller than the first preset value and the distance of the prediction state of the pixel of interest is smaller than the second preset value, the symbol value of the pixel of interest is inverted, and the symbol value of the inverted symbol is inverted. The value is the pixel of interest A binary symbol changing process for generating a binary value, an arithmetic code constructing process for creating an arithmetic code of a binary symbol based on the symbol appearance probability and the symbol value of the pixel of interest, and The gradation of the pixel of interest is estimated from the decoded symbol pattern and the threshold matrix, and the distance between the estimated gradation value and the binarized threshold corresponding to the coordinates of the pixel of interest is calculated. A prediction state calculation process that uses a distance as the prediction state of the pixel of interest, a Markov probability estimation process that estimates each binary symbol appearance probability of the pixel of interest that is decoded for each prediction state, the arithmetic code, and An encoding method of a binary gradation image, characterized in that an arithmetic decoding process for decoding a symbol of a pixel of interest based on a symbol appearance probability of the pixel of interest is sequentially executed.