HK1127525B - Method and arrangement for arithmetic encoding and decoding binary statuses and an appropriate computer program and corresponding computer-readable storage medium - Google Patents

Description

The invention relates to a method and an arrangement for the arithmetic encoding and decoding of binary states, as well as a corresponding computer program and a corresponding computer-readable storage medium, which can be used in particular for digital data compression.

The present invention describes a new efficient method for binary arithmetic coding. The need for binary arithmetic coding arises in the most diverse application areas of digital data compression; here applications in the fields of digital image compression are of particular interest.

The advantages of arithmetic coding (AK) over the Huffman coding [2] so far commonly used in practice can be characterised by three main features: 1. The use of arithmetic coding allows for dynamic adaptation to the existing source statistics by simple adaptation mechanisms (adaptivity).2. Arithmetic coding allows the allocation of a non-integer number of bits per symbol to be coded and is thus suitable for obtaining coding results that represent an approximation of entropy as the theoretically given lower limit (entropy approximation) [3].3. Using appropriate context models, arithmetic coding allows statistical relationships between symbols to be used for further data reduction (in-arrymbol redundancy) [4].

The disadvantage of using arithmetic coding is the increased computational effort compared to Huffman coding.

The concept of arithmetic coding dates back to Shannon's fundamental work on information theory.[5] First conceptual design methods were first published by Elias in [6] A first LIFO (last-in-first-out) variant of arithmetic coding was designed by Rissanen[7] and later modified by various authors into FIFO (first-in-first-out) trainings[8][9][10].

Err1:Expecting ',' delimiter: line 1 column 197 (char 196) $N_{\mathrm{Bit}}=-\log \prod _{i}P\left(S_i\right)=-\sum _i\log P\left(S_i\right)\mathrm{.}$

However, the basic principle first requires (theoretically) unlimited accuracy in the representation of the resulting partial interval and has the disadvantage that only after encoding the last event can the bits to represent the resulting partial interval be output. For practical applications, it was therefore crucial to develop mechanisms for an incremental output of bits when simultaneously representing with numbers of given fixed accuracy. These were first presented in the papers [3] [7] [11].

In the illustrated implementation, the current subinterval is represented by the two values L and R, where L is the starting point and R is the size (width) of the subinterval, and both are represented with b-bit integers. The coding of a bit ∈ {0, 1} is essentially done in five sub-steps: In the first step, the value of the less likely symbol is determined by the probability estimate. For this symbol, also called LPS (least probable symbol) in the distinction code MPS (most probable), the probability symbol PL-1 is given in the second step for further calculation of the width of RPS ∈ B. For each step, the corresponding part of the interval is met.

The main disadvantage of an implementation as outlined above is that the calculation of the RLPS range width requires a multiplication per symbol to be encoded. Multiplication operations are usually time-consuming and costly, especially when implemented in hardware.

The first group of proposals for a multiplication-free binary arithmetic coding is based on the approach of approximating the estimated probabilities of PLPS so that the multiplication in step 2 of Figure 1 can be replaced by one (or more) sliding and addition operations [11] [14].

In the second category of approximate methods, it is proposed to approximate the value range of R by discrete values in the form (1⁄2 - r), where r ∈ {0} {2-k.

The third category of methods is characterized by the replacement of all arithmetic operations by table accesses, which includes the Q-coder used in the JPEG standard and related methods such as the QM and MQ-coder [12], and the quasi-arithmetic coders [13]. While the latter method drastically reduces the number of bits used to represent R to acceptably sized tables, in Q-coder the renormalization of R is designed so that R can be approximated by at least 1 and thus the multiplication to RPSL is avoided.

US5592162 describes a method for performing an arithmetic coding, limiting the number of possible interval widths.

The use of an index that refers to these interval widths can achieve multiplication-free arithmetic coding with reduced memory usage.

The present invention is a method for arithmetic coding and a method for arithmetic decoding according to the claims in the Annex.

The method for arithmetic coding and decoding binary states is preferably performed in such a way that in a first step a predefined range of values for specifying the interval width R is divided into K representative interval widths {Q1, ..., QK}, a predefined range of values for specifying the probabilities into N representative probability states {P1, ..., PN} and assignment rules are specified to assign to each interval width Rk (1 ≤ k ≤ K) and to each probability one Pn (1 ≤ n ≤ N), in a second step the encoding or decoding of the state is performed by calculating the decoding or decoding process representative of the probability interval Q under different probability rules and by dividing the probability intervals into a number of sub-processes representative of the probability interval Q ≤ 1 and representative of the probability interval P ≤ 1 (the probability interval is defined by the following formula:

Another embodiment is characterized by the fact that starting from the currently evaluated interval with width R to determine the assigned interval width Qk an index q_index is determined by a slide and bitmasking operation applied to the internal/binary representation of R.

It is also useful to use the width R of the interval to be evaluated to determine the width Qk of the assigned interval, to obtain an index q_index by a sliding operation applied to the in-computer/binary representation of R and a downlink to a table Qtab, where the table Qtab contains the indices of interval widths corresponding to the values of R prequantized by the sliding operation.

In particular, it is advantageous to assign the underlying probability estimate of the symbol to be encoded or decoded to a probability state Pn by means of an index p_state.

It is also advantageous to determine the range width RLPS corresponding to the LPS by accessing a table Rtab, where the table Rtab contains the values of the range width RLPS corresponding to all K quantized values of R and the N different probability states as product values (Qk * Pn).

It is further envisaged that the method for the N different representative probability states will provide transition rules, specifying which new state is to be used for the next to be encoded or decoded from the currently encoded or decoded symbol, and/or a table Next_State_LPS containing the index m of the new probability state Pm for the occurrence of a most probable symbol (LPS) at the index n of the currently given probability state Pn and/or a table Next_State_MPS containing the index m of the new probability state Pm for the occurrence of a most probable symbol (MPS) at the index n of the currently encoded or decoded symbol (MPS).

Optimization of the method for table-based binary arithmetic encoding and decoding is achieved in particular by storing the values of the RLPS interval width corresponding to all K interval widths and to all N different probability states as product values (Qk * Pn) in a table Rtab.

Further optimization is achieved by selecting the number K of quantization values and/or the number N of representative states depending on the precision of the coding and/or the storage space available.

For example, encoding includes the following steps: The first step is to determine the LPS2 and the second is to quantify R:q_index=QtabR>>qDetermination of RLPS and R:RLPS=Rtabq_indexp_stateR=R-RLPSThe new sub-interval is calculated as follows: 5. Renormalisation of L and R, writing of bits, where q_index the index of a quantification value read from Qtab,p_states the current state,RLPS the range width corresponding to the LPS andva1MPS the bit corresponding to the MPS The following is a description of the

Decoding includes, for example, the following steps: The first step is to determine the LPS2 and the second is to quantify R:q_index=QtabR>>qDetermination of RLPS and R:RLPS=Rtabq_indexp_stateR=R-RLPSDetermination of bit, according to the position of the sub-interval: 5. Renormalization of R, reading out a bit and updating V, wherein q_index the index of a quantization value read from Qtab,p_states the current state,RLPS the width of the range corresponding to the LPS,va1MPS the bit corresponding to the MPS andValue from the inside of the current sub-range The following is a description of the

Another method provides that the calculation of the quantization index q_index is carried out in the second sub-step of the encoding and/or decoding procedure according to the calculation rule: $\mathrm{q\_}\mathrm{index}=\left(R,>,>,q\right)\&\mathrm{Qmask}$ where Qmask is a bitmask selected as appropriate depending on K.

If a uniform probability distribution is available, further optimization of the method for table-based binary arithmetic encoding and decoding can be achieved by: in the case of encoding according to the first specific embodiment, sub-steps 1 to 4 shall be performed according to the following calculation rule: R←R>>1Other or the first specific embodiment encoding sub-steps 1 to 4 shall be performed according to the following calculation rule: L←L<<1Other and in the last alternative, renormalisation (sub-step 5 following the first specific implementation example) with doubled decision thresholds and no doubling of L and R, decoding following the second specific implementation example using sub-steps 1 to 4 according to the following calculation rule: R←R>>1Other or the second special afb decoding sub-steps 1 to 5 are performed in accordance with the following calculation format: 1. read out a bit and update V2. determine bit according to the position of the sub-interval: Other

It is further advantageous to initialize the probability models depending on a quantization parameter SliceQP and predefined model parameters m and n, where SliceQP describes the quantization parameter specified at the beginning of a slice and m and n describe the model parameters.

It is also advantageous if the initialization of the probability models includes the following steps: The following table shows the results of the calculation of the performance of the SliceQP: Other where valMPS is the corresponding bit of the MPS, SliceQP is the quantization parameter specified at the beginning of a slice and m and n are the model parameters.

An arithmetic binary state encoding and decoding device shall include at least one processor that is configured to perform an arithmetic encoding and decoding procedure, with a first step of a predefined range for specifying the range R in K representative ranges {Q1, ..., QK}, a predefined range for specifying the probabilities in N representative probability states {P1, ..., PN} and allocation rules that represent each specified range R in a Qk (1 ≤ k ≤ K) and Qn ≤ Pn (1 ≤ n) to a different decoded range, followed by a second decoded range or decoded range to a different decoded range, and an allocation rule that represents each specified range R in a Qk (1 ≤ k ≤ K) to a different decoded range or decoded range to a different decoded range, by using a decoded range or decoded range to represent the probability of the new range and the probability of the decoded range (or P ≤ P) to a different decoded range, or decoded range, and decoded according to the probability of the decoded range, by using a decoded range or decoded range of probabilities and a decoded range of probabilities, and a decoded range of probabilities, and a decoded range of probabilities, and a decoded range of probabilities, and a decoded range of probabilities, and a decoded range of probabilities, and a decoded intervals, and a decoded interval, and a decoded interval, and a decoded by using a decoded interval or decoded interval (or) to represent the range and decoded interval (or) to a decoded interval, or decoded interval, or decoded by a decoded interval, or decoded interval, or decoded by a decoded interval, or decoded by a decoded interval, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, or decoded, decoded, decoded

A computer program for the arithmetic encoding and decoding of binary states enables a computer, after being loaded into the computer's memory, to perform an arithmetic encoding and decoding procedure, in which a first step is to divide a predefined range of values for specifying the range R into K representative intervals {Q1, ..., QK}, a predefined range of values for specifying the probabilities into widespread representative probabilities {P1, ..., PN} and specify assignment rules that represent each interval a Qk (1 ≤ K) and a Qn ≤ Pn (1 ≤ N) to a different northern range, in a second step the decoding is performed using a decoded range or a decoded range of values, and the resulting probabilities are determined by using a numerical numerical decoding scheme (1 ≤ P) or a numerical decoding scheme (1 ≤ P) to represent each interval and a decoded range of probabilities to a different northern range, and the result is to be determined by using the decoded range of probabilities and the decoded range of the probabilities in accordance with the probability distribution of the widespread value of the new range of probabilities and the decoded range of the original range of the range of probabilities and the resulting values in each decoded range.

For example, such computer programs (whether paid or free, freely accessible or password protected) may be made available for download on a data or communications network, and the computer programs thus made available may be made available by a process whereby a computer program described in claim 22 is downloaded from a data transmission network, such as the Internet, to a network-connected data processing device.

To perform a method for arithmetic encoding and decoding of binary states, it is advantageous to use a computer-readable storage medium on which a program is stored that allows a computer, after being loaded into the computer's memory, to perform an arithmetic encoding and decoding procedure, whereby a first step is to specify a predetermined range of values for specifying the range R in case representative intervals {Q1, ..., QK}, a predetermined range of values for specifying the probabilities in case representative probability states {P1, ..., PN} and specify a set of rules for specifying a range R ≤ K ≤ Q (1 k) and a probability ≤ n (1 k) for each method.in a second step, the binary states are encoded or decoded by calculating the new range to be derived in the encoding or decoding process using a representative range Qk (1 ≤ k ≤ K) and a representative probability state Pn (1 ≤ n ≤ N) by means of arithmetic operations, including multiplication and division, where the representative range Qk is determined by the underlying base range of the range R and the representative probability state Pn by the underlying probability estimate of the symbol to be encoded or decoded in accordance with the prescribed rules.

The invention is explained in more detail below by an example of an embodiment shown in the figure.

It shows: Figure 1Representation of the main operations for binary arithmetic coding;Figure 2Modified scheme for table-based arithmetic coding;Figure 3Principle of table-based arithmetic decoding;Figure 4Principle of encoding or decoding for binary data with uniform distribution;Figure 5Alternative implementation of encoding or decoding for binary data with uniform distribution.Figure 6Initialisation of the probability models depending on a quantization parameter SliceQP and a given model parameter m and n

The first step is to explain the theoretical background:

Table-based probability estimate

As explained above, the method of arithmetic coding is based on the best possible estimate of the probability of occurrence of the symbols to be coded. To allow adaptation to instational source statistics, this estimate must be updated during the coding process. $P_{\mathrm{LPS}}=\frac{c_{\mathrm{LPS}}}{c_{\mathrm{LPS}}+c_{\mathrm{MPS}}}$ Other For practical purposes, the division required in equation (1) is unfavourable, but it is often useful and necessary to recalculate the counter values when a given threshold Cmax of the total numerator cTotal = cMPS + cLPS is exceeded. (Note in this context that in a b-bit representation of L and R, the smallest probability that can still be represented correctly is 2-b+2, so that a recalculation of the counter constants is necessary if necessary to avoid crossing this lower limit.) With a suitable choice of Cmax, the recalculation of the expected values of cTotal (1) can be done in such a way that the necessary equivalent division in a table can be used to fully convert the table and also to avoid the possibility of using a multiplication table, but this method is also used to prevent the operation of this operation.)

In addition, transitional rules are defined to specify which new state to use from the currently coded symbol for the next to be coded symbol. These transitional rules are provided in the form of two tab appearances: {Next_State_LPSk NPSk 0 ≤ k < max} and {Next_State_MPSk NPSk ≤ 0 k Nmax}, whereby the additional tables for the currently available maximum number of states m are defined in such a way that the index of probability of a new state of probability is identified in the appropriate section of the table, and only if it is necessary to specify the value of the MPSk in the appropriate place of the MPSk or its corresponding probability index, or if the MPSk p is not specified in the appropriate section of the table, then the indices for the current state of probability of the new state of probability of the MPSk MPSk < 0 ≤ k < max.

Table-based breakdown of intervals

Figure 2 shows the modified scheme for table-based arithmetic coding as proposed here. After determining the LPS, the given interval width R is first mapped to a quantized value Q by means of a tabulated figure Qtab and a suitable sliding operation (about q bit). Alternatively, in special cases, the quantization can also be performed without the use of a tabulated figure Qtab only with the help of a quantisation of sliding and combining operations.This index is now used together with the index p_state to characterize the current probability state for determining the interval width RLPS. For this purpose, the corresponding entry in the table Rtab is used. There the product values K · Nmax R x PLPS corresponding to all K quantized values of R and Nmax different probability states are stored as integer values with an accuracy of i.a. b-2 bits. For practical implementations, here a possibility is given to weigh between the storage requirements for the table size and the arithmetic accuracy, which ultimately also determines the efficiency of the coding. Both quantities are determined by the granularity of the representation of RPS and PL.

Err1:Expecting ',' delimiter: line 1 column 258 (char 257)

Figure 3 shows the corresponding sequence of table-based arithmetic decoding. The decoder uses the interval width R and a value V to characterize the current sub-interval. The latter is located inside the sub-interval and is successively refined with each bit read.

In applications where, for example, pre-specified values are to be coded with a probability distribution symmetrical to zero, the pre-specification information can usually be coded with a uniform distribution. Since this information is to be embedded in the arithmetic bitstream on the one hand, but it is not practical to use the still relatively complex apparatus of table-based probability estimation and interval subdivision for a probability of P ≈ 0.5, it is proposed to use an optional encoder/decoder procedure, as follows, for this particular case.

In the encoder, the interval width of the new sub-interval can be determined for this special case by a simple sliding operation corresponding to a halving of the width of the output interval R. Depending on the value of the bit to be encoded, the upper or lower half of R is then chosen as the new sub-interval (see Figure 4).

In the corresponding decoder, the necessary operations are reduced to determining the bit to be decoded by the value of V relative to the current interval width R by a simple comparison operation. In the case of setting the decoded bit, V is to reduce the amount of R. As shown in Figure 4, decoding is completed by renormalizing and updating V with the next bit to be read.

An alternative implementation of coding events with uniform probability distribution is shown in Figure 5. In this example implementation, the current interval width R is not modified. Instead, the encoder doubles V by a sliding operation. Depending on the value of the bit to be coded, then, similar to the previous example, the upper or lower half of R is chosen as the new subinterval (see Figure 5).

The second step is performed in the same way as step 1 in Figure 4, i.e. the bit to be decoded is determined by the value of V relative to the current interval width R by a simple comparison operation, and in the case where the decoded bit is set, V is to reduce the amount of R (see Figure 5).

Addressing and initializing the probability models

Each probability model as used in the present invention is characterized by two parameters: 1) the index p_state, which characterizes the probability state of the LPS, and 2) the value valMPS of the MPS. Each of these two quantities must be initialized at the beginning of encoding or decoding a completed coding unit (in video coding applications, such as a slice).

Forward-controlled initialization process

Another way of adjusting the start distributions of the models is provided by the following method: To ensure better adjustment of the model initializations, a selection of default start values of the models can be provided in the encoder; these models can be grouped into groups of start distributions and addressed with indices, so that the adaptive selection of a group of start values is made in the encoder and transmitted to the decoder in the form of an index as page information.

Finally, it is possible to choose the number of possible quantization indices and/or the number of probability states depending on the precision of the coding and/or the storage space available.The probability estimation of the states can be done by a finite state machine (FSM).It is also possible to generate the probability states offline.Finally, it can be envisaged that the selection of the states depends on the statistics of the data to be coded and/or the number of states.

The Commission shall publish the list of the Member States.

Err1:Expecting ',' delimiter: line 1 column 72 (char 71)Err1:Expecting ',' delimiter: line 1 column 112 (char 111)Err1:Expecting ',' delimiter: line 1 column 44 (char 43)Err1:Expecting ',' delimiter: line 1 column 52 (char 51)

Claims (4)

1. A method for arithmetically encoding a symbol to be encoded having a binary state based on a current interval width R and a probability representing a probability estimation for the symbol to be encoded, wherein the probability is represented by a probability index for addressing a probability state from a plurality of representative probability states, wherein the method comprises the following characterizing step:

   encoding the symbol to be encoded by performing the following substeps:

   mapping the current interval width to a quantization index from a plurality of representative quantization indices;

   performing the interval separation by accessing an interval division table using the quantization index and the probability index to obtain a partial interval width value;

   updating the current interval width using the partial interval width value to obtain a new, updated interval width; and

   renormalizing the new updated interval width, outputting one bit per scaling operation.
2. A method for arithmetically decoding an encoded symbol having a binary state based on a current interval width R and a probability representing a probability estimation for the encoded symbol, wherein the probability is represented by a probability index of a probability state from a plurality of representative probability states, wherein the method comprises the following characterizing step:

   decoding the encoded symbol by performing the following substeps:

   mapping the current interval width to a quantization index from a plurality of representative quantization indices;

   performing the interval division by accessing an interval division table using the quantization index and the probability index to obtain a partial interval width value;

   updating the current interval width using the partial interval width value and a value within a partial interval to obtain a new, updated interval width; and

   renormalizing the new updated offset point and, with each bit read in, gradually refining the value within the partial interval.
3. A computer program which enables a computer after it has been loaded into the storage of the computer to perform a method according to claim 1 or 2.
4. A computer-readable storage medium on which a program is stored which enables a computer after it has been loaded into the storage of the computer to perform a method according to claim 1 or 2.