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

• US 10,805,645 B2
• Filed: 01/24/2017
• Issued: 10/13/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:
  US15/413,852
• Publication Number:
  US 20170134761A1
• Time in Patent Office: 1,358 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 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 first and second maximum region sizes, first and second subdivision information, and a maximum hierarchy level, wherein the first maximum region size and the first subdivision information are associated with prediction coding and the second maximum region size and the second subdivision information are associated with transform coding, the encoded information is coded into the data stream by operations including;

dividing the 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 based on the first subdivision information;

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 second subdivision information and the maximum hierarchy level;

generating the encoded information based on the first and second maximum region sizes, first and second subdivision information, and the maximum hierarchy level; and

inserting the encoded information into the data stream.

2. The computer-readable medium according to claim 1, 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.

3. The computer-readable medium according to claim 1, wherein the sub-dividing 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 each of the at least some of the first set of root regions into sub-regions of a first hierarchy level according to a partition rule associated with the first hierarchy level, and

recursively repeating the determining and sub-dividing 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.

4. The computer-readable medium according to claim 3, wherein the sub-dividing at least some of the first set of root regions includes sub-dividing, in accordance with the partition rules associated with the first and higher-order hierarchy levels, into sub-regions of equal size, such that there are an equal number of sub-regions at each hierarchy level.

5. The computer-readable medium according to claim 3, 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.

6. The computer-readable medium according to claim 1, wherein the encoded information in the data stream includes the maximum hierarchy level.

7. The computer-readable medium according to claim 1, wherein syntax elements associated with the first or second set of sub-regions are inserted into the data stream in a depth-first traversal order.

8. The computer-readable medium according to claim 1, wherein the operations further comprise:

combining, based on a first subset of syntax elements of the data stream, disjoint from a second subset of syntax elements 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 array of information samples are coded using the intermediate subdivision.

9. The computer-readable medium according to claim 1, wherein the recursive multi-tree partitioning includes a quadtree partitioning technique.