JP3123795B2 - Encoding device and decoding device using arithmetic code - 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 device and a decoding device that use arithmetic codes for data compression and decompression of image information.

[0002]

2. Description of the Related Art In recent years, as a coding method for coding image information, an arithmetic code, which is one of predictive coding methods, has attracted attention.

An arithmetic code maps a symbol series of data to be encoded on a number line from 0 to 1 into a section having a width determined according to the appearance probability of each symbol, and maps one point in the section. Is a binary decimal value that specifies

In encoding image information using this arithmetic code, while sequentially inputting pixel data of each line as a symbol sequence, the probability of occurrence of the inferior symbol is predicted based on surrounding pixel data, and the prediction is performed. The above processing is performed based on the result.

[0005] The predicted value of the occurrence probability of the inferior symbol can be calculated by a certain arithmetic expression. However, since the calculation requires multiplication, the hardware of the apparatus becomes complicated and the operation time is long. There is an inconvenience.

For this reason, in general, a data group of probability values is stored in a table memory in advance, and the stored probability values are read out one by one according to a result of a certain arithmetic processing. That is, conventionally, for example, as shown in FIG. 10, the probability value data d1 to d10 of each value equal to or less than the appearance probability “0.5” of the inferior symbol is stored in the table memory.

When the encoding process is executed, at the start of the process, the appearance probability of the inferior symbol of the image information to be processed is unknown, and therefore, as shown in FIG. The processing is started on the assumption that appears with the same probability.

By the way, the appearance probability of a symbol differs depending on the type of image. For example, a binary image such as a character has a low probability of about “0.1”, whereas a pseudo halftone image obtained by dithering a grayscale image has a high probability of occurrence of a less probable symbol of about “0.4”. Become.

Assume that the processing of an image in which the actual occurrence probability of the inferior symbol is slightly higher than "0.1" is started.
At this time, the predicted value is the initial value “0.5”, but it is determined that the occurrence probability of the inferior symbol is low based on the appearance frequency of the symbol of the actual pixel data. In this case, as shown by the solid line in FIG.
.. are sequentially read out as in d2. Then, after reading the probability value data d5, it is determined that the actual appearance probability is higher than the value,
The next higher probability value data d4 is read again. Since the actual appearance probability is between the probability value data d4 and d5,
Thereafter, the probability value data d4 and d5 are read alternately, and a predicted value close to the actual value is maintained.

[0010] By the way, in a code generated by encoding an arithmetic code, the smaller the error between the predicted value and the actual appearance probability, the smaller the number of data bits and the higher the coding efficiency.

However, in the above case, it takes time until the probability value data d4 is read and the error of the predicted value decreases. For this reason, the number of data bits of the generated code has increased during that period, and the coding efficiency has decreased.

Next, it is assumed that the processing of an image in which the actual occurrence probability of the inferior symbol is slightly higher than "0.4" is started.
In this case, the probability value data d1 is first read as shown by the dashed line in FIG. Next, it is determined that the actual appearance probability is higher than that value, and “0.
5 ”. And in this case, the predicted value is
"0.5" and the value of the probability value data d1 are set alternately.

However, in this case, the predicted value "0.
5 "and the probability value data d1 have a large error with respect to the actual appearance probability of the inferior symbol. Therefore, as above,
The number of data bits of the generated code increases, and the coding efficiency decreases.

[0014]

As described above, conventionally,
Depending on the type of image to be processed, it takes time until the predicted value of the appearance probability of the inferior symbol approaches the actual appearance probability or the error increases, and the coding efficiency decreases. There is a problem that it is not possible to efficiently execute the processing.

The present invention solves the above-mentioned problems, and provides an encoding device and an encoding device using an arithmetic code capable of always efficiently executing the encoding / decoding processing of image information regardless of the type of image. The purpose is to do.

[0016]

To this end, the present invention provides
When encoding / decoding processing of pixel data is performed, different values are set in the data group of the probability value according to the type of image information to be processed.

[0017]

[Action] By setting a value according to the type of image information in the data group of probability values, the predicted value of the appearance probability of the inferior symbol approaches the actual appearance probability in a short time after the processing is started, and the error of the predicted value is reduced. Also decreases. Thus, the encoding / decoding of the image information can always be efficiently executed regardless of the type of the image.

[0018]

Embodiments of the present invention will be described below in detail with reference to the accompanying drawings.

FIG. 1A is a block diagram showing a transmitting side of an image transmitting apparatus according to a first embodiment of the present invention. In the figure, the inferior symbol appearance probability data table 1 stores a data group of probability values. In this embodiment, a data group Da for binary images such as characters and a data group Db for halftone images such as photographic images are stored in the inferior symbol appearance probability data table 1. The template pixel extracting unit 2 receives pixel data of a transmission image and extracts a plurality of pixel data at a certain position around a target pixel. Probability evaluation / prediction unit 3
Is for predicting the appearance probability of the inferior symbol of the target pixel based on surrounding pixels, and the storage unit 4 temporarily stores a predicted value and the like. The encoding unit 5 generates an arithmetic code, that is, encoded data by a predetermined arithmetic operation based on the prediction result. The transmitting unit 6 adds various data to the generated encoded data and transmits the data.

FIG. 1B shows a receiving side of the image transmitting apparatus, and a receiving section 7 receives transmission data from the transmitting side. The inferior symbol appearance probability data table 8, like the inferior symbol appearance probability data table 1, stores a data group of probability values, and includes a data group Da for binary images such as characters and a data group for halftone images. And a group Db. Decoding section 9
Is to restore the received encoded data to the original pixel data by a predetermined arithmetic operation. The template pixel extracting unit 10 receives the restored pixel data and extracts a plurality of pixel data at a certain position around each pixel. The probability evaluation / prediction unit 11 predicts the appearance probability of the inferior symbol of the pixel data based on surrounding pixels. The storage unit 12 temporarily stores a predicted value and the like.

Next, the operation of the image transmission apparatus according to the present embodiment having the above configuration will be described.

When the transmitting side starts the operation, it first transmits control information, as shown in FIG. This control information is, for example, notification information to the receiving side such as an image size and an image resolution, and transmits various kinds of information as necessary (processing 10).
1). FIG. 3 shows various data transmitted from the transmission side to the reception side.

Thereafter, an external device (not shown) inputs an inferior symbol appearance probability data table 1 with an image type signal indicating whether the transmission image is a binary image or a halftone image. The binary image is, for example, a binary image of black and white like an image of a character document. The halftone image is a halftone image such as a photograph that has been subjected to pseudo halftone processing by dither processing or error diffusion processing.

Inferior symbol appearance probability data table 1
Selects a data group Da for a binary image or a data group Db for a halftone image such as a photographic image in accordance with the instruction of the image type signal. That is, after that, the data group Da selected in response to the read request from the probability evaluation / prediction unit 3
Alternatively, Db is output (process 102). Next, an identification code indicating which of the data groups Da and Db has been selected is transmitted (process 103).

Thereafter, pixel data of a transmission image is sequentially input from an external device (not shown), and encoding processing is performed on the input pixel data. That is, the template pixel extraction unit 2 sets each pixel of the input pixel data as a target pixel and extracts pixel data at a certain position around the target pixel. Next, the probability evaluation / prediction unit 3 inputs the pixel data of the target pixel and the surrounding pixels, and predicts the appearance probability of the inferior symbol for each bit of the target pixel. Then, the probability values are sequentially read from the inferior symbol appearance probability data table 1 as the predicted value.

FIG. 4 shows the reading operation of the probability value. That is, the probability evaluation / prediction unit 3 sets “0.5” as the initial value of the predicted value of the appearance probability of the inferior symbol.
Is set (process 201), and a predetermined arithmetic operation is executed (process 202). In this arithmetic operation, a probability range called an “organ” to be mapped on a number line from 0 to 1 is calculated. The agend becomes smaller each time an arithmetic operation is repeated. Then, when the value of the augend decreases to a certain value, re-normalization to return to “1” is executed. Note that, for this arithmetic processing, the storage unit 4 temporarily stores various variables such as the calculated agent.

When the above arithmetic operation is executed once, it is determined whether or not renormalization has been executed (step 203). If the renormalization has not been executed (N in step 203), the arithmetic operation is repeated. Execute (to process 202).

On the other hand, when the re-normalization is performed (Y in step 203), the appearance symbol of the pixel data is determined (step 204). Here, if the appearing symbol is the superior symbol (“predominant” in step 204), a probability value that is one step smaller than the currently set predicted value is read from the inferior symbol appearance probability data table 1, and The value is output as a predicted value of the appearance probability of a new inferior symbol (process 205).

On the other hand, if the appearing symbol is the inferior symbol ("inferior" in step 204), a probability value that is one step larger than the currently set predicted value is read out, and that value is replaced with the new predicted value. (Step 206). Thereafter, the arithmetic operation is repeated (to process 202).

The probability evaluation / prediction unit 3 sequentially outputs the predicted values of the occurrence probabilities of the inferior symbols as described above,
Generates a predetermined arithmetic code based on the predicted value.
The transmitting unit 6 transmits the generated arithmetic code as encoded data (process 104).

Now, for example, as shown in FIG. 5, a data group Da for binary images in the inferior symbol appearance probability data table 1 includes one having a probability value "0.2" or less.
0 types of probability value data a1 to a10 are stored,
As the data group Db for the halftone image, the probability value “0.5”
It is assumed that the following ten types of probability value data b1 to b10 are stored.

It is now assumed that the pixel data of the binary image is coded, and the appearance probability of the actual inferior symbol of the pixel data is slightly higher than "0.1". At this time, after setting the predicted value of the appearance probability of the inferior symbol to the initial value “0.5”, the probability evaluation / prediction unit 3 as shown in FIG. Judge. Then, as shown by the solid line in the figure, the probability value data a1, a2, and a3 are sequentially read from the data group Da for the binary image, and the predicted value is lowered by one step. And
Thereafter, it is determined that the actual appearance probability is higher than the value of the probability value data a3, and the probability value data a2 one step higher is read out again. Since the actual appearance probability is intermediate between the probability value data a2 and a3, thereafter, the probability value data a2 and a3 are alternately read to maintain a predicted value close to the actual value.

In this case, since the set values of the probability value data a1 to a10 are low as a whole, the predicted value of the occurrence probability of the inferior symbol is clearly calculated by comparison with the predicted value indicated by the solid line in FIG. After the start, it approaches the value of the actual appearance probability in a short time. The smaller the error of the predicted value is, the smaller the number of data bits of the code generated by the encoding unit 5 is. As a result, the coding efficiency is improved compared to the related art.

Next, it is assumed that the pixel data of the halftone image is encoded, and that the actual occurrence probability of the inferior symbol of the pixel data is slightly higher than "0.4". In this case, as shown by a dashed line in the figure, the probability value data b1, b2, and b3 of the halftone image data group Db are sequentially read, and the actual appearance probability is higher than the value of the probability value data b3. The value data b2 is read again. Thereafter, the probability value data b2 and b3 are alternately read to maintain a predicted value close to the actual value.

In this case, the probability value data b1 to b6 are
Since the value is set to a large value at “0.3” or more, FIG.
As is clear from the comparison with the predicted value indicated by the one-dot chain line, the error of the predicted value of the occurrence probability of the inferior symbol is reduced. As a result, similarly to the above, the number of data bits of the code generated by the encoding unit 5 is reduced, and the encoding efficiency is improved.

In the example of FIG. 5, the probability value data b7 to
b10 is set to a low value such as "0.2" or less. In the blank portion of the original image, the probability of occurrence of the inferior symbol of the pixel data decreases. In such a case, the probability value data b7 to b10 are read. Thereby, the error of the predicted value can always be reduced.

As described above, pixel data is coded to 1
After transmitting the pages, it is checked whether there is an image of the next page (process 105). If there is an image of the next page (Y in process 105), the data group D in the inferior symbol appearance probability data table 1 according to the image type of the page
a or Db is selected and the same processing as above is repeated (processing 102). As a result, the data group identification code and the encoded data corresponding to the next page are transmitted.

In this manner, the data is transmitted up to the last page (N in process 105), and the transmission process ends.

On the other hand, on the receiving side, as shown in FIG. 7, the receiving section 7 first receives control information and prepares each section for reception (process 301). Next, the transmitted data group identification code is received (process 302), and the inferior symbol appearance probability data table 8 stores the binary image data group Da or the halftone image data group according to the data group identification code. Db is selected (step 303).

Thereafter, reception of the encoded data is started, the received encoded data is sequentially decoded, and the obtained pixel data is output. That is, in this case, the decoding unit 9 inputs the received encoded data, and
The pixel data is sequentially reproduced based on the prediction result of. The template pixel extraction unit 10 extracts surrounding pixel data each time the pixel data is reproduced by one bit. The probability evaluation / prediction unit 11 includes the probability evaluation / prediction unit 3 on the transmitting side.
By the same processing as described above, the appearance probability of the inferior symbol is predicted for each bit of the pixel data. The pixel data restored in this way is output (the above processing 304).

When the processing for one page is completed in this way, it is checked whether there is an image for the next page (processing 3).
05). If there is a next page (Y in step 305), the same processing is repeated (to step 302). When the processing is performed up to the last page (N in step 305), the operation is terminated.

As described above, in this embodiment, the data group Da for the binary image and the data group Db for the halftone image are stored in advance in the inferior symbol appearance probability data table 1, and the pixel data of the halftone image is stored. When the encoding / decoding process is performed, one corresponding to the image to be processed is selectively used. Thus, after the process starts, the predicted value of the appearance probability of the inferior symbol approaches the actual appearance probability in a short time, and the error of the predicted value also decreases. As a result, the coding / decoding of the image information can be efficiently executed for both the binary image and the halftone image.

The transmitting side selects the data groups Da and Db for each page and notifies the receiving side of the selection result. Accordingly, even when the transmitting side randomly transmits different types of images for each page, the receiving side can set the same data groups Da and Db as the transmitting side and execute the decoding process correctly. .

FIGS. 8A and 8B show an image transmission apparatus according to another embodiment of the present invention. In the figure, the same reference numerals as those in FIGS. 1A and 1B denote the same parts, and the difference from FIGS. 1A and 1B is that the transmitting side has And a table memory 15 is provided in place of the inferior symbol appearance probability data table 8 on the receiving side.

Inferior symbol appearance probability data generator 13
Is to generate a data group of probability values of appearance probabilities of inferior symbols according to the type of image, for example, by a certain arithmetic expression. The table memories 14 and 15 store generated data groups.

With this configuration, in this embodiment, when the transmitting side starts operation, the image type signal to be processed first is input to the inferior symbol appearance probability data generation unit 13. This signal indicates whether the image to be processed is a binary image or a halftone image.

Inferior symbol appearance probability data generator 13
Generates a data group of probability values of appearance probabilities of inferior symbols according to the image type. In this case, the data group to be generated is a binary image as shown in FIG.
Generating data of various probability values like the data group Da of
In the case of a halftone image, data of various probability values like the data group Db is generated. The table memory 14 stores the generated data group Da or Db.

When the transmitting side starts data transmission, the transmitting side shown in FIG.
As shown in (1), control information is transmitted first, and then data of various probabilities of the generated data group Da or Db is transmitted.
Then, similarly to the above-described embodiment, the coded data obtained by coding the pixel data is transmitted.

When the transmission of one page is completed and there is an image of the next page, the data group D corresponding to the type of the next image
Generate a or Db and transmit data of the probability. Then, the encoded data of the page is transmitted.

On the other hand, the receiving side first receives control information, executes a predetermined setting operation, and then receives a data group of probability values. The data memory 15 stores each received probability value. Then, the encoded data is received and decoded in the same manner as in the above-described embodiment. This operation is repeated for each page.

As described above, in this embodiment, the transmitting side:
At the start of the operation, a data group of the probability value of the occurrence probability of the inferior symbol is generated according to the type of the image to be processed, set in the table memory 14 and transmitted to the receiving side, and the receiving side stores the data group in the data memory. It is set to 15. This makes it possible to efficiently execute the encoding / decoding processing on various images, as in the above-described embodiment.

In this case, since the data group of the probability value generated on the transmitting side is transmitted to the transmitting side as it is, there is no need to prepare the data group on the receiving side in advance.

In the above-described embodiment, the probability value of the occurrence probability of the inferior symbol to be used is unilaterally determined on the transmitting side. However, the transmitting side transmits the data from the receiving side to the receiving side device before data transmission. May be set after receiving the above information and confirming that the receiving apparatus can respond to the determination of the transmitting side.

In the data group of the appearance probability of the inferior symbol, ten probability values are set for the binary image and the halftone image, respectively. It is needless to say that the error can be reduced.

Although the data group is set to two types, that is, a binary image and a halftone image, the data group may be set to three or more types of images. For example, it is conceivable that the halftone image is further classified into an image obtained by error diffusion processing and an image obtained by dither processing. The pixel data obtained by the error diffusion processing has a slightly higher probability of occurrence of the inferior symbol than the pixel data obtained by the dither processing. As described above, when the appearance probabilities of the inferior symbols are different, by setting each data group, the coding efficiency can be further improved.

Further, in each of the embodiments described above, the case of transmitting the coded data has been described. However, the coded data is stored in the storage device, or the stored coded data is read and restored to the original pixel data. In this case, it is obvious that the present invention can be similarly applied.

[0057]

As described above, according to the present invention, when encoding / decoding processing of pixel data is performed, different values are respectively assigned to data groups of probability values according to types of image information to be processed. After the start of the process, the predicted value of the appearance probability of the inferior symbol approaches the actual appearance probability in a short time, and the error of the predicted value decreases. The decoding process can always be efficiently executed.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an image transmission apparatus according to an embodiment of the present invention.

FIG. 2 is an operation flowchart of a transmission side.

FIG. 3 is an explanatory diagram of transmission data.

FIG. 4 is a flowchart illustrating an operation of reading a probability value.

FIG. 5 is an explanatory diagram showing a data group of occurrence probabilities of inferior symbols to be stored.

FIG. 6 is a graph showing changes in predicted values after the start of encoding / decoding processing.

FIG. 7 is an operation flowchart of a receiving side.

FIG. 8 is a block diagram of an image transmission apparatus according to another embodiment of the present invention.

FIG. 9 is an explanatory diagram of transmission data in the embodiment.

FIG. 10 is an explanatory diagram showing a conventional example of a data group of occurrence probabilities of inferior symbols to be stored.

FIG. 11 is a graph showing a transition of a conventional predicted value after the start of the encoding / decoding process.

[Explanation of symbols]

 1,8 Inferior symbol appearance probability data table 2,10 Template pixel extraction unit 3,11 Probability evaluation / prediction unit 4,12 Storage unit 5 Encoding unit 6 Transmitting unit 7 Receiving unit 9 Decoding unit 13 Generation of inferior symbol appearance probability data Part 14, 15 Table memory

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) H04N 1/41-1/419 H03M 7/30

Claims (13)

(57) [Claims] 1. A storage means for storing a data group of probability values arranged in order of magnitude, and a probability of appearance of a superior or inferior symbol of pixel data to sequentially read and input said probability values based on a result of a certain arithmetic processing. Encoding means for encoding pixel data according to an arithmetic coding scheme based on the output prediction value. An encoding device using an arithmetic code, characterized in that the group includes probability value setting means for setting different probability values depending on the type of input pixel data. 2. The memory according to claim 2, wherein said probability value setting means stores a plurality of types of data groups of said probability values in said storage means, and sets said probability values from one data group corresponding to the type of pixel data among said plurality of types. 2. The encoding apparatus according to claim 1, wherein said encoding apparatus comprises means for sequentially reading values. 3. The arithmetic unit according to claim 1, wherein said probability value setting means is means for generating a data group having a different probability value for each type of input pixel data and storing the data group in said storage means. An encoding device that uses codes. 4. The probability value setting means according to claim 1, wherein the probability value setting means sets different probability values depending on the type of image, that is, whether the pixel data is a binary image or a halftone image. An encoding device using the arithmetic code described in the above. 5. When transmitting coded data obtained by coding, there is provided means for transmitting identification information for identifying a data group of the probability value set together with the coded data. An encoding device using the arithmetic code according to claim 1. 6. The apparatus according to claim 1, further comprising means for transmitting a data group of the probability value set together with the encoded data when transmitting the encoded data obtained by the encoding. Encoding device using the arithmetic code. 7. When transmitting coded data obtained by encoding, the state of the receiving side is determined at the start of communication, and the data group is determined based on the states of both the receiving side and the transmitting side. 2. A coding apparatus using an arithmetic code according to claim 1, further comprising means for determining a probability value to be set in the arithmetic code. 8. A storage means for storing a data group of probability values arranged in order of magnitude, and said probability values are sequentially read out based on a result of a certain arithmetic processing, and a predicted value of an appearance probability of a superior or inferior symbol of pixel data. A decoding unit using an arithmetic code, comprising: a prediction unit that outputs encoded data; and a decoding unit that restores encoded data to pixel data by an arithmetic code decoding method based on the output prediction value. Is provided with probability value setting means for setting different probability values depending on the types of input pixel data. 9. The probability value setting means includes means for storing a plurality of types of the data group of the probability value in the storage means, and determining the probability value from one data group corresponding to the type of pixel data among the plurality of types. 9. A decoding device using an arithmetic code according to claim 8, wherein said decoding device comprises means for sequentially reading values. 10. The arithmetic unit according to claim 8, wherein said probability value setting means is means for generating a data group having a different probability value depending on the type of input pixel data and storing the data group in said storage means. A decoding device using codes. 11. The apparatus according to claim 8, wherein said probability value setting means is means for setting a different probability value depending on the type of image whether said pixel data is a binary image or a halftone image. A decoding device using the arithmetic code described in the above. 12. When encoded data is received, identification information for identifying the data group of the probability value is received together with the encoded data, and a probability value is set in the data group according to the identification information. 9. The decoding device using an arithmetic code according to claim 8, comprising: 13. When encoded data is received, a means for receiving the data group of the probability value together with the encoded data and storing the data group in the storage means is provided. A decoding device using the arithmetic code according to claim 8.