JPH0132702B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an adaptive predictive decoding device used when decoding codes encoded by an adaptive predictive encoding device that predictively encodes an image signal.

Conventionally, this type of adaptive predictive coding method uses
For example, a prediction means disclosed in Japanese Patent Application Laid-open No. 55-41080 is provided, and the number of mispredicted pixels of a plurality of prediction error signals is compared in a certain block unit, and one of the prediction error signals is selected. There is a way.
This method has the disadvantage that the prediction effect is not sufficient when image signals with different characteristics, such as halftone photographs and characters, are mixed in one block.

An object of the present invention is to eliminate the drawbacks of the conventional prediction means described above, and to provide an adaptive predictive coding method with high prediction effects.

The adaptive predictive decoding device of the present invention generates predicted values P ₁ and P ₂ for the sample value X of pixel x, and calculates the prediction error from prediction error signals Y ₁ and Y ₂ obtained from the predicted values P ₁ and P ₂ . The signal Y is obtained by an adaptive predictive coding device that selects the signal Y pixel by pixel and encodes the error signal E composed of the predictive error signal Y and the predictive selection signal _M1 corresponding to which predictive error signal is selected. When decoding the code, at least _{the above} -mentioned means are provided. Error signal E and predicted values P ₁ , P ₂
and a means for obtaining a sample value X by the reverse logic of encoding using the past prediction selection signal and the past prediction selection signal.

The adaptive predictive decoding device of the present invention is applied, for example, to data compression encoding of newspaper facsimiles, and the encoding device side generates two types of predicted values P ₁ and P ₂ suitable for predicting halftone photographs and characters, respectively. The prediction error signal Y is selected pixel by pixel so that the prediction error is smaller than the prediction error signals Y ₁ and Y ₂ obtained from the predicted values P ₁ and P ₂ . Since the error signal E, which is the logical sum of the prediction selection signal N related to which prediction error signal Y is selected, is encoded, the encoded information as a whole has a higher prediction effect than conventional prediction encoding methods. It has the effect of reducing the amount.

Next, the present invention will be explained in detail with reference to the drawings.
FIG. 1A is a diagram showing an example of reference pixels of a halftone photo predictor used in the adaptive predictive decoding device of the present invention. Note that FIG. 1A is intended for a 45° diagonal halftone image. In FIG. 1A, the distance D (D=10 here) represents the period of the halftone dot, and the pixels that have the same phase relationship (on the two-dimensional mesh periodic pattern of the image) with the sample value X of the pixel x are:
b ₀ and c ₀ . In the figure, the neighboring pixels of pixel x
Sample values A ₁ - A ₆ of a ₁ - _{a 6} , sample values B ₀ of pixel b ₀ separated in the main scanning direction by the period of the halftone dot, and sample values B ₁ - _{B 5} of its neighboring pixels b ₁ - b ₅ The combination of
It shows an example of reference pixels used in the predictor 3a ₁ in Figure A. Similarly, the sample values A ₁ to _{A 6} of neighboring pixels of pixel x, the sample values C ₀ of pixel c ₀ diagonally separated by the period of the halftone dot, and the sample values C 1 to C ₁ of its neighboring pixels c ₁ to c ₅ The combination of C ₅ is also the predictor 3 in Figure 2A.
This is an example used for a ₁ .

FIG. 1B is a diagram showing an example of reference pixels of a character predictor used in the adaptive predictive decoding device of the present invention. In the figure, the sample value X of pixel x is predicted by the sample values of neighboring pixels of pixel x. The combination of sample values A ₁ to _{A 12} of neighboring pixels a ₁ to _{a 12} of pixel x is an example used in the predictor 3a ₂ of FIG. 2A.

FIG. 2A is a block diagram showing a first embodiment of a coding device that produces a code to be decoded by the decoding device of the present invention, and when the reference pixel b ₀ in FIG. 1A is used as a predictor. This is an example using FIG. 1B. In the figure, a sampled and binarized image signal is applied to terminal 1. Assuming that the sample value applied to the terminal 1 is X, this sample value X is supplied to the line memory 2 and the predictors 3a ₁ and 3a ₂ .
Line memory 2 delays the signal by about one line, and the delay amount for one line is set to H (=8000 samples).
Then, a signal delayed by (H-6)=7994 samples is obtained at its output terminal.

The predictors 3a ₁ and 3a ₂ are composed of a shift register and read-only memory (ROM),
Using the combinations shown in FIG. 1A and FIG. 1B as reference pixels, predicted values P ₁ and P ₂ are output, respectively. The predicted values P ₁ and P ₂ are exclusive ORed with the sample value X in exclusive OR circuits 5a ₁ and 5a ₂ and converted into prediction error signals Y ₁ and Y ₂ , which are input to the multiplexer 6a. Selection signal generation circuit 4a
(Details in FIG. 4A or FIG. 4B) generate a prediction selection signal M ₁ and an error signal E from the prediction error signals Y, Y ₁ and Y ₂ , and the error signal E is input to the encoder 7 .

In the multiplexer 6a, the prediction error signal Y is selected pixel by pixel according to the prediction selection signal _M1 .

The error signal E is then encoded by an encoder 7 (a conventionally used encoder such as a run-length encoder) and output from an output terminal 8. 2B is a block diagram showing a second embodiment of an encoding device that produces a code to be decoded by the decoding device of the present invention shown in FIG.
In addition to (prediction error signal Y or selection error signal N), state signal S (prediction state signal S _Y or selection state signal S _N )
This shows an example of a case where both are encoded together.

That is, the predicted state signal S _Y (or selected state signal
The prediction error signal _E (or selection error signal N) is a signal used for grouping, for example,
When there are two prediction states (selection states), the prediction probability is divided into a reference pixel pattern having a certain value or more, and other patterns.

In FIG. 2B, the predicted state signals S ₁ , S ₂ and the selected state signal _SN are sent to the predictor 3 which is composed of a shift register and a ROM in the same way as the predicted values P ₁ , P ₂ .
The selection state signal generation circuit 9 obtains a selection state signal from a _{1 ′} , 3a _{2 ′ , the} sample value Signal S _N is input to multiplexer 6b. multiplexer 6
a ₁ ′ is the prediction error signal Y according to the prediction selection signal M ₁
and prediction state signal S _Y , and prediction error signal Y
is input to the selection signal generation circuit 4a, and the predicted state signal
S _Y is input to multiplexer 6b. The multiplexer 6b selects the state signal S corresponding to the predicted signal E from the predicted state signal SY and the selected state signal _SN according to the error selection signal _M2 , and inputs the selected state signal S to the encoder 7'. The encoder 7' performs run-length encoding on the error signal E using the state signal S. A run-length encoding method using such an error signal E and status signal S is described in Japanese Patent Laid-Open No. 55-41080.

FIG. 3A shows a predictor 3a ₁ used in FIG. 2A.
1A is a block diagram showing an embodiment of the present invention, in which the halftone dots in the main scanning direction of FIG. 1A are used as reference pixels. Current and previous scan line signals are applied to terminals 10 and 11. If the sample value applied to the terminal 10 is X, then the shift register 12
1-2 and 9-11 samples time delayed in a, 12b and 12c, pixels a ₁ ,
Sample values A ₁ ^, A ₂ , B ₀ -B ₂ of a ₂ - , b ₀ -b ₂ are obtained. A signal in which the sample value X is delayed by (H-5)=7995 sample times is applied to the terminal 11, and is further delayed by 4 sample times in the shift register 12d. Shift registers 12e, 12f and 12g
Then, sample values A ₃ -A ₆ and B ₃ -B ₅ of pixels a ₃ -a ₆ and b ₃ -b ₅ in FIG. 1A are obtained by delaying 1-4 and 12-14 sample times.

The sample value A ₁ of the reference pixel obtained in this way
~A ₆ , B ₁ ~B ₅ and B ₀ are applied as addresses to the ROM 13, which generates the aforementioned predicted value P ₁ at its output terminal 14. The embodiment of the character predictor _3a2 shown in FIG. 1B as a reference pixel can be similarly implemented with a circuit configuration using a shift register and ROM.

Although an embodiment has been described above in which only one pixel having the same phase relationship with pixel x is selected as the reference pixel of the predictor, a plurality of pixels having the same phase relationship with pixel x can be used simultaneously as the reference pixel.

For example, x shown in FIG. 1A as a reference pixel
The neighboring pixels a ₁ , a ₄ to a ₆ and the neighboring pixels b ₀ , c ₀ and their neighboring pixels b ₂ , b ₄ , b ₅ , c ₂ , c ₄ , which have the same phase relationship with x,
Sample values of c ₅ A ₁ , A ₄ to _{A 6} , B ₀ , B ₂ , B ₄ , B ₅ , C ₀ ,
Of course, predictors using C ₂ , C ₄ , and C ₅ are included.

FIG. 3B shows the predictor 3 used in FIG. 2B.
FIG. 3 is a block diagram showing an embodiment of _a1 '. The difference in this figure from the predictor 3a ₁ in FIG. 3A is that a ROM for generating a prediction state signal S ₁ is added, and other aspects are exactly the same. The predicted state signal S ₁ , like the predicted value P ₁ , is statistically obtained in advance from several types of papers.

FIG. 4A is a block diagram showing a first embodiment of the selection signal generation circuit 4a used in FIGS. 2A and 2B, and the predicted selection signal shown in FIG. 5A.
This is a circuit that generates _M1 and an error signal E.

Note that FIG. 5A is a diagram for explaining the relationship between selection signals. In FIG. 4A, register 24a is first reset so that prediction selection signal _M1 selects prediction error signal _Y1 at the beginning of a scan line. Next, prediction error signals Y ₁ and Y ₂ applied from selections 20 and 21 and register 24a
The ROM 23 generates a prediction selection signal M ₁ and an error selection signal M ₂ according to the prediction selection signal M _{1 of} the previous pixel which is _the output of , is output from the terminal 28. In the register 24a, the prediction selection signal M ₁
is delayed by one pixel, and the exclusive OR circuit 25 generates a selection error signal N, which is the change point of the predicted selection signal M ₁ , and inputs it to the multiplexer 26 . The multiplexer 26 selects the error signal E from the prediction error signal Y and the selection error signal N according to the error selection signal _M2 , and outputs it from the terminal 29.

Next, using FIG. 5A, the predicted selection signal of the present invention,
The relationship between the error selection signals M ₁ , M ₂ , the prediction error signals Y ₁ , Y ₂ , the selection error signal N, and the error signal E will be described. In the figure, the shaded parts of the error signals Y ₁ , Y ₂ , Y, and N, that is, Y ₁ , Y ₂ , Y, and N=1, indicate the misprediction, and their values, that is, Y ₁ , Y ₂ , Y, and N=0.
indicates the predicted accuracy. The shaded part of the selection signal M ₁ or M ₂ , that is, M ₁ or M ₂ = 1, indicates that the prediction error signal Y ₂ or the selection error signal N is selected _;
Alternatively, M ₂ =0 indicates that the prediction error signal Y ₁ or the prediction error signal Y is selected. Here the predicted selection signal
M ₁ and error selection signal M ₂ are signals for selecting the prediction error signal Y from the prediction error signals Y ₁ and Y ₂ and the error signal E from the prediction error signal Y selection error signal N, respectively, and finally the error signal E is chosen to reduce the number of mispredictions. In other words, the misprediction of the prediction error signals Y ₁ and Y ₂ is the prediction error signal
If Y ₁ and Y ₂ are signals obtained by predictions suitable for each of the photographs and characters, prediction errors will occur continuously in the non-corresponding parts, as shown in the prediction error signals Y ₁ and Y ₂ in Figure 5A. There is a strong possibility. In such a case, the prediction error signal Y ₁ is changed using the prediction selection signal M ₁ to reduce the prediction error.
If Y 2 and Y ₂ are automatically switched, the error signal E
The number of mispredictions decreases, and the amount of information after encoding decreases.

In FIG. 5A, the prediction selection signal M ₁ and the error selection signal M ₂ are obtained as follows.

The prediction selection signal M ₁ is determined so that the prediction error of the prediction error signal Y is minimized. In other words, the prediction error signal Y is selected so that the prediction error signal Y is determined to be a misprediction only when both the prediction error signals Y ₁ and Y ₂ are mispredictions. For this purpose, the prediction selection signal _M1 is switched when the prediction error signal side selected one pixel before is a prediction error. At this time, the error selection signal _M2 is obtained as follows.

The error selection signal _M2 is for selecting a prediction error of either the prediction error signal Y or the selection error signal N (both predictions cannot be wrong at the same time), and it is possible that the selection error signal N is a prediction error. When there is a prediction error signal, that is, when one of the prediction error signals results in an incorrect prediction, the selection error signal N is selected.

Figure 4A used to implement the above logic.
The contents of the ROM 23, that is, the table, are shown in FIG. 6, and the result of expressing the prediction selection signal _M1 and the error signal E in logical expressions is shown in the following equation. Note that "exclusive OR" + means "logical sum", "•" means "logical product", and "×" means the inversion of "×".

M ₁ = ( _{1 2} )・M ₁ ′ + ₁・P ₂・×+P ₁・₂・× E= ₁・₂・×+P ₁・P ₂・×+M ₁ ′M ₁ In figure 1, M ₁ ′ is Prediction selection signal of one pixel before
Represents M ₁ . Using the table in Figure 6A,
Using the prediction error signals Y ₁ and Y ₂ of figure A as input,
The results of determining the prediction selection signal M ₁ , prediction error signal Y, selection error signal N, error selection signal M ₂ and error signal E are shown in the lower part of FIG. 5A. The number of prediction deviations of the error signal E obtained in this way is 8
Therefore, the number of prediction errors of the original prediction error signals Y ₁ and Y ₂ is smaller than 10 and 12.

FIG. 4B is a block diagram showing a second embodiment of the prediction selection signal generation circuit 4a used in FIG. 2A, and a circuit for generating the prediction selection signal _M1 and error selection signal _M2 shown in FIG. 5B. It is.

Note that FIG. 5B is a diagram for explaining the relationship between selection signals. The difference between FIG. 4A and FIG. 4B is that in FIG. 4B, as an input to the ROM 23' that determines the prediction selection signal M ₁ and the error selection signal M ₂ ;
The point is that prediction error signals Y ₁ and Y ₂ with a one-pixel delay are used. In FIG. 5B, the prediction selection signal
M ₁ and the error selection signal M ₂ are obtained as follows since prediction errors in the prediction error signal tend to occur continuously and only on one side. Prediction selection signal M ₁
This switching is performed when only the prediction error signal selected one pixel before is predicted incorrectly, and the previous prediction error signal is also predicted incorrectly. At this time, the error selection signal M ₂ selects the selection error signal N when there is a possibility that the selection error signal N will be incorrect in prediction, that is, when the prediction error signal Y ₁ or Y ₂ will be incorrect in prediction continuously. FIG. 6B shows the contents or table of the ROM 23' of FIG. 4B used to implement the above logic.

In the figure, Y ₁ ′, Y ₂ ′, and M ₁ ′ represent the prediction error signal Y ₁ and the Y ₂ prediction selection signal M ₁ of the previous pixel, respectively. Using the table in FIG. 6B and inputting the prediction error signals Y ₁ and Y ₂ in FIG. 5B, the prediction selection signal M ₁ , prediction error signal Y, selection error signal N, error selection signal M ₂ , and error signal E are determined. The results are shown in Section 5B.
Shown in the bottom part of the figure.

The number of prediction errors in the error signal E at this time is 8
is the number of mispredictions of the original prediction error signals Y ₁ , Y ₂
It is less than 10 and 12. The difference between FIG. 5A and FIG. 5B appears in the 7th to 11th sample values and the 29th to 34th sample values. In the former case, the number of isolated prediction errors only on the prediction error signal _Y1 side is as small as one, so the error signal E on the side of FIG. 5B is small; in the latter case, only the prediction error signal _Y2 side has isolated prediction errors , 3 and 2 or more, the error signal E on the side of FIG. 5A is reduced.

FIG. 7A is a block diagram showing a first embodiment of the present invention. In the figure, a code applied to a terminal 41 is decoded into an error signal E by a decoder 42.
The error signal E is converted by the selection signal generation circuit 4b (FIG. 7A or FIG. 7B) into a prediction error signal Y and a prediction selection signal _M1 according to the predicted values _P1 and _P2 . The prediction error signal Y is exclusive ORed with the predicted values P 1 and P 2 output from the predictors a ₁ and a ₂ in the exclusive OR circuits 5a ₁ and 5a ₂ , and the prediction error signal Y is subjected to exclusive OR with the predicted values P ₁ and P ₂ output from the predictors a ₁ and a 2. Generate ₂ . Next, the multiplexer 6a outputs the decoded signal _X1 according to the prediction selection signal _M1 .
and X is selected from X ₂ . The other parts, such as the line memory 2 and predictors 3a ₁ and 3a ₂ , have exactly the same circuit configuration and operate in the same way as in FIG. 2A, which is the first embodiment of the adaptive predictive encoder of the present invention.

FIG. 7B is a block diagram showing a second embodiment of the present invention. The difference from the first embodiment shown in FIG. 6A is that a decoder 42' uses a state signal S (prediction state signal S _Y or selection state signal S _N ) to use an error signal E (prediction error signal Y or selection error signal N ), and
Similar to the encoder side shown in FIG. 2B, the predictor 3
a ₁ ′, 3a ₂ ′ generate predicted state signals S ₁ , S ₂ , and selection state signal generation circuit 9 and multiplexer 66 are required.

Next, FIGS. 8A and 8B show the selection signal generation circuit 46 used in FIGS. 7A and 7B.
FIG. 2 is a block diagram showing one embodiment of the invention. FIG. 8A shows a circuit 4b corresponding to the selection signal generating circuit 4a of FIG. 4A. That is, the prediction error signal Y and the error selection signal are determined from the error signal E shown in FIG. 5A.
This is a circuit that generates _M1 . In the figure, the terminal 50,
Using the predicted values P ₁ and P ₂ applied from 51 and 52 and the error signal E as addresses, the ROM 53 generates a prediction error signal Y and a selection error signal N, and the prediction error signal Y is outputted from a terminal 56. The selection error signal N is sent to the register 54 and the exclusive OR circuit 5.
5b, it is converted into a prediction selection signal _M1 and outputted from the terminal 57. Further, the error selection signal M ₂ is obtained by taking the exclusive OR of the predicted values P ₁ and P ₂ in the exclusive OR circuit 55a, and is output from the terminal 58. The contents of the ROM, that is, the table used here, are shown in FIG. 9A, and the result of expressing the predicted selection signal _M1 and the decoded signal X by a logical equation is shown in the following equation.

_{M 1 = ( P 1 P 2 ) ・ F 1 ′ _} is the selection signal generation circuit 4a of FIG. 4B.
This is a circuit 4b corresponding to. That is, this circuit generates a prediction error signal Y and a prediction selection signal _M1 from the error signal E shown in FIG. 5B. In the figure, the predicted values P ₁ and P ₂ applied from terminals 51 and 52 are exclusive ORed with the sample value X applied from terminal 59 in exclusive OR circuits 55b and 55c, and a prediction error signal Y ₁ is obtained. , Y ₂ is generated. Prediction error signal
Y ₁ and Y ₂ are delayed by one pixel in the register 60, and are applied as addresses to the ROM 53' in the same manner as the predicted values P ₁ and P ₂ and the error signal E to generate a predicted error signal Y and a selection error signal N. used here
The contents of the ROM 53', ie, the table, are shown in FIG. 9B.

As described above, the adaptive predictive decoding device of the present invention uses a predictor that generates two types of predicted values suitable for predicting halftone photographs and characters, respectively, on the encoding device side, and uses a prediction error signal Y obtained from the predictor. By selecting a pixel by pixel and also simultaneously encoding a selection error signal N indicating which predictor is used, an adaptive predictive encoding method that does not require a mode code, that is, the amount of information after encoding is small, can be achieved. ing.

[Brief explanation of drawings]

FIGS. 1A and 1B are diagrams showing an example of reference pixels of a predictor used in the present invention, and FIGS. 2A and 2B are diagrams showing first and second reference pixels of an adaptive predictive coding device according to the present invention. A block diagram showing an example,
3A and 3B are block diagrams showing an example of a predictor used in the present invention, and FIGS. 4A and 4B are block diagrams showing an example of a selection signal generation circuit of an encoding device according to the present invention. 5A and 5B are diagrams for explaining the relationship between selection signals of the present invention, and FIGS. 6A and 6B are ROMs used in the selection signal generation circuit of the encoding device according to the present invention. Figures 7A and 7B are block diagrams showing an embodiment of the present invention.
8A and 8B are block diagrams showing an example of the selection signal generation circuit of the decoding device of the present invention, and FIGS. 9A and 9B are block diagrams showing an example of the selection signal generation circuit of the decoding device of the present invention. FIG. 3 is a diagram showing the contents of a ROM. In the figure, reference numeral 2 is line memory, 3
a ₁ , 3a ₂ , 3a ₁ ′ and 3a ₂ ′ are predictors, 4a and 4b are selection signal generation circuits, 5a ₁ , 5a ₂ , 2
5, 55a, 55b and 55c are exclusive OR circuits, 6a, 6a', 6b and 26 are multiplexers, 7 and 7' are encoders, 9 is a selection state signal generation circuit, 12a, 12b, 12c, 12d, 1
2e, 12f, 12g, 24a, 24b and 6
0 is shift register, 13, 13', 23, 2
3', 53 and 53' are ROM, 42 and 4
2' represents a decoder, and 54 represents a counter.

Claims (1)

[Claims] 1 Generate two predicted values P ₁ and P ₂ for the current sample value X of the binary image signal, and generate prediction error signals Y ₁ and Y ₂ from the predicted values P ₁ and P ₂ and the current sample value X. Then, a prediction selection signal M 1 is obtained from the prediction error signals Y ₁ , Y ₂ and the prediction selection signal M _{1 '} for past sample values.
is an error selection signal M ₂ indicating that there is a high possibility that only one of Y ₁ and Y ₂ will be a misprediction.
, select one of the prediction error signals Y ₁ and Y ₂ as the prediction error signal Y based on the prediction selection signal, and generate a selection error signal N indicating a change point of the prediction selection signal M ₁ ; One of the prediction error signal Y and the selection error signal N is selected as the error signal E based on the error selection signal _M2 , and the encoded binary image signal is decoded by encoding this error signal E. an adaptive predictive decoding device for decoding the error signal E;
means for providing an initial value of the prediction selection signal M ₁ ; means for reproducing the predicted values P ₁ and P ₂ from already decoded sample values; and means for reproducing the predicted values P ₁ and P ₂ from the already decoded sample values; means for separating the selection error signal N and the prediction error signal Y, and a prediction selection signal for the selection error signal N and already decoded sample values;
means for reproducing _{the prediction selection signal M 1 using} the prediction error signal Y and the prediction value P ₁ ,
_{P2 , and means for selecting one of these X1 and X2 based on} the prediction _selection signal _M1 to obtain the decoded value X. An adaptive predictive decoding device characterized by: