# US 10,873,765 B2 · Techniques for high efficiency entropy coding of video data

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

- Number: US 10,873,765 B2
- Document ID: US10873765B2
- Status: Granted
- Kind: B2
- Application number: 15/939,747
- Filed: 2018-03-29
- Published: 2019-10-03
- Granted: 2020-12-22
- Earliest claimed: 2018-03-29
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Ken Kengkuan Lin; Mitchell H. Oslick
- Web page: https://patentgrep.com/patent/US10873765B2

## CPC

- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- H04N 19/129: Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
- H04N 19/176: the region being a block, e.g. a macroblock
- H04N 19/18: the unit being a set of transform coefficients
- H04N 19/1883: {the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]}
- H04N 19/44: Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
- H04N 19/625: using discrete cosine transform [DCT]
- H04N 19/70: characterised by syntax aspects related to video coding, e.g. related to compression standards
- H04N 19/93: Run-length coding
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

Entropy coding/decoding techniques are disclosed in which data is coded alternately as a series of nonzero values and zero values until the transmitted data is consumed. Nonzero values may be coded first with transmission of data identifying a number of consecutive nonzero values that appear in scan order followed by transmission of the nonzero values themselves. Thereafter, if other data remains to be transmitted, data may be transmitted identifying a number of consecutive zero values that appear next in scan order followed by transmission of a next nonzero value encountered in scan order. By transmitting the nonzero values as a group, it is expected that the proposed entropy-coding process will achieve higher efficiency than competitive techniques.

## Claims

### Claim 1

A coding method, comprising:
transforming pixel blocks representing content of a source image into respective blocks of transform coefficients;
quantizing the transform coefficients of each pixel block;
entropy coding the quantized coefficients of the pixel blocks by, iteratively:
a. transmitting data identifying a number of consecutive nonzero values encountered along a scan direction among the pixel blocks followed by values of the consecutive nonzero values so identified, and
b. transmitting data identifying a number of consecutive zero values encountered along the scan direction.

### Claim 2 (depends on 1)

The method of claim 1, wherein step a precedes step b in a first iteration.

### Claim 3 (depends on 1)

The method of claim 1, further comprising an entropy decoding method, comprising, iteratively:
in a first portion of the method:
extracting, from the transmitted data, an identifier of a number of consecutive nonzero values,
extracting a value of each of the identified number of nonzero values, and
placing the extracted nonzero values in an output data sequence; and
in a second portion of the method:
extracting, from the transmitted data, an identifier of a number of consecutive zero values,
placing a zero value for each of the identified number of consecutive zero values in the output data sequence.

### Claim 4 (depends on 1)

The method of claim 1, wherein step b precedes step a in a first iteration.

### Claim 5 (depends on 1)

The method of claim 1, wherein, when there are additional nonzero values to transmit, the method advances from step b of a first iteration directly to step a of a second iteration.

### Claim 6 (depends on 1)

The method of claim 1, wherein, when there are additional nonzero values to transmit, the method comprises:
transmitting a next nonzero value encountered along the scan direction, and advancing to step a for a second iteration of the method.

### Claim 7 (depends on 1)

The method of claim 1, wherein the method terminates when an end of values encountered along the scan direction is reached.

### Claim 8 (depends on 1)

The method of claim 1, wherein the method terminates when a position along the scan direction is reached from which all remaining values are zero.

### Claim 9 (depends on 1)

The method of claim 1, wherein the scan direction among pixel blocks is a predetermined scan order.

### Claim 10 (depends on 1)

The method of claim 1, wherein the scan direction among pixel blocks proceeds across like-kind transform coefficients of the pixel blocks together, before proceeding to other transform coefficients.

### Claim 11 (depends on 3)

The method of claim 3, further comprising:
organizing the output data sequence into coded video data representing the pixel blocks, and
decoding the coded video data of each pixel block.

### Claim 12 (depends on 3)

The method of claim 3, wherein the first portion precedes the second portion in a first iteration of the method.

### Claim 13 (depends on 3)

The method of claim 3, wherein the second portion precedes the first portion in a first iteration of the method.

### Claim 14 (depends on 3)

The method of claim 3, wherein, following a first iteration of the method, when there are additional nonzero values present in the transmitted data, the method advances from second portion of a first iteration of the method directly to the first portion of a second iteration of the method.

### Claim 15 (depends on 3)

The method of claim 3, wherein, following a first iteration of the method, when there are additional nonzero values present in the transmitted data, the method comprises:
extracting, from the transmitted data, a next nonzero value,
placing the next nonzero value in the output data sequence, and
advancing to a first portion of another iteration of the method.

### Claim 16 (depends on 3)

The method of claim 3, wherein the method terminates when an end of the transmitted data is reached.

### Claim 17 (depends on 3)

The method of claim 3, wherein the method terminates when a position in the transmitted data is reached from which all remaining values are zero.

### Claim 18

A coder, comprising:
a transformer, having an input for pixel blocks representing content of a source image and an output for respective blocks of transform coefficients;
a quantizer, having an input for the blocks of transform coefficients and an output for respective quantized coefficients of the blocks of transform coefficients;
an entropy coder, having an input for the quantized coefficients, that alternates between nonzero value coding and zero value coding of values of the quantized coefficients encountered along a scan direction among the pixel blocks, in which:
during the nonzero value coding, the entropy coder outputs a first data item identifying a number of consecutive nonzero values followed by a data item for each of the nonzero values so identified, and
during the zero value coding, the entropy coder outputs another data item identifying a number of consecutive zero values.

### Claim 19 (depends on 18)

The coder of claim 18, further comprising:
a slice scan system having an input for the quantized coefficients and an output for the values of the quantized coefficients, assembled according to the scan direction among the pixel blocks.

### Claim 20 (depends on 19)

The coder of claim 19, further comprising:
a pixel block encoder, comprising the transformer and the quantizer, wherein the pixel block encoder has an input for prediction data for the respective pixel blocks.

### Claim 21 (depends on 19)

The coder of claim 19, further comprising a video decoder, comprising:
an entropy decoder having an input for the entropy coder output, the entropy decoder alternating between decoding of nonzero values and zero values in which:
during the nonzero value decoding and, responsive to the first data item in the entropy coder output identifying a number of consecutive nonzero values, the entropy decoder extracts a nonzero value of each of the identified number of consecutive nonzero values from the entropy coder output and places the extracted nonzero values into output data; and
during the zero value decoding and, responsive to the another data item in the entropy coder output identifying a number of consecutive zero values, the entropy decoder
places a zero value for each of the identified number of consecutive zero values into the output data;
a slice scan system having an input for the output data and an output for pixel block data arrays representing the output data; and
a pixel block decoder, having an input for the pixel block data arrays and an output for reconstructed pixel block data.

### Claim 22 (depends on 21)

The video decoder of claim 21, wherein the pixel block decoder has an input for prediction data for the respective pixel blocks.

### Claim 23 (depends on 21)

The coder of claim 21, further comprising, after the placing the identified number of consecutive zero values into the output data, the entropy decoder extracts another nonzero value from the entropy coder output and places it in the output data.

### Claim 24

A non-transitory computer readable medium having stored thereon coded video data generated according to a coding method, comprising:
transforming pixel blocks representing content of a source image into respective blocks of transform coefficients;
quantizing the transform coefficients of each pixel block;
entropy coding the quantized coefficients of the pixel blocks by, iteratively:
transmitting a data item identifying a number of consecutive nonzero values encountered along a scan direction among the pixel blocks followed by other data items each representing a value of each of the identified number of consecutive nonzero values, and
transmitting a data item identifying a number of consecutive zero values encountered along the scan direction.

### Claim 25 (depends on 24)

The medium of claim 24, further comprising, after transmitting the data item identifying a number of consecutive zero values, transmitting another data item representing a next nonzero value in the array.

### Claim 26

A coding method consisting essentially of:
transforming pixel blocks representing content of a source image into respective blocks of transform coefficients;
quantizing the transform coefficients of each pixel block;
entropy coding the quantized coefficients of the pixel blocks by,
iteratively:
a. transmitting data identifying a number of consecutive nonzero values encountered along a scan direction among the pixel blocks followed by a value of for each of the identified number of consecutive nonzero values, and
b. transmitting data identifying a number of consecutive zero values encountered along the scan direction.

### Claim 27 (depends on 26)

The method of claim 26, wherein the pixel blocks comprise respective luma component blocks.