JPH0564008A - Encoder - Google Patents

Abstract

(57) [Abstract] [Purpose] To provide an encoding device capable of suppressing the amount of generated codes even when a predicted value does not hit, and having high data compression efficiency. An image data compression device 11 is designated by an image data storage device 12 for storing data to be compressed, and an address generation device 13 for designating an address of a predicted value by the values of several pixels around a pixel to be encoded. The pixel prediction value storage device 14 that outputs the prediction value (X) from the prediction value table 31 based on the value corresponding to the address, the output from the image data storage device 12, and the prediction value (X ) A prediction error calculation device 15 for calculating a prediction error based on the output,
A Q-Coder 16 that encodes the calculated prediction error is provided, and the prediction value table 31 divides the input pattern into a specific input pattern that does not hit the predicted value and an input pattern that does not hit the predicted value, and specifies that the predicted value does not hit easily. For input patterns, the prediction value is invalidated and the encoding variables Qe and M are used.
Fix PS so that Qe is not updated.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an encoding device used in an image data processing device or the like for compressing / decompressing image data, and more particularly to encoding using an Q-Coder which is a type of arithmetic code. The present invention relates to an encoding device.

[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 high-efficiency coding of the image.
ding), or simply picture coding. In addition, this technique is based on data compression coding, redundancy suppression coding, and bit rate reduction coding.
on coding) and so on.

An image that 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 data is called a binary image. Binary images generally have large redundancy, and data compression is possible by the method of information source coding. Since the number of quantization levels in the amplitude direction is two, the image quality of a binary image may be determined by the sampling density.

The most important data compression encoding is
Predictive coding and transcoding
form coding and vector quantiza
tion). Often, these two and three parties are combined (hybrid coding), and entropy coding (variable-length coding, Huffman coding) is a powerful means of increasing the data compression effect by combining the above methods. Often used.

Among the entropy codings for removing redundancy, one of the most typical entropy codings is unequal length coding, which is a short code for a high output level and an appearance frequency. A long code is assigned to each low output level. As a result, the average code length of code output can be shortened. By performing entropy coding, the code generation rate is not constant. Since a general transmission line is designed to transmit information at a constant speed, it is not possible to send out information (codes) generated unevenly to the transmission line as it is. Therefore, the information is temporarily smoothed by the buffer storage and then transmitted as a signal. Further, in order to prevent the overflow and underflow of the buffer storage, the buffer storage occupancy rate is monitored, and the redundancy removal encoding parameter is controlled so that it is always within a certain range.

Hereinafter, the above predictive coding, arithmetic code and Q-
Coder will be explained. Predictive Coding In the predictive coding, the past pixel value that has already been coded is stored in the memory in the encoder, and the predicted value (X) of the pixel X newly input from this is obtained. The difference (referred to as prediction error) X- (X) is quantized, the output level thereof is converted into an appropriate binary code, and the binary code is transmitted. Since the prediction value (X) can be reproduced by the same calculation on the receiving side, the prediction error is reproduced from the transmitted code, and this is added to the previously decoded image signal, and a new image signal is added. Can be restored. Since a highly accurate prediction is possible for a signal having a large correlation between sample values, the predicted value (X) becomes close to the actual signal X, and the prediction error becomes small. Therefore, it is possible to transmit 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 for compressing image data at a pixel level by encoding a prediction error. In FIG. 8, the process until the prediction error is calculated and encoded for one pixel of a binary image (for example, a facsimile) is as follows.

First, in step S1, a predicted value of a pixel to be coded is obtained from the seven pixels around the pixel to be coded (pixel to be coded), and in step S2 the pixel to be coded and the above prediction are calculated. EX-OR the values to calculate the prediction error. Next, the prediction error calculated in step S3 is encoded using Q-Coder (see FIG. 14 described later). This processing 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 predicted value object obtained by enlarging a part thereof. As shown in this figure, at the time of encoding, black and white (0 or 1) binary dot data is obtained by scanning the image data 1 from the upper left to the right. Let's encode the dot of a certain pixel X. In such a case, the original data is not directly encoded, but as shown in the enlarged part of FIG. Predict the value and find the error from the prediction. That is, as shown in FIG. 9, a prediction value table (prediction code table) 2 in which the prediction values are statistically stored based on the values of the seven pixels around a to g in the upper left direction of the pixel X.
(FIG. 10) is created, and the address of the prediction value table 2 is designated by the values of the seven pixels surrounding the above a to g to obtain the corresponding prediction value (X). The above-mentioned predicted value table 2 is a table in which predicted values (X) of 0 to 1 are statistically obtained in advance and stored in correspondence with all combinations of the pixel values ag to 0000000 to 1111111. When the image data 1 is scanned and there are many 0s (for example, white) around the pixel X, it is assumed that the dot data to be encoded also has many whites, so the prediction value (X) is set to 0 (white). .. On the contrary, in the case of solid painting, the probability of being 1 (for example, black) is assumed to be high, so the prediction value (X) is set to 1 (black). Like this
The optimum predicted value (X) corresponding to the pixel value of g is statistically obtained in advance and stored in the ROM or the like, and the predicted value (X) and the pixel X are EX-OR (exclusive Logical OR circuit 3
To EX-OR logic to calculate the prediction error.
As a result of EX-OR, "0" is set if the prediction is correct, and "1" is set if the prediction is incorrect. As long as the prediction is correct, there will be many "0" s. If this data with many "0s" is passed through an encoding device and encoded, this is data with a large amount of bias, so considerable compression can be expected. In this way, if the predicted value (X) based on the pixel values of a to g matches X, the compression rate becomes high.

Q is the prediction error calculated as described above.
-It will be encoded 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 probability of occurrence of data to be encoded on the number line of 0 to 1. Therefore, the arithmetic code will first be briefly described. Arithmetic Code The arithmetic code divides the number of linear numbers 0 to 1 by the occurrence probability of the data to be encoded, thereby replacing the original data once with the occurrence frequency (occurrence probability). For example, as shown in FIG. 12, input values 11001 ... P (0 ≦ P ≦ 1) with a high prediction probability of “1” and prediction probability Q (Q = 1−0) of “0”.
P) and the occurrence frequency according to P. That is,
Give two variables C (origin) and A (width) on the number line,
Initially, C = 0 and A = 1 (see FIG. 13A). When the probability of occurrence 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 a code "1" with a high occurrence frequency is generated when dividing the number line, the width of the number line is set to P and the origin (starting point) is left unchanged. ii) Further, when a code "0" having a low occurrence frequency is generated when dividing the number line, the position of the origin (C) is moved by P to change the width A, as shown in FIG.

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

Therefore, the origin C is divided when a code "1" having a high occurrence frequency comes, but is not changed (moved), and is divided and divided as long as the code "1" having a high occurrence frequency continues. The position of the origin does not change just by cutting. That is, as the number of codes with a high occurrence frequency increases, the means for expressing the division position is below the decimal point, and with a high frequency of occurrence, the number of digits does not increase even if the division progresses further (the code "0" with a low occurrence frequency). The position of the origin moves only when "is"). Therefore, as long as a code with a high occurrence frequency continues, even if a code of thousands of bits comes, it can be expressed by a certain bit line (for example, several tens of bits). If the occurrence probability and the final code are present, the original code can be obtained (restored) by following the reverse procedure. In this way, the greater the deviation of the code with respect to the one whose occurrence probability is known in advance, the higher the compression rate can be encoded.

The arithmetic code described above can be encoded with high efficiency, but has the following drawbacks. First, it is necessary to know the occurrence frequency (occurrence probability) in order to obtain the above-described expected probability P of "1" and expected probability Q of "0". The occurrence frequency must be scanned in advance for all data. If you can't decide. For example, in a facsimile or the like, the frequency of occurrence cannot be known until the entire text or the like is scanned once. Further, since P and Q are not integers, many digits below the decimal point are required to improve the accuracy, and it is very difficult to calculate the number line with a large number of digits.

Q-Coder, which is a kind of arithmetic code, has been proposed as a solution to the above-mentioned drawbacks of arithmetic code (A multi).
-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).

The Q-Coder will be described below. Q-Coder In Q-Coder, the number line 0 to 1 is divided by the probability of occurrence of data to be encoded, which is basically the same as the above-mentioned arithmetic code, but the drawbacks of the above arithmetic code are solved. In order to do so, the following improvements have been made. That is, in order to eliminate the above drawbacks, the P and Q are
Instead of scanning all data in advance and calculating the probability of occurrence, it is assumed that it is 0.5 because the probability of occurrence is unknown at first, and this probability of occurrence changes dynamically as the code is input. Let For example, assuming that P = 0.5, P is 0 ..
The value is changed to be larger than 5 (P> 0.5).
When the number of “0” s increases during scanning, the probability of occurrence is decreased and P is made smaller than 0.5 (P <0.5). By dynamically changing the occurrence probability in this way (this is called the 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 the table shown in FIG. 16, which will be described later.

On the other hand, in order to solve the above-mentioned drawback, in the above-mentioned arithmetic code, the width A of the original number line is multiplied by the occurrence probability P to obtain a new width (A ← A ×
P), if this P has several digits after the decimal point, such as 0.3256, it was difficult to calculate due to the accuracy, but Q-Code
In r, all the multiplications at the time of division are replaced with additions and subtractions so as to eliminate the above drawbacks. 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 probabilities.

Q-Coder with reference to FIGS.
The outline of is described. FIG. 14 is a principle diagram showing a process of Q-Coder encoding. In this figure, the Q-Coder represents a series of input values by one point on the number line in the range of ₀ to A ₀ (normally 1), and the value at that point is transmitted as a code series. First, when the width A ₀ starting point C ₀ is given, the width A _{0 is set} to Pe: Qe (Pe is an expected probability of "M", Qe is an expected probability of "L" according to the input sequence head value, and 0 <P
e ≦ 0.5, Qe = 1−Pe) and obtain the next width A ₁ and starting point C ₁ . Similarly, division is performed according to the next input sequence value to obtain the width A ₂ and the starting point C ₂ . This is sequentially repeated to obtain the desired coded sequence. The encoding process shown in FIG. 14 is performed using 4-bit data “MMLM” (11 when M = 1).
This is the operation when 01) is input. The point at the end of division for all inputs is used 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 into A · Qe.

That is, assuming that 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, multiplication at the time of division is replaced with addition and subtraction to facilitate the calculation, and it is approximated as A _n-1 = 1 and at the time of MPS, An = A _n-1 · Qe, Cn = C _n-1 + Qe. And LPS
In this case, An = Qe is set and the number line is divided (see FIG. 15).
(See Steps S11 to S13 of the Q-Coder flow).
Then, in step S14, A and C are normalized so that 1 ≦ A <2 each time (for example, when A <1 is shifted to the left until A ≧ 1), the calculation accuracy is secured. In S15, Qe is updated and the Q-Coder flow is ended. This Qe update is to dynamically change Qe so that the lower line goes up as shown in FIG. 14 in the case of MPS, for example. In addition, 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 moves toward the center by addition as shown in the figure. Further, in the Q-Coder, the LPS occurrence probability seed value Qe corresponding to the division ratio is also updated every time. Qe value is shown in Figure 1.
In the U-shaped state diagram shown in FIG. 6, the Qe value of the state is determined by designating 30 states that take values from 0 to 29. That is, as shown in FIG. 16, the bit with high occurrence frequency is MPS, and the left side of the U-shape is M
PS = 1, the right side is set to MPS = 0, and the Qe value starts at 0.5 (position of state 0 of states 0 to 29), which is the maximum. Then, every time one input value is encoded, the position of this U-shaped state is moved up and down as shown by m in FIG. 16 to change the state. State 0
There is a unique Qe value for 29, and in state 0, Qe =
0.5, a very small value in state 29 (eg
0.00018).

The method of changing Qe depends on the assumed MPS.
When (for example, MPS = 1) and the MPS that actually comes in match, the states in the table of FIG. 16 are climbed up one by one. That is, if the number of assumed MPS = 1 is large, the occurrence frequency is high, and therefore the occurrence probability is considered to be high.

When several 0s continue, the states in the table of FIG. 16 are skipped by two (or three) to speed up the follow-up. Then, in the middle of the table of FIG. 16 (position of state 0), when 1 other than MPS = 1 comes, it is assumed that the frequency of occurrence is 0 thereafter, and MPS = 0 described above assuming MPS = 0. Change as in the case of 1. Therefore, whether MPS is 1 or 0 can be followed by the one with the highest occurrence frequency.

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, LPS near state 0
When is 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 a conventional coding apparatus using the Q-Coder,
Since the prediction error is uniformly coded using the prediction value table (FIG. 10) even in the input pattern where the prediction value is hard to hit, LPS is often input to the Q-Coder. Since there are many upper and lower glyph states, even if an input pattern with low prediction value accuracy is known, the generated code amount cannot be suppressed. That is, if the assumed MPS and the input MPS match as shown in FIG. 16, the U-shaped states of FIG. 16 are climbed up one by one, and if they do not match, two U-shaped states (3 (3) Although it has good followability because it was designed to go down by skipping, for example, 0 may continue a little when MPS continues to match (when 1 is input when MPS = 1 is assumed). Then, the U-shaped upper state, which has a high probability of occurrence and is highly efficient in encoding, immediately falls to the lower state. For this reason, the division of the number line becomes rough and the generated code amount increases. That is, there is a problem in that the number of codes increases at that point due to a small number of non-MPS portions continuing, and it takes time to climb to the upper state once the state has dropped to the lower 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, there is a high probability that the prediction will be wrong. For example, in the prediction value table 2 of FIG. 10, there is a case where the values of the seven pixels a to g around the pixel X to be coded are 1 or 0 and half. In such a case, there is a high probability that the predicted value will deviate, so if the predicted value deviates, it will fall from the upper state with high coding efficiency to the lower state by skipping two or three, and then the upper state again. It takes a long time to return to, and the generated code amount increases. Therefore, it is an object of the present invention to provide an encoding device that can suppress the amount of generated codes even when the predicted value does not hit and that has high data compression efficiency.

[0026]

The invention according to claim 1 is
In order to achieve the above object, a data supply unit for supplying data to be encoded, and a prediction value that stores a prediction value of a pixel to be encoded corresponding to values of a plurality of pixels around the pixel to be encoded as a prediction value table. Storage means, prediction error calculation means for calculating a prediction error based on the encoding target pixel supplied from the data supply means and the prediction value output from the prediction value storage means, and the prediction error calculation means A prediction error, a coding device comprising a coding means for coding by arithmetic coding in which the division ratio of the arithmetic code dynamically changes by changing a predetermined variable, wherein the prediction value table is When the plurality of surrounding pixels have data indicating that the predicted value is invalid when the pixel has a specific pattern, the variable of the encoding means is fixed to a predetermined value and is encoded when the pixel has the specific pattern. There. According to a second aspect of the present invention, a data supply unit for supplying data to be encoded and a predicted value of a pixel to be encoded corresponding to values of a plurality of pixels around the pixel to be encoded are stored as a prediction value table. Along with the prediction value storage means for storing data indicating that the surrounding plural pixels are a specific pattern, the encoding target pixel supplied from the data supply means and the prediction value output from the prediction value storage means. Prediction error calculating means for calculating a prediction error by means of the above, and encoding means for encoding the prediction error calculated by the prediction error calculating means. The specific pattern in the predicted value storage means is, for example,
And a pixel input pattern having a small probability of hitting the prediction value, as described in claim 2,
Further, the encoding means may use a Q coder in which the division ratio of the arithmetic code dynamically changes.

[0027]

The operation of the means of the present invention is as follows. In the invention of claim 1, the data to be encoded is supplied by the data supply means, and the prediction value of the encoding target pixel corresponding to the values of a plurality of pixels around the encoding target pixel is a prediction value table as a prediction value storage means. Remembered in. When the address of the prediction value table is specified by the values of several pixels around the pixel to be encoded, the value corresponding to the specified address is fetched from the prediction value storage means on the basis of the prediction value table and the prediction error as the prediction value. It is output to the calculation means. In this predicted value table, data indicating that the predicted value is invalid is added to a specific pattern in which a plurality of surrounding pixels have a small probability that the predicted value will hit,
The predicted value is not used for this specific pattern. Then, a prediction error is calculated by the prediction error means based on the encoding target pixel output from the data storage means and the prediction value output from the prediction value generation means. 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.
When the predicted value is difficult to hit, the variable is fixed to a predetermined value and encoded. Therefore, it is possible to suppress the amount of generated code when the predicted value does not hit, and to significantly increase the compression rate. In the invention according to claim 2, the prediction value storage means stores the prediction value of the pixel to be coded as a prediction value table according to the values of the plurality of pixels around the pixel to be coded, and the plurality of surrounding pixels is a specific pattern. Is stored. Therefore, in addition to simply calculating the prediction error based on the prediction value, various controls can be performed based on the additional data when the surrounding pixels have a specific pattern.

[0028]

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 apparatus according to the present invention, which is an example applied to an image data compression apparatus. Figure 1
In the image data compression device 11, the image data storage device 12 that stores the data to be compressed and the address generation that specifies the address of the prediction value by the value of several pixels around the pixel to be encoded (encoding target pixel) The device 13, the pixel prediction value storage device 14 that outputs the prediction value (X) from the prediction value table 31 (FIG. 3) based on the value corresponding to the address designated by the address generation device 13, and the image data storage device 12 A prediction error calculation device 15 for calculating a prediction error based on the pixel to be encoded output from the pixel prediction value storage device 14 and the prediction value (X) output from the pixel prediction value storage device 14, and by 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 and.

FIG. 2 is a block diagram of the Q-Coder 16. In FIG. 2, the Q-Coder 16 is a C register 21 that temporarily stores the starting point C data of the divided number line.
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. 22 output or C register 21 output is input to the input terminal A, the encoding variable (probability estimated value) Qe or fixed value read from the Qe table 26 described later is input to the input terminal B, and these input values are input. An adder / subtractor 24 that divides the number line by adding or subtracting, an S counter 25 that counts the state S that reads the LPS occurrence probability estimated value Qe from the Qe table 26 by taking a value of 0 to 29, and states 0 to 29 Qe table 26 that stores the Qe value corresponding to, and input / output of encode input or decode output bit by bit and MPS is input. It is constituted by outputs a control signal and Q-Coder controller 27 for controlling the operation of each unit.

The input / output bit of the C register 21 is 25b.
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 supplies the encoding input from the encoding storage device 17 to the lower 8 bits at the time of decoding. .. A value whose code range has been narrowed by addition is input to the C register 21, and the number of bits left in the register at the end of encoding due to bit shift internally becomes the width, that is, the code. The C register 21 shifts the divided and reduced value to the value 1 to 2 by left-shifting until a bit is set, and then Q.
2 longer than the 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 code. When adding and outputting the result, the controller 27
D, SHIFT is instructed when shifting left and normalizing.

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

The Qe table 26 has states 0-2.
9 is a table for storing a Qe value that takes a value of 0 to 29 corresponding to 9, and the Qe value designated by the variable (state) S of the S counter 25 is read from the Qe table 26 and added / subtracted. 24 is output. The S counter 2
As shown in FIG. 16, if the MPSs match, the numeral 5 advances the count by 1 to indicate the upper state S, and if the MPSs do not match, the count is returned by 3, 2, or 1 to decrease the lower state. This is a counter that indicates S, and the initial value is 0.
Is.

Further, the Q-Coder controller 27 has 1b
Each time it is encoded, 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 state S is reduced by two or three. If the MPS does not match when S = 0, the MPS and LPS are exchanged, and after the exchange, the MPS
The state S is determined by comparing S with the input bit. S
The Qe table 26 value indicated by is the required Qe value.

FIG. 3 is a diagram showing a prediction value table 31 stored in the pixel prediction value storage device 14. In this figure, the prediction value table 31 is a prediction value (0 or 1) that statistically stores the prediction value based on the values of the seven pixels a to g around the pixel X to be encoded.
The storage unit 31a includes a fixed value storage unit 31b that stores additional information for fixing the Qe and MPS without determining the predicted value (see -in the figure) when the predicted pattern is difficult to hit. The specific input patterns of the surrounding 7 pixels that are hard to hit the predicted value are shown in FIGS. 4 and 5, for example. Figure 4
And as shown in FIG. 5, the peripheral 7 pixels are 1010101 or 0.
For a predictive value such as 101010 whose occurrence probability is close to 50% is hard to hit, the predictive 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. Prediction value table 3 based on the values of several pixels around the pixel to be encoded by the address generator 13
When the address of 1 (FIG. 3) is designated, the pixel prediction value storage device 14 stores the value corresponding to the designated address in the prediction value table 3
It is extracted based on 1 and is output to the prediction error calculation device 15 as a prediction value. In this case, the prediction value is obtained from the surrounding 7 pixels for the coding target X, and if Qe and MPS are not fixed, the prediction error calculation device 15 calculates the prediction error between the coding target and the prediction value as in the conventional case. On the other hand, the peripheral 7 pixels are 0101010
For items such as 1010101 and 1010101 that are difficult to predict, Qe = 0.5, MPS =
It is fixed at 1, and Qe is not updated. Q-Coder 1
At 6, the image data is compressed 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 flow charts shown in FIGS. 6 and 7. 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 encoded is obtained from the peripheral 7 pixels of the pixel to be encoded (encoding target pixel). It is determined whether or not it is the specific input pattern, and when it is not the specific input pattern, it means that Qe and MPS are not fixed. Calculate the error. Next, the prediction error calculated in step S24 is encoded using Q-Coder, and this flow ends.

On the other hand, in the case of the specific input pattern of the surrounding 7 pixels where the predicted value is hard to hit, the predicted value is not used in step S25, the Qe and MPS are fixed and encoded by the Q-Coder 16, and the process ends.

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

First, in step S31, it is determined whether the input value is MPS or LPS. When the input value is MPS, Q is determined in step S32.
Fixing e = 0.5 and 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 each time so that 1 ≦ A <2 (for example, A <
When it is 1, the calculation accuracy is ensured by shifting left until A ≧ 1), and the present flow ends. Also, Qe
= 0.5, MPS = 1 and Qe when coded
Will not be updated. Therefore, even if the LPS is encoded,
The U-shaped state shown by does not decrease, and the generated code amount does not temporarily increase in the subsequent encoding of the input sequence.

As described above, the image data compression apparatus 11 of the present embodiment has the image data storage apparatus 12 for storing the data to be compressed and the several pixels around the pixel to be encoded (encoding target pixel). An address generator 13 for designating 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 the predicted value table 31 based on the value corresponding to the address specified by
4 and a prediction error calculation device 15 that calculates a prediction error based on the pixel to be encoded output from the image data storage device 12 and the prediction value (X) output from the pixel prediction value storage device 14, A Q-Coder 16 that compresses image data by encoding a prediction error, a coding storage device 17 that sequentially stores generated codes, and a control device 18 that controls the operation of each device are provided, and the prediction value Table 3
1 divides the input pattern into a specific input pattern whose predictive value is hard to hit and an input pattern whose predictive value is hard to hit, and invalidates the predictive value for the specific input pattern whose predictive value is hard to hit, and the encoding variables Qe, MPS Fixed, Qe
Since it is not updated, it is possible to prevent the generated code amount from increasing when the predicted value deviates. In this way, since it is possible to suppress an increase in the amount of generated code for an input value whose prediction value often deviates, it is possible to realize a binary image compression / expansion device with a high compression rate. When applied to, the transmission time can be shortened.

The present embodiment is an example in which the encoding device is applied to the image data compression device, but of course the present invention is not limited to this, and can be applied to any device as long as it uses a prediction value. Needless to say.

Further, in the present embodiment, the input pattern of the prediction value table is divided into two, the prediction value is invalid if the prediction value is difficult to hit, the encoding variables Qe and MPS are fixed, and Qe is updated. Although it is not provided, it goes without saying that any information may be added as long as the information corresponding to the pixel input pattern is added to the predicted value.

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

Further, the image data compression device 11 and Q-
It goes without saying that the numbers and types of circuits and members that make up the Coder 16 and the like are not limited to those in the above-described embodiments.

[0045]

According to the first aspect of the present invention, data indicating that the predicted value is invalid when the surrounding plural pixels have a specific pattern is stored, and the variable of the encoding means is set to a predetermined value when the specific pattern is used. Since the fixed value is set to, and the encoding is performed, it is possible to suppress an increase in the generated code amount with respect to an input value whose prediction value often deviates, and to significantly increase the compression rate. As a result, it is suitable for use in a binary image compression / decompression device.

According to the second aspect of the present invention, the predicted values of the pixels to be coded are stored in the values of the plurality of pixels around the pixel to be coded as a prediction value table, and the plurality of surrounding pixels are a specific pattern. Since the data indicating the is stored, various encoding processing can be performed based on this data.

[Brief description of drawings]

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

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

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

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

FIG. 5 is a diagram showing values of surrounding pixels when a prediction value table of the 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 Q-Coder of the encoding device.

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

FIG. 9 is a diagram showing conventional image data and pixels surrounding a pixel to be encoded.

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

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

FIG. 12 is a diagram for explaining an arithmetic code.

FIG. 13 is a diagram for explaining an arithmetic code.

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

FIG. 15 is an encoding flowchart according to Q-Coder.

FIG. 16 is a diagram showing Q-Coder state changes.

[Explanation of symbols]

 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 occurrence probability L Data with low occurrence probability Pe Predicted probability of “M” occurrence of Qe “L” Prediction probability

Claims (4)

[Claims] 1. A data supply unit for supplying data to be encoded, and a prediction value storage for storing a prediction value of a pixel to be encoded corresponding to values of a plurality of pixels around the pixel to be encoded as a prediction value table. Means, a prediction error calculation means for calculating a prediction error based on the encoding target pixel supplied from the data supply means and the prediction value output from the prediction value storage means, and the prediction error calculation means A prediction error, a coding device comprising a coding means for coding by arithmetic coding in which the division ratio of the arithmetic code dynamically changes by changing a predetermined variable, the prediction value table, A plurality of surrounding pixels have data indicating that the predicted value is invalid when the pixel has a specific pattern, and when the pixel has the specific pattern, the variable of the encoding means is fixed to a predetermined value for encoding. Encoding apparatus according to claim. 2. A data supply means for supplying data to be encoded, a prediction value of a pixel to be coded corresponding to values of a plurality of pixels around the pixel to be coded is stored as a prediction value table, and A prediction value storage unit that stores data indicating that a plurality of surrounding pixels have a specific pattern, a prediction error based on the encoding target pixel supplied from the data supply unit and the prediction value output from the prediction value storage unit An encoding device, comprising: a prediction error calculating unit that calculates the error, and an encoding unit that encodes the prediction error calculated by the prediction error calculating unit. 3. The encoding device according to claim 2, wherein the specific pattern in the prediction value storage means is a pixel input pattern having a small probability of being hit by the prediction value. 4. The coding apparatus according to claim 1, wherein the coding means uses a Q coder in which a division ratio of the arithmetic code dynamically changes.