# US 10,771,822 B2 · Coding of a spatial sampling of a two-dimensional information signal using sub-division > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,771,822 B2 - Document ID: US10771822B2 - Status: Granted - Kind: B2 - Application number: 13/649,251 - Filed: 2012-10-11 - Published: 2013-02-14 - Granted: 2020-09-08 - Earliest claimed: 2010-04-13 - Assignees: Ge Video Compression, LLC - Applicants: Ge Video Compression, LLC - Inventors: Heiner Kirchhoffer; Martin Winken; Philipp Helle; Detlev Marpe; Heiko Schwarz; Thomas Wiegand - Web page: https://patentgrep.com/patent/US10771822B2 ## CPC - H04N 19/96: Tree coding, e.g. quad-tree coding - H04N 19/119: Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks - H04N 19/17: the unit being an image region, e.g. an object - H04N 19/176: the region being a block, e.g. a macroblock - 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]} - H04N 19/46: Embedding additional information in the video signal during the compression process (H04N19/517, H04N19/68, H04N19/70 take precedence) - H04N 19/52: by predictive encoding - H04N 19/53: Multi-resolution motion estimation; Hierarchical motion estimation - H04N 19/59: involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution - H04N 19/593: involving spatial prediction techniques - H04N 19/61: in combination with predictive coding - H04N 19/70: characterised by syntax aspects related to video coding, e.g. related to compression standards - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 3) 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. ### Claim 5 (depends on 1) The decoder of claim 1, wherein the sub-divider divides an array of information samples in a depth-first traversal order. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 6) 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 8) 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. ### Claim 11 (depends on 1) 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 1) The decoder of claim 1, wherein the plurality of arrays of information samples is a video accompanied with depth information. ### Claim 14 (depends on 1) 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. ### Claim 15 (depends on 1) 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. ### Claim 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. ### Claim 17 (depends on 16) 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. ### Claim 18 (depends on 16) The method of claim 16, wherein said dividing is performed in a depth-first traversal order. ### Claim 19 (depends on 16) 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. ### Claim 20 (depends on 19) 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. ### Claim 21 (depends on 16) 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. ### Claim 22 (depends on 21) 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. ### Claim 23 (depends on 16) The method of claim 16, wherein the plurality of arrays of information samples is a video accompanied with depth information. ### Claim 24 (depends on 16) 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. ### Claim 25 (depends on 16) 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. ### Claim 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. ### Claim 27 (depends on 26) 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. ### Claim 28 (depends on 26) The medium of claim 26, wherein said dividing is performed in a depth-first traversal order. ### Claim 29 (depends on 26) 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. ### Claim 30 (depends on 29) 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. ### Claim 31 (depends on 26) 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. ### Claim 32 (depends on 31) 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. ### Claim 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. ### Claim 34 (depends on 33) 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. ### Claim 35 (depends on 33) The encoder of claim 33, wherein the sub-divider divides an array of information samples in a depth-first traversal order. ### Claim 36 (depends on 33) 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. ### Claim 37 (depends on 36) 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. ### Claim 38 (depends on 33) 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. ### Claim 39 (depends on 38) 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. ### Claim 40 (depends on 33) The encoder of claim 33, wherein the plurality of arrays of information samples is a video accompanied with depth information. ### Claim 41 (depends on 33) 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. ### Claim 42 (depends on 33) 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. ### Claim 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. ### Claim 44 (depends on 43) 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. ### Claim 45 (depends on 43) The method of claim 43, wherein said dividing is performed in a depth-first traversal order. ### Claim 46 (depends on 43) 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. ### Claim 47 (depends on 46) 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. ### Claim 48 (depends on 43) 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. ### Claim 49 (depends on 48) 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. ### Claim 50 (depends on 43) The method of claim 43, wherein the plurality of arrays of information samples is a video accompanied with depth information. ### Claim 51 (depends on 43) 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. ### Claim 52 (depends on 43) 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. ### Claim 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. ### Claim 54 (depends on 53) 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. ### Claim 55 (depends on 53) The medium of claim 53, wherein said dividing is performed in a depth-first traversal order. ### Claim 56 (depends on 53) 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. ### Claim 57 (depends on 56) 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. ### Claim 58 (depends on 53) 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. ### Claim 59 (depends on 58) 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. ### Claim 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. ### Claim 61 (depends on 60) 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. ### Claim 62 (depends on 60) The data stream of claim 60, wherein each of the arrays of information samples is divided in a depth-first traversal order. ### Claim 63 (depends on 60) The data stream of claim 60, wherein the plurality of arrays of information samples is a video accompanied with depth information. ### Claim 64 (depends on 60) 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. ### Claim 65 (depends on 60) 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.