Search

EP-3652937-B1 - METHOD AND APPARATUS FOR RANGE DERIVATION IN CONTEXT ADAPTIVE BINARY ARITHMETIC CODING

EP3652937B1EP 3652937 B1EP3652937 B1EP 3652937B1EP-3652937-B1

Inventors

  • CHUANG, TZU-DER
  • CHEN, CHING-YEH

Dates

Publication Date
20260513
Application Date
20180712

Claims (20)

  1. A method of entropy coding of coding symbols, the method comprising: applying (510) context-adaptive arithmetic encoding or decoding to a current bin of a binary data of a current coding symbol according to a current binarized probability value of the current bin and a current range associated with a current state of the context-adaptive arithmetic encoding or decoding, wherein the current binarized probability value relates to a probability of the current bin generated according to one or more previously coded symbols before the current coding symbol; deriving (520) an LPS (least-probable-symbol) probability index corresponding to an inverted current binarized probability value or the current binarized probability value depending on whether the current binarized probability value of the current bin is greater than or equal to 2 k-1 , k being a positive integer; deriving (530) a range index for identifying one range interval containing the current range; and deriving (540) an LPS range using one or more mathematical operations comprising calculating a multiplication of a first value of (2 * the LPS probability index + 1) or the LPS probability index and a second value of (2 * the range index + 1) or the range index, or deriving the LPS range using a look-up-table including table contents corresponding to values of LPS range associated with a set of LPS probability indexes and a set of range indexes for encoding or decoding the current binarized probability value of the current bin, wherein the range index corresponds to a result of right-shifting the current range by mm and mm is a non-negative integer and each value of LPS range corresponds to one product of (2 * one LPS probability index + 1) and (2 * one range index + 1) or deriving an LPS range corresponds to an offset and one product of one LPS probability index and one range index, wherein when the current binarized probability value of the current bin is greater than or equal to 2 k-1 , the LPS probability index is set equal to (2 n+1 - 1) minus a result of right-shifting the current binarized probability value by (k-n-1) bits; otherwise, the LPS probability index is set equal to the result of right-shifting the current binarized probability value by (k-n-1) bits; and wherein the current probability is represented by k-bit values, and n and k are positive integers, wherein the LPS range is derived by multiplying the LPS probability index with the range index to obtain a multiplication result, and right-shifting the multiplication result by x bits plus an offset and x is a positive integer, the offset is an integer.
  2. The method of Claim 1, wherein when the probability for the current bin is greater than 0.5 or greater than or equal to 0.5, an LPS probability is set equal to (1 - the current probability) and otherwise, the LPS probability is set equal to the probability; and the LPS probability index is determined based on a target index indicating one probability interval containing the probability or the LPS probability.
  3. The method of Claim 1, wherein when the current binarized probability value of the current bin is greater than or equal to 2 k-1 , an LPS probability is set equal to (2 k - 1 - the current binarized probability value) and the LPS probability index is set equal to a result of right-shifting the LPS probability by (k-n-1) bits; otherwise, the LPS probability is set equal to the current binarized probability value and the LPS probability index is set equal to the result of right-shifting the current binarized probability value by (k-n-1) bits, n and k are positive integers.
  4. The method of Claim 1, wherein k is equal to 15.
  5. The method according to any one of the preceding claims, wherein k is equal to 15 and n is equal to 5.
  6. The method of Claim 1, wherein the LPS range is derived by multiplying (2 * the LPS probability index + 1) with (2 * the range index + 1) to obtain a multiplication result, and right-shifting the multiplication result by x bits and x is a positive integer.
  7. The method of claim 6, wherein x is equal to 3.
  8. The method of claim 1, wherein x is equal to 1, and the offset is equal to 2, 3 or 4.
  9. The method of Claim 1, wherein the look-up-table corresponds to a two-dimensional table with the LPS probability index as a first table index in a first dimension and a clipped range index as a second table index in a second dimension, where the clipped range index corresponding to the range index.
  10. The method of Claim 9, wherein the LPS probability index has a first value range from 0 to 31, the clipped range index has a second value range from 0 to 7 and the LPS range has a third value range from greater than or equal to 0 to smaller than or equal to 255.
  11. The method of Claim 10, wherein the look-up-table corresponds to: (range>>5)&7 rangeIdx 0 1 2 3 4 5 6 7 probIdx, (ProbLPS>>9) 31 133 149 165 181 196 212 228 244 30 129 144 160 175 190 205 221 236 29 125 140 154 169 184 199 213 228 28 121 135 149 163 178 192 206 220 27 116 130 144 158 171 185 199 213 26 112 125 139 152 165 178 192 205 25 108 121 133 146 159 172 184 197 24 104 116 128 140 153 165 177 189 23 99 111 123 135 146 158 170 182 22 95 106 118 129 140 151 163 174 21 91 102 112 123 134 145 155 166 20 87 97 107 117 128 138 148 158 19 82 92 102 112 121 131 141 151 18 78 87 97 106 115 124 134 143 17 74 83 91 100 109 118 126 135 16 70 78 86 94 103 111 119 127 15 65 73 81 89 96 104 112 120 14 61 68 76 83 90 97 105 112 13 57 64 70 77 84 91 97 104 12 53 59 65 71 78 84 90 96 11 48 54 60 66 71 77 83 89 10 44 49 55 60 65 70 76 81 9 40 45 49 54 59 64 68 73 8 36 40 44 48 53 57 61 65 7 31 35 39 43 46 50 54 58 6 27 30 34 37 40 43 47 50 5 23 26 28 31 34 37 39 42 4 19 21 23 25 28 30 32 34 3 14 16 18 20 21 23 25 27 2 10 11 13 14 15 16 18 19 1 6 7 7 8 9 10 10 11 0 2 2 2 2 3 3 3 3 wherein "rangeIdx" corresponds to the range index or the clipped range index, "probIdx" corresponds to the LPS probability index, and "rangeIdx" is derived according to (range>>5)&7 and "range" corresponds to the current range.
  12. The method of Claim 10, wherein the look-up-table corresponds to: (range>>5)&7 rangeIdx 0 1 2 3 4 5 6 7 probIdx, (ProbLPS>>9) 31 128 143 159 174 190 205 221 236 30 124 139 154 169 184 199 214 229 29 120 134 149 163 178 192 207 221 28 116 130 144 158 172 186 200 214 27 112 125 139 152 166 179 193 206 26 108 121 134 147 160 173 186 199 25 104 116 129 141 154 166 179 191 24 100 112 124 136 148 160 172 184 23 96 107 119 130 142 153 165 176 22 92 103 114 125 136 147 158 169 21 88 98 109 119 130 140 151 161 20 84 94 104 114 124 134 144 154 19 80 89 99 108 118 127 137 146 18 76 85 94 103 112 121 130 139 17 72 80 89 97 106 114 123 131 16 68 76 84 92 100 108 116 124 15 64 71 79 86 94 101 109 116 14 60 67 74 81 88 95 102 109 13 56 62 69 75 82 88 95 101 12 52 58 64 70 76 82 88 94 11 48 53 59 64 70 75 81 86 10 44 49 54 59 64 69 74 79 9 40 44 49 53 58 62 67 71 8 36 40 44 48 52 56 60 64 7 32 35 39 42 46 49 53 56 6 28 31 34 37 40 43 46 49 5 24 26 29 31 34 36 39 41 4 20 22 24 26 28 30 32 34 3 16 17 19 20 22 23 25 26 2 12 13 14 15 16 17 18 19 1 8 8 9 9 10 10 11 11 0 4 4 4 4 4 4 4 4 wherein "rangeIdx" corresponds to the range index or the clipped range index, "probIdx" corresponds to the LPS probability index, and "rangeIdx" is derived according to (range>>5)&7 and "range" corresponds to the current range.
  13. The method of Claim 1, wherein the LPS probability is set equal to a result of bitwise exclusive or (XOR) for a value of (current probability >> (k-1)) and the current probability, or the LPS probability index is set equal to the result of bitwise exclusive or for the value of (current probability >> (k-1)) and the value of (current probability >> (k-n-1)); and wherein the current probability is represented by k-bit values, and n and k are positive integers.
  14. The method of Claim 1, further comprising deriving, from the current range, a rangeOne value and a rangeZero value for the current bin having a value of one and a value of zero respectively, wherein if the current probability of the current bin is greater than 0.5 or is greater than or equal to 0.5, the rangeOne value is set to (the current range - the LPS range) and the rangeZero value is set to the LPS range; and otherwise, the rangeZero value is set to (the current range - the LPS range) and the rangeOne value is set to the LPS range.
  15. An entropy coding apparatus (130, 140) for an image or video encoder or decoder, the entropy coding apparatus (130, 140) comprising: apply context-adaptive arithmetic encoding or decoding to a current bin of a binary data of a current coding symbol according to a current binarized probability value of the current bin and a current range associated with a current state of the context-adaptive arithmetic encoding or decoding, wherein the current binarized probability value relates to a probability of the current bin generated according to one or more previously coded symbols before the current coding symbol; derive an LPS (least-probable-symbol) probability index corresponding to an inverted current binarized probability value or the current binarized probability value depending on whether the current binarized probability value of the current bin is greater than or equal to 2 k-1 , k being a positive integer; derive a range index for identifying one range interval containing the current range; and derive an LPS range using one or more mathematical operations comprising calculating a multiplication of a first value of (2 * the LPS probability index + 1) or the LPS probability index and a second value of (2 * the range index + 1) or the range index, or deriving the LPS range using a look-up-table including table contents corresponding to values of LPS range associated with a set of LPS probability indexes and a set of range indexes for encoding or decoding the current binarized probability value of the current bin, wherein the range index corresponds to a result of right-shifting the current range by mm and mm is a non-negative integer and each value of LPS range corresponds to one product of (2 * one LPS probability index + 1) and (2 * one range index + 1) or deriving an LPS range corresponds to an offset and one product of one LPS probability index and one range index, wherein when the current binarized probability value of the current bin is greater than or equal to 2 k-1 , the LPS probability index is set equal to (2 n+1 - 1) minus a result of right-shifting the current binarized probability value by (k-n-1) bits; otherwise, the LPS probability index is set equal to the result of right-shifting the current binarized probability value by (k-n-1) bits; and wherein the current probability is represented by k-bit values, and n and k are positive integers, wherein the LPS range is derived by multiplying the LPS probability index with the range index to obtain a multiplication result, and right-shifting the multiplication result by x bits plus an offset and x is a positive integer, the offset is an integer.
  16. The entropy coding apparatus (130, 140) of Claim 15, wherein when the probability for the current bin is greater than 0.5 or greater than or equal to 0.5, an LPS probability is set equal to (1 - the current probability) and otherwise, the LPS probability is set equal to the probability; and the LPS probability index is determined based on a target index indicating one probability interval containing the probability or the LPS probability.
  17. The entropy coding apparatus (130, 140) of Claim 15, wherein the LPS range is derived by multiplying (2 * the LPS probability index + 1) with (2 * the range index + 1) to obtain a multiplication result, and right-shifting the multiplication result by x bits and x is a positive integer.
  18. The entropy coding apparatus (130, 140) of Claim 15, wherein the look-up-table corresponds to a two-dimensional table with the LPS probability index as a first table index in a first dimension and a clipped range index as a second table index in a second dimension, where the clipped range index corresponding to the range index.
  19. The entropy coding apparatus (130, 140) of Claim 15, wherein the LPS probability is set equal to a result of bitwise exclusive or (XOR) for a value of (current probability >> (k-1)) and the current probability, or the LPS probability index is set equal to the result of bitwise exclusive or for the value of (current probability >> (k-1)) and the value of (current probability >> (k-n-1)); and wherein the current probability is represented by k-bit values, and n and k are positive integers.
  20. The entropy coding apparatus (130, 140) of Claim 15, further comprising deriving, from the current range, a rangeOne value and a rangeZero value for the current bin having a value of one and a value of zero respectively, wherein if the current probability of the current bin is greater than 0.5 or is greater than or equal to 0.5, the rangeOne value is set to (the current range - the LPS range) and the rangeZero value is set to the LPS range; and otherwise, the rangeZero value is set to (the current range - the LPS range) and the rangeOne value is set to the LPS range.

Description

FIELD OF THE INVENTION The present invention relates to entropy coding techniques for image coding and video coding. In particular, the present invention relates to range derivation for Context-Based Adaptive Binary Arithmetic Coder (CABAC) for image coding and video coding. BACKGROUND AND RELATED PRIOR ART EP 3 560 201 A1 discloses a method and an apparatus of entropy coding using Context-Based Adaptive Binary Arithmetic Coder (CABAC), wherein context-adaptive arithmetic coding is applied to a current bin of binary data of a current coding symbol according to a current state of the arithmetic coder for a binary value of the current bin and a current range associated with the current probability. US 2016/353110 A1 discloses a method and techniques for performing context-based entropy coding of video data with different window sizes. The arithmetic coding is known as one of the efficient data compressing methods, and is widely used in coding standards, including JBIG, JPEG2000, H.264/AVC, and High-Efficiency Video Coding (HEVC). In H.264/AVC and HEVC Test Model Version 16.0 (HM-16.0), context-based adaptive binary arithmetic coding (CABAC) is adopted as the entropy coding tool in the video coding system. As shown in Fig. 1(a), a CABAC encoder consists of three parts: binarization unit 110, context modelling unit 120, and binary arithmetic encoding unit 130. The CABAC encoding process comprises the binarization step, the context modelling step and the binary arithmetic encoding step. In the binarization step, each syntax element is uniquely mapped into a binary string (bin or bins). In the context modelling step, a probability model is selected for each bin. The corresponding probability model may depend on previously encoded syntax elements, bin indexes, and side information. After the binarization and the context model assignment, a bin value along with its associated model is transmitted to the binary arithmetic encoding unit 130 for generating the bitstream. On the other hand, a CABAC decoder receives the bitstream, and performs a CABAC decoding process corresponding to the foregoing CABAC encoding process on the bitstream so as to derive the values of the syntax elements. As shown in Fig. 1(b), a CABAC decoder consists of three parts: de-binarization unit 150, context modelling unit 160, and binary arithmetic decoding unit 140. The CABAC decoding process comprises the binary arithmetic decoding step, the de-binarization step and the context modelling step. In de-binarization step and context modelling step, according to the target decoding syntax element, a probability model is selected for each bin. The corresponding probability model may depend on previously decoded syntax elements, bin indexes, and side information. According to the probability model, a bin value is parsed by the binary arithmetic decoding unit 140. A syntax element is decoded by the de-binarization unit 150. Binary arithmetic encoding in 130 is a recursive interval-subdividing procedure. The output bitstream is the pointer to the final probability of coding interval. The probability of coding interval, T is specified by range and the lower bound of coding interval (designated as "low" in the following discussion). The range is the possible scope of the coding interval. Depending on whether the current symbol is the most probable symbol (MPS) or the least probable symbol (LPS), the next coding interval is updated as one of the two sub-intervals accordingly, as shown in eq. (1) and eq. (2). rangen+1=rangen−rangeLPSn,ifMPSrangeLPSn,ifLPS lown+1=lown,ifMPSlown+rangen−rangeLPSn,ifLPS, where rangeLPS is the estimated range when LPS is coded. Fig. 2 illustrates the concept of the binary arithmetic coding. Initially, the probability range (i.e., range0) is 1 and the low boundary (i.e., low0) is 0 as indicated by probability scale 210. If the first symbol is a MPS symbol, a pointer in the lower part of the probability scale 210 may be used to signal the event of an MPS symbol. The range1 is used as the probability scale 220 for processing the next symbol. Again, the probability scale 220 is divided into two parts for MPS and LPS respectively. If the second symbol is an LPS symbol, the rangeLPS1 is selected as the probability scale 230 for the next symbol. Every time when a new symbol is coded, the corresponding range becomes smaller. When a range becomes too small, the range can be re-normalized to form a probability scale 240 with larger range. In modern arithmetic coding, the probability update is often done according to a model. For example, a method is described by Marpe, et al., in a technical publication (" Context-Based Adaptive Binary Arithmetic Coding in the H.264 / AVC Video Compression Standard" , IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, No. 7, pp. 620-636, July 2003), where the following formula is used: pnew=1−α⋅y+α⋅pold. In the above equation, y is equal to"zero" if current symbol is a most probab