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

• US 10,721,495 B2
• Filed: 09/10/2019
• Issued: 07/21/2020
• Est. Priority Date: 04/13/2010
• Status: Active Grant

• Current Assignee: GE Video Compression, LLC (General Electric Company)
• Original Assignee: GE Video Compression, LLC (General Electric Company)
• Inventors: Kirchhoffer, Heiner, Winken, Martin, Helle, Philipp, Marpe, Detlev, Schwarz, Heiko, Wiegand, Thomas
• Primary Examiner(s): Retallick, Kaitlin A
• Application Number:
  US16/566,063
• Publication Number:
  US 20200007897A1
• Time in Patent Office: 315 Days
• Field of Search: None
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/52 by predictive encoding
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

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.

Claims

1. A decoder comprising:

an extractor configured to;

extract, from a data stream representing a video, first subdivision flags associated with prediction coding and second subdivision flags associated with transform coding, wherein each of the first subdivision flags is associated with one of a first set of regions or one of a first set of sub-regions thereof in a multi-tree structure associated with an array of information samples representing a spatially sampled portion of the video, and each of the second subdivision flags is associated with one of a second set of regions or one of a second set of sub-regions thereof in the multi-tree structure,

wherein the first sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the first subdivision flags, and the second sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the second subdivision flags,

entropy decode each of the first subdivision flags using a first probability estimation context, which is determined based on a hierarchy level of a first region in the first set of regions or a sub-region in the first set of sub-regions associated with the respective first subdivision flag, and

entropy decode each of the second subdivision flags using a second probability estimation context, which is determined based on a size of a region in the second set of regions or a sub-region in the second set of sub-regions associated with the respective second subdivision flag; and

a reconstructor configured to reconstruct the array of information samples using prediction coding for the first sets of regions and sub-regions and transform coding for the second sets of regions and sub-regions.

2. The decoder according to claim 1, wherein the first probability estimation context is the same for all first regions or sub-regions that are associated with the same hierarchy level and is different for first regions or sub-regions associated with a different hierarchy level.

3. The decoder according to claim 1, wherein the second probability estimation context is the same for all second regions or sub-regions that are of the same size and is different for second regions or sub-regions of a different size.

4. The decoder according to claim 1, further comprising a divider configured to:

divide the array of information samples into the first set of regions,

sub-divide at least some of the first set of regions into the first set of sub-regions using recursive multi-tree partitioning based on the first subdivision flags,

divide at least one of the first set of sub-regions into the second set of regions,

determine, for each of the second set of regions, whether the respective region of the second set of regions is to be sub-divided, and

responsive to a determination that the respective region of the second set of regions is to be sub-divided, sub-divide the respective region of the second set of regions into the second set of sub-regions using recursive multi-tree partitioning based on the second subdivision flags.

5. The decoder according to claim 4, wherein the divider is configured to perform the division of the array of information samples into the first set of regions such that the first set of regions are rectangular blocks of a size determined by a first maximum region size, wherein the rectangular blocks are arranged in an order to gaplessly cover the array of information samples.

6. The decoder according to claim 4, wherein the divider is configured to, in sub-dividing at least some of the first set of regions,

determine whether a respective first subdivision flag indicates that each of the at least some of the first set of regions is to be sub-divided,

based on a determination that each of the at least some of the first set of regions is to be sub-divided, sub-divide that region into sub-regions of a first hierarchy level within the multi-tree structure according to a partition rule associated with the first hierarchy level, and

recursively repeat the determination and sub-division for the sub-regions of the first hierarchy level in order to obtain regions of higher-order hierarchy levels using respective partition rules associated therewith,

wherein the determination and sub-division is performed until no further division is to be performed according to the first subdivision flags or a maximum hierarchy level is reached.

7. The decoder according to claim 6, wherein the divider is configured to, in accordance with the partition rules associated with the first and higher-order hierarchy levels, sub-divide into sub-regions of equal size, such that there are an equal number of sub-regions at each hierarchy level.

8. The decoder according to claim 1, wherein the extractor is configured to extract syntax elements associated with the first or second set of sub-regions from the data stream in a depth-first traversal order.

9. The decoder according to claim 1, further comprising:

a merger configured to combine, based on a first subset of syntax elements of the data stream, disjoint from a second subset of syntax elements of the data stream including the first subdivision flags, spatially neighboring ones of the first set of sub-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 1, further comprising:

a predictor configured to predict the array of information samples from the data stream,

wherein the reconstructor is configured to perform a spectral-to-spatial domain transform coding to obtain a residual for the array of information samples, and combine the residual and the prediction of the array of information samples to reconstruct the array of information samples.

11. The decoder according to claim 1, wherein the recursive multi-tree partitioning includes a quadtree partitioning technique.

12. A method comprising:

extracting, from a data stream representing a video, first subdivision flags associated with prediction coding and second subdivision flags associated with transform coding, wherein each of the first subdivision flags is associated with one of a first set of regions or one of a first set of sub-regions thereof in a multi-tree structure associated with an array of information samples representing a spatially sampled portion of the video, and each of the second subdivision flags is associated with one of a second set of regions or one of a second set of sub-regions thereof in the multi-tree structure,

wherein the first sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the first subdivision flags, and the second sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the second subdivision flags;

entropy decoding each of the first subdivision flags using a first probability estimation context, which is determined based on a hierarchy level of a first region in the first set of regions or a sub-region in the first set of sub-regions associated with the respective first subdivision flag;

entropy decoding each of the second subdivision flags using a second probability estimation context, which is determined based on a size of a region in the second set of regions or a sub-region in the second set of sub-regions associated with the respective second subdivision flag; and

reconstructing the array of information samples using prediction coding for the first sets of regions and sub-regions and transform coding for the second sets of regions and sub-regions.

13. The method according to claim 12, further comprising:

dividing the array of information samples into the first set of regions;

sub-dividing at least some of the first set of regions into the first set of sub-regions using recursive multi-tree partitioning based on the first subdivision flags;

dividing at least one of the first set of sub-regions into the second set of regions;

determining, for each of the second set of regions, whether the respective region of the second set of regions is to be sub-divided; and

responsive to a determination that the respective region of the second set of regions is to be sub-divided, sub-dividing the respective region of the second set of regions into the second set of sub-regions using recursive multi-tree partitioning based on the second subdivision flags.

14. The method according to claim 12, wherein the first probability estimation context is the same for all first regions or sub-regions that are associated with the same hierarchy level and is different for first regions or sub-regions associated with a different hierarchy level.

15. The method according to claim 12, wherein the second probability estimation context is the same for all second regions or sub-regions that are of the same size and is different for second regions or sub-regions of a different size.

16. The method according to claim 12, wherein the dividing the array of information samples into the first set of regions such that the first set of regions are rectangular blocks of a size determined by a first maximum region size, wherein the rectangular blocks are arranged in an order to gaplessly cover the array of information samples.

17. The method according to claim 13, wherein the sub-dividing of at least some of the first set of regions includes:

determining whether a respective first subdivision flag indicates that each of the at least some of the first set of regions is to be sub-divided,

based on a determination that each of the at least some of the first set of regions is to be sub-divided, sub-dividing that region into sub-regions of a first hierarchy level within the multi-tree structure according to a partition rule associated with the first hierarchy level, and

recursively repeating the determination and sub-division for the sub-regions of the first hierarchy level in order to obtain regions of higher-order hierarchy levels using respective partition rules associated therewith,

wherein the determination and sub-division is performed until no further division is to be performed according to the first subdivision flags or a maximum hierarchy level is reached.

18. The method according to claim 17, wherein, in accordance with the partition rules associated with the first and higher-order hierarchy levels, the sub-dividing is performed to obtain sub-regions of equal size, such that there are an equal number of sub-regions at each hierarchy level.

19. The method according to claim 12, further comprising extracting syntax elements associated with the first or second set of sub-regions from the data stream in a depth-first traversal order.

20. The method according to claim 12, further comprising:

predicting the array of information samples from the data stream,

wherein the reconstructing includes performing a spectral-to-spatial domain transform coding to obtain a residual for the array of information samples, and combining the residual and the prediction of the array of information samples to reconstruct the array of information samples.

21. The method according to claim 12, wherein the recursive multi-tree partitioning includes a quadtree partitioning technique.

22. An encoder comprising:

a data stream generator configured to;

encode an array of information samples representing a spatially sampled portion of the video using prediction coding for a first set of regions and a first set of sub-regions and using transform coding for a second set of regions and a second set of sub-regions,

wherein each of first subdivision flags used for the prediction coding is associated with one of the first set of regions or one of the first set of sub-regions thereof in a multi-tree structure associated with the array of information samples, and each of the second subdivision flags used for the transform coding is associated with one of the second set of regions or one of the second set of sub-regions thereof in the multi-tree structure,

wherein the first sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the first subdivision flags, and the second sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the second subdivision flags,

entropy encode each of the first subdivision flags using a first probability estimation context, which is determined based on a hierarchy level of a first region in the first set of regions or a sub-region in the first set of sub-regions associated with the respective first subdivision flag,

entropy encode each of the second subdivision flags using a second probability estimation context, which is determined based on a size of a region in the second set of regions or a sub-region in the second set of sub-regions associated with the respective second subdivision flag, and

insert into a data stream the encoded array of information samples, the entropy encoded first subdivision flags and the entropy encoded second subdivision flags.

23. The encoder according to claim 22, further comprising a divider configured to:

divide the array of information samples into the first set of regions,

sub-divide at least some of the first set of regions into the first set of sub-regions using recursive multi-tree partitioning based on the first subdivision flags,

divide at least one of the first set of sub-regions into the second set of regions,

determine, for each of the second set of regions, whether the respective region of the second set of regions is to be sub-divided, and

responsive to a determination that the respective region of the second set of regions is to be sub-divided, sub-divide the respective region of the second set of regions into the second set of sub-regions using recursive multi-tree partitioning based on the second subdivision flags.

24. The encoder according to claim 22, wherein the first probability estimation context is the same for all first regions or sub-regions that are associated with the same hierarchy level and is different for first regions or sub-regions associated with a different hierarchy level.

25. The encoder according to claim 22, wherein the second probability estimation context is the same for all second regions or sub-regions that are of the same size and is different for second regions or sub-regions of a different size.

26. The encoder according to claim 23, wherein the divider is configured to perform the division of the array of information samples into the first set of regions such that the first set of regions are rectangular blocks of a size determined by a first maximum region size, wherein the rectangular blocks are arranged in an order to gaplessly cover the array of information samples.

27. The encoder according to claim 23, wherein the divider is configured to, in sub-dividing at least some of the first set of regions,

determine whether a respective first subdivision flag indicates that each of the at least some of the first set of regions is to be sub-divided,

based on a determination that each of the at least some of the first set of regions is to be sub-divided, sub-divide that region into sub-regions of a first hierarchy level according to a partition rule associated with the first hierarchy level, and

recursively repeat the determination and sub-division for the sub-regions of the first hierarchy level in order to obtain regions of higher-order hierarchy levels using respective partition rules associated therewith,

wherein the determination and sub-division is performed until no further division is to be performed according to the first subdivision information or a maximum hierarchy level is reached.

28. The encoder according to claim 27, wherein the divider is configured to, in accordance with the partition rules associated with the first and higher-order hierarchy levels, sub-divide into sub-regions of equal size, such that there are an equal number of sub-regions at each hierarchy level.

30. The computer-readable medium according to claim 26, wherein the first probability estimation context is the same for all first regions or sub-regions that are associated with the same hierarchy level and is different for first regions or sub-regions associated with a different hierarchy level, and the second probability estimation context is the same for all second regions or sub-regions that are of the same size and is different for second regions or sub-regions of a different size.

29. A non-transitory computer-readable medium for storing data associated with a video, comprising:

a data stream stored in the non-transitory computer-readable medium, the data stream comprising encoded information associated with an array of information samples representing a spatially sampled portion of the video, the encoded information including first subdivision flags associated with prediction coding and second subdivision flags associated with transform coding, wherein each of the first subdivision flags is associated with one of a first set of regions or one of a first set of sub-regions thereof in a multi-tree structure associated with the array of information samples, and each of the second subdivision flags is associated with one of a second set of regions or one of a second set of sub-regions thereof in the multi-tree structure, wherein the first sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the first subdivision flags, and the second sets of regions and sub-regions are obtained using recursive multi-tree partitioning based on the second subdivision flags, the encoded information is coded into the data stream by operations including;

encoding the array of information samples using prediction coding for the first set of regions and the first set of sub-regions and using transform coding for the second set of regions and the second set of sub-regions,

entropy encoding each of the first subdivision flags using a first probability estimation context, which is determined based on a hierarchy level of a first region in the first set of regions or a sub-region in the first set of sub-regions associated with the respective first subdivision flag,

entropy encoding each of the second subdivision flags using a second probability estimation context, which is determined based on a size of a region in the second set of regions or a sub-region in the second set of sub-regions associated with the respective second subdivision flag, and

inserting into a data stream the encoded array of information samples, the entropy encoded first subdivision flags and the entropy encoded second subdivision flags.