JP3127513B2 - Encoding device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an encoding apparatus used for an image data processing apparatus for compressing / expanding image data, and more particularly, to encoding using a Q-Coder which is a kind of arithmetic code. The present invention relates to a coding apparatus for performing the coding.

[0002]

2. Description of the Related Art A process for reducing the data amount of an original image signal by removing redundant signal components contained in the image signal is performed by a high-efficiency coding (high-efficiency code) of an image.
ding), or simply picture coding. In addition, this technology uses data compression coding, redundancy suppression coding, bit rate reduction coding (bit-rate reducti coding).
on coding).

An image, such as a facsimile, which does not include a halftone signal component such as a document or a drawing and can be regarded as being made up of only black and white binary is called a binary image. A binary image generally has a large degree of redundancy, and data can be compressed by an information source coding technique. The image quality of the binary image can be considered to be determined by the sampling density because the number of quantization levels in the amplitude direction is sufficient to be two.

[0004] Among the important data compression encodings,
Predictive coding and transform coding (trans
form coding) and vector quantization (vector quantiza)
Option). Entropy coding (variable length coding, Huffman coding) is often used as a powerful means to increase the data compression effect by combining these two methods or three methods (hybrid coding). Often used.

[0005] Among the entropy codings for removing the redundancy, one of the most typical entropy codings is unequal length coding. Are assigned to longer output levels. Thereby, the average code length of the code output can be shortened. By performing entropy coding, the rate of code output generation is not constant. Since a general transmission path is configured to transmit information at a constant speed, information (code) generated unevenly cannot be transmitted to the transmission path as it is. For this reason, information is temporarily smoothed by buffer storage and then transmitted as a signal. Further, in order to prevent overflow and underflow of the buffer storage, the buffer storage occupancy is monitored, and the parameters of the redundancy elimination coding are controlled so as to always fall within a certain range.

Hereinafter, the above-mentioned predictive coding, arithmetic code and Q-
Coder will be described. Predictive coding In predictive coding, a previously stored coded past pixel value is stored in a memory in an encoder, and a predicted value (X) of a newly input pixel X is obtained from this. The difference (referred to as a prediction error) X- (X) is quantized, and the output level is converted into an appropriate binary code and transmitted. On the receiving side, the prediction value (X) can be reproduced by exactly the same calculation. Therefore, a prediction error is reproduced from the transmitted code, and this is added to the immediately preceding image signal already decoded, and a new image signal is generated. Can be restored. Since highly accurate prediction is possible for a signal having a large correlation between sample values, the predicted value (X) is close to the actual signal X, and the prediction error is reduced. Accordingly, transmission can be performed with a smaller amount of information than the signal X, and high-efficiency coding can be realized.

FIG. 8 is an encoding flow of an image data compression apparatus using a Q-Coder which compresses image data at a pixel level by encoding a prediction error. In FIG. 8, the processing from calculating a prediction error to one pixel of a binary image (for example, a facsimile) to encoding is as follows.

First, in step S1, a predicted value of a pixel to be coded is determined from seven pixels around a pixel to be coded (pixel to be coded), and in step S2, the pixel to be coded and the prediction value The prediction error is calculated by EX-ORing the values. Next, the prediction error calculated in step S3 is encoded using Q-Coder (see FIG. 14 described later). This process will be specifically described with reference to FIGS.

FIG. 9 is a diagram showing image data 1 of a document or the like and a target of a predicted value in which a part thereof is enlarged. As shown in this figure, at the time of encoding, the image data 1 is scanned from the upper left to the right to obtain monochrome (0 or 1) binary dot data, but a dot of a certain pixel X will be encoded. In this case, the original data is not directly encoded, but as shown in the enlarged portion of FIG. 9, the values (black and white values) of the seven pixels a to g at the upper left, upper, and right of the pixel X are calculated. A value is predicted and an error from the prediction is obtained. That is, as shown in FIG. 9, a prediction value table (prediction code table) 2 in which prediction values are statistically stored based on values of seven pixels around a to g in the upper left direction of the pixel X.
(FIG. 10) is prepared, and the address of the predicted value table 2 is designated by the values of the seven pixels around the above a to g to obtain the corresponding predicted value (X). The predicted value table 2 is a table in which predicted values (X) from 0 to 1 are statistically obtained in advance and stored in correspondence with all combinations of values 00000000 to 1111111 of the pixels a to g. When the image data 1 is scanned and there are many 0 (for example, white) around the pixel X, it is assumed that the dot data to be coded is also large in white, so that the predicted value (X) is 0 (white). . Conversely, in the case of solid painting, it is assumed that the probability of 1 (for example, black) is high, so the predicted value (X) is 1 (black). Thus a ~
The optimum predicted value (X) corresponding to the value of the pixel of g is statistically obtained in advance and stored in a ROM or the like, and the predicted value (X) and the pixel X are EX-OR (exclusive) shown in FIG. Logical sum) circuit 3
To calculate the prediction error by taking the EX-OR logic.
As a result of the EX-OR, the prediction is “0” if the prediction is correct, and “1” if the prediction is erroneous. As long as the prediction is correct, the number of “0” s increases, and if the data with a large number of “0” s is coded through an encoding device, the data is highly biased, so that considerable compression can be expected. As described above, if the predicted value (X) based on the values of the pixels a to g matches X, the compression ratio increases.

The prediction error calculated as described above is represented by Q
-Encode using Coder.

Next, the outline of the Q-Coder will be described. Q-Coder is a kind of arithmetic code, and is divided one after another by the occurrence probability of data to be encoded on the number line of 0-1. Therefore, the arithmetic code will be briefly described first. Arithmetic Code The arithmetic code temporarily replaces the original data with the occurrence frequency (occurrence probability) by dividing the number of number lines from 0 to 1 by the occurrence probability of the data to be encoded. For example, as shown in FIG. 12, the input values 11001... Are represented by P (0 ≦ P ≦ 1) having a high predicted probability of “1” and Q (Q = 1−1) having a predicted probability of “0”.
P), and this is represented by the division ratio on the number line of the starting point C and the width A shown in FIG. That is,
Put two variables C (origin) and A (width) on the number line,
Initially, C = 0 and A = 1 (see FIG. 13A). When the occurrence probability is high, the number line is divided without changing the origin C, and the size of P in FIG. 13A is newly set to the width of the number line. Then, i) when the code "1" having a high frequency of occurrence comes when dividing the number line, the width of the number line is set to P, and the origin (origin) is left unchanged. ii) If the code “0” having a low frequency of occurrence comes when dividing the number line, the width A is changed by moving the position of the origin (C) by P as shown in FIG.

When the input values 1100... Shown in FIG. 12 are continuously encoded in accordance with the above-described method, the width of the number line becomes narrower and closer to a point between 0 and 1, and finally, the origin line The position converges to a certain point on the number line. Such encoding is called an arithmetic code.

Therefore, the origin C is divided when the code "1" having a high frequency of occurrence comes, but does not change (move), and is divided and divided as long as the code "1" with a high frequency of occurrence continues. The position of the origin does not change just by touching. In other words, as the number of codes with a high frequency of occurrence increases, the means for expressing the division position is below the decimal point, and when the frequency of occurrence is high, the digit does not increase even if the division proceeds further (the code with a low frequency of occurrence “0”). The position of the origin moves only when "comes.) Therefore, as long as a code with a high frequency of occurrence continues, a code of thousands of bits can be represented by a certain bit line (for example, tens of bits). Here, if there is this occurrence probability and the final code, the original code can be obtained (restored) by following the reverse procedure. As described above, the larger the bias of the code with respect to the code whose occurrence probability is known in advance, the higher the compression ratio can be encoded.

Although the above-mentioned arithmetic code can perform high-efficiency coding, it has the following disadvantages. First, it is necessary to know the occurrence frequency (occurrence probability) in order to obtain the expected probability P of "1" and the expected probability Q of "0", but the occurrence frequency means that all data must be scanned in advance. If you can not decide. For example, in the case of a facsimile or the like, the frequency of occurrence cannot be known unless all the sentences are scanned once. Further, since P and Q are not integers, many digits after the decimal point are required to improve the accuracy, and it is very difficult to calculate the division of the number line by the large number of digits.

To solve the above-mentioned disadvantages of arithmetic codes, a Q-Coder which is a kind of arithmetic code has been proposed (A multi-code).
-purpose VLSI chip for adaptive data compressin of
bilevel images and Software imprementation of the
Q-Coder IBM J.RES.DEVELOP VOL32.No6 11-1988).

Hereinafter, the Q-Coder will be described. Q-Coder In Q-Coder, dividing by the probability of occurrence of data to be encoded on the number line of 0 to 1 is basically the same as the arithmetic code described above, but solves the disadvantage of the arithmetic code. In order to do this, the following improvements have been made. That is, in order to solve the above-mentioned drawbacks, P and Q are
Instead of scanning all data in advance and calculating the probability of occurrence, it is assumed that the probability of occurrence is not known at first, so it is assumed to be 0.5, and the probability of occurrence changes dynamically as the code is input. Let it. For example, assuming that P = 0.5, if there are many "1" s in the incoming code, P is set to .0.
It is changed in a direction larger than 5 (P> 0.5).
When “0” increases during the scanning, the occurrence probability is reduced, and P becomes smaller than 0.5 (P <0.5). By dynamically changing the occurrence probability (this is referred to as a predicted occurrence probability), it is not necessary to scan all data in advance to determine the occurrence probability. The method of dynamically changing the occurrence probability is performed using a table shown in FIG. 16, which will be described later.

On the other hand, in order to solve the above-mentioned disadvantage, in the above-mentioned arithmetic code, a new width is obtained by multiplying the original number line width A by the occurrence probability P (A ← A ×
P), it is difficult to calculate from the viewpoint of precision if this P has, for example, 0.3256...
In r, the above disadvantages are eliminated by replacing all multiplications at the time of division with addition and subtraction. That is, dividing the number line is approximated by subtracting the occurrence probability, and moving the position of the origin is approximated by adding the occurrence probability.

Referring to FIGS. 14 to 16, Q-Coder
The outline of is described. FIG. 14 is a principle diagram showing a process of encoding a Q-Coder. In this figure, Q-Coder represents a sequence of input values as one point on a number line ranging from ₀ to A ₀ (usually 1), and transmits the value at that point as a code sequence. First, when the width A ₀ starting point C ₀ is given, the width A ₀ is calculated according to the input sequence head value by Pe: Qe (Pe is the predicted probability of “M”, Qe is the predicted probability of “L”, and 0: <P
e ≦ 0.5, Qe = 1−Pe) to obtain the next width A ₁ and starting point C ₁ . Similarly, according to the next input sequence value, the data is divided to obtain a width A ₂ and a starting point C ₂ . This is sequentially repeated to obtain a coded sequence to be obtained. The encoding process shown in FIG. 14 is based on the 4-bit data “MMLM” (11 when M = 1).
01) is input. The point at which the division is completed at all inputs is taken as a code, and a decimal value of 0 <x <1 is obtained. When the input bit is “M”, the code range A is divided to A · Qe.

That is, assuming data MPS (More Probable Symbol) having a high probability of occurrence and data LPS (Less Probable symbol) having a low probability of occurrence with respect to the input sequence value, if the input value is MPS, An = A _n-1. (1-Q
e), Cn = C _n-1 + A _n-1 · Qe, and if LPS,
The number line is divided as An = A _{n -1} · Qe. In this case, the multiplication at the time of division is replaced with addition and subtraction to facilitate the operation, which is approximated to An _-1 = 1, and in the case of MPS, An = An _-1 * Qe and Cn = Cn _-1 + Qe. And LPS
In the case of, the division of the number line is performed with An = Qe (FIG. 15).
(See steps S11 to S13 of the Q-Coder flow in (1)).
Next, in step S14, A and C are normalized each time so that 1 ≦ A <2 (for example, when A <1, the left shift is performed until A ≧ 1), thereby ensuring the calculation accuracy. In step S15, Qe is updated, and the Q-Coder flow ends. This Qe update is, for example, in the case of MPS, dynamically changing Qe so that the lower line goes up as shown in FIG. Note that this Q
The Coder flow (FIG. 15) corresponds to the step S3 encoding process of the encoding flow of FIG.

As described above, in the Q-Coder, the starting point of encoding is set to 0, and the code C is determined by addition, so that the lower line is shifted toward the center by addition as shown in the figure. Further, in the Q-Coder, the LPS occurrence probability sample value Qe corresponding to the division ratio is updated every time. Figure 1 shows the Qe value
In the U-shaped state diagram shown in FIG. 6, by specifying 30 states that take values from 0 to 29, the Qe value of the state is determined. That is, as shown in FIG. 16, a bit having a high frequency of occurrence is set to MPS, and the left side of the U-shape is set to MPS.
Initially, PS = 1 and the right side are set to MPS = 0, and the Qe value is first started from 0.5 (the position of state 0 among the values of states 0 to 29). Each time one input value is encoded, the position of the U-shaped state is moved up and down as shown in FIG. Each state 0
29, there is a unique Qe value, and in state 0, Qe =
0.5, a very small value in state 29 (for example,
0.00018).

The way of changing Qe depends on the assumed MPS
When (for example, MPS = 1) and the actually input MPS match, the states in the table of FIG. 16 are ascended one by one. That is, when the assumed MPS = 1 is large, the occurrence frequency is high, and the occurrence probability is considered to be high.

When several 0's continue, the following of the table shown in FIG. 16 is skipped by two (or three) to speed up the following. Then, in the middle of the table of FIG. 16 (position of state 0), when 1 which is not MPS = 1 comes further, it is assumed that the frequency of occurrence is high, then MPS = 0 and MPS = It is changed as in the case of 1. Therefore, whether the MPS is 1 or 0 can follow the higher frequency of occurrence.

As described above, when MPS continues to the input value, the state gradually rises and the Qe value becomes small, that is, the division of the number line becomes small, and the generated code amount becomes small. Conversely, MPS does not continue, and MPS and LPS near state 0
Are input alternately, the MPS settings are switched,
The state does not rise, the Qe value is large, and the generated code amount is large.

[0024]

However, in such an encoding apparatus using a conventional Q-Coder,
Even in an input pattern in which a predicted value is difficult to hit, the prediction error is uniformly encoded using the predicted value table (FIG. 10). Therefore, LPS is often input to the Q-Coder. There is a problem that the amount of generated codes cannot be suppressed even if an input pattern with a low accuracy of the predicted value is known because there are many upper and lower states of the character shape. That is, when the assumed MPS and the input MPS match as shown in FIG. 16, the U-shaped states of FIG. 16 are climbed one by one, and when they do not match, two U-shaped states (3 Although the follow-up is good because of the skipping, the 0 may slightly continue, for example, when the MPS continues to match (when 1 is input when MPS = 1 is assumed). Then, the state immediately drops from the upper state to the lower state of the U-shape, which has a high probability of occurrence and has high coding efficiency. Therefore, the division of the number line becomes coarse, and the generated code amount increases. In other words, there is a problem that the code increases at that point due to the continuation of a part that is not the MPS, and once it goes down to the lower state, it takes time to ascend to the upper state, and the code amount increases during that time. .

By the way, the fact that the MPSs do not match is a case where "1" and "0" are mixed and input, and in such a case, the probability that the prediction is incorrect is high. For example, in the predicted value table 2 of FIG. 10, there is a case where the values of seven pixels a to g around the pixel X to be coded exist one by one or half by zero. In such a case, there is a high probability that the predicted value deviates, so if the predicted value deviates, the upper state with high coding efficiency drops to the lower state by skipping two or three states, and again the upper state It takes time to return to the above, and the generated code amount increases. Therefore, an object of the present invention is to provide an encoding device that can suppress the generated code amount even when a predicted value does not hit, and has high data compression efficiency.

[0026]

According to the first aspect of the present invention,
In order to achieve the above object, a data supply unit for supplying data to be encoded, and a prediction storing a predicted value of a pixel to be encoded corresponding to a plurality of pixels around the pixel to be encoded as a predicted value table A value storage unit; a prediction error calculation unit that calculates a prediction error based on the encoding target pixel supplied from the data supply unit and a prediction value output from the prediction value storage unit; Coding means for coding the prediction error by arithmetic coding in which a division ratio of an arithmetic code is dynamically changed by changing a predetermined variable, wherein the prediction value table is When the plurality of surrounding pixels have a specific pattern, the data has data indicating that a predicted value is invalid, and when the specific pattern is used, the variable of the encoding means is fixed to a predetermined value and encoded. To have.

[0027]

The operation of the means of the present invention is as follows. According to the first aspect of the present invention, the encoding target data is supplied by the data supply unit, and the predicted value of the encoding target pixel corresponding to the values of a plurality of pixels around the encoding target pixel is stored as a predicted value table as a predicted value storage unit. Is stored in When the address of the predicted value table is specified by the values of several pixels around the pixel to be coded, the value corresponding to the specified address is extracted from the predicted value storage means based on the predicted value table, and the prediction error is calculated as the predicted value. Output to the calculation means. In this prediction value table, data indicating that the prediction value is invalid when the probability that the prediction value hits a plurality of surrounding pixels is small is added,
No prediction value is used for this specific pattern. Then, a prediction error is calculated by the prediction error unit based on the prediction value output from the prediction value generation unit for the encoding target pixel output from the data storage unit. The encoding means encodes the prediction error by arithmetic encoding in which the division ratio of the arithmetic code dynamically changes by changing a predetermined variable,
In the case of a specific pattern in which the predicted value is unlikely to hit, the variable is fixed to a predetermined value and encoded. Therefore, it is possible to control the generated code amount when the predicted value does not match, and it is possible to greatly increase the compression ratio.

[0028]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described below with reference to the drawings. 1 to 7 are diagrams showing an embodiment of an encoding device according to the present invention, and are examples applied to an image data compression device. FIG.
, An image data compression device 11 stores an image data storage device 12 for storing data to be compressed, and an address generation for designating an address of a predicted value based on values of several pixels around a pixel to be encoded (a pixel to be encoded). Device 13, a pixel predicted value storage device 14 for outputting a predicted value (X) from a predicted value table 31 (FIG. 3) based on a value corresponding to an address designated by the address generating device 13, and an image data storage device 12 A prediction error calculating device 15 for calculating a prediction error based on a pixel to be coded output from and a prediction value (X) output from a pixel prediction value storage device 14, and encoding the calculated prediction error Q to compress image data
A coder 16, a code storage device 17 for sequentially storing generated codes, and a control device 18 for controlling the operation of each of the above devices
It is composed of

FIG. 2 is a block diagram of the Q-Coder 16. In FIG. 2, a Q-Coder 16 is a C register 21 for temporarily storing the starting point C data of the divided number line.
And an A register 22 for temporarily storing the width A data of the divided number line, a selector 23 for selecting an output from the A register 22 and an output from the C register 21, and an A register selected by the selector 23. The output 22 or the output of the C register 21 is input to an input terminal A, and a variable (probability estimate) Qe or a fixed value for encoding read from a Qe table 26 described later is input to an input terminal B. An adder / subtractor 24 that divides a number line by adding or subtracting; an S counter 25 that takes a value of 0 to 29 and counts a state S for reading an estimated occurrence probability Qe of LPS from a Qe table 26; and a state of 0 to 29 And a Qe table 26 for storing a Qe value corresponding to the input and output of the encode input or the decode output one bit at a time and the MPS input. It is constituted by outputs a control signal and Q-Coder controller 27 for controlling the operation of each unit.

The C register 21 has an input / output bit of 25 b
It consists of a register of it, and outputs the upper 8 bits as an encoded output to the encoding storage device 17 at the time of encoding according to the instruction of the controller 27, and the encoding input from the encoding storage device 17 is supplied to the lower 8 bits at the time of decoding. . The value whose code range has been narrowed by addition is input to the C register 21, and the number of bits remaining in the register at the end of encoding after bit shifting inside becomes the width, that is, the code. In the C register 21, the divided value is shifted leftward until a bit is set so as to become a value of 1 to 2 and Q
2 longer than A register 22 to normalize the value of e
It is a 5-bit register. As a result of this left shift,
The part where the value does not change finally becomes the sign. In addition, when adding and outputting the result, the controller 27 sets the LOA.
D, SHIFT is instructed when performing normal shift to the left.

The A register 22 has enough bits (13 bits) to store the operation width.
7 indicates SHIFT / LOAD. The adder / subtractor 24 is switched to an adder or a subtractor by an ADD / SUB control signal from the controller 27, and adds or subtracts the contents of the A register 22 or the contents of the C register 21 to return to the A register 22. It returns to the C register 21.

The Qe table 26 has states 0 to 2
9 is a table for storing a Qe value taking a value of 0 to 29 steps corresponding to 9; a Qe value indicated by a variable (state) S of an S counter 25 is read from a Qe table 26; 24. S counter 2
5, as shown in FIG. 16, if the MPSs match, the count is incremented by one to indicate the upper state S, and if the MPSs do not match, the count is increased by three, two or one to lower the lower state. This counter indicates S, and the initial value is 0.
It is.

Further, the Q-Coder controller 27 includes 1b
Each time it is encoded by it, the current MPS is compared with the input bit, and if they match, the state S of the S counter 25 is advanced by one MPS. If they do not match, the number of states S is reduced by two or three. If the MPSs do not match when S = 0, the MPS and the LPS are exchanged.
The state S is determined by comparing S with the input bit. S
Are the required Qe values.

FIG. 3 is a diagram showing the predicted value table 31 stored in the pixel predicted value storage device 14. In this figure, a predicted value table 31 is a predicted value (0 or 1) in which predicted values are statistically stored based on the values of seven pixels a to g around the encoding target pixel X.
It comprises a storage unit 31a and a fixed value storage unit 31b for storing additional information for fixing Qe and MPS without determining a predicted value when a specific pattern hardly hits the predicted value (see-in the figure). The specific input patterns of the surrounding seven pixels, which are hard to hit by the predicted value, are shown in FIGS. 4 and 5, for example. FIG.
As shown in FIG. 5, the peripheral seven pixels are 1010101 or 0.
If the predicted value such as 101010 is difficult to hit with a predicted value close to 50%, the predicted value is not determined, and the variables Qe and MPS are fixed instead.

Next, the operation of this embodiment will be described. Overall Operation First, the image data storage device 12 stores image data to be encoded. Predicted value table 3 based on the values of several pixels around the pixel to be encoded by the address generator 13
1 (FIG. 3), the pixel prediction value storage device 14 stores the value corresponding to the specified address in the prediction value table 3.
1 and output to the prediction error calculation device 15 as a prediction value. In this case, the prediction value is obtained from the surrounding seven pixels for the encoding target X, and if Qe and MPS are not fixed, the prediction error calculation device 15 calculates the prediction error between the encoding target and the prediction value as in the related art. On the other hand, the surrounding seven pixels are 0101010
For those that are hard to hit with the predicted value, such as and 1010101, Qe = 0.5, MPS =
It is fixed to 1 and Qe is not updated. Q-Coder1
Reference numeral 6 compresses the image data by encoding the calculated prediction error. The generated codes are sequentially stored in the encoding storage device 17.

The specific operation will be described below with reference to the flowcharts shown in FIGS. FIG. 6 is a diagram showing an encoding flow of the image data compression device 11. First, in step S31, a predicted value of a pixel to be coded is determined from seven pixels around a pixel to be coded (pixel to be coded). It is determined whether or not the input pattern is a specific input pattern. When the input pattern is not a specific input pattern, Qe and MPS are not fixed. Calculate the error. Next, the prediction error calculated in step S24 is encoded using the Q-Coder, and the flow ends.

On the other hand, when the input value is a specific input pattern of seven pixels around which it is hard to hit the predicted value, the Q-Coder 16 fixes and encodes the Qe and MPS without using the predicted value in step S25, and ends the processing.

FIG. 7 is a diagram showing the flow of the Q-Coder when Qe and MPS are fixed, and is a process corresponding to step S25 in FIG. The flow of the Q-Coder when Qe and MPS are not fixed (the processing in step S24) is shown in FIG.

First, at step S31, it is determined whether the input value is MPS or LPS.
e = 0.5, MPS = 1, A = A-0.5, C
= C + 0.5, and in the case of LPS, A = 0.5 to divide the number line. Next, in step S34, A and C are normalized such that 1 ≦ A <2 each time (for example, A <C
When it is 1, the arithmetic operation accuracy is ensured by performing a left shift until A ≧ 1), and the flow ends. Also, Qe
= 0.5, MPS = 1 and Qe when encoded
Is not updated. Therefore, even if LPS is encoded, FIG.
Does not decrease, and the amount of generated code does not temporarily increase when encoding the subsequent input sequence.

As described above, the image data compression device 11 of the present embodiment includes an image data storage device 12 for storing data to be compressed, and several pixels around a pixel to be encoded (a pixel to be encoded). An address generator 13 for specifying an address of a predicted value by a value, and an address generator 13
Pixel predicted value storage device 1 that outputs a predicted value (X) from predicted value table 31 based on a value corresponding to an address specified by
4, a prediction error calculation device 15 for calculating a prediction error based on a pixel to be coded output from the image data storage device 12 and a prediction value (X) output from the pixel prediction value storage device 14. A Q-Coder 16 for compressing image data by encoding a prediction error, an encoding storage device 17 for sequentially storing generated codes, and a control device 18 for controlling the operation of each device are provided. Table 3
Numeral 1 divides an input pattern into a specific input pattern whose prediction value is hard to hit and an input pattern whose prediction value is hard to hit. For a specific input pattern whose prediction value is hard to hit, the prediction value is invalidated and the encoding variables Qe, MPS And fix Qe
Is not updated, it is possible to prevent the generated code amount from increasing when the predicted value deviates. As described above, it is possible to suppress an increase in the amount of generated code for an input value that frequently deviates from the predicted value, thereby realizing a binary image compression / expansion apparatus having a high compression rate. When the method is applied to (1), the transmission time can be reduced.

Although the present embodiment is an example in which the encoding apparatus is applied to an image data compression apparatus, the present invention is not limited to this, and can be applied to all apparatuses using prediction values. Needless to say.

Further, in this embodiment, the input pattern of the predicted value table is divided into two, and if the predicted value is hard to hit, the predicted value is invalidated, the encoding variables Qe and MPS are fixed, and Qe is updated. However, it goes without saying that any method may be used as long as information corresponding to the input pattern of the pixel is added to the predicted value.

Further, the method of extracting the pixels surrounding the pixel to be coded and the number thereof, the Qe table 2 of the Q-Coder 16
6 and the state change method are not limited to the above-described embodiment, and any method can be used.

The image data compression device 11 and Q-
It goes without saying that the number and types of circuits and members constituting the coder 16 and the like are not limited to the above-described embodiment.

[0045]

According to the first aspect of the present invention, when a plurality of surrounding pixels are a specific pattern, data indicating that the predicted value is invalid is stored, and when the specific pattern is the specific pattern, the variable of the encoding means is set to a predetermined value. In this case, the encoding is fixedly performed so that an increase in the generated code amount for an input value having a high frequency of deviating the predicted value can be suppressed, and the compression ratio can be significantly increased. As a result, it is suitable for use in a binary image compression / decompression device.

[0046]

[Brief description of the drawings]

FIG. 1 is a block diagram of an encoding device.

FIG. 2 is a block diagram of a Q-Coder of the encoding device.

FIG. 3 is a diagram illustrating a prediction value table of the encoding device.

FIG. 4 is a diagram illustrating values of surrounding pixels when a prediction value table of an encoding device is not used.

FIG. 5 is a diagram illustrating values of surrounding pixels when a prediction value table of an encoding device is not used.

FIG. 6 is a flowchart of encoding performed by the encoding device.

FIG. 7 is a flowchart of encoding by a Q-Coder of the encoding device.

FIG. 8 is an encoding flowchart using a conventional Q-Coder.

FIG. 9 is a diagram showing conventional image data and surrounding pixels of an encoding target pixel.

FIG. 10 is a diagram showing a conventional predicted value table.

FIG. 11 is a circuit configuration diagram of a conventional prediction error calculation device.

FIG. 12 is a diagram for explaining arithmetic codes.

FIG. 13 is a diagram for explaining arithmetic codes.

FIG. 14 is a diagram for explaining the principle of Q-Coder.

FIG. 15 is an encoding flowchart using Q-Coder.

FIG. 16 is a diagram showing a state change of a Q-Coder.

[Explanation of symbols]

 Reference Signs List 11 image data compression device 12 image data storage device 13 address generation device 14 pixel prediction value storage device 15 prediction error calculation device 16 Q-Coder 17 encoding storage device 18 control device 21 C register 22 A register 23 selector 24 adder / subtractor 25 S Counter 26 Qe table 27 Q-Coder controller A Width of number line to be divided C Starting point of number line to be divided M Data with high probability of occurrence L Data with low probability of occurrence Pe Prediction probability of "M" coming out Qe of "L" Probability of coming out

Claims (2)

(57) [Claims] 1. A data supply means for supplying data to be encoded, and a predicted value storage for storing, as a predicted value table, predicted values of pixels to be encoded corresponding to values of a plurality of pixels around the pixel to be encoded. Means, a prediction error calculation means for calculating a prediction error based on the encoding target pixel supplied from the data supply means and a prediction value output from the prediction value storage means, A prediction error, an encoding device comprising encoding means for encoding by arithmetic encoding in which a division ratio of an arithmetic code is dynamically changed by changing a predetermined variable, wherein the prediction value table is It has data indicating that the prediction value is invalid when a plurality of surrounding pixels are a specific pattern, and in the case of the specific pattern, encoding is performed by fixing the variable of the encoding means to a predetermined value. Encoding apparatus according to claim. 2. The encoding means according to claim 1, wherein said arithmetic code has a division ratio of:
Claims characterized by using a dynamically changing Q coder
Item 7. The encoding device according to Item 1.