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

• US 10,771,822 B2
• Filed: 10/11/2012
• Issued: 09/08/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:
  US13/649,251
• Publication Number:
  US 20130039422A1
• Time in Patent Office: 2,889 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 for decoding a data stream corresponding to a video comprising a plurality of arrays of information samples, comprising:

an extractor configured for extracting, from the data stream, information related to first subdivision information, second subdivision information, and a maximum hierarchy level associated with each of the plurality of arrays of information samples, wherein the first subdivision information is associated with regions of the array of information samples in a spatial domain and includes a first maximum region size and multi-tree subdivision information, the second subdivision information is associated with regions of the array of information samples in a spectral domain and includes a second maximum region size and subordinate multi-tree subdivision information, and the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain;

a sub-divider configured for dividing each of the arrays of information samples in accordance with the first and second maximum region sizes, the multi-tree subdivision information and the subordinate multi-tree subdivision information, and the maximum hierarchy level for the array of information samples, by

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith; and

a reconstructor configured for reconstructing each of the arrays of information samples based on the first and second sets of sub-regions generated by the sub-divider.

2. The decoder of claim 1, wherein

each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

3. The decoder of claim 2, wherein when the corresponding multi-tree subdivision information indicates that the region is to be sub-partitioned, the extractor is further configured to extract a maximum hierarchy level associated with the region that specifies a maximum level based on which the region is to be hierarchically sub-partitioned.

4. The decoder of claim 3, wherein the region is sub-partitioned based on the multi-tree subdivision information and the maximum hierarchy level in accordance with one or more partition rules.

5. The decoder of claim 1, wherein the sub-divider divides an array of information samples in a depth-first traversal order.

6. The decoder of claim 1, wherein the extractor is further configured for extracting, for at least some of the first set of regions, inheritance information indicative of whether inheritance is to apply.

7. The decoder of claim 6, wherein when the inheritance information associated with a region in the first set of regions indicates that inheritance applies, at least one of the sub-regions, obtained by sub-partitioning the region, inherits at least one coding parameter from the region.

8. The decoder of claim 7, wherein the at least one of the first set of sub-regions is reconstructed based on the at least one coding parameter inherited from the region.

9. The decoder of claim 8, wherein the at least one of the sub-regions in the first set of sub-regions is reconstructed using the inherited at least one coding parameter.

10. The decoder of claim 8, wherein the at least one of the sub-regions in the first set of sub-regions is reconstructed using one or more enhanced coding parameters derived based on the inherited at least one coding parameter.

11. The decoder of claim 1, wherein the first set of sub-regions generated by the sub-divider corresponds to first order coding regions for prediction based coding.

12. The decoder of claim 11, wherein the second set of sub-regions generated by the sub-divider corresponds to second order coding regions for at least one of residual coding and filtering.

13. The decoder of claim 1, wherein the plurality of arrays of information samples is a video accompanied with depth information.

14. The decoder of claim 1, wherein a scaling factor for a spatial resolution of an array of chroma samples relative to an array of luma samples in the horizontal direction differs from a scaling factor for a spatial resolution of the array of chroma samples relative to the array of luma samples in the vertical direction.

15. The decoder of claim 1, wherein at least one of the plurality of arrays of information samples is one of samples arrays related to different color components and forming color planes of a picture, and the decoder is configured to decode the different color planes of the picture independently.

16. A method of decoding a data stream corresponding to a video comprising a plurality of arrays of information samples, comprising:

extracting, from the data stream, information related to first subdivision information, second subdivision information, and a maximum hierarchy level associated with each of the plurality of arrays of information samples, wherein the first subdivision information is associated with regions of the array of information samples in a spatial domain and includes a first maximum region size and multi-tree subdivision information, the second subdivision information is associated with regions of the array of information samples in a spectral domain and includes a second maximum region size and subordinate multi-tree subdivision information, and the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain;

dividing each of the arrays of information samples in accordance with the first and second maximum region sizes, the multi-tree subdivision information, the subordinate multi-tree subdivision information, and the maximum hierarchy level for the array of information samples, by

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith; and

reconstructing each of the arrays of information samples based on the first and second sets of sub-regions generated by said dividing.

17. The method of claim 16, wherein each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

18. The method of claim 16, wherein said dividing is performed in a depth-first traversal order.

19. The method of claim 16, further comprising extracting, from the data stream, for at least some of the first set of regions, inheritance information indicative of whether inheritance is to apply.

20. The method of claim 19, wherein when the inheritance information associated with a region in the first set of regions indicates that inheritance applies, at least one of the sub-regions, obtained by sub-partitioning the region, inherits at least one coding parameter from the region.

21. The method of claim 16, wherein the first set of sub-regions generated by said dividing corresponds to first order coding regions for prediction based coding.

22. The method of claim 21, wherein the second set of sub-regions generated by said dividing corresponds to second order coding regions for at least one of residual coding and filtering.

23. The method of claim 16, wherein the plurality of arrays of information samples is a video accompanied with depth information.

24. The method of claim 16, wherein a scaling factor for a spatial resolution of an array of chroma samples relative to an array of luma samples in the horizontal direction differs from a scaling factor for a spatial resolution of the array of chroma samples relative to the array of luma samples in the vertical direction.

25. The method of claim 16, wherein at least one of the plurality of arrays of information samples is one of samples arrays related to different color components and forming color planes of a picture, and wherein the different color planes of the picture are decoded independently.

26. A non-transitory machine readable digital storage medium having computer instructions stored thereon for decoding, wherein the computer instructions, when read by the machine, causing the machine to perform at least:

extracting, from a data stream, information related to first subdivision information, second subdivision information, and a maximum hierarchy level associated with each of a plurality of arrays of information samples, wherein the first subdivision information is associated with regions of the array of information samples in a spatial domain and includes a first maximum region size and multi-tree subdivision information, the second subdivision information is associated with regions of the array of information samples in a spectral domain and includes a second maximum region size and subordinate multi-tree subdivision information, and the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain;

dividing each of the arrays of information samples in accordance with the first and second maximum region sizes, the multi-tree subdivision information and the subordinate multi-tree subdivision information, and the maximum hierarchy level for the array of information samples, by

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith; and

reconstructing each of the arrays of information samples based on the first and second sets of sub-regions generated by said dividing.

27. The medium of claim 26, wherein each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

28. The medium of claim 26, wherein said dividing is performed in a depth-first traversal order.

29. The medium of claim 26, wherein the machine is further caused to perform extracting, from the data stream, for at least some of the first set of regions, inheritance information indicative of whether inheritance is to apply.

30. The medium of claim 29, wherein when the inheritance information associated with a region in the first set of regions indicates that inheritance applies, at least one of the sub-regions, obtained by sub-partitioning the region, inherits at least one coding parameter from the region.

31. The medium of claim 26, wherein the first set of regions generated by said dividing corresponds to first order coding regions for prediction based coding.

32. The medium of claim 31, wherein the second set of regions generated by said dividing corresponds to second order coding regions for at least one of residual coding and filtering.

33. An encoder for encoding a video comprising a plurality of arrays of information samples into a data stream, comprising:

a sub-divider configured for dividing each of the plurality of arrays of information samples by

determining, with respect to the array of information samples, a first maximum region size, multi-tree subdivision information, a second maximum region size, and subordinate multi-tree subdivision information for the array of information samples, wherein the first maximum region size and the multi-tree subdivision information are associated with regions of the array of information samples in a spatial domain, and the second maximum region size and the subordinate multi-tree subdivision information are associated with regions of the array of information samples in a spectral domain,

determining a maximum hierarchy level for the array of samples, wherein the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain,

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith; and

a data stream generator configured for

encoding each of the arrays of information samples by

encoding, into the data stream, information related to first subdivision information, second subdivision information, and the maximum hierarchy level associated with each of the arrays of information samples, wherein the first subdivision information includes the first maximum region size and the multi-tree subdivision information, and the second subdivision information includes the second maximum region size and the subordinate multi-tree subdivision information.

34. The encoder of claim 33, wherein each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

35. The encoder of claim 33, wherein the sub-divider divides an array of information samples in a depth-first traversal order.

36. The encoder of claim 33, wherein the data stream generator is further configured for encoding, into the data stream, for at least some of the first set of regions, inheritance information indicative of whether inheritance is to apply.

37. The encoder of claim 36, wherein when the inheritance information associated with a region indicates that inheritance applies, at least one of the sub-regions, obtained by sub-partitioning the region, inherits at least one coding parameter from the region.

38. The encoder of claim 33, wherein the first set of regions generated by the sub-divider corresponds to first order coding regions for prediction based coding.

39. The encoder of claim 38, wherein the second set of regions generated by the sub-divider corresponds to second order coding regions for at least one of residual coding and filtering.

40. The encoder of claim 33, wherein the plurality of arrays of information samples is a video accompanied with depth information.

41. The encoder of claim 33, wherein a scaling factor for a spatial resolution of an array of chroma samples relative to an array of luma samples in the horizontal direction differs from a scaling factor for a spatial resolution of the array of chroma samples relative to the array of luma samples in the vertical direction.

42. The encoder of claim 33, wherein at least one of the plurality of arrays of information samples is one of samples arrays related to different color components and forming color planes of a picture, and the encoder is configured to encode the different color planes of the picture independently.

43. A method of encoding a video comprising a plurality of arrays of information samples into a data stream, comprising:

dividing each of the plurality of arrays of information samples by

determining, with respect to the array of information samples, a first maximum region size, multi-tree subdivision information, a second maximum region size, and subordinate multi-tree subdivision information for the array of information samples, wherein the first maximum region size and the multi-tree subdivision information are associated with regions of the array of information samples in a spatial domain, and the second maximum region size and the subordinate multi-tree subdivision information are associated with regions of the array of information samples in a spectral domain,

determining a maximum hierarchy level for the array of information samples, wherein the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain,

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith; and

encoding each of the arrays of information samples by encoding, into the data stream, information related to first subdivision information, second subdivision information, and the maximum hierarchy level associated with each of the arrays of information samples, wherein the first subdivision information includes the first maximum region size and the multi-tree subdivision information, and the second subdivision information includes the second maximum region size and the subordinate multi-tree subdivision information.

44. The method of claim 43, wherein each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

45. The method of claim 43, wherein said dividing is performed in a depth-first traversal order.

46. The method of claim 43, further comprising encoding, into the data stream, for at least some of the first set of regions, inheritance information indicative of whether inheritance is to apply.

47. The method of claim 46, wherein when the inheritance information associated with a region indicates that inheritance applies, at least one of the sub-regions, obtained by sub-partitioning the region, inherits at least one coding parameter from the region.

48. The method of claim 43, wherein the first set of regions generated by said dividing corresponds to first order coding regions for prediction based coding.

49. The method of claim 48, wherein the second set of regions generated by said dividing corresponds to second order coding regions for at least one of residual coding and filtering.

50. The method of claim 43, wherein the plurality of arrays of information samples is a video accompanied with depth information.

51. The method of claim 43, wherein a scaling factor for a spatial resolution of an array of chroma samples relative to an array of luma samples in the horizontal direction differs from a scaling factor for a spatial resolution of the array of chroma samples relative to the array of luma samples in the vertical direction.

52. The method of claim 43, wherein at least one of the plurality of arrays of information samples is one of samples arrays related to different color components and forming color planes of a picture, and wherein the different color planes of the picture are encoded independently.

53. A non-transitory machine readable digital storage medium having computer instructions stored thereon for encoding, wherein the computer instructions, when read by the machine, causing the machine to at least perform:

dividing each of the plurality of arrays of information samples by

determining, with respect to the array of information samples, a first maximum region size, multi-tree subdivision information, a second maximum region size, and subordinate multi-tree subdivision information for the array of information samples, wherein the first maximum region size and the multi-tree subdivision information are associated with regions of the array of information samples in a spatial domain, and the second maximum region size and the subordinate multi-tree subdivision information are associated with regions of the array of information samples in a spectral domain,

determining a maximum hierarchy level for the array of information samples, wherein the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain,

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith; and

encoding each of the arrays of information samples by

encoding, into the data stream, information related to first subdivision information, second subdivision information, and the maximum hierarchy level associated with each of the arrays of information samples, wherein the first subdivision information includes the first maximum region size and the multi-tree subdivision information, and the second subdivision information includes the second maximum region size and the subordinate multi-tree subdivision information.

54. The medium of claim 53, wherein each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

55. The medium of claim 53, wherein said dividing is performed in a depth-first traversal order.

56. The medium of claim 53, wherein the machine is further caused to perform encoding, into the data stream, for at least some of the first set of regions, inheritance information indicative of whether inheritance is to apply.

57. The medium of claim 56, wherein when the inheritance information associated with a region indicates that inheritance applies, at least one of the sub-regions, obtained by sub-partitioning the region, inherits at least one coding parameter from the region.

58. The medium of claim 53, wherein the first set of regions generated by said dividing corresponds to first order coding regions for prediction based coding.

59. The medium of claim 58, wherein the second set of regions generated by said dividing corresponds to second order coding regions for at least one of residual coding and filtering.

60. A data stream stored in a non-transitory storage medium, the data stream comprising an encoded plurality of arrays of information samples, wherein each of the plurality of arrays of information samples is divided by

determining, with respect to the array of information samples, a first maximum region size, multi-tree subdivision information, a second maximum region size, and subordinate multi-tree subdivision information for the array of information sample, wherein the first maximum region size and the multi-tree subdivision information are associated with regions of the array of information samples in a spatial domain, and the second maximum region size and the subordinate multi-tree subdivision information are associated with regions of the array of information samples in a spectral domain,

determining a maximum hierarchy level for the array of information samples, wherein the maximum hierarchy level is associated with regions of the array of information samples in the spectral domain,

partitioning the array of information samples into a first set of regions in the spatial domain based on the first maximum region size,

sub-partitioning at least a subset of the first set of regions into a first set of sub-regions in the spatial domain based on the multi-tree subdivision information associated therewith,

responsive to a determination that a size of at least one of the first set of sub-regions exceeds the second maximum region size, partitioning the at least one of the first set of sub-regions into a second set of regions in the spectral domain, and

responsive to a determination that at least one of the second set of regions of the second maximum size is to be sub-divided, sub-partitioning the at least one of the second set of regions into a second set of sub-regions in the spectral domain based on the subordinate multi-tree subdivision information and the maximum hierarchy level associated therewith,

wherein each of the arrays of information samples is encoded by encoding, into the data stream, information related to first subdivision information, second subdivision information, and the maximum hierarchy level for the array of information samples, wherein the first subdivision information includes the first maximum region size and the multi-tree subdivision information and the second subdivision information includes the second maximum region size and the subordinate multi-tree subdivision information.

61. The data stream of claim 60, wherein each of the first set of regions has corresponding multi-tree subdivision information associated therewith, indicative of how the region is to be further sub-partitioned.

62. The data stream of claim 60, wherein each of the arrays of information samples is divided in a depth-first traversal order.

63. The data stream of claim 60, wherein the plurality of arrays of information samples is a video accompanied with depth information.

64. The data stream of claim 60, wherein a scaling factor for a spatial resolution of an array of chroma samples relative to an array of luma samples in the horizontal direction differs from a scaling factor for a spatial resolution of the array of chroma samples relative to the array of luma samples in the vertical direction.

65. The data stream of claim 60, wherein at least one of the plurality of arrays of information samples is one of samples arrays related to different color components and forming color planes of a picture, and the encoder is configured to encode the different color planes of the picture independently.