Tree-Structured Partitioning for Motion-Compensated Prediction

Tree-structured partitioning for motion-compensated prediction is a concept for increasing the efficiency of motion-compensated prediction in hybrid video coding.

In the first Test Model for H.264/MPEG-4 AVC, 7 different partitionings were supported, by which a 16×16 macroblock could be splitting into up to 16 equal-sized blocks. For each of the resulting 1 to 16 blocks, a separate set of motion parameters was signaled to the decoder. This concept already provided a good degree of encoding options that could be employed for adjusting a suitable tradeoff between the obtained video quality and the required bit rate for signaling the motion data.

The Image and Video Coding group proposed a more flexible concept for partitioning a macroblock into blocks that are used for motion-compensated prediction. The flexible concept for partitioning a macroblock basically represents a tree-structured approach. It supports basically 4 different macroblock modes for motion-compensated prediction, which are referred to as Inter16×16, Inter16×8, Inter8×16, and Inter8×8 mode. As illustrated in Figure 1, in the Inter16×16, the entire macroblock is coded using a single set of motion parameters. For the Inter16×8 and Inter8×16 modes, the macroblock is partitioned into two 16×8 and 8×16 blocks, respectively. In the Inter8×8 mode, the macroblock is partitioned into four 8×8 blocks. If a macroblock is coded in Inter8×8 mode, a so-called sub-macroblock mode is transmitted for each 8×8 block. This sub-macroblock specified whether and how the corresponding 8×8 blocks is further split into smaller blocks. An 8×8 sub-macroblock can be either coded as a single 8×8 block, or it can be further split into two 8×4 blocks, two 4×8 blocks, or four 4×4 blocks. Overall, 259 different patterns are supported for partitioning a macroblock. The increased number of possibilities allows to increase the coding efficiency in relation to the concept that was included in the first Test Model. Furthermore, the tree structure of the macroblock partition is particularly suitable for designing fast encoding strategies.

Tree-Structured Partitioning in Video Coding Standards

The concept of tree-structured partitioning is included in the following standards:

The concept has been proposed for H.264/MPEG-4 AVC and is now an integral part of the standard. An extension of the concept, which provides more levels of the tree-structures partitioning, is included in the design of the upcoming HEVC standard. It was already included in the first HEVC Test Model.