Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2002-01-17
2004-01-13
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
C341S067000, C382S247000
Reexamination Certificate
active
06677869
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an arithmetic coding apparatus and image processing apparatus.
2. Description of the Related Art
An arithmetic coding system that predicts a coding symbol based on states of already coded pixels and carries out arithmetic coding on the prediction result based on a probability estimate of the coding symbol determined for each state is known to have the most excellent characteristic in terms of compressibility.
A QM-coder, a coder adopted by JBIG (ITU Recommendation T.82), is a typical example of an apparatus for carrying out arithmetic coding.
A general configuration and operation of the QM-coder, which is an arithmetic coder for binary images, will be explained below.
As shown in
FIG. 18
, the QM-coder comprises context generation section
200
, context table (context memory)
210
, probability estimator
220
and arithmetic coder
230
.
Context generation section
200
detects 1024 states created by 10 pixels surrounding to a coding pixel.
FIG. 20
shows an example of a template.
“?” in the figure is the coding pixel and the 10 pixels marked “x” are reference pixels. When coding of one pixel is completed, the template is shifted by one rightward as shown with dotted line in FIG.
20
and coding of the next pixel is performed.
Each of 1024 states determined by the values of 10 pixels is called “context” (hereinafter expressed with “S”). A predicted value of a more probable symbol MPS(s) (that is, if MPS of the coding pixel is predicted as “1” by the context s, MPS(s)=1) and a state number of the probability estimator are read from context memory for each context and output to probability estimator
220
.
Probability estimator
220
outputs interval width of a less probable symbol Qe(s) to arithmetic coder
230
based on this information. Here, “Qe” is a probability that LPS will occur and the present specification sometimes refers to Qe as a “symbol occurrence probability” or simply as a “probability estimate”.
Furthermore, interval width of a less probable symbol Qe(s) means the width corresponding to the probability of occurrence of LPS which is calculated by multiplying the probability of occurrence of LPS by the width of an augend. The augend refers to the overall width of a number line shown in FIG.
19
.
Arithmetic coder
230
performs arithmetic coding calculations based on the coding symbol, predicted value of MPS(S), and interval width Qs(s), and outputs code stream.
As shown in
FIG. 19
, arithmetic coding divides a number line of initial value 0 to 1 into two sub-intervals of a more probable symbol (MPS) and a less probable symbol (LPS). A series of coding symbols is associated with a point (a coding point) some where within each sub-interval. For the simplicity, the QM-coder uses the convention that the coding point is located at the bottom of the sub-interval.
When a coding symbol matches a predicted value, an MPS width is selected for coding of the symbol and an LPS width is selected otherwise.
As described above, a coding point is provided in this sub-interval and a binary fraction of the point denotes an arithmetic code stream.
When the interval width falls short of a predetermined value, an arithmetic coding calculation repeats the doubling operation until the interval width exceeds a predetermined value (more specifically ½ of the initial value) to maintain the accuracy of decimal points. This processing is called “renormalization”.
Renormalization is also carried out when LPS is coded. That is, when an LPS width is selected as a result of estimation failure, the LPS width is always smaller than ½ of the initial value and therefore renormalization is performed every time.
When renormalization is performed, the MPS value and state number (ST) in context table
210
in
FIG. 18
are updated. The state number is updated when the “next state number” written in probability estimation section
220
is overwritten in context table
210
. In
FIG. 18
, this overwrite is indicated by an arrow RX.
With this update of the context table
210
, even if the next context is also the same as the previous context (that is, even if the template in
FIG. 20
is shifted by one rightward, the positions of 1 and 0 of the reference pixels are the same as the previous positions), the value of Qe(S) that occurs is different.
In this way, a Qe (S) value suitable for a probability distribution of the information source is selected. That is, the coding parameter Qe (s) is more adapted to the target image.
Here, the coding target is not limited to binary data. Multi-valued data such as continuous-tone image can also be coded using the QM-coder. However, it is necessary to use a context model which matches the coding target.
For example, a discrete cosine transform coefficient (DCT coefficient) includes a DC component and AC component. The both components have different natures of signal. Therefore, it is important to construct a context model suited to these natures in improving the coding efficiency.
In the current technology, different contexts are created for the DC component and AC component.
The conventional arithmetic coding processing has the following problems.
(Problem 1)
Originally, arithmetic coding is excellent in compressibility, but since it is necessary to repeat generation of a context, estimation of symbol occurrence probability and arithmetic code calculation symbol by symbol, arithmetic coding has a disadvantage that it requires a long processing time. A reduction of the processing speed is quite a big problem in such a field as a digital copier that requires high image quality and high speed processing.
Furthermore, when arithmetic coding is pipelined, if renormalization occurs at some midpoint, disturbance occurs with the pipeline resulting in an increase of useless wait time. The processing efficiency may reduce in this way. Especially, renormalization occurs with considerable frequency and pipeline disturbance is likely to occur in image patterns whose context has continuity. The same problem may also occur in the case of decoding.
Therefore, even if arithmetic coding is pipelined, the accuracy cannot be said to be high and speeding up of arithmetic coding/decoding is not expected much.
(Problem 2)
It is desirable to carry out high accuracy pipeline processing in the case of not only coding of binary data but also coding or decoding of multi-valued data (e.g., numerical data such as orthogonal transform coefficient, etc. obtained by JPEG compression).
However, high-speed arithmetic coding or decoding of numerical values such as orthogonal transform coefficients involves the following problems.
That is, making pipeline processing effectively requires data necessary for the next pipeline stage to be supplied continuously at a constant rate.
For example, performing high-speed decoding requires context indices to be supplied simultaneously to a plurality of symbols which are likely to be reconstructed. A set of these context indices will be called “context index vector”.
It is actually difficult to supply context data of such a vector format at a constant rate. As described above, an orthogonal transform coefficient includes a DC component and AC component. Since the DC component and AC component have statistically different natures, the current technology provides different contexts for the respective components.
It is difficult to supply different contexts consecutively. Thus, when DC components and AC components are mixed in a plurality of symbols to be coded, it is difficult to supply a context index vector at a constant rate.
Therefore, high-speed arithmetic coding of multi-valued data is more difficult than in the case of binary data.
(Problem 3)
It would be convenient if it is possible to divide an input image into blocks of a predetermined size, apply arithmetic coding block by block independently and freely perform decoding in block units.
However, since an arithmetic code is a variable-length code, the code length of a code corresponding to one
Greenblum & Bernstein P.L.C.
Panasonic Communications Co. Ltd.
Wamsley Patrick
LandOfFree
Arithmetic coding apparatus and image processing apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic coding apparatus and image processing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic coding apparatus and image processing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3194712