JPH046954A - Image predictive coding method - Google Patents

Abstract

PURPOSE:To attain efficient picture coding suitable for an input picture by discriminating whether or not an area in the vicinity of a noted picture element is a pseudo intermediate tone picture and selecting a reference picture element template for a pseudo intermediate tone picture and that for a general picture adaptively based on the discrimination. CONSTITUTION:An inputted binary signal string is stored in a line memory 10 from an input terminal 200 and inputted to a latch 12 together with information of 3-preceding line. A reference signal H300 for 18 picture elements for half tone detection, a reference signal Sel301 for 14 picture elements for prediction coding and a coded picture element signal D203 are outputted from the latch 12. When a half tone detector 15 discriminates it that the current coded part is a half tone, the level of the signal Ed302 is logical 1 and the level of others is logical 0. A prediction state decision circuit 13 selects a proper prediction template according to the signal Ed302 and outputs the picture element information in the template as a status signal St206. The signal St206 enters a coder 11 together with the coded picture element data D203, in which the data and the signal are coded and sent.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an image predictive coding method in a facsimile device that communicates images, an image file device that stores images, and the like.

[Conventional technology]

The run-length encoding method, typified by the conventional 03.64 facsimile, counts the length of time that a pixel remains white or black (run length), and determines the code corresponding to that count value from a code table prepared in advance. This is a method to do so. The code table used here is characterized in that relatively short codes are assigned to long white spaces, which are common in document images. Therefore, if the statistical properties of the run length are different from those of the image used as a reference when creating the codebook, for example, when encoding a pseudo-halftone image in which black and white are frequently reversed, the code amount may differ from the original data. The problem is that the amount is exceeded.

Therefore, as an encoding method that can perform efficient encoding even for images that would cause problems when encoded based on such run lengths, encoding using Markov model codes such as arithmetic codes is proposed. Proposed.

Conventionally known arithmetic codes convert input signal sequences into 2 decimal numbers.
This is a method in which the code is formed by arithmetic operations so that the code is expressed in base numbers. This method is based on Langdon
and the document “Comp
r e s s i o n o f B l a c
k/WhitteImage
5w1th Arithmetic Coding
, IEEE TranCom, C0M-29,6,(
Published in 1981, 6), etc. According to this document, an input signal sequence that has already been encoded is
The probability of S) appearing is q1, and the calculation register Augend is A.
(S) and the code register is C(S), perform the following arithmetic operations for each input signal.

A(Sl) = A(S) Xq A= A(S) X2
-' ...(1) A(So) = <A(S)
-A(Sl)>i...(2)<
>1 indicates truncation at 12 significant digits c (so
)=c (s)...(3)C(
Sl)=C(S)+A(SO)...(4
) Here, if the encoded data is a dominant symbol (MPS: O in the above example), A (SO) and C (SO) are used to encode the next data. Furthermore, in the case of a less-likely symbol (LPS: l in the above example), A (Sl) and C (Sl) are used to encode the next data.

The new value of A is multiplied by 25 (S is an integer greater than or equal to 0) and 0.
It falls within the range of 5<A<1.0. This processing corresponds to shifting the calculation register A eight times in hardware. The code register C is also shifted to the left the same number of times, and the shifted out signal becomes the code. The above process ζ is repeated to form a code.

Further, as shown in equation (1), the occurrence probability q of LPS is approximated by a power of 2 (2-Q: Q is a positive integer), thereby replacing the multiplication calculation with a shift calculation. In order to further improve this approximation, it has been proposed to approximate q with a polynomial of a power of 2, such as equation (5). This approximation improves the worst point of efficiency.

q~2-" + 2-02...
(5) However, in the arithmetic encoding described above, the appearance probability approximated by a power of 2 is fixed, and images with different appearance probabilities may not be efficiently encoded.

Therefore, it has been proposed to change the LPS appearance probability q according to the characteristics of the image to be encoded to perform efficient encoding suitable for the image. Note that this probability estimation method includes a static method in which the probability is determined uniquely depending on the state of the encoded pixel, and a dynamic method in which the probability is estimated while encoding.

[Problem that the invention is trying to solve]

Refers to the former coded surrounding pixels and changes them to white/white depending on their status.
When using the method of estimating the probability of black occurrence, if the object to be encoded is something with a very strong correlation, such as a document image, several surrounding pixels are referred to in order from the one closest to the pixel of interest to be encoded. Even by simply dividing the states by , the entropy can be considerably lowered and highly efficient encoding is possible.

However, for an image such as an error diffusion image (such as an image composed of nearly random dots), there is no known reference method suitable for efficient encoding other than widening the reference range.

[Means for Solving the Problems (and Effects)] The present invention has been made in view of the above points, and uses a method for determining whether or not a region near a pixel of interest is a pseudo halftone image in an image predictive coding method. The present invention provides an image predictive encoding method that adaptively switches a reference pixel template used for encoding pixel prediction between a pseudo halftone image and a general image based on the determination.

〔Example〕

FIG. 1 shows an embodiment of an image transmission system to which the present invention is applied. The input binary number string is 4 from the input terminal 200.
It is stored in the line memory 10 which has a capacity for 3 lines.
It is input to latch 12 along with the information before the line. The latch 12 outputs a 188-pixel reference signal H3O0 for halftone detection, a 14-pixel reference signal Sel 301 for predictive encoding, and an encoded pixel signal D203.

The halftone detection signal H3O0 enters the halftone detector 15 and outputs a 1-bit signal Ed302. That is, when the halftone detector 15 determines that the currently encoded portion is a halftone, the signal Ed302
is 1 and the others are 0. According to the signal Ed302, the prediction state determination circuit 13 selects an appropriate (more efficient) prediction template and outputs pixel information in the template as a status signal 5t206. signal 5
t206 is sent to the encoder 11 together with the encoded pixel data D203.
is input, encoded and transmitted.

FIG. 2 is a block diagram of the line memory 10 and latch 12. Pixel signals input from the input terminal 200 are sent to four line buffers 40-1 to 40- included in the line memory 10.
4 allows data up to three lines before to be stored. Data output in parallel from these four line buffers enters the latch column, making it possible to simultaneously refer to the pixel of interest and its surrounding pixels.

The A-L (including C, , C2, L, , L2) latch is for capturing 14 reference pixel candidates for the predictive code, and these are output as a signal 5e1301. Also,
A, B+ CI + B+ B+ Gy B
+ a+L Jt K+ C2+ J C+ Ll+
The d+ er f latch is used for halftone portion detection and is output as signal H3O0. X is a latch that stores the pixel value of interest, and this value is output as a signal D203.

FIG. 3 is a diagram of the halftone detector 15. Signal H3
Pixel information around the pixel of interest is input to the ROM 65 from O0. The ROM 65 stores in advance a determination result l or 0 (1 if it is a halftone part) as to whether or not the surrounding 188 pixels have a high probability of being a halftone part for all states 218 states, and a signal H3O0 is stored in the ROM 65. In response to the input, the judgment result is immediately output as Ed302.

FIG. 4 is a block diagram of the predicted state determination circuit 13.

The halftone flag signal Ed302 and reference candidate pixel signal Sel301 are input to the multiplexer 66.

The multiplexer 66 follows the halftone flag signal Ed302 from the halftone detector 15, and if it is determined to be a halftone, sends the 12 pixel data shown in Figure 5 from the signal 5e1301 to the ROM 67; otherwise, , 12-pixel data used for boat fishing as shown in FIG.

ROM67 is connected to signal Ed302 and multiplexer 66
State signal 5t2 according to 12 pixel data from
Outputs 06.

FIG. 6 is a block diagram of the encoder 11.

The status signal 5t206 from the status determining circuit 13 is input to the counter memory 23 and the encoding condition memory 24.

The encoding condition memory 24 stores, for each state represented by the state signal 5t206, a dominant symbol MP3108, which is a symbol that is likely to appear, and an index l107 indicating the encoding condition including the probability of appearance of LPS of an arithmetic code, which will be described later. has been done. MP5108 is input to the predictive conversion circuit 27, and the pixel signal D203 is input to the predictive conversion circuit 27.
A YN signal 101 is generated which becomes 1 when it matches S108. The YN signal lot is input to the update circuit 25, and the update circuit 25 increments the count of the corresponding state among the count values stored in the counter memory 23 when the YN signal is 1. And counter memory 13
If the count value C106 stored in the count value C106 matches the set value MC105 from the count table ROM12, the index l107 is updated in the direction in which it becomes thicker (in the direction in which the appearance probability q of LPS becomes smaller). (Inversion of MPS) Note that the count table ROM 22 supplies the update circuit 25 with the number MC105 of MPS shown in Table 1, which is determined corresponding to the index I representing the probability of appearance q of the LPS.

Furthermore, in the update circuit 25, the MP8108 and the pixel signal D2
03 does not match, that is, Y from the prediction conversion circuit 27
When the N signal is 0, the index ■107 is updated in the direction that decreases (the probability of LPS appearance q becomes thicker). Also, when the index is 1 and a YN signal with a value of 0 comes, the MPS is updated. Inversion processing (0→1 or 1→0) is performed.Outputs i' 109 and MPS' 110 are the updated index values, and are stored again in the encoding condition memory 24.

In the encoding parameter determination circuit 26, the index l1
The coding parameter Qll of the arithmetic code based on the value of 07
Set l in the arithmetic encoder 28. This arithmetic encoder 28
Now, the YN signal lO1 from the predictive conversion circuit 27 is arithmetic encoded using the parameter Qllll to obtain a code 102.

Note that an initial value is given to the encoding condition memory 24, and I,
By not updating the MPS, static encoding can be easily achieved.

FIG. 9 is a block diagram of the predictive conversion circuit 27.

The binary series signal D203 and MPS108 are input to the EX-NOR circuit 29, and the YN signal 1 becomes 11 when the binary sign D203 and MPS108 match, and becomes 0 when they do not match.
01 is output.

FIG. 7 is a block diagram of the update circuit 25. When the YN signal 101 is 1, the count value C106 from the counter memory 23 is incremented by +1 by the adder 31 and becomes the signal C' 112. This value is compared with MC105 from the count table ROM 22 in the comparator 33, and C'
If the value of MC matches the value of MC, update signal UPA11
Set 3. Further, the YN signal 101 passes through the inverter 34 and becomes an update signal UPB114, which is then UPA.

UPB enters the index change circuit 35. Also, UP
A and UPB are logically ORed by an OR circuit 37, and an output signal 115 of the OR circuit 37 becomes a switching signal for the selector 32. When the signal 115 is 1, the selector 32 selects the 0 signal 119 to reset the counter value, and otherwise selects the output signal C' 112 of the adder 31 and outputs it as the counter update signal C' 116. It is stored in the counter memory 23.

The index change circuit 35 includes a signal dl17 (typically d=1) that controls the index update increments, and a UPA113. UPB114 and encoding condition memory 2
4 to the current index 1107 is input.

Table 2 is a table showing the index update method in the index change circuit 35 (Table 2 shows cases where the update increments are d=1 and d=2.) Input this table 11 Conditions dSUPA, UPB Determine the updated index ■′ by referring to it. Also, I
When UPB=1 and UPB=1, EX signal 118 is set.

When the EX signal is 1, the inverter 36 outputs the current MP3108.
(0→l or 1→0) and update M
Get PS' 110. Also, when the EX signal is O, the MP
S' is not changed. The updated I' 109 and MPS' 110 are stored in the encoding condition memory 24 and used as the index I and MPS for the next processing. Note that the updating method shown in Table 2 can be configured as a table using a ROM or the like, or it can be configured as a logic using an adder/subtractor.

As described above, when MPSs as many as the number of MPSs determined according to the value of the index I representing the appearance probability q of an LPS approximated by a polynomial of a power of 2 are generated, the index ■ is added by d and the arithmetic code is The appearance probability q of the LPS used is made small, and on the other hand, when an LPS occurs,
The index ■ is subtracted by d, and the probability of occurrence q of the LPS used for the arithmetic code is increased.Furthermore, if an LPS occurs in a state where the index I, which represents the probability of occurrence q of LPS is 0.5, is 1, then Invert MPS.

FIG. 8 is a block diagram of the arithmetic encoder 28.

Of the control signals Qclll (Table 3) determined by the code parameter determination circuit 26, shift register A7
Q1 is input to 0, Q2 is input to shift register B, and Q3 is input to selector 72. Ql and Q2 are Augend signals for the shift register ASB, respectively.
Instructs how many bits to shift 23 to the right.

The shifted result becomes the output signal 130.131.

The signal 131 is complemented by the inverter 76, and the selector 72 selects the signal 131 or the output signal of the inverter 76 using the control signal Q3 to obtain the output signal 132.

Adder 73 receives signal 130 from shift register A70.
and the signal 132 from the selector 72 are added, and As
+ signal 124 is output. The subtracter 74 subtracts the As+ signal 124 from the AS signal 123 to obtain As.

A signal 125 is obtained. The selector 75 receives the Aso signal 125.
and the ASI signal 124 are selected by the YN signal 101. That is, when the YN signal is 1, the Aso signal becomes the A' signal 126, and when the YN signal is O, the As+ signal becomes the A' signal 126. In the shift circuit 80, processing is performed to shift the A' signal to the left until the MSB becomes 1.
An S signal 127 is obtained. A shift signal 132 corresponding to the number of shifts is entered into the code register 79,
From the code register 79, a number b corresponding to the number of shifts is sent.
It is output in order starting from KSB and becomes code data 130.

The code data 130 is processed using a bit processing method (not shown).
The bitl sequence is processed so that it is within a finite number of bits, and is transmitted to the decoder 14 side.

Further, the contents 'CR128 of the code register 79 are added to the Aso signal 125 by the adder 77 and input to the selector 78. Also, the signal C to which the Aso signal 125 is not added is
R128 also enters the selector 78, when the YN signal 101 is 1, cR' = when the CRSYN signal is 0, CR' = CR
+Aso is output as a CR' signal 129.

The shift processing described above regarding the code register 79 is CR
' Do this for the signal.

Determination of the reference pixel position in the prediction state determining circuit 13 will be explained below using FIG. 10. Assume now that the input halftone image is obtained by the error diffusion method.

Error diffusion images are generally said to have weak correlations, but on the other hand, a tortoiseshell pattern, which is a characteristic of the error diffusion method, appears in medium and low density regions.

Therefore, a template indicating the position of a reference pixel for error diffusion is created with this point in mind.

That is, using a 12-pixel diffusion matrix (FIG. 10A) commonly used in the error diffusion method, a gray scale of 8 bits per pixel was binarized and prepared as training data.

Next, the entropy of the training image is determined using the 12-pixel reference template shown in Figure 1B, and among these, the states with particularly low entropy and those that occur frequently in this image are determined, and the states are divided into 12 dimensions. Plotted. The plotted data is not uniform in space, but exists in several clusters. Each cluster is a collection of similar surroundings such that each cluster has a low entropy. From these, select some representative points (mainly points near the center of gravity of the cluster and have the smallest variance) to the extent that interference with other clusters is suppressed, and then The template shown in Figure 1C was obtained as a result.

A commonly used document template has a fixed correlation order, and its shape is uniquely determined depending on how many pixels are referenced. When the entropy of a document image is measured using this template, the entropy decreases as the number of reference pixels increases, but almost saturates around the 8-pixel reference.

The template at that time is shown in Figure 1O.

The 12-pixel reference template proposed in this example is as shown in Figure 1E,
It is a logical sum of 0 pixels and made into 12 pixels, and while it provides the same encoding efficiency as the conventional method for document images, it also enables a considerable improvement in efficiency for error diffusion images. be. The present proposal is for 12-pixel reference, but it goes without saying that other types can be created in exactly the same way.

In the above embodiments, explanations were given using monochrome binary signals of 1 bit per pixel, but 3-bit signals such as RGB, MMC, etc.
The present invention can be easily expanded to the encoding of binary color images by sequentially encoding the t-color signal and the YMCK 4-bit color signal.

Also, although the templates were switched between document and error diffusion templates, it goes without saying that this can also be extended by adding dither templates.

Further, by providing a plurality of templates and using these templates depending on the image, even more efficient encoding becomes possible.

As explained above, in predictive coding of binary images,
Coding efficiency can be improved by having multiple templates used for prediction, determining which template to use as pre-processing for prediction, and performing prediction and encoding accordingly.

In particular, for pseudo-halftone images produced by the error diffusion method, the amount of code is reduced by several percent, and a clear effect can be seen.

Furthermore, if the processing according to the present invention is applied to a binary color (3-bit or 4-bit color) image in a frame-sequential manner, the amount of code reduction can be tripled by simple calculation, and it can be said that there is a greater effect.

No. table ) is don' c a r e.

〔Effect of the invention〕

As explained above, according to the present invention, it is determined whether or not the region near the pixel of interest is a pseudo-halftone image, and based on the determination, the reference pixel template used for encoding pixel prediction is set for the pseudo-halftone image. Adaptively switches between general images and
Since image predictive encoding is performed in accordance with this, efficient image encoding suitable for the input image can be achieved.

[Brief explanation of drawings]

Fig. 1 is a block diagram of a binary image transmission system according to the present invention, Fig. 2 is a block diagram of the line memory section, Fig. 3 is a block diagram of the halftone judge, and Fig. 4 is a block diagram of the state determination circuit. , Fig. 5 is a diagram showing a reference pixel template, Fig. 6 is a block diagram of the encoder, Fig. 7 is a block diagram of the update circuit, Fig. 8 is a block diagram of the arithmetic encoder, and Fig. 9 is a predictive conversion circuit. 10 is a diagram for explaining the template, 11 is an encoder, 10 is a line memory, 12 is a latch circuit, 15 is a halftone detector, 13 is a prediction state determination circuit, and 14 is a decoder. It is. Note 3 times 4 drawings ￥1:) Drawing ``LL inspection'' Lth fish B

Claims (1)

[Claims] In the image predictive coding method, it is determined whether the region near the pixel of interest is a pseudo-halftone image, and based on the determination, reference pixel templates used for coding pixel prediction are divided into one for pseudo-halftone images and one for general images. An image predictive coding method that is characterized by adaptively switching between