Coding of a spatial sampling of a two-dimensional information signal using sub-division

Patent metadata

Field	Value
Publication number	US-9591335-B2
Application number	US-201615195067-A
Country	US
Kind code	B2
Filing date	Jun 28, 2016
Priority date	Apr 13, 2010
Publication date	Mar 7, 2017
Grant date	Mar 7, 2017

Abstract

Coding schemes for coding a spatially sampled information signal using sub-division and coding schemes for coding a sub-division or a multitree structure are described, wherein representative embodiments relate to picture and/or video coding applications.

First claim

What is claimed is:

1. A decoder comprising:
an extractor configured to extract a maximum region size and multi-tree subdivision information from a data stream representing an encoded video sequence;
a sub-divider configured to spatially divide an array of information samples representing a spatially sampled portion of the video sequence into tree root regions of the maximum region size and subdividing, in accordance with a multi-tree subdivision information, at least a subset of the tree root regions into smaller simply connected regions of different sizes by recursively multi-partitioning the subset of tree root regions; and
a reconstructor configured to reconstruct the array of samples from the data stream using the subdivision into the smaller simply connected regions;
wherein the reconstructor is configured to perform a prediction of the array of information samples at a granularity which depends on the subdivision into smaller simply connected regions and the extractor is configured to extract subordinate multi-tree subdivision information from the data stream, and wherein the decoder further comprises:
a further subdivider configured to subdivide, in accordance with the subordinate multi-tree-subdivision information, at least a subset of the smaller simply connected regions into even smaller simply connected regions by recursively multi-partitioning the subset of the smaller simply connected regions, wherein the reconstructor is configured to perform a retransformation from spectral to spatial domain in units of the even smaller simply connected regions, and
wherein the extractor is configured to extract a further maximum region size from the data stream, and wherein the further sub-divider is configured to divide each smaller simply connected region exceeding the further maximum region size into tree root sub-regions of the further maximum region size and subdivide, in accordance with the subordinate multi-tree-subdivision information, at least the subset of the tree root sub-regions into the even smaller simply connected regions,
wherein the further sub-divider is configured to, in subdividing the subset of smaller simply connected regions,
check, for each smaller simply connected region, as to whether the respective smaller simply connected region exceeds the further maximum region size, and, if the respective smaller simply connected region does exceed the further maximum region size, divide the respective smaller simply connected region into tree root sub-regions of the further maximum region size;
for each tree root sub-region,
check the subordinate multi-tree-subdivision information as to whether the respective tree root sub-region is to be partitioned, and
if the respective tree root sub-region is to be partitioned,
partition the respective tree root sub-region into sub-sub-regions, and
recursively repeat the check and partitioning for the sub-sub regions until no further partition is to be performed according to the subordinate multi-tree-subdivision information or a further maximum hierarchy level is reached, and
wherein for smaller simply connected region not exceeding the further maximum region size, the division into tree root sub-regions is skipped.

2. The decoder according to claim 1 , wherein the reconstructor is configured to, for a smaller simply connected region, compute, for each even smaller simply connected region of the smaller simply connected region, using a decoding order, a prediction signal p using an intra-prediction mode of the smaller simply connected region and reconstructed samples of neighboring even smaller simply connected regions out of a buffer and compute a reconstructed signal r by adding the prediction signal p to a reconstructed residual of the even smaller simply connected region with storing the reconstructed signal r in the buffer for a next intra-prediction.

3. The decoder according to claim 1 , wherein the sub-divider is configured to perform the division of the array of information samples into tree root regions such that the tree root regions are rectangular blocks of a size determined by the maximum region size, regularly arranged in order to gaplessly cover the array of information samples.

4. The decoder according to claim 1 , wherein the sub-divider is configured to, in subdividing the subset of tree root regions,
check, for each tree root region, the multi-tree-subdivision information as to whether the respective tree root region is to be partitioned, and
if the respective tree root region is to be partitioned,
partition the respective tree root region into regions of a first hierarchy level according to a partition rule associated with the first hierarchy level, and
recursively repeat the check and partitioning for the regions of the first hierarchy level in order to obtain regions of higher-order hierarchy levels using partition rules associated therewith,
with stopping the recursive repetition when no further partitioning is to be performed according to the multi-tree subdivision information, or a maximum hierarchy level is reached,
wherein regions of the subset of tree root regions not further partitioned in accordance with the multi-tree-subdivision information, represent the smaller simply connected regions and the leaf regions of the multi-tree subdivision, respectively.

5. The decoder according to claim 4 , wherein the extractor is configured to extract also the maximum hierarchy level from the data stream.

6. The decoder according to claim 4 , wherein the sub-divider is configured to, in accordance with the partition rules associated with the first and higher-order hierarchy levels, perform a partition into sub-regions of equal size, the number sub-regions thus obtained being common to all hierarchy levels.

7. The decoder according to claim 4 , wherein the extractor is configured to extract syntax elements associated with the leaf regions of the subset of tree root regions in a depth-first traversal order from the data stream.

8. The decoder according to claim 4 , wherein the multi-tree subdivision information has a partition indication flag associated with each tree root region and region of the first and higher-order hierarchy levels not belonging to the regions of the maximum hierarchy level, respectively, the partition indication flags indicating as to whether the associated tree root region and region of the first and higher-order hierarchy level, respectively, is partitioned.

9. The decoder according to claim 1 , further comprising:
a merger configured to combine, depending on a first subset of syntax elements of the data stream, disjoint from a second subset of syntax elements of the data stream forming the multi-tree subdivision information, spatially neighboring ones of the smaller simply connected regions to obtain an intermediate subdivision of the array of information samples, wherein the reconstructor is configured to reconstruct the array of information samples using the intermediate subdivision.

10. The decoder according to claim 9 , wherein the array of information samples is a simply connected portion out of an overall array of information samples, the decoder comprising:
a predictor configured to predict the array of information samples from the data stream, wherein the reconstructor is configured to perform a retransformation from spectral to spatial domain in units of the even smaller simply connected regions to obtain a residual for the array of information samples, and to combine the residual and the prediction of the array of information samples to reconstruct the array of information samples.

11. A decoding method comprising:
extracting a maximum region size and multi-tree subdivision info

Assignees

• Ge Video Compression Llc

Inventors

• Kirchhoffer Heiner
• Winken Martin
• Helle Philipp
• Marpe Detlev
• Schwarz Heiko
• Wiegand Thomas

Classifications

• H04N19/53

  Multi-resolution motion estimation; Hierarchical motion estimation · CPC title

• H04N19/52 Primary

  by predictive encoding · CPC title

• H04N19/46

  Embedding additional information in the video signal during the compression process (H04N19/517, H04N19/68, H04N19/70 take precedence) · CPC title

• H04N19/61

  in combination with predictive coding · CPC title

• H04N19/17

  the unit being an image region, e.g. an object · CPC title