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

1. A decoder comprising:

an extractor configured to extract, from a data stream representing video information, information related to a maximum hierarchy level, information related to a first maximum region size associated with prediction coding and a second maximum region size associated with transform coding;

a divider configured to:

divide an array of information samples representing a spatially sampled portion of the video information into a first set of root regions based on the first maximum region size,

sub-divide at least some of the first set of root regions into a first set of sub-regions using recursive multi-tree partitioning,

determine whether a size of at least one of the first set of sub-regions exceeds the second maximum region size;

responsive to a determination that the size of at least one of the first set of sub-regions does exceed the second maximum region size, divide at least one of the first set of sub-regions into a second set of root regions of the second maximum region size,

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

responsive to a determination that the respective root region of the second set of root regions is to be sub-divided, sub-divide the respective root region of the second set of root regions into a second set of sub-regions using recursive multi-tree partitioning based on the maximum hierarchy level; and

a reconstructor configured to reconstruct the array of information samples using prediction coding in accordance with the first set of sub-regions and transform coding in accordance with the second set of sub-regions.

2. The decoder according to claim 1 , wherein the reconstructor is configured to, for a sub-region of the first set of sub-regions:

compute a prediction signal based on an intra-prediction mode associated with the sub-region and reconstructed samples of a neighboring subset of the second set of sub-regions,

compute a reconstructed signal by adding the prediction signal to a reconstructed residual of a subset of the second set of sub-regions associated with the sub-region, and

store the reconstructed signal in a buffer for a next intra-prediction cycle.

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

4. The decoder according to claim 1 , wherein the extractor is configured to extract, from the data stream, first subdivision information, and the divider is configured to, in sub-dividing at least some of the first set of root regions,

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

based on a determination that each of the at least some of the first set of root regions is to be sub-divided, sub-divide that root 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 another maximum hierarchy level is reached.

5. The decoder according to claim 4 , 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.

6. The decoder according to claim 4 , wherein the first subdivision information includes a partition indication flag indicating whether any of the first set of root regions or the sub-regions at the first or higher-order hierarchy level is sub-divided.

7. The decoder according to claim 1 , wherein the extractor is configured to extract second subdivision information from the data stream, and the divider is configured to sub-divide the respective root region of the second set of root regions into the second set of sub-regions using recursive multi-tree partitioning further based on the second subdivision information.

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 4 , 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 information, 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 video information, information related to a maximum hierarchy level, information related to a first maximum region size associated with prediction coding and a second maximum region size associated with transform coding;

dividing an array of information samples representing a spatially sampled portion of the video information into a first set of root regions based on the first maximum region size;

sub-dividing at least some of the first set of root regions into a first set of sub-regions using recursive multi-tree partitioning;

determining whether a size of at least one of the first set of sub-regions exceeds the second maximum region size;

responsive to a determination that the size of at least one of the first set of sub-regions does exceed the second maximum region size, dividing at least one of the first set of sub-regions into a second set of root regions of the second maximum region size;

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

responsive to a determination that the respective root region of the second set of root regions is to be sub-divided, sub-dividing the respective root region of the second set of root regions into a second set of sub-regions using recursive multi-tree partitioning based on the maximum hierarchy level; and

reconstructing the array of information samples using prediction coding in accordance with the first set of sub-regions and transform coding in accordance with the second set of sub-regions.

13. The method according to claim 12 , wherein the reconstructing for a sub-region of the first set of sub-regions includes:

computing a prediction signal based on an intra-prediction mode associated with the sub-region and reconstructed samples of a neighboring subset of the second set of sub-regions,

computing a reconstructed signal by adding the prediction signal to a reconstructed residual of a subset of the second set of sub-regions associated with the sub-region, and

storing the reconstructed signal in a buffer for a next intra-prediction cycle.

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

15. The method according to claim 12 , further comprising extracting, from the data stream, first subdivision information, and the sub-dividing of at least some of the first set of root regions includes:

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

based on a determination that each of the at least some of the first set of root regions is to be sub-divided, sub-dividing that root region into sub-regions of a first hierarchy level 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 determining and sub-dividing is performed until no further division is to be performed according to the first subdivision information or another maximum hierarchy level is reached.

16. The method according to claim 15 , 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.

17. The method according to claim 15 , wherein the first subdivision information includes a partition indication flag indicating whether any of the first set of root regions or the sub-regions at the first or higher-order hierarchy level is sub-divided.

18. The method according to claim 12 , further comprising extracting second subdivision information from the data stream, wherein the sub-dividing the respective root region of the second set of root regions into the second set of sub-regions using recursive multi-tree partitioning is further based on the second subdivision information.

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 divider configured to:

divide an array of information samples representing a spatially sampled portion of video information into a first set of root regions based on a first maximum region size,

sub-divide at least some of the first set of root regions into a first set of sub-regions using recursive multi-tree partitioning,

determine whether a size of at least one of the first set of sub-regions exceeds a second maximum region size,

responsive to a determination that the size of at least one of the first set of sub-regions does exceed the second maximum region size, divide the at least one of the first set of sub-regions into a second set of root regions of the second maximum region size,

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

responsive to a determination that the respective root region of the second set of root regions is to be sub-divided, sub-divide the respective root region of the second set of root regions into a second set of sub-regions using recursive multi-tree partitioning based on a maximum hierarchy level; and

a data stream generator configured to:

encode the array of information samples using prediction coding in accordance with the first set of sub-regions and transform coding in accordance with the second set of sub-regions, and

insert into a data stream the encoded array of information samples, information related to the maximum hierarchy level, information related to the first maximum region size that is associated with the prediction coding and the second maximum region size that is associated with the transform coding.

23. The encoder according to claim 22 , wherein the data stream generator is configured to, for a sub-region of the first set of sub-regions:

compute a prediction signal based on an intra-prediction mode associated with the sub-region and reconstructed samples of a neighboring subset of the second set of sub-regions,

compute a difference signal by subtracting the prediction signal from an original signal of the sub-region to obtain a residual associated with the sub-region, and

store the difference signal in a buffer for a next intra-prediction cycle.

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

25. The encoder according to claim 22 , wherein the data stream generator is configured to insert into the data stream, first subdivision information, and the divider is configured to, in sub-dividing at least some of the first set of root regions,

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

based on a determination that each of the at least some of the first set of root regions is to be sub-divided, sub-divide that root 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 another maximum hierarchy level is reached.

26. The encoder according to claim 25 , 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.

27. The encoder according to claim 25 , wherein the first subdivision information includes a partition indication flag indicating whether any of the first set of root regions or the sub-regions at the first or higher-order hierarchy level is sub-divided.

28. The encoder according to claim 22 , wherein the data stream generator is configured to insert into the data stream second subdivision information, and the divider is configured to sub-divide the respective root region of the second set of root regions into the second set of sub-regions using recursive multi-tree partitioning further based on the second subdivision information.

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 information related to a maximum hierarchy level, information related to a first maximum region size associated with prediction coding and a second maximum region size associated with transform coding, the encoded information is coded into the data stream by operations including:

dividing an array of information samples representing a spatially sampled portion of video information into a first set of root regions based on the first maximum region size;

sub-dividing at least some of the first set of root regions into a first set of sub-regions using recursive multi-tree partitioning;

determining whether a size of at least one of the first set of sub-regions exceeds the second maximum region size;

responsive to a determination that the size of at least one of the first set of sub-regions does exceed the second maximum region size, dividing the at least one of the first set of sub-regions into a second set of root regions of the second maximum region size;

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

responsive to a determination that the respective root region of the second set of root regions is to be sub-divided, sub-dividing the respective root region of the second set of root regions into a second set of sub-regions using recursive multi-tree partitioning based on the maximum hierarchy level;

encoding the array of information samples using prediction coding in accordance with the first set of sub-regions and transform coding in accordance with the second set of sub-regions; and

inserting into a data stream the encoded array of information samples, and information related to the first and second maximum region sizes.

30. The computer-readable medium according to claim 29 , wherein the dividing of the array of information samples into the first set of root regions is performed such that the first set of root regions are rectangular blocks of a size determined by the first region size, the rectangular blocks are arranged in an order to gaplessly cover the array of information samples.