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

A decoder comprising:

• a sub-divider configured to spatially sub-divide an array of information samples, representing a spatially sampled information signal, into blocks of different sizes by:
• dividing the array of information samples into a regular arrangement of tree root blocks of zero-order hierarchy level size, and
• sub-dividing the tree root blocks by
• checking, for each tree root block, partitioning information contained in a data stream into which the array of information samples is coded, as to whether the respective tree root block is to be partitioned, and
• if the respective tree root block is to be partitioned, partitioning the respective tree root block into blocks of a first hierarchy level, and
• repeating the checking and partitioning for the blocks of the first hierarchy level in order to obtain blocks of higher-order hierarchy levels, with stopping the repetition when no partitioning is to be performed according to the partitioning information, or a maximum hierarchy level is reached;
• a reconstructor configured to reconstruct the array of information samples from the data stream using the blocks of different sizes into which the array of information samples is spatially subdivided, by traversing the blocks of different sizes in a scan order according to which the tree root blocks are scanned in a zigzag scan order with, for each tree root block being partitioned, treating the blocks of different sizes therein in depth-first traversal order before stepping further to a next tree root block in the zigzag scan order;
• and
• an extractor configured to extract syntax elements associated with the blocks of different sizes, in the scan order from the data stream,
• wherein the partitioning information is formed by a sequence of flags associated with nodes of the partitioning in the depth-first traversal order, and the extractor is configured to extract the sequence of flags of the partitioning information from the data stream using the depth-first traversal order and to choose a context to decode a respective flag of the sequence of flags using flags:
• preceding the respective flag in accordance with the depth-first traversal order and
• being associated with areas lying on top and/or left of an are to which the respective flag belongs.

A method for decoding comprising:

• spatially sub-dividing an array of information samples, representing a spatially sampled information signal, into blocks of different sizes by:
• dividing the array of information samples into a regular arrangement of tree root blocks of zero-order hierarchy level size, and
• sub-dividing the tree root blocks by:
• checking, for each tree root block, partitioning information contained in the data stream into which the array of information samples is coded, as to whether the respective tree root block is to be partitioned, and
• if the respective tree root block is to be partitioned, partitioning the respective tree root block into blocks of a first hierarchy level, and
• repeating the checking and partitioning for the blocks of the first hierarchy level in order to obtain blocks of higher-order hierarchy levels, with stopping the repetition when no partitioning is to be performed according to the partitioning information, or a maximum hierarchy level is reached;
• reconstructing the array of information samples from the data stream using the blocks of different sizes into which the array of information samples is spatially subdivided, by traversing the blocks of different sizes in a scan order according to which the tree root blocks are scanned in a zigzag scan order with, for each tree root block being partitioned, treating the blocks of different sizes therein in depth-first traversal order before stepping further to a next tree root block in the zigzag scan order;
• and
• extracting syntax elements associated with the blocks of different sizes, in the scan order from the data stream,
• wherein the partitioning information is formed by a sequence of flags associated with nodes of the partitioning in the depth-first traversal order, and the sequence of flags of the partitioning information are extracted from the data stream using the depth-first traversal order and a context to decode a respective flag of the sequence of flags is chosen using flags:
• preceding the respective flag in accordance with the depth-first traversal order and
• being associated with areas lying on top and/or left of an area to which the respective flag belongs.

An encoder comprising:

• a sub-divider configured to spatially sub-divide an array of information samples, representing a spatially sampled information signal, into blocks of different sizes by:
• dividing the array of information samples into a regular arrangement of tree root blocks of zero-order hierarchy level size, and
• sub-dividing the tree root blocks according to partitioning information contained in the data stream into which the array of information samples is coded, and indicating, for each tree root block, as to:
• whether the respective tree root block is to be partitioned, wherein if the respective tree root block is indicated to be partitioned, the respective tree root block is partitioned into blocks of a first hierarchy level, and
• whether the partitioning is repeated for the blocks of the first hierarchy level in order to obtain blocks of higher-order hierarchy levels, with the repetition being stopped when no partitioning is to be performed according to the partitioning information, or a maximum hierarchy level is reached;
• and
• a data stream generator configured to encode the array of information samples into the data stream using the blocks of different sizes into which the array of information samples is spatially subdivided, by traversing the blocks of different sizes in a scan order according to which the tree root blocks are scanned in a zigzag scan order with, for each tree root block being partitioned, treating the blocks of different sizes therein in depth-first traversal order before stepping further to a next tree root block in the zigzag scan order,
• wherein the data stream generator is configured to insert syntax elements associated with the blocks of different sizes, in the scan order into the data stream,
• wherein the partitioning information is formed by a sequence of flap associated with nodes of the partitioning in the depth-first traversal order, and the data stream generator is configured to insert the sequence of flap of the partitioning information into the data stream using the depth-first traversal order and to choose a context to encode a respective flag of the sequence of flags using flags:
• preceding the respective flag in accordance with the depth-first traversal order and
• being associated with areas lying on top and/or left of an are to which the respective flag belongs.

A method for encoding comprising:

• spatially sub-dividing an array of information samples, representing a spatially sampled information signal, into blocks of different sizes by:
• dividing the array of information samples into a regular arrangement of tree root blocks of zero-order hierarchy level size, and
• sub-dividing the tree root blocks according to partitioning information contained in the data stream into which the array of information samples is coded, and indicating, for each tree root block, as to:
• whether the respective tree root block is to be partitioned, wherein if the respective tree root block is indicated to be partitioned, the respective tree root block is partitioned into blocks of a first hierarchy level, and
• whether the partitioning is repeated for the blocks of the first hierarchy level in order to obtain blocks of higher-order hierarchy levels, with the repetition being stopped when no partitioning is to be performed according to the partitioning information, or a maximum hierarchy level is reached;
• and
• encoding the array of information samples into the data stream using the blocks of different sizes into which the array of information samples is spatially subdivided, by traversing the blocks of different sizes in a scan order according to which the tree root block are scanned in a zigzag scan order with, for each tree root block being partitioned, treating the blocks of different sizes therein in depth-first traversal order before stepping further to a next tree root block in the zigzag scan order,
• wherein the encoding the array of information samples of the data stream further comprises:
• inserting syntax elements associated with the blocks of different sizes, in the scan order into the data stream,
• wherein the partitioning information is formed by a sequence of flags associated with nodes of the partitioning in the depth-first traversal order, and the sequence of flags of the—partitioning information are inserted into the data stream using the depth-first traversal order and a context for encoding a respective flag of the sequence of flags is chosen using flags:
• preceding the respective flag in accordance with the depth-first traversal order and
• being associated with areas lying on top and/or left of an are to which the respective flag belongs.

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 information signal, wherein the array of information samples is encoded into the data stream using blocks of different sizes into which the array of information samples is spatially subdivided, by operations including:
• spatially sub-dividing the array of information samples into the blocks of different sizes by:
• dividing the array of information samples into a regular arrangement of tree root blocks of zero-order hierarchy level size, and
• sub-dividing the tree root blocks according to partitioning information contained in the data stream into which the array of information samples is coded, and indicating, for each tree root block, as to:
• whether the respective tree root block is to be partitioned, wherein if the respective tree root block is indicated to be partitioned, the respective tree root block is partitioned into blocks of a first hierarchy level, and
• whether the partitioning is repeated for the blocks of the first hierarchy level in order to obtain blocks of higher-order hierarchy levels, with the repetition being stopped when no partitioning is to be performed according to the partitioning information, or a maximum hierarchy level is reached, and
• encoding the array of information samples into the data stream using the blocks of different sizes into which the array of information samples is spatially subdivided, by traversing the blocks of different sizes in a scan order according to which the tree root block are scanned in a zigzag scan order with, for each tree root block being partitioned, treating the blocks of different sizes therein in depth-first traversal order before stepping further to a next tree root block in the zigzag scan order,
• wherein the encoding the array of information samples of the data stream further comprises:
• inserting syntax elements associated with the blocks of different sizes, in the scan order into the data stream,
• wherein the partitioning information is formed by a sequence of flags associated with nodes of the partitioning in the depth-first traversal order, and the sequence of flags of the partitioning information are inserted into the data stream using the depth-first traversal order and a context for encoding a respective flag of the sequence of flags is chosen using flags:
• preceding the respective flag in accordance with the depth-first traversal order and
• being associated with areas lying on top and/or left of an area to which the respective flag belongs.