Hierarchical data structure

Patent metadata

Field	Value
Publication number	US-11601662-B2
Application number	US-201816769794-A
Country	US
Kind code	B2
Filing date	Dec 6, 2018
Priority date	Dec 6, 2017
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

A method of decoding a stream of encoded data the method comprising, at a decoder: receiving an encoded dataset comprising multiple tiles; receiving a data structure, said data structure indicative of the amount of data required to encode a plurality of tiles; identifying a portion of the encoded dataset to be decoded by: identifying the tiles associated with the portion to be decoded; determining the location of data related to the tiles based on the amount of data required to encode said tiles; extracting the identified portion of the encoded dataset from the encoded dataset; and decoding said identified portion of the encoded data set.

First claim

The invention claimed is:

1. A method of decoding a stream of encoded data that has been selectively encoded in a manner such that some, but not all, values of a residual frame are encoded while other values of the residual frame are not encoded, the method comprising, at a decoder:
receiving an encoded dataset comprising multiple tiles, wherein the decoder is configured to decode sparse residual data included in the encoded dataset, and wherein the sparse residual data is generated by:
subdividing a residual frame of data into a plurality of tiles;
identifying, from among the plurality of tiles, a first block of residual data, a second block of residual data, and a third block of residual data, the first and second blocks having associated values above a threshold while the third block has an associated value equal to or below the threshold; and
selecting tiles comprising the first and second blocks to be encoded and to be included among said multiple tiles while refraining from encoding a tile comprising the third block such that a sparse encoding process is performed in which some, but not all, tiles in the plurality of tiles are encoded and such that the encoded dataset includes residual frame tiles whose values were encoded and does not include residual frame tiles whose values were not encoded;

receiving a data structure, said data structure indicative of an amount of data required to encode the tiles comprising the first and second blocks;
identifying a portion of the encoded dataset to be decoded, wherein said portion includes the tiles comprising the first and second blocks but does not include the tile comprising the third block, and wherein said identifying is performed by determining a location of data related to the tiles comprising the first and second blocks based on the amount of data required to encode the tiles comprising the first and second blocks;
extracting the identified portion of the encoded dataset from the encoded dataset; and
causing the identified portion, which includes the tiles comprising the first and second blocks, to be decoded such that the decoder decodes the first block and the second block and such that the decoder refrains from decoding the third block.

2. The method of claim 1 , wherein the encoded dataset is organized into tiers, with a first tier further comprising:
information indicative of a distribution of tile data included within the dataset.

3. The method of claim 2 , wherein the sparse residual data is generated by computing a difference between (i) a frame after that frame has been down sampled once and (ii) the frame after that frame has been down sampled twice and then subsequently up-sampled.

4. The method of claim 2 , wherein the tiers further comprise a second tier, the second tier further comprising information relating to the amount of the data required to encode the tiles comprising the first and second blocks.

5. The method of claim 4 further comprising determining a particular location of particular data for a particular tile to be decoded within the encoded dataset based on the information in the second tier.

6. The method of claim 5 , wherein the encoded dataset was encoded sequentially, and wherein the method further comprises determining the particular location of the particular data for the particular tile in the encoded dataset based on a summation of a particular amount of data required to encode any preceding tile.

7. The method of claim 6 further comprising decoding the encoded dataset at the determined particular location of the particular data for the particular tile.

8. The method of claim 1 further comprising identifying a second portion of the encoded dataset to be decoded, and decoding said second portion wherein the first portion is decoded by a first decoder and the second portion is decoded by a second, different decoder.

9. A method of decoding a stream of encoded data that has been selectively encoded in a manner such that some, but not all, values of a residual frame are encoded while other values of the residual frame are not encoded, the method comprising, at a decoder:
receiving an encoded dataset comprising multiple tiles, wherein the decoder is configured to decode sparse residual data included in the encoded dataset, and wherein the sparse residual data is generated by:
subdividing a residual frame of data into a plurality of tiles;
identifying, from among the plurality of tiles, a first block of residual data, a second block of residual data, and a third block of residual data, the first and second blocks having associated values above a threshold while the third block has an associated value equal to or below the threshold; and
selecting tiles comprising the first and second blocks to be encoded and to be included among said multiple tiles while refraining from encoding a tile comprising the third block such that a sparse encoding process is performed in which some, but not all, tiles in the plurality of tiles are encoded and such that the encoded dataset includes residual frame tiles whose values were encoded and does not include residual frame tiles whose values were not encoded;

receiving a data structure, said data structure indicative of a distribution of data above, below, or equal to, the threshold for the multiple tiles;
identifying the tiles comprising the first and second blocks, wherein the tiles comprising the first and second blocks have the associated values that are above, or equal to, the threshold, and wherein the tiles comprising the first and second blocks are encoded at a first level of quality and at a second level of quality, the second level of quality being a higher level of quality than the first level of quality; and
causing the tiles comprising the first and second blocks to be decoded such that the decoder decodes the first block and the second block and such that the decoder refrains from decoding the third block.

10. The method of claim 9 , wherein the encoded dataset is organized in tiers, with a first tier further comprising the data structure, which is indicative of the distribution of the data within the dataset, and a second tier comprising information relating to an amount of data required to encode the multiple tiles.

11. The method of claim 10 further comprising determining a location of particular data for a particular tile to be decoded within the encoded dataset based on the information in the second tier.

12. The method of claim 11 , wherein the multiple tiles are encoded sequentially, and wherein the method further comprises determining the location of the particular data for the particular tile in the encoded dataset based on a summation of a particular amount of data required to encode any preceding tile.

13. The method of claim 12 further comprising decoding the encoded dataset at the determined location of the particular data for the particular tile.

14. The method of claim 9 , wherein the received encoded dataset is encoded at a plurality of levels of quantisation, wherein the method comprises decoding a first tile of the encoded dataset at a first level of quantisation, and decoding a second tile, or area, at a second, different, level of quantisation.

15. A decoder for decoding an encoded stream of video data, where the encoded stream is selectively encoded in a manner such that some, but not all, values of a residual frame are encoded while other values of the residual frame are not encoded, the decoder configured to execute a method comprising:
receiving an encoded dataset comprising multiple tiles wherein the decoder is configured to decode sparse residual data incl

Assignees

• V Nova Int Ltd

Inventors

• Makeev Ivan
• Keszthelyi Balazs
• Poularakis Stergios
• Sanna Michele
• Ettinger Robert

Classifications

• H04N19/96

  Tree coding, e.g. quad-tree coding · CPC title

• H04N19/176

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

• H04N19/119 Primary

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

• H04N19/182

  the unit being a pixel · CPC title

• H04N19/167

  Position within a video image, e.g. region of interest [ROI] · CPC title