Sparse matrix representation using a boundary of non-zero coefficients

Patent metadata

Field	Value
Publication number	US-11388439-B2
Application number	US-201916726408-A
Country	US
Kind code	B2
Filing date	Dec 24, 2019
Priority date	Oct 21, 2019
Publication date	Jul 12, 2022
Grant date	Jul 12, 2022

Abstract

A sparse matrix representation of image or video data for encoding or decoding uses a boundary of non-zero coefficients within the image or video data. A bounding box encloses each non-zero coefficient within an image or video block. The coefficients enclosed within the bounding box are encoded to a bitstream along with dimensional information usable to identify the bounding box within the image or video block during decoding. Coefficients not enclosed within the bounding box are not specifically encoded within the bitstream. The dimensional information represents one or more of a shape, size, or position within the image or video block of the bounding box. The bounding box may be identified according to a scan order used to process the coefficients within the image or video block. The bounding box may be rectangular or non-rectangular.

First claim

What is claimed is:

1. A method for encoding a current block of image or video data, the method comprising:
transforming data of the current block to produce transform coefficients;
quantizing the transform coefficients to produce quantized transform coefficients, wherein the quantized transform coefficients include non-zero value coefficients and zero value coefficients;
identifying, according to a first scan order, a first bounding box which encloses a first total number of coefficients, wherein the first total number of coefficients includes at least each of the non-zero value coefficients and a first number of the zero value coefficients;
identifying, according to a second scan order, a second bounding box which encloses a second total number of coefficients, wherein the second total number of coefficients also includes at least each of the non-zero value coefficients and a second number of the zero value coefficients;
determining that the first total number of coefficients is lower than the second total number of coefficients; and
responsive to determining that the first total number of coefficients is lower than the second total number of coefficients, encoding, to a bitstream, data representative of the first total number of coefficients and dimensional information of the bounding box, wherein the dimensional information is configured to signal the bounding box to a decoder.

2. The method of claim 1 , wherein the first bounding box is identified based on locations of the non-zero value coefficients within a two-dimensional matrix representation corresponding to the current block along the first scan order, wherein the second bounding box is identified based on locations of the non-zero value coefficients within the two-dimensional matrix representation along the second scan order, and wherein the first bounding box is smaller than the second bounding box.

3. The method of claim 2 , wherein a location of a first end of block position along the first bounding box is different from a location of a second end of block position along the second bounding box.

4. The method of claim 1 , further comprising:
encoding, to the bitstream, a syntax element configured to signal a use of the bounding box for encoding the current block to the decoder.

5. The method of claim 1 , wherein at least one of the first bounding box or the second bounding box has a non-rectangular shape.

6. A method for encoding a current block of image or video data, the method comprising:
transforming data of the current block to produce transform coefficients;
quantizing the transform coefficients to produce quantized transform coefficients, wherein the quantized transform coefficients include non-zero value coefficients and zero value coefficients;
iterating through the quantized transform coefficients according to a scan order to identify locations of the non-zero value coefficients within a two-dimensional matrix representation corresponding to the current block;
identifying, based on the locations of the non-zero value coefficients within the two-dimensional matrix representation, a bounding box which encloses a total number of coefficients including each of the non-zero value coefficients and a number of the zero value coefficients; and
encoding, to a bitstream, data representative of the total number of coefficients and of dimensional information of the bounding box.

7. The method of claim 6 , further comprising:
identifying groupings of the non-zero value coefficients within the two-dimensional matrix representation according to each of a plurality of candidate scan orders; and
identifying, as the scan order, a candidate scan order of the plurality of candidate scan orders used to identify a tightest grouping of the groupings.

8. The method of claim 7 , wherein a shape of the bounding box and a size of the bounding box are based on an arrangement of the tightest grouping of the groupings, wherein the dimensional information represents at least one of the shape of the bounding box or the size of the bounding box.

9. The method of claim 6 , wherein the bounding box has a non-rectangular shape.

10. The method of claim 6 , wherein the dimensional information of the bounding box is represented within the bitstream using one or more coded syntax element values.

11. A method for encoding a current block of image or video data, the method comprising:
transforming data of the current block to produce transform coefficients;
quantizing the transform coefficients to produce quantized transform coefficients, wherein the quantized transform coefficients are arranged in a two-dimensional matrix representation;
identifying a bounding box which encloses a first set of the quantized transform coefficients within the two-dimensional matrix representation, wherein the first set of the quantized transform coefficients includes each non-zero value coefficient of the quantized transform coefficients, wherein a second set of the quantized transform coefficients located outside of the bounding box within the two-dimensional matrix representation is limited to zero-value coefficients; and
encoding, to a bitstream, the first set of the quantized transform coefficients and dimensional information of the bounding box.

12. The method of claim 11 , wherein identifying the bounding box which encloses the first set of the quantized transform coefficients within the two-dimensional matrix representation comprises:
identifying the bounding box based on locations of non-zero value coefficients of the quantized transform coefficients, wherein the non-zero value coefficients are identified by iterating through the quantized transform coefficients according to a scan order.

13. The method of claim 12 , wherein the scan order is one of a plurality of candidate scan orders available for encoding the current block, wherein identifying the bounding box based on the locations of non-zero value coefficients of the quantized transform coefficients comprises:
identifying bounding box candidates for at least some candidate scan orders of the plurality of candidate scan orders;
determining that a first bounding box candidate identified for a first candidate scan order encloses a lower total number of coefficients than a second bounding box candidate identified for a second candidate scan order; and
responsive to the determining, identifying the first bounding box candidate as the bounding box.

14. The method of claim 12 , further comprising:
determining the dimensional information of the bounding box based on the locations of the non-zero value coefficients of the quantized transform coefficients.

15. The method of claim 14 , wherein the dimensional information represents one or more of a shape of the bounding box, a size of the bounding box, or a position of the bounding box within the two-dimensional matrix representation.

16. The method of claim 11 , wherein identifying the bounding box which encloses the first set of the quantized transform coefficients within the two-dimensional matrix representation comprises identifying, for use in encoding the current block, a reference bounding box used for encoding a previously encoded block,
wherein encoding the first set of the quantized transform coefficients and the dimensional information of the bounding box comprises encoding, to the bitstream, a differential indicating to use the reference bounding box for decoding the current block.

17. The method of claim 16 , wherein a buffer stores data representative of a plurality of reference bounding boxes, wherein identifying the

Assignees

• Google Llc

Inventors

• Massimino Pascal
• Rabaud Vincent

Classifications

• H04N19/129 Primary

  Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO] · CPC title

• H04N19/124 Primary

  Quantisation · CPC title

• H04N19/122

  Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type · CPC title

• H04N19/176

  the region being a block, e.g. a macroblock · CPC title

• H04N19/119

  Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks · CPC title