Joint Collaborative Team on Video Coding (JCT-VC)
`of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11
`5th Meeting: Geneva, CH, 16-23 March, 2011
`
`Document: JCTVC-E335
`
`Title:
`Status:
`Purpose:
`Author(s) or
`Contact(s):
`
`Source:
`
`Unified scans for the significance map and coefficient level coding in high coding efficiency
`Input Document to JCT-VC
`Proposal
`J. Sole, R. Joshi, M. Karczewicz
`5775 Morehouse Drive,
`San Diego, CA 92121-1714
`USA
`Qualcomm
`
`Tel: +1-858-845-2429
`Email: joels@qualcomm.com
`
`_____________________________
`
`Abstract
`This contribution proposes the use of the same underlying scan for significance map coding and
`coefficient level coding in high efficiency configuration. Two methods are proposed. In the first one, for
`coefficient level coding, the coefficients are scanned in a reverse order from last significant coefficient to
`the first coefficient (DC). The BD-rate for this approach for the high efficiency intra, random access, and
`low-delay configurations is 0.01℅, 0.10℅, and -0.03℅, respectively. The second method uses reverse
`scan order for both significance map and coefficient level coding after explicitly sending the position of
`the last coefficient as proposed in JCTVC-D262 and JCTVC-E338. The BD-rate for this case (for RDOQ
`off) is -0.27℅, -0.18℅, and -0.10℅ for the intra, random access, and low-delay configurations,
`respectively.
`1 Scanning process in the HM2.0 design
`Current high efficiency transform coefficient coding is implemented using CABAC. The scanning for the
`significance map is a forward zig-zag, horizontal or vertical pattern (depending on the prediction mode).
`Figure 1 depicts these scans.
`
`Figure 1-Zig-zag, horizontal and vertical scanning used for the significance map
`
`In contrast, for coding absolute transform coefficient levels, each block is mapped onto an ordered set of
`4×4 sub-blocks by using a forward zig-zag scan; while the transform coefficient levels inside a sub-block
`are processed in a backward zig-zag scan [1]. Figure 2 depicts this forward-backward zig-zag scan.
`Following the handling of 4×4 blocks in H.264/AVC CABAC, the context model set for each sub-block
`consists of two times five context models with five models each for the first bin and all remaining bins
`(up to and including the 14th bin) of the coeff_abs_level_minus_one syntax element, where the selection
`of context models is done as in the original CABAC. However, different sub-blocks may select different
`sets of context models, where the choice of the context model set for a sub-block depends on certain
`statistics of one or more already coded sub-blocks.
`
`Page: 1
`
`Date Saved: 2017-10-23
`
`SAMSUNG EXHIBIT 1006
`
`Page 1 of 16
`
`

`

`
`
`Figure 2-Scanning order for level coding
`
`
`
`The approach uses 60 contexts: 6 sets of 10 contexts distributed as follows. For a 4×4 block, 10 models
`are used (5 models for bin1 and 5 models for bins 2 to 14). There are 5 different sets of these 10 models
`for blocks larger than 4×4. The context set selection depends on the number of coefficients larger than 1
`in the previous 4×4 sub-block. Table 1 describes the contexts set and the model bins.
`
`
`Context Set 
`0 
`For block size 4x4 only 
`0‐3 Coefficients Larger Than 1 in 
`previous sub‐block  
`4‐7 LargerT1 in prev sub‐block  
`8‐11 LargerT1 in prev sub‐block  
`12‐15 LargerT1 in prev sub‐block  
`First 4x4 sub‐block (for blocks>4x4)        
`16 LargerT1 in prev sub‐block  
`
`5 
`
`1 
`
`2 
`3 
`4 
`
`Model bin 1 
`0  1 or more larger than 1 
`
`Model bin 2‐14 
`0 
`Initial ‐ no larger than one 
`
`1 
`
`Initial ‐ no trailing ones 
`
`2  1 trailing one 
`3  2 trailing ones 
`4  3 or more trailing ones 
`
`1 
`
`2 
`3 
`4 
`
`1 larger than one 
`
`2 larger than one 
`3 larger than one 
`4 or more larger than one 
`
` 
`
` 
`
` 
`
` 
`
`Table 1-Contexts Set and Context for bin 1 and bins 2 to 14 for the coefficient level
`
`2 Technical description
`As stated in [2], the coefficient scanning scheme is complex and it would be desirable to simplify the
`scanning processes as much as possible without impacting coding efficiency much. Part of the current
`complexity arises from the different scan patterns for significance map and coefficient level data and from
`the forward-backward scan for the coefficient level.
`Part 1 of this contribution unifies both scans, so that level data coding re-uses the zig-zag, horizontal or
`vertical scan of the significance map. Additionally, the same context sets are used for all block sizes.
`Part 2 of the contribution further unifies the scans, so that both significant map and coefficient level
`follow the same backward order, from the last significant coefficient to the first. In this way, all the scans
`in a TU follow exactly the same process: same scan (zig-zag, vertical or horizontal) in the same direction.
`2.1 Part 1: Unified scan pattern
`The proposed method applies the scan used for the significance map (zig-zag, vertical or horizontal) to
`the coefficient level coding. In this way, no additional scans have to be introduced. The scan is not
`
`
`
`Page: 2
`
`Date Saved: 2017-10-23
`
`Page 2 of 16
`
`

`

`forward-backward like the current one. Instead, it only follows a backward direction: from the last
`significant coefficient to the first (DC component).
`Current method in HM2.0 divides the coefficient level scan in sub-sets, where each sub-set is a 4×4 sub-
`block. The proposed algorithm keeps the sub-sets concept in a similar way as in [2]: each sub-set consists
`of 16 consecutive coefficients in the scanning order. Therefore, the coefficient level scan goes from the
`last significant coefficient to the first coefficient, being the scan conceptually partitioned in different sub-
`sets in order to derive the contexts to apply.
`The context derivation is harmonized, so that it doesn’t depend on the block size. The context set depends
`on whether the sub-set is sub-set 0 (defined as the sub-set with the lowest frequencies, i.e., containing the
`DC coefficient) or not, as shown in table 2.
`
`
`Sub‐set 0 
`
`Context Set 
`0 
`1 
`2 
`3 
`4 
`5 
`
`Other sub‐sets 
`
`0 LargerT1 in previous sub‐set 
`1 LargerT1 in previous sub‐set 
`>1 LargerT1 in previous sub‐set 
`0 LargerT1 in previous sub‐set 
`1 LargerT1 in previous sub‐set 
`>1 LargerT1 in previous sub‐set 
`
`Table 2- Proposed context set table. There is a dependency on the sub-set; whether it is sub-set 0 (lowest
`frequencies) or not.
`
`2.1.1 Results for Part 1
`The proposed method is implemented in HM2.0. Simulation results are presented for the full sequences
`with high efficiency common test conditions. Table 3 shows the results. The BD-rate is 0.01℅, 0. 10℅
`and -0.03℅ for intra, random access and low delay configurations, respectively. Detailed results are
`provided in the accompanying excel file.
`
`
`BD-rate
`
`Class A
`Class B
`Class C
`Class D
`Class E
`All
`Enc T[%]
`Dec T[%]
`
`Y
`0.17
`-0.02
`-0.08
`-0.11
`0.13
`0.01
`
`Intra HE
`U
`-0.02
`-0.02
`-0.03
`-0.10
`0.06
`-0.03
`99%
`99%
`
`V
`0.03
`0.00
`0.00
`-0.09
`0.10
`0.00
`
`Random access HE
`Y
`U
`V
`0.26
`-0.26
`-0.13
`0.05
`-0.13
`-0.06
`0.06
`-0.20
`-0.13
`0.04
`-0.47
`-0.27
`
`
`
`0.10
`-0.25
`-0.14
`100%
`98%
`Table 3. BD-rate for part 1 of the proposal
`
`Y
`
`0.09
`0.00
`-0.12
`-0.14
`-0.03
`
`Low delay HE
`U
`
`-0.60
`-0.47
`-1.53
`-1.43
`-0.96
`100%
`100%
`
`V
`
`-0.64
`-0.50
`-1.47
`-0.17
`-0.72
`
`2.2 Part 2: Unified reverse scan pattern
`Part 2 proposes that the scan of the coefficient levels is the same as the scan of the significance map and
`that both are done backwards (reverse scan of the ones in HM2.0). To that goal, first the algorithm
`described in [3] is applied. This algorithm indicates the position of the last significant coefficient within
`the block. Once that is done, the backward scan order can be applied to both significance map and
`coefficient level.
`
`
`
`Page: 3
`
`Date Saved: 2017-10-23
`
`Page 3 of 16
`
`

`

`The current contexts of the significant map are kept. For blocks larger than 8×8, the only change is that
`they are reversed, so that causality for the decoder is attained. Figure 3 shows the contexts.
`
`Context mask at
`position X.
`
`The context at X is
`based on the sum of
`the significance at B,
`E, F, H, I positions.
`
`I H
`E
`
`BX
`
`F
`
`Context mask in a 16x16 block
`
`
`
`Figure 3- Contexts for the reverse scan of the significance map
`
`2.2.1 Results for Part 2
`This method is also implemented in HM2.0. Simulation results are presented for the full sequences with
`high efficiency common test conditions and RDOQ off. Table 4 shows the results for this method. The
`luma BD-rate is -0.27℅, -0.18℅ and -0.10℅ for intra, random access and low delay configurations,
`respectively.
`
`BD-rate
`
`Class A
`Class B
`Class C
`Class D
`Class E
`All
`Enc T[%]
`Dec T[%]
`
`Y
`-0.60
`-0.22
`-0.10
`-0.21
`-0.20
`-0.27
`
`
`Random access HE
`Intra HE
`Y
`U
`V
`U
`-0.32
`0.47
`0.21
`-0.35
`-0.13
`-0.37
`-0.41
`0.03
`-0.04
`-0.73
`-0.61
`-0.18
`-0.25
`-0.58
`-0.89
`-0.19
`
`
`
`-0.12
`-0.18
`-0.31
`-0.42
`-0.15
`99%
`100%
`95%
`96%
`Table 4. BD-rate for part 2 of the proposal (RDOQ off)
`
`V
`-0.48
`-0.04
`-0.14
`-0.15
`-0.17
`-0.19
`
`Y
`
`0.07
`-0.09
`-0.34
`-0.07
`-0.10
`
`Low delay HE
`U
`
`-1.22
`-1.62
`-3.49
`-3.79
`-2.37
`100%
`96%
`
`V
`
`-1.71
`-1.72
`-3.05
`-3.25
`-2.33
`
`Table 5 shows the results of part 2 with RDOQ on. Note that the RDOQ function used does not take into
`account the reverse scanning pattern used in the coding process. The employed function, a variant of the
`one in HM2.0, computes the rate-distortion as a forward process.
`
`
`BD-rate
`
`Class A
`Class B
`Class C
`Class D
`Class E
`
`
`
`Intra HE
`U
`-0.25
`-0.08
`-0.11
`-0.14
`-0.61
`
`Y
`-0.10
`0.26
`0.21
`0.05
`0.43
`
`V
`-0.22
`-0.02
`-0.11
`0.00
`-0.66
`
`Random access HE
`Y
`U
`V
`-0.11
`-1.79
`-2.12
`0.26
`-0.57
`-0.42
`0.35
`-0.97
`-0.87
`0.13
`-1.60
`-1.21
`
`
`
`
`Page: 4
`
`Low delay HE
`U
`
`-1.78
`-2.08
`-4.39
`-3.91
`
`Y
`
`0.31
`0.32
`-0.10
`0.30
`
`V
`
`-2.17
`-2.24
`-4.32
`-2.19
`
`Date Saved: 2017-10-23
`
`Page 4 of 16
`
`

`

`0.16
`
`All
`Enc T[%]
`Dec T[%]
`
`-0.17
`
`0.16
`
`-1.19
`-0.21
`98%
`98%
`95%
`95%
`Table 5. BD-rate for part 2 of the proposal (RDOQ on)
`
`-1.11
`
`0.21
`
`-2.73
`
`-2.91
`99%
`97%
`
`3 Conclusions
`Two methods for unifying the scans in HM2.0 are proposed. The first one unifies the scan (zig-zag,
`vertical and horizontal) for the significance map and the coefficient level. The BD-rate of this unification
`for the high efficiency intra, random access, and low-delay configurations is 0.01℅, 0.10℅, and -0.03℅,
`respectively. The second method further unifies the direction of the scan: all the scans are backward. The
`BD-rate of this case (for RDOQ off) is -0.27℅, -0.18℅, and -0.10℅ for the intra, random access, and
`low-delay configurations, respectively.
`
` 4
`
` References
`
`
`[1] M. Winken et al, “Description of video coding technology proposal by Fraunhofer HHI”, JCTVC-
`A116, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC
`JTC1/SC29/WG11, 1st Meeting: Dresden (Germany), April, 2010.
`[2] T. Davies, “Unified Scan Processing for high efficiency coefficient coding”, JCTVC-D219, 4th JCT-
`VC Meeting, Daegu, KR, January 2011.
`[3] J. Sole, R. Joshi, I.-S. Chong, M. Coban, M. Karczewicz, “Parallel Context Processing for the
`significance map in high coding efficiency”, JCTVC-D262, 4th JCT-VC Meeting, Daegu, KR, January
`2011.
`
`5 Patent rights declaration(s)
`Qualcomm may have IPR relating to the technology described in this contribution and, conditioned
`on reciprocity, is prepared to grant licenses under reasonable and non-discriminatory terms as
`necessary for implementation of the resulting ITU-T Recommendation | ISO/IEC International
`Standard (per box 2 of the ITU-T/ITU-R/ISO/IEC patent statement and licensing declaration
`form).
`
`
`
`
`Page: 5
`
`Date Saved: 2017-10-23
`
`Page 5 of 16
`
`

`

`www.qualcomm.com/qct
`
`PAGE 1
`
`JCTVC-E335
`Unified scans for the significance map and
`coefficient level coding in high efficiency
`
`J. Sole, R. Joshi, M. Karczewicz
`
`Page 6 of 16
`
`

`

`Summary
` Unify scans for significance map and coefficient level
`
` Part 1
` Coefficient level scan uses the scan employed by the significance map
`– Reverse zig-zag, horizontal or vertical
` BD-rate 0.01% (AI) 0.10% (RA) -0.03% (LD)
`
` Part 2
` Both, significance map and coefficient level scan use reverse zig-zag,
`horizontal or vertical
` BD-rate (RDOQ off) -0.27% (AI) -0.18% (RA) -0.10% (LD)
`
`PAGE 2
`
`Page 7 of 16
`
`

`

`Background
` In HEVC, significance map coding uses 3 scans
` Forward zig-zag, vertical or horizontal
` Scan depends on prediction mode
`
`
`
` Coefficient level coding uses a different scan
` Forward zig-zag scan on 4×4 sub-blocks
` Backward zig-zag scan within each sub-block
` Problem: mismatch between scans
`
` No need for the additional coefficient level scan
`
`PAGE 3
`
`Page 8 of 16
`
`

`

`Part 1: Unified scan pattern
` Use the scan applied to the significance map for coefficient level coding
`
` Scan follows backward direction
` From the last significant coefficient to the first coefficient (DC)
`
` Context sets
` Set consists of 16 consecutive coefficients in scan order
`– Instead of 4x4 sub-blocks in HEVC
` Unification: same context derivation for all blocks sizes
`– Same number of contexts as in HEVC
`
`PAGE 4
`
`Page 9 of 16
`
`

`

`Part 1: BD-rate
`
`BD-rate
`
`Class A
`Class B
`Class C
`Class D
`Class E
`All
`Enc T[%]
`Dec T[%]
`
`Y
`0.17
`-0.02
`-0.08
`-0.11
`0.13
`0.01
`
`Intra HE
`U
`-0.02
`-0.02
`-0.03
`-0.10
`0.06
`-0.03
`99%
`99%
`
`V
`0.03
`0.00
`0.00
`-0.09
`0.10
`0.00
`
`Random access HE
`Y
`U
`V
`0.26
`-0.26
`-0.13
`0.05
`-0.13
`-0.06
`0.06
`-0.20
`-0.13
`0.04
`-0.47
`-0.27
`
`-0.14
`
`0.10
`
`-0.25
`100%
`98%
`
`Low delay HE
`U
`
`V
`
`Y
`
`0.09
`0.00
`-0.12
`-0.14
`-0.03
`
`-0.64
`-0.50
`-1.47
`-0.17
`-0.72
`
`-0.60
`-0.47
`-1.53
`-1.43
`-0.96
`100%
`100%
`
`* Thanks to DOCOMO USA Labs for the cross-check
`
`PAGE 5
`
`Page 10 of 16
`
`

`

`Part 2: Unified reverse scan pattern
` Use the scan applied to the significance map for coefficient level coding
` Both scans are backward
` From the last significant coefficient to the first coefficient (DC)
` Use of explicit signaling of the last coefficient (JCTVC-D262 / JCTVC-E338)
` Use the reverse of current contexts of the significance map for blocks
`larger than 8×8
`
`Context mask at
`position X.
`
`The context at X is
`based on the sum of
`the significance at B, E,
`F, H, I positions.
`
`H
`
`I
`
`E
`
`BX
`
`F
`
`PAGE 6
`
`Page 11 of 16
`
`

`

`Part 2: BD-rate
` RDOQ off
`
`BD-rate
`
`Class A
`
`Class B
`
`Class C
`
`Class D
`
`Class E
`
`All
`Enc T[%]
`Dec T[%]
`
`Y
`-0.60
`
`-0.22
`
`-0.10
`
`-0.21
`
`-0.20
`-0.27
`
`Intra HE
`U
`-0.35
`
`0.03
`
`-0.18
`
`-0.19
`
`-0.12
`-0.15
`100%
`96%
`
`V
`-0.48
`
`-0.04
`
`-0.14
`
`-0.15
`
`-0.17
`-0.19
`
`Random access HE
`Y
`U
`V
`-0.32
`0.47
`0.21
`
`Low delay HE
`U
`
`V
`
`Y
`
`-0.13
`
`-0.04
`
`-0.25
`
`-0.18
`
`-0.37
`
`-0.73
`
`-0.58
`
`-0.31
`99%
`95%
`
`-0.41
`
`-0.61
`
`-0.89
`
`-0.42
`
`0.07
`
`-0.09
`
`-0.34
`
`-0.07
`-0.10
`
`-1.71
`
`-1.72
`
`-3.05
`
`-3.25
`-2.33
`
`-1.22
`
`-1.62
`
`-3.49
`
`-3.79
`-2.37
`100%
`96%
`
`PAGE 7
`
`Page 12 of 16
`
`

`

`Part 2: BD-rate
` RDOQ on (RDOQ function not adapted to backward coding of TU)
`
`BD-rate
`
`Class A
`
`Class B
`
`Class C
`
`Class D
`
`Class E
`
`All
`
`Enc T[%]
`Dec T[%]
`
`Y
`-0.10
`0.26
`0.21
`0.05
`0.43
`0.16
`
`Intra HE
`U
`-0.25
`-0.08
`-0.11
`-0.14
`-0.61
`-0.21
`98%
`95%
`
`V
`-0.22
`-0.02
`-0.11
`0.00
`-0.66
`-0.17
`
`Random access HE
`Y
`U
`V
`-0.11
`-1.79
`-2.12
`0.26
`-0.57
`-0.42
`0.35
`-0.97
`-0.87
`0.13
`-1.60
`-1.21
`
`-1.11
`
`0.16
`
`-1.19
`98%
`95%
`
`Low delay HE
`U
`
`Y
`
`V
`
`0.31
`0.32
`-0.10
`0.30
`0.21
`
`-2.17
`-2.24
`-4.32
`-2.19
`-2.73
`
`-1.78
`-2.08
`-4.39
`-3.91
`-2.91
`99%
`97%
`
`PAGE 8
`
`Page 13 of 16
`
`

`

`Conclusions
`
` Proposed a unification of the scan pattern
` No penalty on performance
` Part 1: coefficient level scan same as significance map scan pattern
` Part 2: additional unification of scanning order (reverse)
`
`PAGE 9
`
`Page 14 of 16
`
`

`

`Thank you!
`
`Thank you!
`
`PAGE 10
`
`Page 15 of 16
`
`

`

`Context Sets
` Set consists of 16 consecutive coefficients in scan order
` Instead of 4x4 sub-blocks in HEVC
` Same contexts derivation for all blocks sizes
` Same number of contexts as in HEVC
`
`HEVC
`
`Proposal
`
`Context Set  (for 4x4 sub‐blocks)
`0
`For block size 4x4 only
`1
`0‐3 LargerT1 in previous sub‐block 
`2
`4‐7 LargerT1 in previous sub‐block 
`3
`8‐11 LargerT1 in previous sub‐block 
`4
`12‐15 LargerT1 in previous sub‐block 
`First 4x4 sub‐block (for blocks>4x4)        
`5
`16 LargerT1 in previous sub‐block 
`
`PAGE 11
`
`Sub‐set 0
`
`Context Set (for 16 consecutive coefficients)
`0
`0 LargerT1 in previous set
`1
`1 LargerT1 in previous set
`2
`>1 LargerT1 in previous set
`3
`0 LargerT1 in previous set
`4
`1 LargerT1 in previous set
`5
`>1 LargerT1 in previous set
`
`Other sub‐
`sets
`
`Page 16 of 16
`
`