# US 10,484,695 B2 · Refined entropy coding for level maps

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,484,695 B2
- Document ID: US10484695B2
- Status: Granted
- Kind: B2
- Application number: 15/798,495
- Filed: 2017-10-31
- Published: 2019-04-25
- Granted: 2019-11-19
- Earliest claimed: 2017-10-23
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Joseph Young; Dake He
- Web page: https://patentgrep.com/patent/US10484695B2

## CPC

- H04N 19/18: the unit being a set of transform coefficients
- H04N 19/124: Quantisation
- H04N 19/129: Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
- H04N 19/13: Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
- H04N 19/147: according to rate distortion criteria (rate-distortion as a criterion for motion estimation H04N19/567)
- H04N 19/159: Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction
- H04N 19/176: the region being a block, e.g. a macroblock
- H04N 19/184: the unit being bits, e.g. of the compressed video stream
- H04N 19/45: {performing compensation of the inverse transform mismatch, e.g. Inverse Discrete Cosine Transform [IDCT] mismatch}
- H04N 19/60: using transform coding
- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- H04N 19/93: Run-length coding
- H04N 19/122: Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

Coding using level maps is disclosed. A method includes coding a scan position, in a forward scan direction, corresponding to an end-of-block and coding, in a backward scan direction, a non-zero map indicating positions of the transform block containing non-zero transform coefficients. The method also includes coding, in the backward scan direction, lower-range level maps, each lower-range level map having a respective map level up to a maximum map level, the lower-range level map indicating which absolute values of the non-zero transform coefficients are equal to the respective map level and which absolute values of the non-zero transform coefficients are greater than the respective map level. The method also includes coding a coefficient residual map, each residual coefficient of the coefficient residual map corresponding to a respective non-zero transform coefficient of the transform block having an absolute value exceeding the maximum map level.

## Claims

### Claim 1

A method for coding a transform block using level maps, comprising:
coding a scan position, in a forward scan direction, corresponding to an end-of-block;
coding, in a backward scan direction, a non-zero map indicating positions of the transform block containing non-zero transform coefficients, wherein the coding the non-zero map starts at a position that is based on the scan position;
coding, in the backward scan direction, lower-range level maps, each lower-range level map having a respective map level up to a maximum map level, the lower-range level map indicating which absolute values of the non-zero transform coefficients are equal to the respective map level and which absolute values of the non-zero transform coefficients are greater than the respective map level, wherein the coding, in the backward scan direction, the lower-range level maps comprising:
selecting, based on a transform class used to generate the transform block, a template for determining a coding context for coding a value of the non-zero map, wherein the transform class is one of a vertical transform class, a horizontal transform class, or a two-dimensional transform class; and
coding a coefficient residual map, each residual coefficient of the coefficient residual map corresponding to a respective non-zero transform coefficient of the transform block having an absolute value exceeding the maximum map level.

### Claim 2 (depends on 1)

The method of claim 1, wherein the template comprises scan positions of previously coded non-zero neighboring values of the value of the non-zero map.

### Claim 3 (depends on 2)

The method of claim 2, wherein the template consists of 7 positions.

### Claim 4 (depends on 1)

The method of claim 1, wherein coding the scan position corresponding to the end-of-block comprises:
coding an index of a scan positions group that includes the scan position; and
coding an offset within the scan positions group, the offset corresponding to a position of the scan position within the scan positions group.

### Claim 5 (depends on 4)

The method of claim 4, wherein the scan positions group includes a power of 2 number of scan positions.

### Claim 6 (depends on 5)

The method of claim 5, wherein the scan positions group includes 16 scan positions.

### Claim 7 (depends on 4)

The method of claim 4, wherein coding the offset within the scan positions group comprises:
coding the offset using literal mode.

### Claim 8 (depends on 4)

The method of claim 4, wherein the offset comprises prefix bits and suffix bits, and wherein coding the offset within the scan positions group comprises:
context-coding the prefix bits; and
coding the suffix bits using literal mode.

### Claim 9 (depends on 1)

The method of claim 1, wherein encoding the non-zero map further comprises:
determining a coding context for a value of the non-zero map, the coding context based on previously coded non-zero neighboring values, in the non-zero map, of the value.

### Claim 10

An apparatus for coding a transform block using level maps, the apparatus comprising:
a memory; and
a processor, wherein the memory includes instructions executable by the processor to:
code a scan position, in a first scan direction, corresponding to an end-of-block;
code, in a second scan direction that is different from the first scan direction, an up to whether a transform coefficient of the transform block is greater than a maximum map level of the level maps, wherein the coding starts at a position that is based on the scan position, wherein to code the up to whether the transform coefficient of the transform block is greater than the maximum map level of the level maps comprises to:
select, based on a transform class used to generate the transform block, a template for determining a coding context to code the up to whether the transform coefficient is greater than the maximum map level, wherein the transform class is one of a vertical transform class, a horizontal transform class, or a two-dimensional transform class; and
code a coefficient residual map, each residual coefficient of the coefficient residual map corresponding to a respective non-zero transform coefficient of the transform block having an absolute value exceeding the maximum map level.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein a same context is selected when the transform class is one of the vertical transform class or the horizontal transform class.

### Claim 12 (depends on 10)

The apparatus of claim 10, wherein to select, based on the transform class used to generate the transform block, the template for determining the coding context to code the up to whether the transform coefficient is greater than the maximum map level comprises to:
determine a context index by summing values corresponding to positions of the template, each value corresponding to a position of the template is determined by summing respective values of at least some of the level maps; and
upper-bound the context index by a predetermined number.

### Claim 13

A method for decoding a transform block using level maps, comprising:
decoding a scan position, in a first scan direction, corresponding to an end-of-block;
decoding, in a second scan direction that is different from the first scan direction, an up to whether a transform coefficient of the transform block is greater than a maximum map level of the level maps, wherein the decoding starts at a position that is based on the scan position, the decoding the up to whether the transform coefficient of the transform block is greater than the maximum map level of the level maps comprising:
selecting a template based on a transform class used for the transform block, wherein the transform class is at least one of a vertical transform class, a horizontal transform class, or a two-dimensional transform class;
selecting, using the template, a context to code the up to whether the transform coefficient is greater than the maximum map level, wherein selecting the context comprises:
determining a context index by summing values corresponding to positions of the template, each value corresponding to a position of the template is determined by summing respective values of at least some of the level maps; and
upper-bounding the context index by a predetermined number; and
decoding a coefficient residual map, each residual coefficient of the coefficient residual map corresponding to a respective non-zero transform coefficient of the transform block having an absolute value exceeding the maximum map level.

### Claim 14 (depends on 13)

The method of claim 13, wherein a same context is selected when the transform class is one of the vertical transform class or the horizontal transform class.