JPH0262992B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to an image signal encoding device that compresses and encodes an image signal with high efficiency. Typical of conventional image signal encoding devices
There is a DPCM encoding device. This uses the input image signal S (hereinafter referred to as the reference image signal) to determine the prediction signal X^ of the currently input image signal X (hereinafter referred to as the current image signal), and its prediction error code e is determined by the difference between X and X^, e _D =X-X^ (1), and compression encoding is performed by taking advantage of the fact that e _D tends to concentrate on small values around 0. The prediction error code e _D determined by equation (1) will be referred to as a differential prediction error code below. The subscript D is added to the differential prediction error code e _D to indicate that it is an example of how to determine the prediction error code e. S for X
For example, the case where three pixels a, b, and c in FIG. 1 are selected will be explained in more detail. 1st
In the figure, the dotted line indicates the main scanning line, along which the image is scanned from left to right. When the right end is reached, scanning continues from the left end along the main scanning line one line below. Image signals are input to the encoding device in scanning order. There are various ways to determine X^ by S = ( _a , _b , c), but the image signal a belonging to the _input image signal S is , b, and c. _K1 ,
K ₂ and K ₃ are constants called prediction coefficients, and are determined so that e _D concentrates on small values around 0. For example, reduce the root mean square value of e _D ＜e ² _D ＞ _AV = ＜(X−X^) ² ＞ _AV = ＜(X−K ₂ a−K ₂ b−K ₃ c) ² ＞ _AV (3) It is determined that e _D determined in this way follows a zero-concentrated probability distribution P _D (e _D ) as shown in FIG. However, the image signal had eight values from 0 to 7. At this time, from equation (1), e _D is between -7 and 7.
15 values. _eD is compressed and encoded using this zero concentration. That is, a short code is assigned to an e _D with a small absolute value and a high probability of occurrence, and a long code is assigned to an e _D with a large absolute value and a low probability of occurrence. FIG. 3 shows an example of the code length L _D of this code F _D (e _D ). When considered in more detail, the occurrence probability distribution of e _D differs depending on S, and is considered to be an occurrence probability distribution of P _D |s) for each S. Here, P _D (eD|s) is the occurrence probability distribution of e _D under condition S, and is a different distribution for each S. P _D (e _D ) in Figure 2 explained earlier
is the average of P _D (e _D |s) over S, P _D (e _D )= 〓 ^S P _D (e _D |s) P(S) (4). Here, P(S) is the probability of occurrence of the reference image signal S, and 〓 ^S means the sum of all S. (4) is the average of P _D (e _D |s) for each S, weighted by the probability of occurrence of S, which is P _D (e _D ).
. Give a concrete example, P _D (e _D | s)
Let me explain the difference between and P _D (e _D ). In all the following explanations, it is assumed that S consists of the three pixels a, b, and c shown in FIG. 1, and the image signal has eight values from 0 to 7 (3 bits/pixel). If the prediction coefficients K ₁ , K ₂ , K ₃ are 0.7,
Let's say you choose 0.2 and 0.1. When S is S ₁ =(6,6,5) (5), the predicted signal X^ is X^=0.7×6+0.2×6+0.1×5=6 (6). However, numbers below the decimal point were rounded off. The calculations below are also similar. X is an 8-value 0X7 (7) from 0 to 7. From this and equation (1), −X^e _D 7−X^. Like X, X^ also has 8 values from 0 to 7, so it is 0X^7 (9). From equations (8) and (9), -7e _D 7 (10). e _D can take on 15 values from -7 to 7. However, if the value of X^ is known, the value of e _D is −
It is limited to 8 ways from X^ to 7-X^. For example, S
When = S ₁ , from equation (6), X^ = 6, so -6e _D 1 (11). Similarly, the reference image signal S is S ₂ = (0, 1, 2) S ₃ = (4, 4, 4), S ₄ =
Table 1 shows the values determined for the range of the prediction signal X^ and the prediction error code e _D when (3, 4, 5). As with S ₁ , the prediction coefficients K ₁ , K ₂ , K ₃ are 0.7, 0.2, 0.1
X ₀ to X ₇ and M in Table 1 will be explained later. Examples of P _D ((e _D | s) for S=S ₁ to _{S 4} are shown in Figs. 4 to 7. _{P D} (e _D ) (see Fig. 2) and P _D (e _D | s) ) (see Figures 4 to 7) are mostly different in shape. Below, P _D (e _D ) and P _D (e _D | s)
Compare. First, let's compare e _D , which gives the maximum value. Both P _D (e _D ) and P _D (e _D |s) are maximum at e _D =0. In this respect, both are the same.
Next, let's compare the range in which e _D occurs (see Figure 1). In P _D (e _D ), e _D can take 15 values from -7 to 7. On the other hand, in P _D (e _D |s), e _D can take only eight values of −X^−X^+7 (see equation (8)). Next, let's compare the left and right symmetry.
P _D (e _D ) is generally symmetrical about e _D =0. That is, P _D (e _D )=P _D (−e _D ) (12). On the other hand, in general, equation (12) does not hold for P _D (e _D |s). That is, P _D (e _D | s)≠P _D (−e _D | s) (13)

[Table] Let us explain equation (13) in detail for S=S ₁ to _{S 4} . For the sake of simplicity, e=±1 will be explained in detail. When S=S ₁ : a, b are equal to X^=6. From now on, it is unclear whether there is a strong tendency for X to become larger than X^ or a strong tendency for it to become smaller. C=5 is less than X^=6. From this it can be thought that X tends to be smaller than X^. Therefore, e will be more likely to be -1 than +1. That is, P _D (−1|S ₁ )>P _D (+1|S ₁ ) (14). When S=S ₂ : Since X^=0, e _D =0 to 7 and e _D cannot be -1. The larger e _D becomes, the smaller P _D (e _D | s ₂ ) will become. That is, P _D (0 | S ₂ )> P _D (1 | S ₂ )> P _D (2 | S ₂ )>...>
It would be P _D (7 | S ₂ ) (15). When S=S ₃ : a, b, c are all equal to X^=4. From this, it can be considered that the tendency for X to become larger than X^ is equal to the tendency for X to become smaller. That is, P _D (+1|S ₃ )=P _D (−1|S ₃ ) (16). When S=S ₄ : Only a is equal to X^=3, and b and c are larger than X^. From now on, it is thought that there is a strong tendency for X to become larger than X^. Therefore, e _D will be more likely to be +1 than -1. That is, P _D (+1|S ₄ )=P _D (−1|S ₄ ) (17). In this way, P _D (e _D | S) changes in various forms depending on S, but when P _D (e _D | S) is averaged over S (see equation (4)), P _D (e _D ) has a symmetric zero-concentrated distribution as shown in Figure 1. In conventional DPCM encoding, e _D is the occurrence probability distribution P _D
(e _D ), the code length L _D as shown in Figure 3 is
e _D is encoded using a code F _D (e _D ) having (e _D ). For the code F _D (e _D ), P _D (e _D )=P _D (−e _D ) ((12)
(see formula), L _D (e _D )=L _D (−e _D ) (18) holds true for most e _D . (In Fig. 3, this does not hold only for e _D = 6.) Also, for the sign F _D (e _D ), if |e′D | e _D |, then P _D (e′ _D )P _D (e _D ) ( 19) If |e′D|e _D |, then L _D (e′ _D )L _D (e _D ) (20). Also, corresponding to e _D = -7 to 7, F _D (e _D ) is
It has 15 different codes. However, as already explained in detail, the conditional probability of occurrence of e _D P _D (e _D |s) varies greatly depending on S. Therefore the sign F _D (e _D ) is
matches P _D (e _D ) but not P _D (e _D |s). For example, in general P _D (e _D | s)≠P _D (−e _D |
s) (see equation (13)), but L _D (e _D )=L _D (−e _D )
(See equation (18)) is strange. If we consider each S, we always prepare 15 codes F _D (e _D ) from e _D = -7 to 7, even though e _D takes only eight values (see equation (8)). There is no point in doing so. In this way, for any e _D corresponding to any S, the sign F _D
(e _D ) encoding is not efficient. Traditional
In DPCM encoding _, e _D is encoded assuming that the probability distribution of e D is P _D (e _D ), and it does not take into account at all that the probability distribution of e _D changes greatly depending on S. . Therefore, the code length L _D (e _D ) given by S in FIG. 3 is often not appropriate, resulting in a disadvantage of low compression ratio. Traditional
The DPCM encoding device uses a differential prediction error code e _D (see equation (1)) as the prediction error code e, but there is also a different way of determining e. For example, as the prediction error code e, a prediction rank error code e _J indicating the ranking of the likelihood of occurrence of X in each S is used (1981,
IEICE Communications Division National Conference, S7-7, Mizuno et al. "Entropy Coding of Halftone Image Signals"). This means that the conditional probability of occurrence P(X|S) of X at a certain S is P(X ₀ |S)P(X ₁ |S)P( _X2 |S)...
When (X ₇ |S) (21), the prediction error code e is set as the prediction rank error code e _J shown below. X=X _i →e _J =i (i=0 to 7) (22) However, when (X _i >X _J )P(X _i |S)=P(X _j |S), i<j. A subscript _J is added to indicate that e J is an example of how to determine the prediction error code e.
The prediction error code e _J takes eight values from 0 to 7,
The conditional probability of occurrence P _J (e _J | S) for each S is calculated from equations (21) and (22) as P _J (O | S) P _J (1 | S) P _J (2 | S)...P _J
(7|S)(23) and is monotonically decreasing with respect to e _J. The conditional probability of occurrence P _D (e _D | s) of the prediction error code e _D is S = S ₁ ~ S ₄
Regarding the case shown in FIGS. 4 to 7, the corresponding P _J (e _J |s) becomes as shown in FIGS. 8 to 11. Furthermore, X ₀ to X ₇ in equation (21) are as shown in Table 1. Since P _J (e _J |s) is always monotonically decreasing with respect to e _J , all distributions are downward-sloping. Therefore, by averaging P _J (e _J | s) over S, we get P _J (e _J ) P _J (e _J ) = 〓 ^S P(S) P _J (e _J | s) (24) Again The distribution is downward to the right, and P _J (e _J ) and P _J (e _J |
The shape of s) will be similar. However (24)
In the formula, 〓 ^S means the sum of S. Therefore, the code F _J (e _J ) is set to match the probability distribution P _J (e _J ).
It is efficient to design the following and uniformly encode e _J (following the occurrence probability distribution of P _J (e _J |s)) in each S using its code F _J (e _J ). For the above reasons, using the prediction rank error code e _J as the prediction error code e is more efficient than the conventional DPCM encoding apparatus. However, in order to generate e _J, for each S and each X, e _J
A predictive encoding ROM is required to store the data as data. The reference image signals are 3 pixels a,
When the number of levels of the b and c image signals is 8, the prediction error code generation ROM has 9 bits of S and 3 bits of
A total of 12 bits are input as an address signal, and 3 bits _eJ are output as a data signal. The capacity of this prediction error code generation ROM increases as the number of image signal levels and the number of reference image signals increases. For example, if the number of image signal levels is 256 values (8 bits/pixel),
When the number of reference image signals is 5, the address is 8×6=
It is 48 bits, and the data is 8 bits. Such a large capacity ROM would have an enormous physical size given the current technology level. If the prediction rank error code e _J is used as the prediction error code e, encoding can be performed more efficiently than the DPCM encoding device, but there is a drawback that a large capacity prediction error code generation ROM is required. The purpose of the present invention is to
An object of the present invention is to provide an image signal encoding device having a higher compression rate than a DPCM encoding device. According to the present invention, the already input image signal S
A predicted signal of the multivalued image signal X currently being input using
A means for generating X^; a means for generating a code e indicating the actual rank of X in the order of the possible signal values of X based on X^; and a compression code for e. An image signal encoding device having a means for encoding is obtained. Further, according to the present invention, there is provided a means for generating a prediction signal X^ of a multivalued image signal X that is currently being input using an image signal S that has already been input, and a means for calculating the distance between X and S and based on the distance. A means for generating a mode signal M indicating a tendency to become larger or smaller than X^, and a method for arranging the possible signal values of X based on An image signal encoding device having means for generating a code e indicating the order of X and means for compressing and encoding e is obtained. According to the present invention, image signals can be encoded efficiently. The present invention will be explained in detail below using the drawings. The image signal is 0 to 7 (3 bits/pixel), and the case where the reference image signal S consists of three pixels a, b, and c in FIG. 1 will be described as an example. First, the first invention will be explained. FIG. 12 is an example of a block diagram of an encoding device according to the first embodiment of the first invention. In FIG. 12, an image signal (3 bits/pixel) is sequentially input to a 3(l+2) bit shift register 1. Here, l is the number of pixels per main scanning line, and the shift register 1 stores image signals of 1 line + 2 pixels. In shift register 1, the pixel that has just been input is X, the one that was input just before is a, the one that was input (l-1) pixels ago is c, and the one that was input one line ago is l pixels, that is, the one that was input one line ago. is b. Prediction signal generator 2
is the reference image signal S=(a,
b, c), and input a, for example as in equation (2).
A predicted signal X^ of X is created and output by linear calculation of b and c. The prediction error code generator 3 inputs X^ from the prediction signal generator 2, and arranges the possible signal values of X based on X^ in the order of the probability of occurrence.
A code e indicating the actual rank of X among them is output. e is compressed and encoded by the compression encoder 4 into a code F(e). Each part of the block diagram of FIG. 12 will be explained in more detail using the drawings. Various configurations are possible for the predicted signal generator 2 shown in FIG. 12, examples of which are shown in FIGS. 13 and 14.
The predicted signal generator in FIG. 13 is a linear predicted signal generator corresponding to equation (2). In Fig. 13, the multiplier 5,
6 and 7, the prediction coefficients K ₁ , K ₂ ,
K ₃ is multiplied, and the sum of the multiplication results is sent to the adder 8.
is calculated by and output as X^. 14th
The predicted signal generator shown in the figure generates each reference image signal S=(a,
A method is used in which the prediction signal X^ is recorded in the ROM for each of b and c). The method of determining X^ by linear operation of a, b, and c as shown in Fig. 13 is often used because it is simple, but the resulting X^ is not necessarily optimal when considered for each S. Let's consider the reasons below. The prediction coefficients K ₁ , K ₂ , and K ₃ are determined, for example, so that the root mean square prediction error obtained by equation (3) is minimized. Equation (3) can be considered in detail as follows. <e ² _D >=A _V =<(X-X^) ² >A _V = 〓 ^S 〓 ^X P(X,S)(X-X^) ² =X^ 〓 ^S P(S)P(X ｜ ^S ) ^{( X} -X^) ² = 〓 ^S P(S) ^{ (X−K ₁ a−K ₂ b−K ₃ c) ² } (25) Here, P(S) is the probability of occurrence of the reference image signal S,
P(X ₁ |S) is the conditional probability that the current image signal becomes X when the reference image signal is S. Further, 〓 ^S means the sum of the reference image signal S, and 〓 ^X means the sum of the target image signal X (0 to 7). (3)
In equation (25), the mean square prediction error over all S is considered. By the way, the mean square prediction error <e ² _S > A _V for each S is different from this, and is expressed as <e ² _DS > A _V =<(X _S −X^ _S ) ² A _V = 〓 ^X P(X| S)(XX^) ² = 〓 ^X P(X|S)(X-K _1s a-K _2s b-K _3s c) ² (26) is given. In equation (26), e _D , X, X^, K ₁ , K ₂ ,
The subscript S added to _K3 means that the reference image signal is S.
It shows that e, X, X^, K ₁ , K ₂ , K ₃ when . If the prediction coefficients K _1s , K _2s , K _3s are determined for each S so that ＜ ^e 2 _S ＞A _V is minimized, the mean square prediction error for all S is ＜e ² _D ＞A _V = 〓 ^S P (S) < e ² _S > _AV (27). Obviously, <e ² _D > _AV in equation (27) is smaller than <e ² _D > _AV in equation (25). But (25)
In the formula, the prediction coefficients K ₁ , K ₂ , and K ₃ were constant regardless of S, but in the formula (27), it is necessary to give different prediction coefficients K _1S , K _2S , and K _3S for each S. That is, it is necessary to store prediction coefficients K ₁ , K ₂ , and K ₃ for each S. This ends up being a predicted signal for each S.
It is the same as memorizing and preparing X^. In many cases, the X^ _S that minimizes <e ² _DS > _AV in equation (26) is the X that occurs with the highest probability in each S.
is the same as FIG. 14 shows the configuration of a predicted signal generator using this method. In FIG. 14, the ROM 9 receives the reference image signal S=(a, b, c) as an address signal (9 bits) and outputs the contents of the memory at the corresponding address as a prediction signal X' (3 bits). Although the predicted signal generator shown in FIG. 14 requires a ROM, it has a higher prediction accuracy than the predicted signal generator shown in FIG. 13, as explained in detail above. This concludes the explanation regarding the predicted signal generator 2 in FIG. 12. Next, the prediction error code generator 3 shown in FIG. 12 will be explained. An example of the prediction error code generator 3 of FIG. 12 is shown in FIGS. 15 to 17. First, the prediction error code generator shown in FIG. 15 will be explained. In Fig. 15, the ROM 10 inputs the current image signal X (3 bits) of 8 values from 0 to 7 as an address signal (6 bits) and the prediction signal X^ (3 bits), and inputs 0 as a data signal (3 bits). from 7 to 8
The prediction error code e _A (3 bits) of the value is output. e _A
A subscript A is added to indicate that this is an example of how to determine the prediction error code e. An example of the contents of the ROM 10 is shown in Table 2. X (3 bits) specifies the upper 3 bits of the address, and X^ specifies the lower 3 bits of the address. When ranking the possible values of X for each X^ in the order of likelihood of occurrence, the code indicating the ranking is e _A. In Table 2, X is the absolute value |X−X^
It is considered that the smaller | is, the more likely it is to occur, and when |X - X^| is equal, the smaller X is larger than X^, the more likely it is to occur. Next, the prediction error code generator shown in FIG. 16 will be explained. FIG. 16 is almost the same as FIG. 15. However, the contents of ROM11 are slightly different from ROM10. Table 3 shows an example of the contents of the ROM 11.
X (3 bits) specifies the upper 3 bits of the address, and X^ (3 bits) specifies the lower 3 bits of the address. Third
In the table, as in Table 2, it is assumed that the absolute value of I think this is more likely to occur. When considering how likely X is to occur in this way, e _B is a signal that indicates the ranking of how likely X is to occur. A subscript _B is added to e B to indicate that it is an example of how to determine the prediction error code e. Next, the prediction error code generator shown in FIG. 17 will be explained. The difference from FIGS. 15 and 16 is that the address of the ROM 12 in FIG. 17 is 7 bits.
This is because X^ is expressed in 4 bits.

【table】

【table】

Claims (1)

[Claims] 1. Means for generating a prediction signal X^ of a multivalued image signal X currently being input using an already input image signal S; It is characterized by having means for arranging possible signal values in descending order of |X-X^| and generating a code e indicating the actual rank of the image signal X therein, and means for compressing and encoding the code e. An image signal encoding device. 2 Means for generating a prediction signal X^ of the currently input multivalued image signal X using the already inputted image signal S, and means for calculating the distance between the image signal X and the image signal S and generating the image signal S based on the distance. Means for generating a mode signal M indicating whether the image signal X becomes larger or smaller than the predicted signal X^, and the possible signal values of the image signal X arranged in descending order of |X-X^| means for arranging the one that is more likely to occur first based on the mode signal M when
An image signal encoding device comprising means for compressing and encoding an image signal.