Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1998-09-23
2002-02-26
Tran, Phuoc (Department: 2721)
Image analysis
Image compression or coding
Lossless compression
C382S233000
Reexamination Certificate
active
06351569
ABSTRACT:
TECHNICAL FIELD
The present invention relates to implementation of encoding and decoding image data.
BACKGROUND ART
A number line encoding method (arithmetic encoding method) is also known as encoding method for Markov information source, where a symbol sequence is mapped between 0.0 and 1.0 on the number line, and its coordinate is encoded into a codeword indicated by, for example, binary notation.
FIG. 1
is a conceptual drawing of the above method. For simplifying an explanation, binary symbols “1” and “0” are supplied at random out of a memoryless state, which is independent of past occurrence states. In this case, an occurrence probability of symbol “1” is defined as r and an occurrence probability of symbol “0” is expressed as 1−r. A range for the symbol “1” is placed at the bottom of the figure. The length of an output sequence of memoryless source is assumed to be three, and coordinates for C(000) through C(111) shown in the right rows are respectively expressed by binary numbers. These binary numbers are cut off at digit, where the number can be identified, and the binary numbers are defined as respective codewords. By defining as above, the codewords can be decoded at a receiving side by operating a process similar to a transmitting side.
In the above case, a mapping range A
i
for mapping on the number line of the symbol sequence at the i-th point, minimum coordinates C
i
of the mapping range A
i
are as follows where an initial value of the mapping range is A
0
=1.0 and the minimum coordinates C
0
=0.0:
when an occurring symbol value a
i
is “0”,
A
i
=(1−
r
)
A
i−1
C
i
=C
i−1
+rA
i−1
;
and
when the symbol value a
i
is “1”,
A
i
=rA
i−1
C
i
=C
i−1
As described in “An overview of the basic principles of the Q-coder Adaptive binary arithmetic coder” (IBM Journal of Research & Development Vol. 32 No. 6, November, 1988), in order to reduce a number of operations such as a multiplication with large operational load, instead of calculating rA
i−1
, a set of fixed values S may be provided as a table. Encoding and decoding with finite precision is implemented by selecting a value corresponding to Markov status out of the table.
Accordingly, as mapping is continuously repeated, the range (interval) A
i−1
becomes smaller, renormalization is performed (e.g., A
i−1
is multiplied by power of 2 to keep the value A
i−1
more than a predefined value), and an operational precision is kept under a virtual decimal point by virtually resetting a decimal point. In obtaining an actual codeword, the above set of fixed values can be always used.
Here, by approximating rA
i−1
to S, each of the above expressions becomes each of the following:
when the symbol value a
i
is “0”,
A
i
=A
i−1
−S
C
i
=C
i−1
+S;
and
when the symbol value a
i
is “1”,
A
i
=S
C
i
=C
i−1
The range (interval) A
i−1
resulted from the previous symbol, essentially becomes smaller as mapping is continuously repeated, thus, S should accordingly be reduced. This reduction can be performed by shifting operation into one n-th (n is power of 2). However, the reduction of S causes to increase a number of 0 aligning in the high order bits of S, which does not directly effect to the operation. On the contrary to the above operation, by multiplying A
i−1
by power of 2 and by keeping A
i−1
more than a minimum value (1/2), it is possible that S having the fixed value is used. The foregoing process is called renormalization.
In the following explanation, a symbol is called MPS (more probable symbol: symbol having higher probability of occurrence) when the symbol a
i
is “0”, and a symbol is called LPS (less probable symbol: symbol having lower probability of occurrence) when the symbol a
i
is “1”. Namely, a prediction conversion is previously performed and MPS showing a higher probability of occurrence or LPS showing a lower probability of occurrence is assigned to each symbol. And when the symbol a
i
is “1”, the range
A
i
=rA
i−1
=S
becomes a range (interval) of the less probable symbol.
FIG. 2
is a block diagram showing an example of an encoder of a conventional encoding apparatus. In the figure, reference numeral
1
shows a register for temporarily storing a value of range (interval) assigned to the previous symbol. Reference numeral
2
shows a subtracter,
3
shows a switch of range (interval),
4
shows a switch of coordinates,
5
shows a shifter for determining a shifting amount for renormalization, and
6
shows a calculator for calculating encoded output.
Next, an operation of the apparatus will be described referring to the figure.
S (within a range (interval) of LPS), which is previously selected from the states of Markov information source based on the table specifying a plurality of values at a prediction estimator (not shown in the figure), is entered to the subtracter
2
. The subtracter
2
obtains and outputs a difference (A
i−1
−S) from the range (interval) A
i−1
for the previous symbol stored in the register
1
.
The switch
3
receives the range (interval) (A
i−1
−S) assigned to MPS and the range (interval) S assigned to LPS, and the switch
3
switches the range according to whether the symbol is MPS or LPS. Namely, when the symbol is MPS, the range (interval) A
i
assigned to the symbol is determined and output as
A
i
=A
i−1
−S
and when the symbol is LPS, the range (interval) A
i
assigned to the symbol is determined and output as
A
i
=S
The switch
4
selects one of the range (interval) S for LPS and a fixed value 0 according to whether received symbol is MPS or LPS and outputs the selected value as &Dgr;C, difference coordinates between the range (interval) assigned to the previous symbol and the minimum coordinates C
i−1
. Namely, when the received symbol is MPS placed in the high order bit, the difference coordinates &Dgr;C is output as
&Dgr;C=S
when the received symbol is LPS placed in the low order bit, the difference coordinates &Dgr;C is output as
&Dgr;C=0
The output A
i
of the switch
3
is supplied to the register
1
and to the shifter
5
.
The range (interval) A
i
assigned to the symbol a
i
is stored in the register
1
and the range (interval) for a next symbol is calculated based on the data of A
i
. The shifter
5
compares the range (interval) A
i
with {fraction (1/2+L )}. When the range (interval) A
i
is smaller than {fraction (1/2+L )}, the shifter
5
doubles the range (interval) A
i
and compares the doubled result of the range (interval) A
i
with {fraction (1/2+L )} again. The shifter
5
repeats this doubling of the range (interval) A
i
until the doubled result of the range (interval) A
i
is greater than {fraction (1/2+L )}. The number 1 of the above doublings is obtained and output to the register
1
and the calculator
6
as a shifting amount
1
. Then, the calculator
6
calculates a codeword using the outputs supplied from the switch
4
and the shifter
5
and outputs the codeword. The calculator
6
stores difference coordinates accumulated from the past. Namely, this accumulated value equals to the minimum coordinates C
i−1
of the range (interval) assigned to the previous symbol. The input difference coordinates &Dgr;C is added to the minimum coordinates C
i−1
of the previous symbol to obtain the minimum coordinates C
i
of the range (interval) assigned to the present symbol. The minimum coordinates C
i
is shifted by the shifting amount 1 (bits). Then, it is checked whether one of the high order bits of the maximum coordinates within the effective range matches to any of the high order bits of the shifted minimum coordinates C
i
. If there exists a bit matched, the matched bit is determined and output as determined bit of coordinates, in other words, a codeword.
Next, the general arithmetic encoder and the general arithmetic decoder will be explained in detail.
T
Kimura Tomohiro
Ono Fumitaka
Yoshida Masayuki
Alavi Amir
Mitsubishi Denki & Kabushiki Kaisha
Tran Phuoc
LandOfFree
Coding method, decoding method, coding device and 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 Coding method, decoding method, coding device and decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding method, decoding method, coding device and decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960359