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

Abstract

The invention relates to a method and ana arrangement for arithmetially encoding and decoding binary state, a corresponding computer program, and a corresponding computer-readable storage medium, which can be used particularly for digital data compression. According to the invention, table-supported binary arithmetic encoding and decoding is done by using two or several tables, for example.

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] An early 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 encoding 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 likely), the probability symbol PL-1 is given in the second step [2], for further calculation of the width of the BPSB.

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 range of values of R by discrete values in the form (1⁄2 - r), where r ∈ {0} {2-k ribofk >0, k integer} is chosen [15] [16].

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 an arithmetic coding device and an arithmetic decoding device 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 by using a scroll operation applied to the internal/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 pre-quantized by the scroll 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 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 andvalMPS 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,valMPS 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}$ Other 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: For encoding according to the first specific embodiment, sub-steps 1 to 4 shall be performed according to the following calculation rule: Other or The first specific embodiment encoding step 1 to 4 shall be performed according to the following calculation rule: Other 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: Other or the second special afb decoding sub-steps 1 to 5 are performed according to 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: 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 Qt ≤ N (1 ≤ Pn ≤ N) to a different northern range, in a second step the decoding is performed using a decoding or decoding procedure based on different probability rules, by using a numerical symbol representing the range of probabilities and a decoding function representing each interval and decoding the range of probabilities to a different northern range (or a decoding function) by using the decoding symbols and decoding operations to represent the range of probabilities and the range of probabilities to be decoded in accordance with the basic probability intervals (1 ≤ Pn ≤ N) and decoding operations to be performed by dividing the range of probabilities into two or more regions, and decoding them into two groups according to the probability of the number of the widespread or the number of possible values.

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. Table-based probability estimation 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 stationary source statistics, this estimate must be updated during the coding process.PLPS=cLPScLPS+cMPSOther 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 interval division 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 (by q bit). Alternatively, in special cases, quantization can also be performed without the use of a tabulated figure Qtab only by a combination of sliding and masking operations.This index is now used together with the p_state index 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 K · Nmax product values 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 target; PL. Both quantities are determined by the granularity of the representation of RPS and Re.

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 values must be initialized at the beginning of encoding or decoding a completed quantity unit (in video coding applications, for example, a slice). The initialization values can be derived from control information, such as the encoding parameter (of a slice), as illustrated in Figure 6.

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 (2)

1. An arrangement 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 device comprises the following characterizing feature:

   means for encoding the symbol to be encoded, comprising the following means:

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

   means for 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;

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

   means for renormalizing the new updated interval width, outputting one bit per scaling operation.
2. An arrangement 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 for addressing a probability state from a plurality of representative probability states, wherein the device comprises the following characterizing feature:

   means for decoding the encoded symbol, comprising the following means:

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

   means for 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;

   means for 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

   means for renormalizing the new updated offset point and, with each bit read in, gradually refining the value within the partial interval.