Hierarchical data structure

Patent metadata

Field	Value
Publication number	US-12526440-B2
Application number	US-202318179154-A
Country	US
Kind code	B2
Filing date	Mar 6, 2023
Priority date	Dec 6, 2017
Publication date	Jan 13, 2026
Grant date	Jan 13, 2026

Abstract

A method of decoding a steam 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 for operating on a signal to facilitate sparse encoding of the signal by defining a data structure that identifies non-zero and zero elements in the signal so that only the non-zero elements are subsequently encoded, the method comprising:
obtaining a dataset to be encoded, said dataset being indicative of one or more properties of a signal; mapping the dataset into a data structure, wherein the data structure is structured to identify non-zero elements and zero element in the dataset, and wherein said mapping comprises:
subdividing the dataset into a plurality of tiles, each tile in the plurality of tiles defining a corresponding block of elements in said dataset;
subdividing each tile in the plurality of tiles into a corresponding plurality of sub-blocks;
defining, for each sub-block included in the plurality of sub-blocks, a corresponding node, such that a plurality of nodes is defined;
assigning a corresponding value to each node in the plurality of nodes, said corresponding value indicating whether the sub-block corresponding to said each node includes data above, equal, or below a threshold value, such that a plurality of values are assigned; and
mapping the plurality of values into a first level of the data structure; and
while encoding the dataset, using the data structure to identify the non-zero elements and encoding only the non-zero elements identified via the data structure.

2 . The method of claim 1 , wherein the dataset comprises residual data.

3 . The method of claim 1 , wherein the method comprises mapping the first level of the data structure in a sparsified manner.

4 . The method of claim 1 , wherein the node comprises four sub-blocks.

5 . The method of claim 1 , wherein the mapping the first level of the data structure is as a sparsified quadtree.

6 . The method of claim 1 , wherein the method further comprises defining further levels of the data structure by:
grouping a plurality of nodes to define a plurality of parent nodes; assigning a value to each of the parent node, the value indicating whether said parent node contains any data above, equal or below, the threshold value; and mapping the assigned values into a further level of the data structure.

7 . The method of claim 1 , wherein encoding the dataset is performed in a sequential manner.

8 . The method of claim 7 , wherein the sequential manner includes implementing an encoding sequence is in having a traverse z shape.

9 . An encoder that operates on a signal to facilitate sparse encoding of the signal by defining a data structure that identifies non-zero and zero elements in the signal so that only the non-zero elements are subsequently encoded, the encoder comprising:
one or more processors; and one or more non-transitory computer readable storage media that stores instructions that are executable by the one or more processors to cause the encoder to:
obtain a dataset to be encoded, said dataset being indicative of one or more properties of a signal;
map the dataset into a data structure, wherein the data structure is structured to identify non-zero elements and zero elements in the dataset, and wherein the mapping comprises:
subdividing the dataset into a plurality of tiles, each tile in the plurality of tiles defining a corresponding block of elements in said dataset;
subdividing each tile in the plurality of tiles into a corresponding plurality of sub-blocks;
defining, for each sub-block included in the plurality of sub-blocks, a corresponding node, such that a plurality of nodes is defined;
assigning a corresponding value to each node in the plurality of nodes, said corresponding value indicating whether the sub-block corresponding to said each node includes data above, equal, or below a threshold value, such that a plurality of values are assigned; and
mapping the plurality of values into a first level of the data structure; and

while encoding the dataset, use the data structure to identify the non-zero elements and encode only the non-zero elements identified via the data structure.

10 . The encoder of claim 9 , wherein the dataset comprises residual data.

11 . The encoder of claim 9 , wherein the encoder maps the first level of the data structure in a sparsified manner.

12 . The encoder of claim 9 , wherein at least one node comprises four sub-blocks.

13 . The encoder of claim 9 , wherein the encoder maps the first level of the data structure as a sparsified quadtree.

14 . The encoder of claim 9 , wherein the encoder defines further levels of the data structure by:
grouping a plurality of nodes to define a plurality of parent nodes; assigning a value to each of the parent node, the value indicating whether said parent node contains any data above, equal or below, the threshold value; and mapping the assigned values into a further level of the data structure.

15 . The encoder of claim 9 , wherein the encoder performs the encoding in a sequential manner.

16 . The encoder of claim 15 , wherein the sequential manner includes implementing an encoding sequence having a traverse z shape.

17 . A non-transitory computer readable storage medium that stores thereon computer executable instructions that, when executed by a processor, cause an encoder to perform the following:
obtain a dataset to be encoded, said dataset being indicative of one or more properties of a signal; map the dataset into a data structure, wherein the data structure is structured to identify non-zero elements and zero elements in the dataset, and wherein the comprises:
subdividing the dataset into a plurality of tiles, each tile in the plurality of tiles defining a corresponding block of elements in said dataset;
subdividing each tile in the plurality of tiles into a corresponding plurality of sub-blocks;
defining, for each sub-block in the plurality of sub-blocks, a corresponding node, such that a plurality of nodes is defined;
assigning a corresponding value to each node in the plurality of nodes, said corresponding value indicating whether the sub-block corresponding to said each node includes data above, equal, or below a threshold value, such that a plurality of values are assigned; and
mapping the plurality of values into a first level of the data structure; and
while encoding the dataset, use the data structure to identify the non-zero elements and encode only the non-zero elements identified via the data structure.

Assignees

• V Nova Int Ltd

Inventors

• Makeev Ivan
• Keszthelyi Balázs
• Poularakis Stergios
• Sanna Michele
• Ettinger Robert

Classifications

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• H04N19/182

  the unit being a pixel · CPC title

• H04N19/44

  Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder · CPC title

• H04N19/129

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

• H04N19/96

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