Methods and apparatuses for encoding and decoding a bytestream

Patent metadata

Field	Value
Publication number	US-11743479-B2
Application number	US-201816770226-A
Country	US
Kind code	B2
Filing date	Dec 6, 2018
Priority date	Dec 6, 2017
Publication date	Aug 29, 2023
Grant date	Aug 29, 2023

Abstract

There may be provided a method of decoding a received set of encoded data, the method comprising: receiving the encoded data set representing information that has been compressed; identifying from the encoded data set an ordered set of interspersed node symbols and data symbols; processing an ordered tree having a predetermined number of layers from the ordered set of identified node symbols and data symbols, wherein each node symbol comprises a set of indicator elements which indicate if a further symbol is expected later in the dataset for a branch in the tree, such that the ordered set of identified node symbols determine the tree and such that data symbols are arranged in data locations in the tree based on the indicator elements, and wherein each data symbol represents one or more values associated with the information that has been compressed; and, reconstructing the information that has been compressed using the values represented by the data symbols based on location of the data symbols in the ordered tree and using a predetermined value when the node symbols indicate that no data symbol is included in the data set corresponding to a location in the ordered tree.

First claim

The invention claimed is:

1. A method of decoding a received set of encoded data, the method comprising:
receiving the encoded data set representing information that has been compressed;
identifying from the encoded data set an ordered set of interspersed node symbols and data symbols;
retrieving a plurality of entropy decoding parameters, each entropy decoding parameter associated with a respective type of symbol;
applying an entropy decoding operation to the encoded data set to decode a symbol of a first type of symbol using parameters associated with the first type of symbol;
determining an expected type of symbol by analysing at least one previously decoded symbol of the first type of symbol to identify the type of symbol expected in the encoded data set;
updating the entropy decoding operation to use parameters associated with the expected type of symbol;
constructing an ordered tree having a root node and a predetermined number of layers from the ordered set of identified node symbols and data symbols,
wherein each node symbol comprises a set of indicator elements which indicate whether or not a further symbol is expected later in the dataset for a branch in the tree, such that the ordered set of identified node symbols determines the tree and such that, based on the indicator elements, the data symbols are arranged in data locations in the tree and no data symbols are arranged at data locations in the tree where an indicator element indicates no further symbol is expected later in the dataset for a respective branch in the tree,
wherein a data location is a terminal node of the tree, and
wherein each data symbol represents one or more values associated with the information that has been compressed; and
reconstructing the information that has been compressed using the values represented by the data symbols based on location of the data symbols in the ordered tree and using a predetermined value when the node symbols indicate that no data symbol is included in the data set corresponding to a particular location included in the ordered tree.

2. The method according to claim 1 , wherein the step of processing the ordered tree comprises:
traversing the tree according to the indicator elements of each node symbol and associating a node symbol or data symbol with each visited node based on a location in the tree of the visited node.

3. The method according to claim 2 , wherein a data symbol is associated to the tree if a visited node is in a final layer of the tree, no symbol is associated to the tree if a visited node is in a penultimate layer of the tree and node symbols are associated to the tree for other layers of the tree.

4. The method according to claim 2 , wherein the step of processing the ordered tree, comprises:
associating a first node symbol with a root node of the ordered tree; and,
traversing the tree according to the indicator elements of the first node symbol associated with the root node.

5. The method according to claim 2 , wherein traversing the tree is a depth-first pre-order traversal.

6. The method according to claim 1 , wherein the ordered tree is a quadtree and each node symbol comprises four indicator elements.

7. The method according to claim 1 , wherein reconstructing the information comprises:
mapping at least a portion of the ordered tree to an array such that each data symbol represents an element in the array.

8. The method according to claim 7 , wherein the mapping comprises inserting a predetermined value where no data symbol has been associated with a data location of the ordered tree.

9. The method according to claim 1 , wherein each node symbol is associated with a node which shall have a grandchild node in the tree.

10. The method according to claim 1 , wherein after arranging a data symbol at a data location in tree, the method further comprises
deleting the node symbols associated with that branch of tree.

11. An apparatus for decoding a received set of encoded data, comprising a processor configured to:
receive the encoded data set representing information that has been compressed;
identify from the encoded data set an ordered set of interspersed node symbols and data symbols;
retrieve a plurality of entropy decoding parameters, each entropy decoding parameter associated with a respective type of symbol;
apply an entropy decoding operation to the encoded data set to decode a symbol of a first type of symbol using parameters associated with the first type of symbol;
determine an expected type of symbol by analysing at least one previously decoded symbol of the first type of symbol to identify the type of symbol expected in the encoded data set;
update the entropy decoding operation to use parameters associated with the expected type of symbol;
construct an ordered tree having a root node and a predetermined number of layers from the ordered set of identified node symbols and data symbols,
wherein each node symbol comprises a set of indicator elements which indicate whether or not a further symbol is expected later in the dataset for a branch in the tree, such that the ordered set of identified node symbols determine the tree and such that, based on the indicator elements, data symbols are arranged in data locations in the tree and no data symbols are arranged at data locations in the tree where an indicator element indicates no further symbol is expected later in the dataset for a respective branch in the tree,
wherein a data location is a terminal node of the tree, and
wherein each data symbol represents one or more values associated with the information that has been compressed; and
reconstruct the information that has been compressed using the values represented by the data symbols based on location of the data symbols in the ordered tree and using a predetermined value when the node symbols indicate that no data symbol is included in the data set corresponding to a particular location included in the ordered tree.

12. A method of encoding an array of data representing information to be compressed, the method comprising:
constructing an ordered tree having a root node and a predetermined number of layers from the array of data, including arranging data symbols at data locations in the tree and not arranging data symbols at data locations included in the tree where sections of the array correspond to a predetermined value;
retrieving a plurality of entropy encoding parameters, each entropy encoding parameter associated with a respective type of symbol;
applying an entropy encoding operation to the data set to encode a symbol of a first type of symbol using parameters associated with the first type of symbol;
determining an expected type of symbol by analysing at least one previously encoded symbol of the first type of symbol to identify the type of symbol expected in the encoded data set;
updating the entropy encoding operation to use parameters associated with the expected type of symbol; and
generating an ordered set of interspersed node symbols and data symbols,
wherein each node symbol comprises a set of indicator elements which indicate whether or not a further symbol is expected later in the dataset for a branch in the tree, such that the ordered set of identified node symbols determines the tree and such that, based on the indicator elements, data symbols are arranged in data locations in the tree and no data symbols are arranged at data locations in the tree where an indicator element indicates no further symbol is expected later in the dataset for a respective branch in the tree,
wherein a data location is a terminal node of the tree, and
wherein each data symbol represents one or mo

Assignees

• V Nova Int Ltd

Inventors

• Makeev Ivan
• Keszthelyi Balázs
• 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/436 Primary

  using parallelised computational arrangements · CPC title

• H04N19/129

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