JP3457269B2 - Arithmetic encoding / decoding method and arithmetic encoding / decoding device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a coding device and a decoding device, and more particularly to an entropy prediction coding device / decoding device.

[0002]

2. Description of the Related Art A method of predicting a coded symbol according to the state of already coded peripheral pixels and arithmetically coding the prediction result based on the probability estimation value of the coded symbol determined for each state is the compression rate. It is known that it exhibits the most excellent characteristics. An example is the QM-coder, which is an encoder used in JBIG (ITU Recommendation T.82).

Hereinafter, QM-cod which is an arithmetic encoder for binary images
The general configuration and operation of er will be described.

As shown in FIG. 50, the QM-coder includes a context generation section 200, a context table (context memory) 210, a probability estimator 220, and an arithmetic encoder 230.
And.

The context generator 200 detects 1024 states formed by 10 pixels around the coded pixel.
FIG. 52 shows an example of the template. In the figure, “?” Indicates a pixel to be encoded, and 10 pixels indicated by “x” are reference pixels. When the coding of one pixel is completed, the template is shifted to the right by one, as shown by the dotted line in FIG. 52, and the coding of the next pixel is performed.

Each of the 2 ¹⁰ states determined by the values of the 10 pixels is called a context (hereinafter "S"). Predicted value of dominant symbol MPS (s) for each context
(That is, for the coded symbol of interest, MPS
Is predicted to be “1”, MPS (S) = 1)
And the state number of the probability estimator are read from the context memory and output to the probability estimator 220.

The probability estimator 220 outputs the area width Qe (s) of the inferior symbol from the above information to the arithmetic encoder 230. Here, “Qe” is “probability of LPS occurrence”, and in the present specification, this is referred to as “probability of occurrence of coded symbol”,
It may also be simply referred to as the "probability estimate".

The area width Qe (s) of the inferior symbol is L
Calculated by multiplying the probability of occurrence of PS by the range of augend,
It means the width corresponding to the occurrence probability of LPS. The augend refers to the entire width of the number line as shown in FIG.

The arithmetic encoder 230 executes an arithmetic encoding operation from the encoded symbol, the predicted value MPS (s) of the dominant symbol and the area width Qe (s), and outputs the code.

As shown in FIG. 51, in arithmetic coding, a number line having an initial value of 0 to 1 is divided into an area width of a dominant symbol (MPS) and an area width of an inferior symbol (LPS). The symbol sequence to be encoded is associated with a representative point in the divided area. The representative point is taken at the bottom of the partial section.

When the coded symbol and the predicted value are the same, the MPS width is selected for coding the next symbol, and the LPS width is selected otherwise. As described above, a representative point is provided in this area width, and its binary point represents the sign.

In the arithmetic coding operation, when the area width becomes less than a predetermined value, the doubling process is repeated until it becomes a predetermined value (specifically, half the initial value) or more to prevent the precision of the decimal point. . This process is called "normalization process".

The normalization process is also performed when LPS is encoded. That is, when the estimation is deviated and the LPS width is selected, the LPS width is always smaller than ½ of the initial value, so that the normalization is performed every time.

When the normalization process is performed, the MPS value and the state number (ST) in the context table 210 of FIG. 50 are updated. The state number is updated by the probability estimation unit 22.
The “next state number” written in 0 is realized by overwriting the context table 210. In FIG. 50, this overwrite is indicated by an arrow RX.

Due to the update of the context table 210, the next context is also the same as the previous one (that is, even if the template of FIG. 52 is shifted right by one, the arrangement of reference pixels 1 and 0 is the same as the previous one. Was)
The generated Qe (S) value will be different.

As a result, a value more suitable for the probability distribution of the information source can be selected. That is, the adaptation to the image to be encoded is performed. The encoding / decoding of the binary image has been described above.

The object to be encoded is not limited to binary data. Multi-valued data such as numerical data can also be processed by QM-coder
Can be encoded with. However, when encoding a numerical value, the context required for encoding must use the suitable thing. For example, the coefficient after the discrete cosine transform includes a DC component and an AC component. Each component has a different signal property. Therefore, constructing a context model suitable for them is important in improving the coding efficiency. In the current technology, the context is separately generated for each of the DC component and the AC component.

[0018]

The conventional arithmetic coding processing has the following problems.

(Problem 1) Originally, the arithmetic coding is excellent in compression rate, but it is necessary to repeat the context generation, the symbol occurrence probability information estimation, and the arithmetic code calculation for each symbol. Therefore, there is a weak point that the processing time is long. The decrease in processing speed is a serious problem in fields such as digital copiers, which require high image quality and high speed.

Here, in the binary arithmetic encoder shown in FIG. 50, if pipeline processing is executed and the performance of the pipeline processing is improved, very high-speed arithmetic code processing with no waste is realized. be able to.

However, when the arithmetic coding process is pipelined, if the normalization process occurs in the middle of the pipeline, the pipeline is disturbed, and as a result, unnecessary waiting time increases. Therefore, the processing efficiency may decrease. In particular, it is considered that normalization occurs at a fairly high frequency, and pipeline disturbance is likely to occur in an image pattern having a continuous context. A similar problem occurs in the case of decoding.

Therefore, even if it is pipelined, its accuracy cannot be said to be high, and the speeding up of arithmetic coding / decoding processing cannot be expected so much.

(Problem 2) Not only in encoding binary data, but also in encoding and decoding multi-valued data (for example, numerical data such as orthogonal transform coefficients obtained by JPEG compression), high accuracy is achieved. It is desirable to perform pipeline processing.

However, there are the following problems in high-speed arithmetic coding and decoding of numerical values such as orthogonal transform coefficients.

That is, in order to effectively operate the pipeline processing, it is necessary to continuously supply necessary data to the next pipeline stage at a constant speed.

For example, in order to execute the decoding process at high speed, the context index needs to be simultaneously supplied to a plurality of symbols which may be restored. This set of context indexes will be referred to as "context index vector".

In practice, it is difficult to supply such vector format context data at a constant rate.
As described above, the orthogonal transform coefficient includes the DC component and the AC component. Since the DC component and the AC component have different statistical properties, the current technology provides a different context for each component.

It is difficult to continuously supply different contexts. Therefore, when a DC component and an AC component are mixed in a plurality of symbols to be encoded, it is difficult to supply the context index vector at a constant speed.

Therefore, high-speed arithmetic coding of multi-valued data is more difficult than that of binary data.

If a dedicated circuit for processing multi-valued data is provided separately from the circuit for processing binary data,
It is possible to speed up to some extent. However, the circuit configuration is complicated, the amount of hardware increases, and the cost increases.

In consideration of such a current situation, the present invention realizes arithmetic coding / decoding of super-high speed and high compression rate regardless of binary data or multi-valued data.

One object of the present invention is to achieve ultra-high-speed operation in binary arithmetic arithmetic coding / decoding processing, in which disturbance of the pipeline can be removed and symbol coding and decoding can be executed continuously in one clock. An object is to provide an encoding / decoding device.

Another object of the present invention is to perform symbol coding and decoding continuously in one clock in the arithmetic coding / decoding processing of multi-valued data, as in the case of binary data. It is to provide an ultra-high-speed encoding / decoding device capable of performing.

[0034]

[Means for Solving the Problems] For (Problem 1),
The following method is adopted.

That is, in the entropy coding apparatus, when it is necessary to update the parameters for maintaining accuracy and adaptation to the input image, the probability estimation value () that will be output after the parameters are updated ( The future probability estimation value) is output in parallel with the current estimation value (probability estimation value output in normal processing). Then, when a predetermined situation occurs (for example, when it is necessary to update the parameter, and when the reading and writing of the RAM conflict due to the continuous context), the current estimated value is The future estimate is fed to the encoder. This eliminates the need to wait for encoding while rotating the loop and updating the parameters, thus preventing pipeline turbulence.

For (Problem 2), the following method is adopted.

The conventional fixed idea in which the compression rate is absolutely important is discarded, and a new idea in which the processing speed is most emphasized is introduced. Based on this idea, the context for the DC component and the context for the AC component are actively shared. Then, both the encoding and the decoding of the context index can be realized by the state transition table.

It is easy to generate the context index vector at the time of decoding, and an encoder or decoder suitable for pipeline processing can be realized. Since the encoding context is simplified, the compression performance is slightly degraded. However, in the applied device, the processing speed is often prioritized over the compression performance, and there is no problem in actual use.

According to the present invention, both binary images and multi-valued images can be coded flexibly and at a limit speed almost determined by the mathematical coding algorithm.
Can be arithmetically decoded. Moreover, since encoding / decoding can be performed using a common context without distinguishing between a binary image and a multi-valued image, the configuration of the encoding / decoding device is greatly simplified.

In order to achieve even higher speed, it is preferable to process consecutive symbols collectively when white is continuous, as in the space between lines of a character image. In this case, it is desirable to make the number of continuously processed symbols variable in accordance with local conditions. As a result, as high a speed as possible is realized according to the complexity of the image.

[0041]

DESCRIPTION OF THE PREFERRED EMBODIMENTS A feature of the present invention is that an ultra-high-speed processing is performed by a highly accurate pipeline processing, and that this ultra-high-speed processing is applied to both binary data and multi-valued data. Further, for all white areas, batch processing of a plurality of symbols is executed, and processing for adaptively changing the number of symbols is added to realize further high speed processing.

The features of the present invention will be described in order with reference to the drawings.

(Embodiment 1) In this embodiment, FIG.
~ Pipeline arithmetic encoding and decoding of binary data will be described with reference to Figs. 3, 7, and 9. (Arithmetic Coding Process) FIG. 1 is a block diagram showing the configuration of the arithmetic encoder according to the first embodiment of the present invention.

As shown, the encoder includes a context generator 700 and a context table (context R).
AM) 701, probability estimator (Qe ROM) 702, and arithmetic code calculator 703, each of which executes one process in one clock. That is, the arithmetic encoder of FIG. 1 has a 4-stage pipeline structure.

The basic processing contents of these constituent elements are as follows.
The same as before. The feature of this embodiment lies in the configuration of the Qe ROM and the circuit configuration of its peripheral portion.

The contents of the table installed in the Qe ROM 702 are as shown in FIG. The feature of the table of FIG. 2 is that each data of “next Qe (LPS)” and “next Qe (MPS)” is further added to the data of the conventional table. As a result, the table of FIG. 2 has a width of 63 bits, and the number of bits is expanded as compared with the conventional table.

Here, "next Qe (MPS)" means that the result of MPS encoding by the arithmetic encoder 703 is that the augend is less than 1/2 of the initial value and normalization processing occurs. , The state of the transition destination of the context ROM 701 is updated, and the next encoded symbol has the same context as the previous time, so that the same address as the previous time is accessed to the context RAM 701, and as a result, the Qe ROM702
When the address corresponding to the updated state of the transition destination is accessed, as a result, it is the width (Qe) of the LPS that will be output from the Qe ROM 702.

Similarly, "next Qe (LPS)" means that the arithmetic encoder 703 inevitably causes a normalization process due to the encoding of LPS, and in response to this, the loop is rotated to update the context table, If you access the same address, Qe
It is the width (Qe) of the LPS that will be output from the ROM 702.

That is, if the normalization process occurs, the table in the context RAM 701 is updated, and the same address is accessed again, the future Qe value that will occur will be Qe ROM702 in advance. In the table in the current Q
The feature of this embodiment is that it is described together with the value of e.

The control circuit 709 of FIG. 1 is supplied with all kinds of information such as the context of the coded symbol and the presence / absence of normalization in the arithmetic encoder. Therefore, the control circuit 70
9 selects the current Qe from those information, or the future Qe (M
You can select in real time whether to select PS) or Qe (LPS). A selector 706 is provided to enable such selection.

As a result, even if the normalization process occurs, it is not necessary to wait for the process while the loop is updated to update the table, and the future Qe (MPS) or Q
All you have to do is select e (LPS). Therefore, the pipeline is not disturbed.

The selectors 704 and 705 consider the possibility that the normalization process may occur again after the normalization process occurs, so that the MPS value used last time and the state number of the transition destination are used. It is provided so that it can be reused. This point will be described later.

A detailed description will be given below.

The state number of the state transition table is input to the Qe ROM 702 as an address. The output signal is the current probability estimate Qe (s) (signal 713), and the new Qe (S) when the state transition occurs due to normalization is signal 71 for LPS normalization and MPS normalization.
4, the signal 715 is output, and two types of state transition numbers by normalization are also output (signal 716 and signal 717). Also, a flag (swi) indicating whether or not to invert MPS (S) is output.
tch-MPS, signal 718) is output.

A new prediction symbol is created by taking the exclusive OR of this flag and the current prediction symbol MPS (S) in the EOR circuit 708. This value and the output of the selector 707 become the memory content of the index 724 to be normalized.

The selectors 704 and 705 select the lower signal when the coded symbol immediately after "normalization has occurred" is coded with "same context". That is, the MPS for update and the next state number, which are overwritten in the context RAM 701, are selected.

In such a case, the probability estimation may be deviated again and the normalization process may continue, so that the MPS for update and the next state number should be used again. There is. In this case, the state number output via the selector 705 is used as an address variable to access the Qe ROM 702, and the same value as the previous time, Qe713, next Qe714, 715, is output in parallel, and waits for the encoding result. One of them will be selected.

The selection signal of each selector is appropriately output by the control circuit 709 while observing a necessary status signal.
The details of the control signal are omitted because the figure becomes complicated.

As described above, FIG. 2 shows a configuration example of the Qe ROM. As described above, the pipeline is disturbed because the Qe ROM needs to be reread.

In this embodiment, in such a case, Qe
The transition destination Qe during LPS normalization and the transition destination Qe during MPS normalization are stored at the same address so that ROM re-reading is not required. Bits 15 to 46 correspond to this part.

From the state transition table, it can be seen that the transition destination (Qe-index) of MPS normalization and LPS normalization is 1 when Qe-index is 0. Also, when Qe-index is 1, Qe is 0x
It turns out to be 2586. Therefore, 0x2586 is stored in bits 15 to 30 of FIG. Bit 31 as well
From bit 46, 0x2586 is also stored.

By doing so, even when the same context is encoded immediately after the normalization occurs, it is not necessary to reread the ROM, and since it has already been read,
All you have to do is select the one you need.

Next, an outline of the operation of the arithmetic encoder of FIG. 1 will be described with reference to FIG.

The encoding of the i-th symbol is synchronized with the clock, and context generation (context det.), Context RAM read (context RAM RD), Qe ROM read (QeRD), encoding operation and normalization Arithmetic operation (coding / renor
It is processed in the order of m).

The encoded symbol and its context are detected by the context generator 700. The encoded symbol is sent to the arithmetic code calculator 703 through the delay circuit 710 for adjusting the timing of the pipeline.

The context index “s”, which is the identification number of the context, becomes an input signal of the context RAM 701. At the same time, when normalization occurs in the context, the normalization index 712 is input as address information for updating the contents of RAM. The normalization index 712 is a delay circuit that gives a delay of 3 clocks. The output signal 724 of the normalization index 712 becomes a signal (context index) that specifies an address for updating the state of the next transition destination or the MPS value when the normalization process occurs.

The context RAM 701 is composed of a dual port RAM capable of performing reading and writing in parallel. As a result, even if the normalization process occurs and the RAM needs to be updated, the next context (arrangement of 1s and 0s in the reference pixels when the template in FIG. 52 is shifted to the right) is different from the previous one. For example, the reading (reading) of the context information for encoding and the updating (writing) of the context information when the normalization occurs can be simultaneously executed in the same cycle.

Therefore, even if the normalization process occurs, if the next contexts are different, there is no conflict of access to the ROM, so there is no need to wait for the overwriting, and the pipeline is disturbed. Absent.

The output signal of the context RAM is the predicted value MPS (S) of the coded symbol and the state number of the probability estimator (st in the figure).
ate No). The predicted value MPS (S) is sent to the arithmetic code calculator 703 through the delay adjustment circuit 711 of the pipeline.

These two output signals are output to the selectors 704 and 7
Enter 05. The control circuit 709, when normalization does not occur,
Upper signal (that is, M output from context RAM)
Selector 704, 705 so that PS value and status number) are selected
To control.

The Qe ROM 702 is accessed using the state number input via the selector 705 as an address variable.

As shown in FIG. 2, one address contains 3
Since the types of Qe are also written, the QeROM 702 always outputs three types of values as probability estimation values. And
The control circuit 709 determines the presence or absence of normalization and the presence or absence of consecutive contexts, and selects one of them in real time according to the situation.

The operation when the normalization process occurs will be described below with reference to FIG.

In the process 801 in FIG. 3, Qe (Si) (signal 7
13) is selected. Here, the i-th context is Si.

In process 802, the encoding operation of the i-th symbol and the normalization process are performed. Here, it is assumed that the LPS is encoded and the normalization occurs. The i th symbol for the i + 1 th symbol
The Qe ROM 702 is read in the same cycle as the symbol encoding operation (process 804).

The context of the i + 1th symbol is also Si
It was. Then, since LPS normalization has occurred at the i-th symbol, the selector 706 selects the Qe value 714 to which transition is made by LPS normalization.

In process 805, an encoding operation using this value is executed. At this time, in the processing 803, the context RAM 70
Contents of context Si in 1 are updated.

The update process is performed as follows. That is, in the selector 707, the next state number 716 at the time of LPS normalization is set.
Is selected. On the other hand, the EOR circuit 708 creates a new prediction value (signal 721) from the switch-MPS (signal 718) and the current prediction value MPS (Si) (signal 723).

As described above, if the signal 718 is "1", M
The value of PS (Si) is inverted. These two pieces of information are written in the address Si of the context RAM 701.

At this time, the address Si is output as the signal 724 from the delay circuit 712. At the timing of this update processing, it is necessary to read the Qe ROM 702 for the (i + 2) th symbol.

At this time, if the i + 2th symbol also has the same context Si, the selectors 704 and 705 control so that the lower signal is selected. The reason is, as described above, the processing 805.
This is because normalization may occur again in. After updating the Si context information, select 704
, The signal above 705 is selected.

The context RAM is read in this cycle for the (i + 3) th symbol (process 808). As described above, if the context of the i + 3th symbol is Sj, which is different from Si, the reading of the context to the dual port ROM 701 and the updating of the context Si are executed at the same time.

If the context of the (i + 3) th symbol is Si, its contents are updated in processing 803. At this time, selector 7
For 04 and 705, the lower signal is selected.

Even when encoding is performed continuously in the context in which normalization has occurred in this way, an invalid cycle as in the conventional example does not occur and the pipeline is not disturbed.
Therefore, one symbol can be continuously encoded with one clock for any image pattern.

FIG. 9 shows the results of an experiment (computer simulation) that supports the effect of the present invention.

Disturbances in the pipeline are apt to occur
The image pattern has a high frequency of normalization and a high degree of context continuity. In a document image, the context is often continuous, but normalization does not occur often. On the contrary, normalization occurs frequently in a random image with a black ratio of about 50%, but there is almost no context continuity. Then, in the image pattern near the compression rate of 0.5, which is the midpoint, the pipeline is likely to be disturbed. FIG. 9 is a QM-coder encoding simulation result using such a test image.

In FIG. 9, the number of cycles in which one symbol can be encoded per line is plotted. The upper characteristic line A shows the conventional example, and the lower characteristic line B shows the data according to the present invention.

As is clear from the results of this simulation, it can be seen that the number of cycles exceeds 1.1 cycles / symbol in the conventional example. This means that the processing capacity will drop to about 90 Msymbols / second even if it is operated with a 100 MHz clock. On the other hand, it can be seen that the encoder according to the present invention can obtain a processing capability of 100 M symbols / sec in any case regardless of the image pattern.

The main procedure of the encoding of the present invention described above is summarized as shown in FIG.

That is, the current Qe and the Qe (next Qe that will be output if normalization processing occurs in MPS encoding)
e) and Qe (next Qe) that would be output if the normalization processing occurred in LPS encoding are output in parallel (step 30).

Then, when normalization occurs and the next context is also the same (step 31), depending on whether the normalization is by MPS coding or LPS coding, Any one of future Qe (next Qe) is selected (step 32). If no normalization occurs, the current Qe is selected (step 33).

Comparative Example Timing charts when the present invention is not used are shown in FIGS. 33 and 34. When normalization does not occur, pipeline processing is performed as shown in FIG. 33. However, when normalization occurs and Qe ROM needs to be updated, an invalid cycle is generated as in step 2002 of FIG. 34. Occurs, where the pipeline is disturbed.

On the other hand, in the present invention, step 21 in FIG.
As in 08 to 2110, Qe is generated in parallel, and when normalization occurs, one of them can be selected by the selector, so that the pipeline is not disturbed.

The above is the description of the highly accurate pipeline control in the arithmetic coding process.

Next, the arithmetic decoding process will be described with reference to FIGS.
And it demonstrates with reference to FIG. (Regarding Arithmetic Decoding Process) An example of the binary data arithmetic decoder of the present invention is shown in FIG.

The decoder is also configured to continuously decode one symbol in one cycle. That is, like the encoder, it executes five stages of pipeline processing in the order of context generation, context index output, context RAM reading, Qe ROM reading, and decoding operation processing.

Arithmetic decoding determines whether the input code belongs to MPS or LPS on the divided number line, and determines whether MPS or LPS at that time is "1" or "0". By knowing, the symbol to be restored (restored symbol) is restored.

Then, the restored symbol is used as a reference pixel for decoding the next input code. Usually, four clocks or more is required to restore one symbol by such a method, and pipeline processing cannot be realized as it is. Unlike the case of encoding, in the case of decoding, the value of the pixel to be processed is unknown until the decoding actually ends, and after the restoration of the pixel,
Since there is no choice but to perform encoding (generation of Qe) using the restored pixel as a reference pixel, the number of steps inevitably increases.

Therefore, in the present embodiment, first, the same idea as that in the case of encoding (the idea of predicting the future and outputting in parallel in advance) is also introduced in decoding.

That is, in the case of binary arithmetic code, since the restored symbol is only "1" or "0", both the case where the currently restored symbol is "1" and the case where it is "0" are Assuming that, in each case, Qe for restoring the next symbol (one symbol ahead) is output at the same time during the restoration of the current symbol. That is, two Qe ROMs are provided and they are operated simultaneously. Then, depending on the restoration result for the current symbol, any Qe is selected.

Similarly, the read from the context RAM necessary for restoring the symbol to be restored next (symbol of two destinations) is simultaneously executed during the restoration of the current symbol.

At this time, the symbol currently being restored is "0".
When the next symbol is "1" and the current symbol is "
When 0 and the next symbol is “0”, when the current symbol is “1” and the next symbol is “1”, and when the current symbol is “1” and the next symbol is “0” Therefore, four context RAMs (dual port memories) are provided and they are operated simultaneously.

In addition, each of the four context indexes (S) necessary to restore the next next next symbol (three symbols ahead) is converted into four contexts R.
Write to the input ports of AM (dual port memory) at the same time.

The four states assumed in this case are the case where the first symbol is "0" and the second symbol is "1", and the first symbol is "0" and the second symbol is two. Symbol is "0", one symbol ahead is "1" and two symbol ahead is "1", and one symbol ahead is "
When the symbol is "1" and the second symbol is "0", it is roughly classified into four.

Thus, during restoration of the current symbol,
A method in which information necessary for the restoration of one-to-three symbols is advanced in advance, input / output in parallel, and when the restoration result is known, one of the outputs is selected according to the information. By adopting, the arithmetic decoding process can be pipelined.

However, normalization occurs similarly to the encoding,
And when the context is continuous, the pipeline is disturbed. Therefore, as in the case of encoding, a method is adopted in which the current Qe and the updated Qe are output in parallel and either is selected according to the actual decoding result.

A detailed description will be given below.

As described above, in order to continuously perform decoding in one cycle, it is necessary to start the decoding process for the next i + 1-th pixel before the i-th pixel is determined. For that purpose, it is necessary to perform the parallel processing separately when the i-th pixel is “0” and “1”. Similarly, the i + 2 th pixel is also subjected to parallel processing for each value of the i + 1 th pixel. The contents of these parallel processes are determined by the pipeline configuration.

In FIG. 4, two Qe ROMs 913 and 914 are simultaneously operated, and four context RAMs 905, 906 and 90 are also used.
Operate 7 and 908 at the same time. Then, the arithmetic decoding calculator 91
The value (1 or 0) of the restored symbol of 7 is also used as the selection control signal to select the selectors 909, 910, 911, 912, 915, 916.
To output the output corresponding to the restored symbol,
The configuration is appropriately selected.

FIG. 5 is a block diagram showing more specifically by extracting only the periphery of the Qe ROM 913 and the context RAMs 905 and 906 in FIG. As is clear from comparison with FIG. 1, the detailed configuration of the circuit is almost the same.
This is natural because the decoding apparatus also performs the same encoding operation as that on the encoding side to generate the MPS value and Qe and supplies them to the decoder.

According to the overall configuration of FIG. 4, the decoder can be pipelined for the time being, but if normalization occurs and the context is continuous, the pipeline is disturbed. Therefore, as shown in FIG. 5, both the current Qe and the updated Qe are generated and output, and either Qe is selected according to the actual decoding result. As a result, the pipeline is not disturbed regardless of the image pattern and the state of the decoder.

The output signal of the Qe ROM 913 and the functions of the selectors 1008 and 1009 shown in FIG. 5 are the same as those of the selector in the case of encoding described above. Further, the functions of the selectors 1003 and 1004 on the input side of the Qe ROM 913 are also for selecting the lower signal when performing decoding in the same context when updating the context RAM by normalization, as in the case of encoding.

The delay circuit 901 is a delay circuit for timing adjustment, and outputs the context index to be normalized as an address of the context RAM.

When the decoder is constructed as described above, no invalid cycle occurs and the pipeline is not disturbed even when decoding is performed continuously in the context where the normalization has occurred. Therefore, for any image pattern, one symbol can be continuously decoded with one clock.

The basic operation of the arithmetic decoder of FIG. 4 is shown in FIG.
This will be specifically described with reference to the timing chart of.

At the time of decoding the i-th symbol (process 1100), the i + 1-th
For the symbol (the restored symbol one step ahead), assume that the i-th symbol is "0" and "1", and in parallel Qe R
The OM913 and 914 are read (processing 1101 and 1102).

At the same time, for the (i + 2) th symbol (restored symbol that is two steps ahead), the context RAMs 905 to
908 is read (processing 1104-1107).

At the same time, for the (i + 3) th symbol,
I + 1th not yet restored from the arrangement of reference pixels in FIG.
Four kinds of context indexes are generated assuming the value of the symbol and the i + 2nd symbol.

When the arrangement of the reference pixels extends to the left on the decoding line, the number is 2 in the pipeline stage n stages away from the pipeline stage of the arithmetic decoding arithmetic unit.
N pieces of data are processed in parallel, and when these parallel data are symbolized by decoding the i-th symbol, one of them is selected and sent to the next pipeline stage. Become .

Next, the operation of the specific circuit shown in FIG. 5 will be described. Here, the arithmetic decoding unit
Assuming that the decoding process of the i-th symbol is being executed in 917 (FIG. 4), the operation will be described with reference to that time point.

At this timing, the context generator
The 900 generates a context index Si + 3 for decoding the i + 3rd pixel.

In FIG. 5, when the i-th symbol is Di, Si + 3 has four combinations from Di + 1 and Di + 2.
It is represented as, for example, Si + 3 (Di + 2 = 0 / Di + 1 = 0). This represents the context index of the i + 3th symbol in which both the Di + 2 symbol and the Di + 1th symbol are assumed to be “0”. Reference numerals 901 to 904 are delay circuits for outputting the context index to be normalized to the context RAM. Reference numerals 905 to 908 are context RAMs.

Each one has the same structure as that for encoding.
The outputs of the context RAMs 905 and 906 are the state numbers of the Qe ROM for decoding the i + 2th symbol. Where the symbol Qe-i
ndexi + 2 (Di + 1 = 0 / Di = 0) indicates the Qe-index assuming that the i-th symbol and the i + 1-th symbol are both “0”. Others are the same. MPSi + 2 is the predicted value of the i + 2th symbol.
Assumptions are omitted because they are the same as those of the corresponding Qe-index.

The selectors 909 to 912 select the input signal according to the value of the restored symbol Di. If Di is decoded and the value is “0”, the signal above the selector is selected. As a result, for example, D
Qe-index for i + 1 restoration is selected. Similarly, selector 9
The output of 10 is the predicted value of Di + 1 when Di = 0 MPSi + 1 (Di = 0)
Is selected.

The Qe value for restoring Di + 1 is output to the output of the Qe ROM 913. This is Qei + 1 (Di = 0). This signal contains three types of Qe values as in the case of encoding. Since they are complicated, they are expressed together.

In the selector 915, Qei + 1 (Di = 0) and Qei + 1 (Di
= 1) is selected by the value of Di, and the MPS of the selector 916 output
It is input to the arithmetic decoding calculator 917 together with i, and the decoding of Di + 1 is executed after the decoding of Di. A control signal such as a selector selection signal is supplied to each unit by the control circuit 918.

The main steps of pipeline processing of the arithmetic decoding method of the present invention described above are summarized in FIG.

That is, the preceding symbol, the preceding symbol, and the preceding symbol (the same applies to the preceding symbol) are processed in advance to obtain information (probability estimation) corresponding to each of the states that can be actually taken. Values) are output in parallel (step 40).

Then, using the actual decoding result, the selector is controlled to select one of the information output in parallel (step 41).

Then, in order to prevent the disturbance of the pipeline in the case where the normalization process occurs and the contexts are the same, the probability estimation value corresponding to each state (context) is generated as shown in FIG. , Perform the same method as in the case of arithmetic coding.

In the above description, the probability estimation table is
Although the example of configuring with ROM has been described, it may be configured with RAM. Further, not limited to the QM-coder, the same idea as the present invention can be applied to a coding / decoding device that operates by supplying to the encoder while adaptively updating the probability estimation value for each context. .

In the above description, the image coding is described as an example. However, such an encoder and a decoder can be applied to general data compression other than image data. Also, the probability estimation RO
It is not necessary to form one M, but a plurality of M may be used and the output data may be as in the embodiment. Also, Qe
It is also possible to realize the same function as ROM by real-time calculation by DSP.

Further, in the above-mentioned embodiment, an example of completely preventing the disturbance of the pipeline is explained.
Even if some turbulence occurs, it is naturally possible to reduce the turbulence of the pipeline by a method of parallel output / selection of a plurality of information by future prediction.

The arithmetic code / decoder of the present invention described above is suitable for mounting on a multi-function machine (a device having the functions of a scanner, a facsimile machine and a copying machine) as shown in FIG. That is, applications such as scanning images and temporarily storing them in memory, such as scanners and fax machines,
In order to apply QM-coder to multi-function peripherals, high speed processing is required as the speed of scanners and printers increases. If the present invention is applied, pipeline processing is not disturbed for any image, and very high-speed encoding / decoding can be performed.

The multifunction machine shown in FIG. 49 is the host processor 102.
An encoding circuit 103 such as MH, an image processing circuit 104, a QM
An encoding / encoding circuit 105, an image line memory 106, an encoding memory 107, a communication interface 108 such as a modem,
An image input device 111 such as a scanner and an image recording / display device 112 such as a printer are included. The arithmetic code / decoder of the present invention is mounted on the QM code / coding circuit 105.

The above is the description of the arithmetic coding / decoding processing for binary data.

(Embodiment 2) In the present embodiment, FIG.
The pipeline arithmetic encoding / decoding processing of multi-valued data will be described with reference to FIGS.

(Construction of Context Generator Necessary for Continuously Encoding Multi-Valued Image Data) Not only binary image data but also multi-valued image data is the object of encoding, the encoder The overall block configuration is the same as that shown in FIG. In other words, whether it is the coding of a binary image,
Regardless of the encoding of a multi-valued image, pipeline encoding can be performed using the block configuration described with reference to FIG. That is, the arithmetic coding / decoding operation is common.

However, in order to perform continuous encoding of multi-valued image data (hazardless pipeline encoding), it is necessary to continuously generate contexts as in the case of a binary image. . Conversely, if the context indexes can be continuously generated, symbol coding and decoding can be continuously realized without pipeline hazard. Therefore, in FIG. 1, how to construct the internal structure of the context generator 700 as such becomes a problem.

FIG. 10 is a block diagram showing an example of the structure of a context generator having a function of continuously generating contexts at the time of encoding.

In FIG. 10, image data is converted into frequency component data by a two-dimensional discrete cosine transformer 740, which is quantized by a quantizer 741 to obtain a direct current component (DC component) and an alternating current component (AC component). ) Is obtained. Numerical data (multi-valued data) such as DCT transform coefficients (orthogonal transform coefficients) and flag information obtained in this way are targets of arithmetic coding.

However, since binary image data may also be input, the selector 406 first determines whether the input data is binary image data or multivalued data (specifically, orthogonal transform). Coefficient). Then, in the case of the orthogonal transform coefficient, the data is sent to the format converter / EOB detector 407, and in the case of the binary image data, the data is sent to the JBIG context generator 410.

The JBIG context generator 410 is the context generator for binary image coding already described.

The context generator 700 outputs a coded symbol and a context identification index. The selectors 411 and 412 select the encoded context information of the numerical data and the binary image encoded context information. The selection condition is whether to encode a binary image or numeric data.

Hereinafter, the encoding of multi-valued data (that is, the format converter / EOB detector 407 of FIG.
Configurations and functions of the value decomposition processing circuit 408 and the multi-valued data encoding context generator 409) will be specifically described.

Numerical data will be described below assuming that they are orthogonal transform coefficients (DCT transform coefficients) in blocks of 8 × 8 pixels according to the JPEG standard. The same applies to other multi-valued data, and the generality is not lost.

The orthogonal transform coefficient enters the format converter / EOB detector 407 via the selector 406. Here, the format is converted into a data format convenient for the subsequent processing. Here, the position of the "EOB code" is also detected. "EOB
“Sign” means that when the transform coefficients are arranged in a predetermined order,
It is a symbol that indicates the start position of the zero lined up at the end of the block. In JPEG, the quantized transform coefficients are scanned in a zigzag manner from low frequencies to high frequencies. Since the high frequency components are quantized relatively coarsely, zeros will be arranged in the back of the block. It is known that if this is regarded as one symbol and encoded, the compression effect is improved.

The output of the format converter / EOB detector 407 is such that one numerical value is represented by 16-bit data and is constructed as follows. (1) Bit 15: EOB identification bit (2) Bit 14: DC / AC identification bit (3) Bit 13: +/- identification bit (4) Bits 12 to 0: Binary data "EOB identification that represents the absolute value of a numerical value" Bit "indicates whether the numerical data is an EOB symbol. In other words, it indicates whether or not all values after that number are zero.

The "DC / AC identification bit" indicates whether the numerical value is encoded as a DC component or an AC component.

The "+/- identification bit" indicates positive or negative. Bits 12 to 0 are binary data that represent the absolute value of a numerical value. If the multi-valued image has 8 bits / pixel, the maximum value of the DCT transform coefficient can be represented by 11 bits, so a bit number of this level is sufficient.

The format-converted orthogonal transform coefficient is then input to the binary decomposition processing circuit 408.

The arithmetic code predicts the appearance probability with "1" or "0" as the dominant symbol or the inferior symbol, and generates a code as the penalty when the estimation misses. Therefore, in order to encode the multi-valued data, it is necessary to decompose the multi-valued data into "1" or "0" by some procedure. This is the binary decomposition process.

FIG. 12 shows the format converter /
3 is a block diagram showing the configuration of the main parts of an EOB detector 407 and a binary decomposition processing circuit 408. FIG. The binary decomposition process is a process that decomposes numerical data into binary sequences of "0" and "1". Further, the processing procedure of the binary decomposition processing is shown in FIG.

The basis of the binary decomposition process is to prepare a plurality of questions (judgements) whose order has been decided in advance,
When data is input, ask questions according to the order, branch with “yes” or “no”, and branch that branch.
This is expressed by 1 "and" 0 ". By this, a binary symbol to be arithmetically encoded is generated. The decoding side asks what kind of order and what kind of question (judgment). If it is known in advance, it is possible to decode that code.

The problem here is how to set the context when arithmetically coding the coded symbols obtained by the binary decomposition. That is, what kind of context is to be generated by the multi-valued data unencoded context generator 409 of FIG. 10 becomes a problem.

Since the DCT transform coefficient has a DC component and an AC component, and each has different properties, conventionally, it has been necessary to set the context for the DC component and the context for the AC component independently. Was being considered.

That is, as shown in FIG. 42, it has been naturally considered that the DC component context index generator 3202 and the AC component context index generator 3203 are separately provided.

However, when the contexts of the DC component and the AC component are different, since the symbols belonging to the DC context and the symbols belonging to the AC context are mixed in the binary data string to be restored, the index vector is stored in the state transition table. It is difficult to output continuously based on this, which causes pipeline hazard.

That is, as shown in FIG. 43 (a), in order to switch the context, in the first place, the binary representation data of the DC component (or AC component) and the binary representation of the next DC component (AC component data) are used. It is necessary to determine the boundary with the expression data. Then, as shown in FIG. 43 (b), when generating a context, it is necessary to make a transition from the tree of the DC context to the tree of the AC context.

Therefore, when the data is restored, it is necessary to determine the end of the DC component / AC component each time one symbol is restored, and at least two cycles are required for each symbol. Complete pipeline processing, which completes processing in one clock, becomes impossible. Also, if there are multiple context models,
At the boundary between the DC component and the AC component, the pipeline will have to have a circuit configuration that starts from the initial state. High speed processing cannot be expected with such a decoder. In addition, in the circuit configuration having the DC context and the AC context as described above, the circuit scale is large, and the control between the components having different contexts becomes complicated.

Therefore, in the present invention, the DC component and AC
A common context is assigned to both component data without distinguishing between the components. If this is done, the compression rate will deteriorate slightly, but the DC component / A as shown in FIG.
The process of determining the end of the C component is completely unnecessary.
In other words, as shown in FIG. 44 (a), it is not necessary to determine the boundary between the DC component / AC component, so as shown in FIG. 44 (b),
The context tree is unified into one tree.

If the contexts are common, the symbol restoration can be continuously executed, and the DC / AC signal reconstruction processing can be performed in parallel by a circuit different from the decoding operation.

The above is the format converter / EOB of FIG.
The basic operation and characteristics of the detector 407, the binary decomposition processing circuit 408, and the multi-valued data coding context generator 409 are described.

Next, each will be specifically described with reference to FIGS. 12 to 14.

FIG. 12 shows a characteristic configuration of the format converter / EOB detector 407 and the binary decomposition processor 408 shown in FIG.

As shown in the figure, the main components are a register 501, a predictive converter 515, comparators 506 to 509 for decomposing into binary information, and binary information is sequentially selected and encoded. A selector 510 for outputting a symbol.

The predictive converter 515 is a DC converter in this embodiment.
It works on components and outputs the difference from the previous block. The difference is taken to reduce the code amount, but
It is not limited to this.

In the present embodiment, it is essential to make the context models of the DC component and the AC component the same so that the generation of the context index or the context index vector can be executed at high speed so as to be suitable for pipeline processing. It's an idea. However, in the current configuration, there is a problem that the compression ratio is slightly reduced due to the commonality and simplification of the context. To improve this, more advanced prediction technology for DC and AC components can be introduced into the predictive converter.

The register 501 receives one numerical value such as a flag to be encoded or an orthogonal transform coefficient. Each numerical value includes the above identification information and absolute value binary data. Of the register outputs, the EOB identification information 511 and the +/- identification information 512 enter the selector 510. The absolute value of the number V is the subtractor 504 and D
Input to the register 502 for C signal.

Since the DC component is relatively easy to predict, the DC component corresponding to the immediately preceding block is predicted and the prediction error signal is encoded. The AC component is encoded as it is.

The DC register 502 is composed of a plurality of registers for storing the DC value of one block. This is a delay register for calculating the difference value of the DC component. AC / D
The input of the selector 503 is selected by the C component identification signal. The upper component is selected for the DC component and the lower component is selected for the AC component.
The subtractor 504 outputs an absolute value, which is the absolute value of ΔV which is the difference between V for the DC component and the absolute value V for the AC component. Hereinafter, these will be referred to as ΔV without being particularly distinguished.

The difference value ΔV is then input to the binary decomposition processor 520. Then, ΔV is further subtracted by the subtractor 505, Sz =
Converted to a signal of ΔV (V) -1.

The comparator 506 determines whether ΔV (V) is zero. The comparator 507 determines Sz> 0. Comparator 5
The 07-comparator 509 determines the minimum number of digits n representing Sz. Here, the symbol "**" represents exponentiation. For example, Sz
= 5, Sz> 0, Sz> 1, Sz> 3, but Sz> 7
= 2 ** 3-1, so Sz is in the range of 4 to 7.

This range is called a magnitude category. n
The fact that is 3 indicates that when Sz is expressed in binary, it has a length of 3 bits. Signal 514 represents each bit of Sz. This is called the magnitude bit. If Sz = 5, then 3
“101” is the signal 514 since it is sufficient to use bits. More than
Numerical values can be uniquely represented by binary decomposition information. Selector 510 selects binary decomposition information according to a predetermined encoding order and outputs it as an encoded symbol.

The encoding procedure and context of binary information will be described with reference to FIGS. 13 and 14. The method of expressing these figures is described in the book WB. Pennebaker and J. L. Mitchell, "JPEG-S
tillImage Data Compression Standard, "New York: V
Referenced to an Nostrand Reinhold, 1993.

First, the binary decomposition process of FIG. 13 will be specifically described.

First, it is checked whether or not the difference data ΔV (V) is EOB (all data of the frequency component block including DC and AC components is zero) (step 601), and the result is encoded. If yes, "1" is encoded with the context represented by the index "EOB", and the encoding is completed. Encoding "1" in the context expressed by the index "EOB"
In the figure, it is written as 1 (EOB).

On the other hand, if it is not EOB in step 601, then "
"0" is encoded by the context expressed by the index "EOB". This is described as 0 (EOB) in the figure.
This notation is the same below.

As described above, when the determination is made at each step and there are two outputs, the right side indicates the determination of yes, and the lower side indicates the determination of no. Therefore, as described above, step 60
If EOB in 1, the 1 is encoded in the context of EOB, and the encoding is completed. Otherwise, 0 is encoded in the context EOB.

Next, in step 602, it is judged whether or not ΔV (V) of the difference data is zero. The determination result is encoded in the context "S0". If ΔV (V) is zero, encoding ends at this point and the next numerical value is encoded. If ΔV (V) is not zero, the process proceeds to step 603, and positive / negative (+ or −) signs are encoded. The context at this time is "S1".

Then, the process proceeds to step 604 or step 605. In step 604, it is determined whether the absolute value of the difference data ΔV is larger than “1”. That is, Sz> 0
Then, the result is encoded in the context S2.

If ΔV is not "1", step 60
At 6, it is determined whether the absolute value of ΔV is larger than “2”. That is, it is determined whether Sz> 1 and the result is encoded in the context of X1.

If Sz> 1 (the absolute value of ΔV is “2”), in step 607 the absolute value of ΔV is 3 or
It is determined whether it is 4 or greater than 4. That is, it is determined whether or not Sz> 3, and the result is encoded with the context X2.

Here, when Sz = 2, in step 608, the lower bit "0" of the binary notation "10" of 2 is encoded in the context M2. When Sz = 3, in step 608, the lower bit "1" of the binary notation "11" of 2 is encoded in the context M2.

At step 609, it is determined whether or not Sz> 7, and the result is encoded by the contest X3. Where Sz
Is 4 to 7, the binary notation of each of 4, 5, 6, and 7 is "10.
Lower 2 bits of "0", "101", "110", "111""0"
0 ”,“ 01 ”,“ 10 ”,“ 11 ”are encoded by the context M3 (steps 610, 611).

In step 612, it is determined whether Sz> 15, and the result is encoded in the context X4. At this time, when Sz = 8 to 15, each numerical value is expressed in binary, and the lower 3 bits are encoded by the context M4.

When the value of the input difference data ΔV is large, the same processing is repeated thereafter. In step 616, it is determined whether Sz> 32768, and the result is encoded in the context X15. If Sz is 32768 or less, each numerical value is represented in binary and the lower order bits are encoded in the context M15.

In the above description, X1 to X15 are magni of Sz.
It is a context for encoding data indicating a tude category, and M2 to M15 are contexts for encoding a magnitude bit of Sz.

In the above-described order, the binary decomposition processor 520 of FIG. 12 binarizes the numerical value to generate an encoded symbol, and the multilevel data encoding context 409 to the contexts XX1 to X15 of FIG. , M2 to M15 are output, and the arithmetic coding operation is performed thereby.

14 (a) and 14 (b) are a summary of the contexts appearing in FIG. Since the block of multi-valued image coding is 8 pixels x 8 pixels, there are 64 frequency components. This is represented by k = 0 to 63.

As shown in FIG. 14A, N, context EO
For B, S0, S1, and S2, the context is defined for each frequency component (703 to 706), and there is a context that encodes numerical values such as flags that can be treated as DC components (70
1, 702).

Further, as shown in FIG. 14 (b), the magnitude
The context of category and magnitude bit are common
(707, 708). Each of these pieces of context information is represented by 1 byte like the encoding of a binary image.

FIG. 15 (a) is a flow chart showing the overall procedure of encoding multi-valued data, and FIG. 15 (b) is a frequency component.
It is a flowchart which shows the specific processing procedure of 64 encoding.

As shown in FIG. 15A, in the encoding process of multi-valued data, first, the format conversion / EOB detection process is performed (step 810). Then, the binary decomposition processing is performed in a predetermined order (step 811). Then, the context is generated without distinguishing between the AC component and the DC component (step 812) and arithmetic coding is performed (step 813).

The coding of the frequency component is performed by the procedure as shown in FIG. 15 (b). Here, k represents a zigzag scan index. First, k = 0 (step 80)
1). Next, it is determined whether the numerical value of k = 0 represents an EOB symbol (step 802). Here, E at k = 0
Being OB means that the DC and AC components are all zero. If the result of this determination is EOB, 1 is encoded (code-1) in step 804, and the block ends encoding.

If it is not EOB, 0 is encoded in step 803, and then ΔV (V) is encoded in step 805. If one block has not ended in the determination in step 806, the index is updated in step 807 and the same processing is repeated.

In this way, the encoding of one block is completed. Although not shown here, if there is information to be coded as a DC component other than the frequency component, those are first coded. In the present embodiment, the DC component and the AC component are encoded in this order. For example, as shown in Fig. 14 (a), if there are two flags that can be handled as DC components in each block, one block is composed of 66 components, so k
= 66, and encoding may be performed according to the flow of FIG. As is clear from FIG. 15 (b), the coding process flow is common without distinction between DC and AC components.

As described above, according to the predetermined procedure, the binary decomposition is performed mechanically regardless of the AC component / DC component, and the common context is used for encoding, so that there is no hazard even for multi-valued data. Pipeline processing can be realized. That is, by using the block configuration of FIG. 1, ultra-high-speed arithmetic coding processing that executes one processing in one clock is realized.

FIG. 17 shows a coding example of frequency components. This example shows how each numerical value is encoded as binary information when the DC difference is +1 and the AC component is four and the subsequent EOB.

When the DC difference value +1 is encoded according to FIG. 15B, it is not EOB first, so 0 is encoded in the context EOB in step 803. This is represented as 0 (EOB). In the coding of the numerical value in step 805, when the coding is performed while looking at FIG. 13, the numerical value ΔV is not zero, so 1 is set in the context S0.
Is encoded. Next, since the positive and negative signs are +, 1 is coded in the context S1.

Since Sz = 0, the determination of Sz> 0 is no, and 0 is encoded in the context S2. In this way, the DC difference value ΔV can be encoded. This process is EOB
It will be understood that the encoding is performed as shown in FIG. 16 by repeating the above operation until all the values in one block can be encoded. As described above, the binary decomposition process and the binary information encoding are performed.

In encoding multi-valued data, the binary data string is decomposed in this way, and each decomposed binary data becomes an encoded symbol. To encode this binary data string at high speed, it is necessary to output the context corresponding to each symbol at the same time.

The multi-valued data coding context generator 409 in FIG. 10 generates a context string synchronized with the symbol sequence. In this embodiment, the multi-valued data encoding context generator 409 is composed of a state transition ROM. Since encoding can be performed according to FIG. 13 without distinction between DC and AC components, the state transition table of the context index can be created from FIG. FIG. 29 is a diagram showing an example of the configuration of the context index state transition table.
The context column on the left is the name of the context and its index. The next status column on the right shows the next status number and output index. This table is all
It consists of 70 states, state 0 is the context EOB. If 0 is coded (code-0) in this state, the state moves to 1. At that time, index 1 is output. State 1 when 1 is encoded
Stays at and outputs index 0. The index is 0 to 23, but the number of states is larger because the same context is defined as different states. In this way, the context index can be output at high speed in synchronization with the symbol encoding.

In the conventional example, since the DC component and the AC component have different contexts, the state transition at the timing when the DC component and the AC component are switched becomes complicated. Further, when it is necessary to increase the number of DC components such as flags depending on the application, it is necessary to recreate the index state transition table, and there is a problem of lack of flexibility.

As described above, the coded symbol and its context index are simultaneously output from the selector 411 and the selector 412 shown in FIG. The context index is input to the context RAM701 in Figure 1,
The encoded symbol is delayed by 2 clocks and then arithmetic encoder 70
Enter in 3. The subsequent pipeline processing is the same as the case of encoding a binary image.

The hazard-less pipeline arithmetic encoding of multi-valued image data has been described above.

(Multi-Valued Image Decoder) Next, the hazard-less pipeline arithmetic decoding of multi-valued data will be described. Like the encoding, the description will focus on the context generation. The other parts are common to the decoding of binary images.

FIG. 11 illustrates the configuration of the context generator (reference numeral 700 in FIG. 1) at the time of decoding multi-valued data.

The multi-value synthesizing process 403 synthesizes numerical values from the restored binary data string by following the reverse procedure of binary decomposition. The multi-valued data decoding context generator 404 generates a context index vector. Selector 405 is 2
Select index vectors for decoding value images and multivalued data. The selector 401 selects the restored data.

The lower part of FIG. 17 shows a portion for generating a context index. Context generator for JBIG reconstruction
The output signal of the 402 corresponds to the decoder shown in FIG.
i + 1 = 0 / Di = 0), Si + 2 (Di + 1 = 1 / Di = 0), Si + 2 (Di + 1 = 0 / Di =
1) and Si + 2 (Di + 1 = 1 / Di = 1). These were indices for four possible combinations of the currently decoded symbol Di and the next symbol Di + 1. The same applies to the output signal of the context generator 404 for multilevel data decoding.
In this case, the symbols Di and Di + 1 are binary decomposed symbols.

FIG. 18 is a Context Tree created by the context for decoding multi-valued data. The binary decomposition process at the time of encoding is performed according to a predetermined procedure as shown in FIG. Therefore, by following the procedure in reverse, the context necessary for data restoration is
As in 18, it will be decided uniquely in order. Therefore, even at the time of restoration, the necessary context can be continuously generated.

As described above, the Context Tree created by the context for decoding multi-valued data in FIG. 18 can be constructed with reference to FIG.

For example, the context following the context EOB (1101) is S0 (1103) or EOB (1102), and the context after the context S0 is S1 (1105) or EOB (1104).

In this way, the Context Tree of FIG. 18 can be constructed. Although many EOBs are written in FIG. 18, they are all in the same state as the EOB of 1101. When the EOB is reached, coding of one block is completed. The numbers 0 and 1 attached to the edges are the values of the reconstruction symbol Di.

FIG. 30 is a state transition table of context indexes corresponding to the Context Tree of FIG. In this table, the state number 1601 is a number corresponding to each node of the Context Tree in FIG. The context 1602 is a context name and an index corresponding to it. 1603 is Di
And the four output indices determined by Di + 1. 1604 is the state number of the transition destination after one symbol decoding.

For example, in the cycle in which the symbol Di is decoded in the EOB context in the state 0, the index vector (0, 2, 1, 0) is output. When Di is restored as 0, it transits to state 1. In this state, the index vector (1, 0, 2, 2) is output. The context generator 404 in FIG. 17 implements this state transition table in ROM. In this way, context vectors can be generated one after another in synchronization with symbol decoding.

Since the pipeline operation of the decoder operates in the same way as the decoding of the binary image, the binary symbol can be restored at high speed without the occurrence of pipeline hazard. Reconstructing the numerical values such as the orthogonal transform coefficient from the restored binary symbol sequence is easy because it is necessary to follow the reverse of the decomposition process. If the DC component and the AC component have different contexts as in the conventional example, since the binary data string to be restored contains symbols belonging to the DC context and symbols belonging to the AC context, the index vector is stored in the state transition table. Based on this, it is difficult to output continuously.

As shown in FIG. 43 (b), since the context is switched, DC / AC is restored every time one symbol is restored.
The process of determining the end of the component is required, which takes 2 cycles per symbol.

As shown in FIG. 44 (b), if the context is common as in this embodiment, symbol restoration can be continuously executed, and DC / AC signal reconstruction processing is performed by decoding operation. Parallel operation is possible with a circuit different from the above.

If there are a plurality of context models,
At the boundary between the DC component and the AC component, the pipeline will have to have a circuit configuration that starts from the initial state. High speed processing cannot be expected with such a decoder. Further, in such a circuit configuration having a DC context and an AC context, the circuit scale is large, and control between components of different contexts becomes complicated. The decoder of the present invention does not have such a problem.

Further, the arithmetic decoder of FIG. 27 has a maximum symbol length detector 1316 as in the case of the encoder, and always detects the maximum number of symbols that can be collectively decoded. That is, when the data to be finally restored is binary data, it is always detected by the plurality of detectors that the reference pixels corresponding to the predetermined plurality of consecutive decoded symbols match the specific pattern. It detects and determines the maximum number of symbols that can be collectively decoded based on the detection results of these detectors, supplies the maximum number of symbols to the arithmetic decoding calculator, and adaptively performs collective arithmetic decoding. As a result, a higher speed decoding process is realized.

When the data to be finally restored is multi-valued data, the binary data decoded by the arithmetic decoding arithmetic unit is processed by the multi-value synthesis processing circuit 403 as described with reference to FIG. They are combined (the procedure is the reverse of the binary decomposition), and thereby multi-valued data is restored. As shown in FIG. 11, the JBIG (binary data) context generator 402 and the multi-value data decoding context generator 404 are selectively used as appropriate for decoding.

The encoding / decoding of multi-valued data has been described above.

(Embodiment 3) In the embodiment described above,
The technique for implementing the hazard-less pipeline coding for a binary (or multi-valued) image has been described. However, in the actual image, such as margins and line spacing of characters,
There is also a continuous white (or black) area. It is not necessary to code such a region for each symbol.

In view of this point, in the present embodiment, the method proposed by the applicant of the present invention to carry out collective coding by stopping coding for each symbol when the contexts are continuous. And the method of preventing the disturbance of the pipeline due to the future prediction of the binary arithmetic code described in the first embodiment.

FIG. 20 shows an example of the image. As shown, areas A, C, etc. are character areas, and areas B, D
Is a white area (row-to-line area). And area E,
On the right side of F, there are high-definition images 10 and 20 which have high context continuity and whose probability estimation is difficult.

In the character area, since probability estimation is easy and normalization frequency is low, it is considered that the disturbance of the pipeline is not so problematic. In addition, high-definition image 10,
With respect to 20 as well, by using the above-described present invention, it is possible to prevent the disturbance of the pipeline.

The present invention adopts a method of outputting information based on the future prediction in parallel with the current information and selecting afterwards. For example, in an all-white (or all-black) interline area, There is no need for such a technique.

Therefore, when an all-white area appears, the coding (decoding) is collectively performed to reduce waste.
It becomes possible to perform encoding (decoding) of one image at a higher speed.

Even with non-white lines, a certain amount of collective coding
Although it is possible to perform decoding, it is possible to collectively process all white lines in a larger number of symbols than the number of collectively processed symbols in non-white lines. Thereby, the processing speed can be further improved.

In order to perform the collective coding of the all-white area,
As shown in FIG. 21, while the data input to the context generator 3200 is latched in the line memory 2000, the sequence control unit 4000 detects a white line and sends its identification signal to the multi-symbol processing determination unit 3300. The maximum number of symbols that can be collectively processed is determined.

It should be noted that the disturbance of the pipeline is prevented (reduced).
The configuration of the present invention to achieve the context generator 3200,
Even in the context memory 3400 and the probability estimator 3600,
It is adopted in the same manner as the above-mentioned embodiment.

As shown in FIG. 22, the collective coding of white lines (eg, MPS coding) is performed a plurality of times by using Qe for a plurality of times within a range from the agend (Areg) to ½ (0x8000) or less of the initial value. It is easily realized by subtracting all at once. If the normalization occurs, there is a concern that the processing becomes complicated. Therefore, it is generally desirable that no normalization occurs as a condition for batch processing of consecutive symbols.

FIG. 23 shows the procedure of the collective encoding process for the all-white area. That is, it is determined whether or not the median value is greater than or equal to when the Qe is collectively subtracted (step 10), the continuity of the context and MPS is determined (step 20), and the batch encoding processing or the sequential processing is performed depending on the determination result. An encoding process is selected (steps 30 and 40).

In the present embodiment, since the pipeline is not disturbed, the coding and decoding can be executed at a constant speed regardless of the image pattern, and the blank area is collectively coded. Further, the arithmetic coding process can be further speeded up.

(Embodiment 4) In the present invention, the hazardless pipeline encoding / decoding function for binary data and multi-valued data described in Embodiment 1 and Embodiment 2 is applied to Embodiment 3. The batch coding function for all white areas, which has been explained (the version has been upgraded with additional adaptability)
Is added and integrated. In batch coding of all-white areas, a function of adaptively changing the number of symbols to be coded collectively is provided according to the local property of the image to be coded.

An ultra-high-speed arithmetic encoder / decoder (codec) that integrates encoding / decoding of binary images and encoding / decoding of multi-valued images will be specifically described below with reference to the drawings.

(Description of Overall Structure) FIG. 24 is a block diagram showing the structure of the arithmetic encoder according to the embodiment of the present invention.

A more detailed block configuration will be described step by step. The main components are a context generator 1001, a maximum symbol length detector 1002, a context memory 1003, a probability estimator 1004, an arithmetic encoder 1005, and a timing controller 1006 that controls the operation timing of these processing blocks.

Numerical data such as binary images, orthogonal transform coefficients, and various identification flags are to be encoded. The context generator 1001 outputs a context index suitable for these data.

The maximum symbol length detector 1002 functions when coding / decoding a binary image. Areg, Creg, Qe (S), M
It outputs the symbol length using PS (S) and binary image data as input signals. The context memory 1003 stores the prediction symbol MPS (S) and the probability estimator 10 for each context as in the conventional example.
The 04 status number is output. The arithmetic encoder 1005 is a block that executes encoding / decoding operations. (Binary Image Encoder) First, the binary arithmetic encoder will be described.

FIG. 25 is a block diagram showing the structure of the encoder.

Context generator 201, context RAM
202, Qe ROM203, and arithmetic encoder 204 are pipeline-connected. The state of the pipeline operation timing is monitored by the encoder timing control unit 207, and an appropriate control signal is supplied to each unit based on the state monitoring.

This pipeline is a functional block common to the coding of binary images and the coding of numerical data. On the other hand, the Qe ROM 205 and the maximum symbol length detector 206 are functional blocks peculiar to binary image coding.

First, the pipeline operation will be described.

The input data is a binary image. The context generator 201 outputs the context index S and the coded symbol according to the value of the reference pixel of the template shown in FIG.

The coded symbols are supplied to the arithmetic encoder after a delay of 2 clocks in order to adjust the pipeline timing.

Index S that identifies the context
Input to the context RAM 202 and the delay element 208. The delay element 3D represents a delay of 3 clocks. The output timing of the delay element is set to be the context update timing.

From the context RAM 202, the symbol prediction value MPS (S) and the state number (state No.) of the Qe ROM 203 are output. The context RAM is a 2-port RAM, where the index S is the address, MPS (S) and the status number are the data on the read side, and the index 3D (S) delayed by 3 clocks is the address and the context 3D. (S)
Another set of ports uses the updated value of as the data on the write side.

Since it is a 2-port RAM, index S and 3D (S)
If different, read and write can be done in the same cycle. The output data of the context RAM 202 is passed through the selector 212.
It is supplied to the Qe ROM 203 and the arithmetic encoder 204. Selector 212
The operation of will be described later. The Qe ROM 203 outputs Qe (S) and the next state number according to the input state number. The contents of this ROM are as shown in FIG. 38, which is significantly different from the conventional example as shown in FIG.

FIG. 40 shows the contents of a normal probability estimation table, and this table is a ROM that is a Qe ROM. In the conventional example using the ROM with the contents as shown in Fig. 41, the cause of pipeline hazard is, as explained earlier, when the normalization occurs in the context S, and the symbol immediately after that is the same context,
This is because the output value of the RAM is an old value before the normalization update and needs to be reread.

Therefore, in this embodiment, Qe (S) and Qe (S) after the normalization occurs and the state transition is output at the same time so that re-reading is unnecessary, and these are output as the status. You can choose according to.

All information necessary for encoding calculation is Qe ROM203.
Since it is supplied from, even if the context continues and normalization occurs in the middle, the context RAM does not need to be re-read and the pipeline hazard does not occur.

FIG. 38 shows an example of the structure of a binary arithmetic code Qe ROM in the present embodiment. As shown in the figure, the data in the table of this Qe ROM is Qe ROM.
(S), Qe (S) after encoding LPS to cause normalization and state transition, and similarly, Qe (S) after encoding MPS to cause normalization and state transition, and LPS Information of the state transition destination when the encoding is performed and normalization occurs, information of the state transition destination when the encoding of MPS is performed and the normalization occurs, and the flag switch
Is.

Here, the operation timing around the Qe ROM will be described with reference to FIG.

It is assumed that the context of the i-th symbol is Si. Process 2101 displays information about context Si in FIG.
Read from the context RAM 202 (context RAM RD (S
i)). In the next cycle, from the Qe ROM to the context Si Qe
Value 2102, next Qe value 2 if normalization occurs in MPS encoding 2
103, next Qe value when normalization occurs in LPS encoding 2104
Are being output at the same time. Similarly, the next transition destination number is also output, but it is not shown here.

Since normalization has not yet occurred, 2102 to 2104
Qe (Si) 2102 is selected from among. In process 2105, arithmetic code calculation and normalization process as necessary are performed. Now, it is assumed that LPS is encoded in this cycle and normalization occurs.
In process 2106, the content of context Si is updated. The value written in the context RAM is the new state number and the new M
It is PS (Si). The new state number is the 7-bit data 215 selected by the selector 213, and the new MPS (Si) is the exclusive OR 211 of the current predicted value MPS (Si) 216 and the flag switch-MPS217 1 It is a bit signal. Selector 21
3 The selection condition of the lower selector is whether MPS is encoded or LPS is encoded.

The i + 1th symbol also has the same context Si as the ith symbol. In the processing 2108 to the processing 2110, similarly to the processing 2102 to the processing 2104, there are three kinds of Qe (Si) for the context Si.
Are being output at the same time. Since normalization has occurred in the process 2105, the Qe value 2108 after the state transition is selected from this.

The selection condition of the selector on the upper side of the selector 213 is determined by the presence / absence of normalization and the symbol at the time of normalization. An encoding operation is performed in the next cycle 2111 using this Qe value.

The context of the (i + 2) th symbol is also Si. In process 2112, the state number of the Qe ROM read in the previous cycle is that before update, so the lower input of the selector 212 is selected and the Qe ROM is read.

Below the selector 212, the next state number and the next predicted value MPS (Si) have already been input. Q from Qe ROM
e (Si) and Qe (Si) after transition are output. Since no normalization has occurred in the (i + 1) th symbol encoding, Qe (Si) is selected. If normalization occurs again in the (i + 1) th symbol encoding, Qe (Si) after the transition may be selected.

If the context of the i + 3th symbol is Sj, which is different from Si, the context Sj data is read in step 2114. At this time, the process 2106 is writing to the context RAM.
Is a 2-port RAM, processing 2106 and processing 2114 can be executed in the same cycle.

If the (i + 3) th symbol is the context Si, the process 2116 gives priority to the writing of data and does not read it. In process 2117, the selector is the same as in process 2112.
Select the lower input of 212 to read Qe ROM. In this way, it can be seen that the area around the Qe ROM operates and no pipeline hazard occurs.

Next, returning to FIG. 25, the maximum symbol length detector 20
The relationship with 6 is explained.

The maximum symbol length detector 206 selects the maximum symbol length from the symbol lengths in a predetermined range when the same context continues. In this embodiment, the reference pixels are all white contexts and all black contexts.

Since the reference pixels in the all-white context are all white (0), the index S is set to "0", and the index S of the all-black context is set to "1023".

Therefore, the prediction symbols of the all-white and all-black contexts are represented as MPS (0) and MPS (1023).

FIG. 26 shows a configuration example of the maximum length symbol detector. This detector detects the maximum number of symbols that can be collectively processed when a plurality of symbols are collectively processed for all white areas.

In the present embodiment, four symbol lengths "64", "32", "16" and "8" are defined as batch processable symbol lengths, and the optimum symbol length is selected from these. In FIG. 26, four processing units 301 are lined up. From the right, the order is 64 symbol detection unit, 32 symbol detection unit, 16 symbol detection unit, 8 symbol detection unit. Since all the configurations are the same, one processing unit will be described.

Whether or not collective coding processing (continuous coding processing) is possible is determined by the following conditions. Condition (C1): n contexts are the same, and coded symbols are the same as MPS (S). Condition (C2): Areg-n · Qe (s)> = 0x8000 Here, “Areg” is the value of the register indicating the area width. Also, “0x” represents hexadecimal display.

On the other hand, at the time of decoding, it is determined by the following conditions. Condition (D1): n contexts are the same Condition (D2): Areg-nQe (s)> = 0x8000 Condition (D3): Creg <Areg-nQe (s) where "Creg" is It is the value of the register that points to the representative point taken in the region width.

In the 6-bit shifter 302, Qe (S) is multiplied by 64.
The arithmetic unit 303 calculates Areg -64 * Qe (S). The comparator 304 compares Areg -64 * Qe (S) with 0x8000 and outputs the result to the maximum symbol length determination circuit 306. Here, the conditions (C2) and (D2) are determined. Further, the condition (D3) at the time of decoding is compared by the comparator 305.

[0273] Context continuous condition and MPS at encoding
The continuous conditions of the same context / MPS64 continuous detection circuit 307
It is judged by. The determination result is sent to the maximum symbol length determination circuit 306. The above determination is similarly simultaneously performed on 32 symbols, 16 symbols, and 8 symbols. The maximum symbol length determination circuit determines the maximum value of the symbol length that can be continuously processed based on these determination results. Since the symbol length that can be continuously processed is 2 to the n-th power, the symbol length is 3
08 outputs this n. If there are 64 symbols, 6 will be output. If continuous processing cannot be performed, "0" is output.

Returning to FIG. 25, the relationship between the maximum symbol length detector and the surroundings will be described.

The Qe ROM 205 outputs Qe (0) and Qe (1023). The ROM configuration is different from the Qe ROM 203, and the output data only needs to have the Qe value. The state numbers of the Qe ROM 205 for the index 0 and the index 1023 are stored in the two registers 209.

The initial value of the register is zero, and the value of the register is updated with the normalization. Signal 218 is the updated value of the context. The index detection circuit 210 detects two indexes and updates the register 209. The selector 214 that switches the input data of the arithmetic encoder selects the right side during continuous processing. The arithmetic encoder performs arithmetic processing for n symbols.

Next, the mutual operation of the pipeline processing and the symbol continuous processing will be described with reference to FIG. FIG. 36 shows an example of switching timing between the pipeline encoder and the symbol continuous processing. Here, the pipeline encoder means the context generator 201, the context RAM 202, and the Qe ROM2 of FIG.
It refers to symbol sequential processing composed of 03 and arithmetic encoder 204.

As shown in FIG. 39, the pipeline encoder and the symbol continuation processing section are always operating at the timing shifted by one pixel. When the i-th pixel is encoded by the pipeline encoder, the maximum symbol length detector always detects the maximum symbol length that can be encoded from the i + 1-th pixel.

In processing 2201 of FIG. 36, it is assumed that the arithmetic encoder 204 executes the encoding operation / normalization processing of the i-th pixel. At this time, Qe for the (i + 1) th symbol is read from the Qe ROM of the pipeline encoder (process 2202). On the other hand, the maximum symbol length detector determines in process 2204 and process 2205 whether the context continuity or Areg satisfies a predetermined condition. Since Areg is calculated in the initial stage of processing 2201, the calculation result of processing 2205 is finalized in the latter half of this cycle.

The maximum symbol length is determined by combining the results of processing 2204 and processing 2205. As a result, when continuous processing cannot be performed, pipeline processing continues in step 2203. If continuous processing of n symbols is possible, in operation 2207 the arithmetic encoder 204
Performs a continuous encoding operation of n symbols.

In the same cycle as this, the image data in the context generator is shifted by n bits to prepare for the detection of a new context. If the context information needs to be updated as a result of the n-symbol encoding operation, it is executed in processing 2209. In this way, the pipeline processing is switched to the continuous processing.

On the contrary, when continuous processing cannot be performed, the processing is switched to pipeline processing. At this time, since the pipeline is not clogged with data, a 4-stage pipeline causes a pipeline delay of 4 clocks. Control is performed so that switching from pipeline processing to continuous processing is not performed during this process. When the switching from continuous processing to pipeline processing occurs frequently, pipeline delay occurs. Therefore, when the symbol length is short, the speedup effect is small.

Regarding the all-white context, Qe quickly converges to the vicinity of the minimum value.
(C2) is a relatively mild condition, and continuous processing is determined by the condition (C1). Since white parts such as line spacing and left and right margins are gathered in the document image, it is often possible to continuously encode 64 pixels, which is a predetermined maximum value, in such places, and the speedup effect for the entire page is large.

(Binary Image Decoder) Next, the decoding operation will be described. First, a processing method that can be commonly applied to high-speed arithmetic decoders will be described. FIG. 19 (a) is a block diagram of an arithmetic code decoder capable of high-speed operation. In addition,
Fig. 19 (b) shows Tre that is composed of the context of the restored symbol.
indicates e.

This drawing has a configuration common to decoding of a binary image and decoding of numerical data such as an orthogonal transform coefficient. Constituent elements are context generator 1201, multiple context RAs
M1202-1205, selector 1206, 1207, 1210, Qe ROM120
8 and 1209, an arithmetic code decoder 1211, and a multilevel synthesis processor 1212.

Similar to the encoder, the context generation processing, the context RAM reading, the Qe ROM reading, and the arithmetic code decoding processing are pipeline-connected, and each pipeline stage is executed in one cycle. The decoding process of multi-valued data will be described later, and the decoding operation of a binary image will be described below.

In decoding, the currently decoded symbol determines the future context containing that symbol. Therefore, in order to perform pipeline processing, multiple contexts that may occur in the future are processed in parallel, and each time one symbol is restored and confirmed, it is necessary to process the data in parallel. It is necessary to narrow things down.

FIG. 19 (b) shows a Tree formed by the context of the restored symbol. Now, assume that the i-th symbol Di is restored in the context Si. Since Di is "0" or "1", the node representing the context Si is divided into two and becomes the next context Si + 1. Similarly for the branch from Si + 1, there are four possibilities for Si + 2 by combining the restoration symbols Di and Di + 1. The Tree having the above-described structure and representing a branch of the context will be referred to as a Context Tree. The decoder performs pipeline processing according to this Context Tree. It is assumed that the arithmetic code decoder 1211 restores the symbol Di in the context Si. Since it is pipeline processing, Qe ROM1208 is used in the same cycle as it.
And from Qe ROM 1209, assuming the following context Si + 1, Q
The e value is being read. Qe ROM 1208 has Di = 0 context, and Qe ROM 1209 has Di = 1 context. When Di is restored, its value selects
The Qe value selected in 1210 and necessary for the decoding process in the next context Si + 1 is supplied to the arithmetic code decoder 1211.
Similarly, in the context RAM reading process, the reading of the context information for the context Si + 2 is performed in the same cycle. When the decoded symbol Di is decided, possible candidates are narrowed down to half by the selectors 1206 and 1207.

Pipeline processing is performed in this manner. Context Tree Decod this pipeline decoder
I'll call it er. In Context Tree Decoder, the output of context generator is not one index,
There will be multiple indexes 1213-1216. These are collectively called an index vector.

27 and 28 are block configuration diagrams of a decoder corresponding to FIG. The decoding operation will be described with reference to these figures.

As can be seen from the conceptual description with reference to FIG. 19A, the main constituent elements are the context generator 1301, four context RAMs 1302-1305, two Qe ROMs 1310, 1311,
An arithmetic decoding arithmetic unit 1314, a maximum symbol length detector 1316, and a decoder timing control unit 1317 for controlling timing. The decoder timing control unit is a block that performs pipeline timing and switching control between the pipeline decoder and the maximum symbol length decoding process, like the encoder.

The maximum symbol length detector 1316 and the Qe ROM 1315 connected to it are exactly the same as those used in the encoder. Similar to FIG. 19A, it is assumed that the arithmetic decoding operator 1314 restores the i-th symbol Di in the context Si.

The context generator 1301 generates a context index vector. The elements of the vector are Di
And Di + 1 as shown in the figure, Si + 2 (Di +
1 = 0 / Di = 0), Si + 2 (Di + 1 = 0 / Di = 1), Si + 2 (Di + 1 = 1 / Di = 0), S
i + 2 (Di + 1 = 1 / Di = 1). The subscript indicates that it is the context index for the (i + 2) th symbol, and the values in parentheses are the conditions for the symbol to be restored.

Hereinafter, symbols are used in the same manner as this. The context RAM 1302 outputs the Qe ROM state number Qe-index i + 2 and the symbol prediction value MPSi + 2 for the i + 2th symbol. The output of other context RAMs is similar.

It is assumed that the selectors 1306 to 1309 select the upper side when Di = 0 and the lower side when Di = 1. Therefore, for example, the input signal on the upper side of the selector 1306 is Qe-index.
i + 2 (Di + 1 = 0 / Di = 0), the lower input signal is Qe-index i + 2 (Di
+ 1 = 0 / Di = 1). Others are the same. Although not shown, the pipeline registers are assumed to be included in the output stages of the selectors 1306 to 1309 and the selectors 1312 and 1313.

From the selector 1312 and the selector 1313,
It outputs Qe value Qei and MPS prediction value MPSi required for Di decoding operation. MPSi is supplied to the arithmetic decoding arithmetic unit through the predicted value from the maximum symbol length detector and the selector 1318.
The selection condition of the selector 1318 is determined by whether the pipeline decoder performs sequential processing or continuous processing of a plurality of symbols.

When Di is decoded, the next Qe value Qei + 1 (Di = 0) or Qei + 1 (Di = 1) is output from the selector 1312 according to the value of Di.
Is supplied to the arithmetic decoding calculator. At this time, the selector 13
MPSi + 1 (Di = 0) or MPSi + 1 (Di = 1) is output from 13. In this state, the i + 1th symbol Di + 1 is decoded.

Similarly, in synchronization with the above signal change, the selector 1306 outputs Qe-index i + 2 according to the value of the symbol Di.
(Di + 1 = 0 / Di = 0) or Qe-index i + 2 (Di + 1 = 0 / Di = 1) is output, and this is replaced by the current data Qe-index i + 1 (Di = 0) It becomes Qe-indexi + 2 (Di + 1 = 0). Other selector 1
Similarly for 307 to 1309, a signal for decoding Di + 2 is selected according to the value of Di. The context generator also outputs a new index vector in synchronization with this signal change.

FIG. 37 is a time chart showing the above operation.

At clock i, Di decoding 2301, QeROM reading 2302, 2303, and context RAM reading 2304-2
Running 307 When restored as Di = 0, clock i + 1
Then, if necessary, context update, Di + 1 decoding,
The reading 2310 and 2311 of the Qe ROM for Di + 2 is executed. Di
If + 1 = 0, the signal of Qe RD (Di + 1 = 0) is selected as shown in the figure. By repeating this, pipeline decoding is executed.

FIG. 28 shows the context RAMs 1302 and 130 of FIG.
3 and the area around Qe ROM 1310 are shown in detail. Qe RO
The contents of M and its periphery and the context RAM are the same as the encoder. Selectors 1405 and 1406 select an input signal by decoding the same context immediately after normalization occurs.

Similar to the encoding, the context in which the continuous decoding of symbols is effective is the all white (index-0) and all black (index-1023) contexts. The index-0 detector 1402 and the register 1403 are used for symbol continuous decoding processing. register
The output of 1403 is MPS (0), which is the MPS prediction value at index-0.
This is the QeROM status number Qe-index (0). Although not shown, the context information of index-1023 is output from the context RAM 1305 peripheral area in the same configuration.

These signals enter the Qe ROM 1315 and the maximum symbol length detector 1316 of FIG. The operation of maximum symbol length detection based on these signals is the same as in the case of encoding.
Further, switching between the pipeline decoder and the continuous decoding of symbols can be realized in the same manner as the encoding. As described above, the binary image can be decoded at high speed.

(Encoding / Decoding of Multivalued Image) Encoding / decoding of a multivalued image will be described in the above-mentioned Embodiment 2.
This is as described in detail with reference to FIGS. 10 to 18, and detailed description is omitted here.

That is, the coded symbols are generated without distinguishing the AC component / DC component of the DCT transform coefficient by the binary decomposition processing according to the predetermined procedure, and in accordance with this, the AC component / DC component is generated. The common context is used without distinction, and the context is continuously supplied at a constant speed.
It achieves decryption.

An example of the contents of the table stored in the context generator is shown in FIGS. 29 and 30. 29 is a state transition table of a context index for encoding, and FIG. 30 is a state transition table of a context index for decoding.

In the present invention, the DC component and the AC component are intentionally not distinguished, and a common context is assigned to both component data. In this way, although the compression rate is slightly deteriorated, the process of determining the end of the DC component / AC component as shown in FIG. 43 (a) is completely unnecessary. That is,
As shown in FIG. 44 (a), since it is not necessary to determine the boundary between the DC component / AC component, the context tree is unified into one tree as shown in FIG. 44 (b).

In this way, the high speed of pipeline processing is considered to be of utmost importance, and the code amount is set to the first level as in the conventional case.
The feature of the present embodiment is that the above-mentioned idea is not adopted.

If the context is common, symbol restoration can be continuously executed, and the DC / AC signal reconstruction processing can be performed in parallel by a circuit different from the decoding operation. Therefore, simplification of the device is also achieved.

(Application Example of Multi-Valued Image Compression) An application example of the high-speed arithmetic encoder / decoder described above will be described. Since JBIG coding of binary images and orthogonal transform coding of multivalued images are obvious as direct applications, here we will describe application examples related to adaptive quantization.

FIG. 31 shows an example in which an adaptive control function of a quantizer is added to orthogonal variable coding such as DCT. Arithmetic encoder 1701 is an encoder according to an embodiment of the present invention.

The orthogonal transform coding is composed of an orthogonal transformer 1705, a quantizer 1702 and an arithmetic encoder 1701. Orthogonal transformation shall be performed in 8x8 pixel units like JPEG.

In orthogonal transform coding, if the compression performance is improved, ringing noise is generated at a steep edge portion. To improve this, for example, the edge detection circuit 1704 detects whether there is an edge component for each block, and when the output signal is a predetermined value or more, the scaling coefficient of the quantization table 1703 is changed, and the quantization step You can reduce the width.

The edge detection circuit can be configured by combining edge detection filters in the horizontal and vertical directions. In order to convey the quantizer scaling information to the decoder, the scaling factors need to be encoded. The scaling factor is
Since it does not change frequently, the difference value may be encoded as a DC component. Then, the coding information of each block is 65 in total including the scaling coefficient and the 64 orthogonal transform coefficients. Of these, two are encoded as DC components and 63 as AC components.

FIG. 32 shows an example in which the arithmetic encoder 1801 according to the present invention is used for rate control encoding. In digital copying and the like, it is convenient to keep the coding rate constant in a predetermined range when encoding and storing an image in the buffer memory.

In such a case, the quantization step width may be controlled so that the coding rate falls within a predetermined range for each block or for each macroblock defined from a plurality of blocks. When controlling the rate for each block,
The coding information is a scaling coefficient and 64 frequency components. In a more complicated model, the information to be encoded increases in addition to the frequency component, but the context area and the register (reference numeral 502 in FIG. 12) for delaying the DC component by one block so as to include it in advance. You should implement more.

Since the context model does not change even if the number of encoded information increases, the encoder / decoder configured as in this embodiment can flexibly cope with various applications.

By combining the DCT converter or quantizer capable of high-speed operation with the arithmetic encoder according to the present invention, an extremely high-speed encoder as a whole can be realized even in the above-mentioned application example.

FIG. 49 shows the overall configuration of a digital multi-function peripheral (equipment having both a copy function and a fax function) equipped with the arithmetic code / decoder of the present invention.

The arithmetic code / decoder of the present invention is mounted on the QM code / decoding circuit 105. As shown, the digital device 101 includes a host processor 102, an MH / MR / MM
R code / decoding circuit 103, image processing circuit 104, QM code / decoding circuit 105, image line memory 106, code memory 107, communication interface 108 such as a modem, and image input device 111 such as a scanner. And an image recording / display device 112 such as a printer. According to the present invention, it is possible to realize a highly functional digital device having an unprecedentedly high speed and flexible expandability.

(Results of Simulation of this Embodiment)
Hereinafter, the effect of the present invention will be described based on simulation data. The effects of the high speed processing of the present invention are as follows. (1) Speed-up effect by adapting symbol length for continuous encoding / decoding (applied to binary image) (2) Speed-up effect of pipeline processing by preventing pipeline hazard (binary, multi-valued) (Applicable to binary images) (3) Speed-up effect by enabling pipeline processing by sharing the context of DC and AC components (Applied to multi-valued images) Fig. 45 shows the coding processing speed of binary images The simulation result of is shown. The horizontal axis represents the compression rate and the vertical axis represents the number of cycles (clock number) per symbol. For the document image, the halftone image, a mixed image of these images, and the random image, the compression ratio per page and the number of cycles required for encoding are obtained, and the relationship between them is plotted.

The processing speed is calculated with some allowance for switching between pipeline processing and continuous symbol processing. From this figure, it can be seen that the effect of continuous processing appears when the compression rate is 0.5 or less. The document image has a compression ratio of 0.2 or less. Compression rate 0.2-
0.5 is a mixed image or halftone image, and compression ratios of 0.5 or more are random images with different black ratios. It can be seen that the speed-up effect on the document image is large, and the coding can be performed at about 0.2 cycle / symbol. Since 1 symbol is 1 pixel,
It shows that a processing performance of 400M pixels / second can be realized when operated with an 80MHz clock.

Further, in the present invention, since a plurality of symbol lengths are simultaneously judged in parallel, it is characterized in that the speedup effect can be obtained even for a relatively complicated image such as a mixed image of characters and halftones. For example, if the continuous symbol length is only 64 as in the conventional case, the processing speed becomes 1 cycle / symbol at a low compression rate such as 0.3 or 0.4.

FIG. 46 shows the effect of preventing pipeline hazards. This figure is a plot of the processing speed for each line. The horizontal axis represents the number of lines, and the vertical axis represents the number of processing cycles per symbol.

As the test image, a random image having a compression rate of about 0.5 was used. The upper plot shows the performance of the encoder according to the conventional Qe ROM configuration, and the lower plot shows the performance of the encoder according to the present invention. It can be seen that in the conventional configuration, the performance is degraded by 5% to 10% with respect to the present invention due to the disturbance of the pipeline. When changing the image pattern,
What is the maximum value of deterioration is a difficult problem to evaluate. Depending on the image, the deterioration may be greater. In the present invention, it is not necessary to worry about this.

The lower plot (dotted line) in FIG. 47 is simulation data of the encoding processing speed of a multivalued image.

Similar to JPEG, the orthogonal transform is a DCT transform, the transform coefficient is quantized using a predetermined quantization table, and the quantized value is encoded using the context model according to the present invention. The number of coding cycles was counted assuming that the binary decomposed data string can be coded in one cycle for one symbol.

The horizontal axis is the scaling factor of the quantizer, and the vertical axis is the number of cycles per pixel. Quantization table is J
The table described in PEG Annex-K was used. A scaling coefficient of 2.0 indicates that quantization is performed with a half value of the quantization table value.

The test image is a portrait image. The upper plot in FIG. 47 shows the processing speed when pipeline processing is performed with the DC component and the AC component as separate contexts.
Two cycles / symbol were used for determining the DC / AC context switching each time one symbol was decoded. DC / AC
The number of cycles to initialize the pipeline at the boundary of is also counted.

According to this figure, it is shown that the scaling factor of 1.0 enables encoding by 1 cycle / pixel or less by pipeline processing. According to the principle of the present invention, the decoding speed becomes the same. The present invention standardizes the context of the DC component and the AC component so as to be suitable for pipeline processing,
The context index and index vector can now be generated based on the state transition table. This facilitates pipeline processing, and particularly in the decoder, the high-speed processing effect is improved. On the other hand, there is a drawback in that the compression performance is lowered by sharing the context. Next, the degree of this deterioration is evaluated.

FIG. 48 shows the evaluation of compression performance using the same test image as in FIG. Similar to FIG. 45, the horizontal axis represents the scaling coefficient and the vertical axis represents the compression rate. In this figure, the upper plot shows the compression performance of the conventional example shown in FIG. 42, and the lower plot shows the compression performance of the encoder according to the present invention. Deterioration was about 3% although it varied depending on the scaling factor. This deterioration is mainly DC
It occurs in the encoding of the component.

In the embodiment according to the present invention, the signal encoded as the DC component has a simple configuration for encoding the difference value.
The compression rate can be improved by introducing more advanced signal prediction. High-speed performance is more important than high-speed digital copying and the slight difference in compression performance of the fax machine. The effect of the present invention is great not only in these devices but also in application fields requiring high-speed performance.

The effect of the present invention is not only high in speed, but also characterized in that a CODEC that can be commonly used for encoding binary images and encoding multivalued data can be realized. Further, although the QM-coder is used as the arithmetic code in the description of the present invention, the present invention is not limited to this and can be similarly applied to other arithmetic codes.

[0334]

As described above, the present invention has the following effects (1) to (3). Not only the probability Qe for the current context but also the probability Qe in the future are output in parallel, and as a configuration for selecting them according to the situation (change the configuration of the probability estimation table to enable such processing). ), Eliminating the turbulence of the pipeline, enabling ultra-high speed processing. By distinguishing between DC and AC components, a mechanical binary decomposition process according to a predetermined procedure and a common context are set to realize a hazardless pipeline process for multi-valued image data. Further, since the processing is simplified, it is possible to obtain effects such as flexible expandability and reduction in the amount of hardware. By performing batch encoding / decoding processing while adaptively changing the number of batch processing symbols according to the complexity and resolution of the image, the margins and line spacings achieve higher speed processing. As a result, according to the present invention, it is possible to realize an epoch-making codec capable of flexibly processing a binary image or a multi-valued image and processing at a limit speed almost determined by an arithmetic code algorithm. it can.

[Brief description of drawings]

FIG. 1 is a block diagram showing an overall configuration of a hazardless pipeline arithmetic encoder according to the present invention.

FIG. 2 is a diagram showing a configuration example of a probability estimation memory according to the present invention.

3 is an operation of the arithmetic encoder of FIG. 1 (pipeline operation)
Timing diagram to explain

FIG. 4 is a block diagram showing the overall configuration of a hazardless pipeline arithmetic decoder according to the present invention.

5 is a block diagram showing in detail the configuration around the Qe ROM of the arithmetic decoder of FIG.

6 is an operation of the arithmetic decoder of FIG. 4 (pipeline operation)
Timing diagram to explain

FIG. 7 is a flowchart for explaining the characteristic operation of the arithmetic encoder of the present invention.

FIG. 8 is a flowchart for explaining a characteristic operation of the arithmetic decoder of the present invention.

FIG. 9 is a diagram for explaining the effect of the arithmetic encoder of the present invention.

FIG. 10 is a block diagram showing a configuration of a context generator in an arithmetic encoder having a multi-valued image data encoding function of the present invention.

FIG. 11 is a block diagram showing the configuration of a context generator in an arithmetic decoder having a decoding function for multi-valued image data according to the present invention.

12 is a block diagram showing the configuration of a binary decomposition processor of the arithmetic encoder of FIG.

FIG. 13 is a diagram showing a procedure of binary decomposition processing (generation of encoded symbols) in the binary decomposition processor.

14 (a) is a diagram showing an example of a common context used in the arithmetic encoder of FIG. 10 (b) is a diagram showing another example of a common context used in the arithmetic encoder of FIG.

15A is a flowchart showing the procedure of encoding processing of multivalued data in the arithmetic encoder of FIG. 10, and FIG. 15B is a flowchart showing the procedure of arithmetic encoding of DCT transform coefficients (frequency component data).

FIG. 16 is a diagram showing an example of a specific encoding sequence when encoding is performed according to the procedure of FIGS. 13 and 15A and 15B.

FIG. 17 is a diagram showing an example of the overall configuration of a decoding context generator of the present invention.

FIG. 18 is a diagram showing, in a tree structure, how the context index for multilevel data encoding changes.

FIG. 19A is a block diagram showing the outline of the configuration of a context generator in a multi-valued data decoder, and FIG. 19B is a diagram showing a change in context index at the time of decoding in a tree structure.

FIG. 20 is a diagram showing an example of an image to be encoded.

FIG. 21 is a block diagram showing an overall configuration of an arithmetic encoder / decoder having a collective encoding function for a plurality of symbols in an all-white area according to the present invention.

FIG. 22 is a diagram for explaining the relationship between the batch subtraction of Qe and the normalization processing in arithmetic sign calculation.

FIG. 23 is a flowchart showing a processing procedure when collectively encoding a plurality of symbols in an all-white area.

FIG. 24 is a diagram showing the overall configuration of an arithmetic code / decoder of the present invention.

FIG. 25 is a block diagram showing a detailed configuration of an arithmetic encoder of the present invention (having both a binary / multilevel hazardless pipeline function and an adaptive multiple symbol batch function).

26 is a block diagram showing the configuration of a maximum symbol number detector in the arithmetic encoder of FIG. 25.

FIG. 27 is a block diagram showing a main configuration of an arithmetic decoder according to the present invention.

FIG. 28 is a block diagram showing a main configuration of an arithmetic decoder according to the present invention.

FIG. 29 is a diagram showing state transition of a context index for multilevel data encoding.

[Fig. 30] Fig. 30 is a diagram showing a state transition of a context index for multilevel data decoding.

FIG. 31 is a diagram showing an example of an apparatus to which multilevel arithmetic coding is applied.

FIG. 32 is a diagram showing another example of an apparatus to which multilevel arithmetic coding is applied.

FIG. 33 is a diagram for explaining pipeline processing in a conventional arithmetic encoder.

FIG. 34 is a diagram for explaining a problem of pipeline processing in the conventional arithmetic encoder.

FIG. 35 is a diagram for explaining hazardless pipeline processing in the arithmetic encoder of the present invention.

FIG. 36 is a diagram for explaining a switching timing between pipeline processing and continuous processing of a plurality of symbols in the arithmetic encoder of the present invention.

FIG. 37 is a diagram for explaining main operation timings of the arithmetic decoder of the present invention.

FIG. 38 is a diagram showing a configuration example of a Qe ROM in the arithmetic encoder of the present invention.

FIG. 39 is a diagram showing a template for arithmetic coding in JBIG.

FIG. 40 is a diagram showing the contents of a general probability estimation table.

FIG. 41 is a diagram showing a configuration of a conventional Qe ROM.

FIG. 42 is a diagram showing a configuration example of a multi-valued data coding context in a conventional example (comparative example).

43A is a diagram for explaining switching between the DC component context and the AC component context in the conventional example, and FIG. 43B is a diagram of the DC component context tree to the AC component context tree in the conventional example. Diagram showing transitions

FIG. 44 (a) is a diagram for explaining switching between the DC component context and the AC component context in the present invention; and (b) is a diagram showing a unified context tree in the present invention.

FIG. 45 is a diagram showing a simulation result of a processing speed of a binary image of the arithmetic encoder of the present invention.

FIG. 46 is a diagram showing pipeline processing performance of the arithmetic encoder of the present invention in comparison with a conventional example.

[Fig. 47] Fig. 47 is a diagram illustrating a simulation result regarding a coding processing speed of a multi-valued image of the arithmetic encoder of the present invention.

FIG. 48 is a diagram showing a simulation result regarding compression performance of a multi-valued image in the arithmetic encoder of the present invention.

FIG. 49 is a block diagram showing the overall configuration of a digital device equipped with an arithmetic encoder / decoder according to the present invention.

FIG. 50 is a diagram for explaining the outline of the overall configuration of the arithmetic encoder.

FIG. 51 is a diagram for explaining the principle of arithmetic coding.

FIG. 52 is a diagram showing a template for arithmetic coding in JBIG.

[Explanation of symbols] 700 context generator 701 Context RAM 702 Qe ROM 703 Arithmetic code calculator 704-707 selector 708 EOR circuit 709 control circuit 710,711,712 Timing adjustment circuit

─────────────────────────────────────────────────── ─── Continuation of front page (56) References JP-A-7-249995 (JP, A) JP-A-2000-115549 (JP, A) JP-A-2000-278538 (JP, A) JP 3406550 (JP, B2) Patent 3350482 (JP, B2) Patent 3308940 (JP, B2) (58) Fields investigated (Int.Cl. ⁷ , DB name) H04N 1/41-1/419

Claims (17)

(57) [Claims] 1. A DC component obtained by orthogonally transforming multivalued image data.
And an AC component are mixed and converted into an orthogonal transform coefficient,
The AC conversion coefficient begins with the DC component and the high frequency component
Sorted in the order of minutes, the decision event is a tree-like sequence.
If it is a can and the judgment event is YES, NO judgment
Decision sequence for binary decomposition of orthogonal transformation coefficient by repeating
To set the orthogonal transformation coefficient to the decision sequence.
Therefore, in the decision event that was subject to the decision by binary decomposition
Outputs YES / NO judgment results for the
Min. And AC component are used in common
The context for each decision event in the decision sequence.
Event that has been assigned, and the judgment event corresponding to the judgment result
Output the context assigned to
An arithmetic encoding method for multi-valued data, which is arithmetically encoded using a text and a determination result . 2. The determination sequence is the orthogonal transform function.
The smaller the number, the faster the judgment result will be output.
2. The multiple according to claim 1, wherein the disconnection events are arranged.
Arithmetic encoding method for value data. 3. The orthogonal transform coefficients are after rearrangement in order.
EOB information and positive / negative information of each orthogonal transform coefficient detected in
And the decision sequence begins with EOB information and
Positive / negative information is binary decomposed and then the number of orthogonal transform coefficients
Arrangement of decision events so as to process the values in binary.
The multivalued data according to claim 1 or 2,
Arithmetic encoding method. 4. The decision sequence is provided for each decision event.
"1" or "0" is assigned to the judgment result
The arithmetic coding method for multivalued data according to claim 1 , wherein the conversion coefficient is converted into a determination result of a binary number sequence . 5. Dominance sequence estimated by context
The probability of the predicted value and inferiority symbol symbols when coding and supplies the code calculator executes the pipeline processing, a method for arithmetic coding a multivalued data at a high speed, multi-level The image data is orthogonally transformed to obtain a DC component and an AC component.
The step of converting into mixed orthogonal transform coefficients, and the orthogonal transform coefficients are DC components at the beginning,
The step of rearranging in the order of frequency components and the judgment
Orthogonal transformation is possible by repeating YES and NO judgments for elephants.
A decision sequence for binary decomposition of the replacement coefficient is provided, and the orthogonality
The conversion factor is binary decomposed according to the determination sequence.
Yes or NO for the judgment event
The step of outputting the judgment result and the context model shared by the DC component and the AC component
For each decision event in the decision sequence.
The text is assigned, and the judgment in the judgment sequence is performed.
Assigned to the judgment event corresponding to the judgment result in synchronization with
The output of the detected context, and the determination result and the context corresponding thereto are output.
Each time the
Obtain the predicted value and the current probability estimate of the recessive symbol
Therefore, if a normalization process occurs and the prediction conditions are updated , the step of obtaining a future probability estimate for the same context as the context, and the difference between the previous context and the current context and the previous context
According to the presence / absence of normalization processing at the time of encoding, selecting either the current probability estimated value or the future probability estimated value and supplying the selected probability estimated value to the code calculator. Arithmetic encoding method for data. 6. After identifying binary data and multi-valued data,
For multi-valued data, no to encode decomposed into binary data after generating the encoded symbols of the binary co
Predicted value of dominant symbol estimated according to context
And an inferiority symbol occurrence probability are supplied to a code calculator, which is an arithmetic coding method for performing high-speed arithmetic coding by pipeline processing, wherein multivalued image data is orthogonally transformed with respect to the processing of the multivalued data. DC component and AC component
The step of converting into mixed orthogonal transform coefficients, and the orthogonal transform coefficients are DC components at the beginning,
The step of rearranging in the order of frequency components and the judgment
Orthogonal transformation is possible by repeating YES and NO judgments for elephants.
A decision sequence for binary decomposition of the replacement coefficient is provided, and the orthogonality
The conversion factor is binary decomposed according to the determination sequence.
Yes or NO for the judgment event
The step of outputting the judgment result and the context model shared by the DC component and the AC component
For each decision event in the decision sequence.
The text is assigned, and the judgment in the judgment sequence is performed.
Assigned to the judgment event corresponding to the judgment result in synchronization with
The output of the scrambled context, and for a process common to binary and multi-valued data, the predicted value of the dominant symbol depending on the generated context.
To estimate the current probability estimate of the recessive symbol,
Furthermore, if the normalization process occurs, the prediction conditions are updated.
Later, in the same context as the above
The step of obtaining the future probability estimate, and the difference between the previous context and the current context and the previous context
Depending on the presence or absence of normalization processing at the time of encoding,
Choose either the probability estimate or the future probability estimate.
Optionally, supplying to the code calculator.
See further, with respect to the binary data processing, the called context and dominant symbol are consecutive 1
And the second condition that the value of the remaining area does not become less than a predetermined value after the area widths of recessive symbols corresponding to the number of consecutive dominant symbols are collectively subtracted from the current orient. Is always detected, and if those conditions are satisfied, the maximum number of symbols satisfying the first and second conditions is detected under predetermined conditions, and the collective code for the detected number of symbols is detected. An arithmetic coding method , comprising the step of adaptively performing encoding. 7. A DC component obtained by orthogonally transforming multivalued image data.
Orthogonal transform that transforms into an orthogonal transform coefficient in which
The conversion means and the orthogonal transformation coefficient have a DC component at the beginning and a high frequency component from a low frequency component.
Format conversion means for rearranging in the order of frequency components and judgment event is a sequence in which tree-like judgment events are connected.
Orthogonal transformation is possible by repeating YES and NO judgments on elephants.
A decision sequence for binary decomposition of the replacement coefficient is provided, and the orthogonality
The conversion factor is binary decomposed according to the determination sequence.
Yes or NO for the judgment event
Disassembly processing means for outputting a determination result and each determination made based on the determination sequence
Both the state number corresponding to the event and the DC and AC components
Based on the adapted context model, it is determined for each state number.
Transition according to the determined context and the judgment result
It has a state transition table in which the following state numbers are registered,
Corresponding to the judgment event to be judged by the decomposition processing means
The state transition table based on the context number
Read out from the
Context generating means for determining the next state number, and the judgment result output from the decomposition processing means and the context.
Using the context output from the
, The predicted value of the dominant symbol and the probability estimate of the recessive symbol
The estimation means for estimating and the predicted value of the dominant symbol and the probability estimate of the recessive symbol
Arithmetic code operation means for executing arithmetic encoding using the
Arithmetic encoder provided. 8. The estimation means stores a probability estimation value of a recessive symbol in association with a state number.
Stored memory, the state is
The recessive symbol for the context corresponding to the state number
The current probability estimate and the normalization process
After the prediction condition is updated,
Estimated future probability for the same context
The recorded probability estimation memory is paired with each context corresponding to the context model.
The predicted value of the dominant symbol and the probability estimation memory
Context memo that corresponds to the status number for
The difference between the previous context and the current context and the previous
Depending on the presence / absence of normalization processing at the time of encoding,
Constant memory from the current probability estimate or the future probability estimate.
Select one of the rate estimation values to the arithmetic code operation means
8. Arithmetic code according to claim 7, comprising a control means for supplying.
Device. Wherein said probability estimation memory, the current probability estimate (Qe), the future probability estimates (next Qe) and, if an update of the state number stored in said context memory has occurred The updated status number (ne
xt state No.) stores a and the current probability estimate, the probability estimate of the future, and outputs each of the updated state number in parallel, said control means, said probability estimating A first selector for selecting one of the current probability estimate value (Qe) output from the memory and the future probability estimate value (next Qe); and the state number output from the context memory ( state No.) or the updated state number (next state No.) output from the probability estimation memory, and supplies it to the probability estimation memory as address information. , before the control to probability estimation value selected by the first selector and (Qe or next Qe), the predicted value of the symbols output from said context memory and (MPS), the a
The arithmetic code calculator is supplied to the arithmetic means.
8. The arithmetic coding device according to item 8 . 10. Regarding input binary data, a value of a predetermined plurality of consecutive encoded symbols and a value of a reference pixel used when encoding each encoded symbol match a predetermined pattern. That the maximum number of symbols that can be coded collectively is determined based on the detection results of these detectors, and the maximum number of symbols to be supplied to the arithmetic code calculation means is the maximum symbol. The arithmetic coding device according to any one of claims 7 to 9 , further comprising a number determination circuit. 11. A context generation process, a probability estimation memory read process, a context memory read process, and an arithmetic coding operation are executed in the same cycle to be pipelined, and one pixel is coded in one cycle. The arithmetic coding device according to any one of claims 8 to 10 . 12. Arithmetic code for orthogonal transform coefficient of multi-valued data
The arithmetic code data obtained by digitizing the
An arithmetic decoding method for performing arithmetic decoding below, wherein the input arithmetic code data is a probability estimation of a dominant symbol.
On the number line divided by the value and the probability estimate of the recessive symbol
, Whether it belongs to a dominant symbol or a recessive symbol
Judge and recover the predicted value of the symbol to which the arithmetic code data belongs.
Decoding step of outputting as a signal symbol and determination for binary decomposition of orthogonal transform coefficients during arithmetic coding
Corresponds to a decision sequence in which events are arranged in a tree.
The text tree is constructed, and the DC component and the AC component are shared.
The context using a specialized context model
Assign a context to each node of the tree and restore
Each time a symbol symbol is generated, it corresponds to the value of the decoded symbol.
Then transitions on the context tree, and
Context that outputs the context assigned to
Probability generation step and the probability of recessive symbol estimation based on the output context.
Estimate predicted values for constant values, dominant symbols and / or recessive symbols
And an estimation step which is given to the decoding step,
Arithmetic decoding method provided. 13. An arithmetic code for orthogonal transform coefficients of multi-valued data.
The arithmetic code data obtained by digitizing the
An arithmetic decoding device for performing arithmetic decoding below, wherein the input arithmetic code data is a probability estimation of a dominant symbol.
On the number line divided by the value and the probability estimate of the recessive symbol
, Whether it belongs to a dominant symbol or a recessive symbol
Judge and recover the predicted value of the symbol to which the arithmetic code data belongs.
Used for binary decoding of orthogonal transform coefficients during arithmetic coding and arithmetic decoding operation means for outputting as a symbol
State number corresponding to each judgment event, DC component and AC component
State number based on the context model shared by and
It corresponds to the context defined for each and the value of the decoded symbol.
The next state number to be transitioned to and the state transition where is registered
A table is provided, and the status number is generated each time a decoded symbol is generated.
Context generator that generates the context according to the issue
And a context output from the context generating means.
To the predicted value of the dominant symbol and the probability estimate of the recessive symbol
Estimating means for estimating and giving to the arithmetic decoding operation means
An arithmetic decoding device comprising: 14. The context generating means includes:
And have use of the state transition tables, each transition destination of up to 2 cycles destination
Four contexts are generated according to the state number, and the estimation means stores the probability estimation value of the recessive symbol in association with the state number.
Stored memory, the state is
The recessive symbol for the context corresponding to the state number
The current probability estimate and the normalization process
After the prediction condition is updated,
Estimated future probability for the same context
Two recorded probability estimation memories and the dominance of the context model for each context
Symbol predictor and recessive symbol in each context
To access the probability estimate and the probability estimate memory
4 context memories that store the state number of
And four contexts generated by the context generating means
Parallel from the corresponding context memory
2 status numbers from 4 status numbers output to
Two states selected by the decoded symbol and selected
It is output in parallel from the probability estimation memory corresponding to the state number.
Selected probability estimation value according to the latest decoded symbol
14. Arithmetic according to claim 13, further comprising:
Decoding device. 15. Arithmetic decoding for arithmetically decoding the coded data obtained by binary-decomposing multivalued data and arithmetically coding or the coded data obtained by arithmetically coding binary data by pipeline processing. The state of the symbol sequence that has already been decoded by the device (context)
A first context generation for generating a context for decoding binary data as means for estimating a probability of occurrence of a decoded symbol from, and supplying the estimated value and the predicted value of the symbol to a decoder for decoding. Means and a second context generating means for generating a context for decoding multi-valued data, a current probability estimate, an updated probability estimate, and an updated probability. Probability estimation memory that outputs in parallel each piece of address information indicating the address where the estimated value is stored, and the current probability estimated value and updated probability estimated value that are output in parallel to this probability estimation memory. First selecting means for selecting any one of them, and a context memory storing predicted symbol and address information of the probability estimation memory for each context And, as the address of the probability estimation memory, either the output of the context memory or the address information output from the probability estimation memory and indicating the address in which the updated probability estimation value is stored is selected. Second selecting means, the probability estimation value selected by the first selecting means,
An arithmetic decoding operation unit for performing an arithmetic decoding operation using the predicted value (MPS) of the symbol output from the context memory, and the data to be finally restored is binary data. , A plurality of detectors that constantly detect that a reference pixel corresponding to a plurality of predetermined consecutive decoded symbols matches a specific pattern, and a batch decoding based on the detection results of these detectors. A maximum symbol number determining means for determining the maximum possible symbol number and supplying the maximum symbol number to the arithmetic decoding arithmetic unit, and the data to be finally restored is multi-valued data. An arithmetic decoding device comprising a multi-value synthesizing processing circuit for synthesizing binary data decoded by the arithmetic decoding arithmetic unit to restore multi-valued data. 16. The method according to claim 14 or 15, wherein the context generation processing, the probability estimation memory reading processing, the context memory reading processing, and the arithmetic decoding operation are executed in the same cycle and pipelined. An arithmetic decoding device characterized by executing decoding of one pixel in one cycle. 17. The arithmetic coding device according to any one of claims 7 to 11 , or claims 13 to 1.
An electric device equipped with the arithmetic decoding device according to any one of 6 above.