Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2001-08-07
2002-12-03
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
37, C375S240000
Reexamination Certificate
active
06489903
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to an encoding method, an encoding apparatus, a decoding method, and also a decoding apparatus, capable of compressing/decompressing data.
2. Description of the Related Art
As an example of known encoding systems, a description will be made of an arithmetic encoding operation capable of achieving a high compression rate. Before describing a concrete operation, a conceptional idea of a binary arithmetic encoding operation is explained with reference to FIG.
16
. An arithmetic encoding operation is realized in such a manner that a coordinate system value of a binary decimal number on a numerical straight line defined larger than, or equal to 0.0 and smaller than 1.0 becomes a code C. In a process stage, a range defined on the above-explained numerical straight line is divided as a valid section (effective section) width A in direct proportion to an appearance probability of a binary symbol, and a partial section corresponding to an actually appearing symbol is divided as a new valid section, which is repeatedly carried out. MPS (More Probable Symbol) corresponds to a superior symbol which indicates a data value of higher appearance probability. LPS (Less Probable Symbol) corresponds to an inferior symbol which indicates a data value of lower appearance probability. One coordinate value which is updated by a final symbol within a valid section is outputted as a code. During process operation, the code C is calculated as a lower bound value of a valid section, and this code C is updated as well as a width of a valid section, which is equal to a difference between an upper bound value and a lower bound value in this drawing. As the final code, it is also possible to select a coordinate value where a significant digit number is minimum within a valid section where 0 subsequent to a tail of a coordinate system is cut off.
In general, to practically execute the arithmetic encoding operation, a subtraction type arithmetic encoding operation is employed which is adaptive to cope with an increase in a significant digit number when a code calculation is carried out. It is assumed in the below-mentioned description that an arithmetic code indicates a subtraction type arithmetic code.
FIG. 17
is a diagram for representing a conceptional idea of a subtraction type arithmetic encoding operation and a conceptional idea of a renormalizing process operation. A symbol LSZ corresponds to a partial section allocated to LPS, and an approximate value is selected from a previously prepared table based upon appearance probability of the symbols. In this step, when the valid section becomes smaller than
½, such a renormalizing process operation is carried out that the valid section is multiplied by power of
2 so as to be enlarged larger than, or equal to
½. As a consequence, a digit number of a decimal portion is kept constant during a calculation. At this time, in an integer portion, these digits which constitutes ‘
1’ subsequent to a decimal point and ‘0’ of an upper digit of this ‘1’, may be changed by a carry-up propagation in a coordinate calculation which will be performed later. Thus, the values are not defined. Since digits upper than these values do not contain the carry-up propagation, these upper digits can be sent out from an encoder.
Both the most typical encoder (Encoder) of the subtraction type arithmetic encoding operation and also the most typical decoder (Decoder) thereof may be realized by employing the table and the process flow, which are described in the International Standard Recommendation T. 82 of ITU-T. Here, this arithmetic encoding operation will the be referred to as a QM coder, and while data to be encoded is used as a binary image, the calculation process operations of both the encoding operation and the decoding operation defined in the above-explained preceding technical publication will now be described. In this case, when the encoding calculation process operation and the decoding calculation process operation of the QM coder are carried out, the correcting techniques for partial sections corresponding to the symbols disclosed in Japanese Patent No. 2128115 (U.S. Pat. Nos. 5,307,062, 5,404,140) are employed. This correcting technique will be explained with reference to
FIG. 18
, in which numeral values are expressed by the decimal system. In FIG.
18
(
a
), while the valid section is 0.6, 0.2 is selected as LSZ which may occupy ⅓ of the entire section. Since this LSZ is not larger than ½, LSZ is allocated to LPS, and the remaining section is allocated to MPS. However, as shown in FIG.
18
(
b
), when LSZ may occupy ⅔ of the entire section, which exceeds ½ thereof, since the symbol correspondences between the appearance probability rate and the actual occupation rate are inversed, the correction is performed by simply exchanging the sections by both MPS and LPS so as to suppress deterioration of the encoding performance. This is referred to as an “conditional MPS/LPS exchange”.
FIG.
19
and
FIG. 20
respectively represent block structural diagrams of an encoder
1
A and a decoder
1
B of QM coder, which are provided to explain operations with respect to both the encoding calculation process operation and the decoding calculation process operation. In this prior art, both an image memories
5
A and
5
B are assumed to be arranged inside the encoder
1
A and the decoder
1
B, respectively.
In FIG.
19
and
FIG. 20
, reference numeral
2
shows a context (Context), reference numeral
3
indicates a pixel (Pixel) which should be encoded, reference numeral
4
represents a code, and reference numerals
5
A and
5
B are image memories. Reference numeral
7
shows a prediction value table MPS, reference numeral
8
indicates a state table ST, reference numeral
9
represents an LPS section width table LSZ, reference numeral
10
shows an MPS state transition destination table NMPS, reference numeral
11
denotes an LPS state transition destination table NLPS, reference numeral
12
shows a prediction value inversion judgement table SWTCH, reference numerals
13
A and
13
B show arithmetic encoders, reference numeral
14
represents a symbol, and also reference numerals
15
A and
15
B represent pixel symbol converters.
Operations of the QM coder will now be explained. The image memory
5
A employed in the QM encoder
1
A stores thereinto an entered image
6
, and refers to a predetermined encoded pixel by a model template with respect to the pixel
3
which should be encoded, and outputs the pixel
3
which should be encoded and the context
2
equal to a pattern produced from the pixel at the same time.
On the other hand, the image memory
5
B employed in the QM decoder
1
B stores therein the decode pixel
3
which has already been decoded, produces the context
2
with respect to such a pixel that should be decoded later from this stored pixel
3
, and then outputs the produced context
2
. The image memory
5
B obtains such a pixel that should be decoded and is decoded by using this context to store thereinto this pixel which should be decoded, and then, outputs an image
6
.
In the QM coder, prediction coincident probability of a pixel value is predicted in every context with respect to the pixel which should be encoded/decoded, and the encoding/decoding operations are executed, while the QM coder erans in connection with this variation. Learning is carried out by rewriting two variable tables
7
and
8
in which the context
2
is used as an index. One of these variable tables corresponds to a prediction value table MPS
7
of each 1 bit (will be referred to as “MPS table 7” hereinafter) which stores thereinto as a prediction value in a state in which a pixel value MPS whose appearance probability is high. The other corresponds to a state table ST
8
of each 7-bit (will be referred to as an “ST table 8” hereinafter) which stores thereinto state numbers (
0
to
112
). The state numbers are produced by classifying a degree of predicti
Kimura Tomohiro
Ueno Ikuro
Yoshida Masayuki
Mitsubishi Denki & Kabushiki Kaisha
Nguyen John
Young Brian
LandOfFree
Data encoding method, data encoding apparatus, data decoding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data encoding method, data encoding apparatus, data decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data encoding method, data encoding apparatus, data decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992330