Partitioning methods

Generalized Binary Splitting

In modern video codecs, prediction and transform coding are carried out on a block basis. The specific partitioning of a video frame into such blocks can be signal adaptive. This means that the partitioning is selected by an encoder and transmitted in the bitstream to the decoder. This way, the partitioning is adopted to the video signal’s characteristics.

We developed a partitioning scheme, called generalized binary splitting (GBS), that is an extension of previous splitting methods. As in the previous approaches, a video frame is initially divided into so-called coding tree units (CTUs). The CTUs cover squares of Nmax×Nmax luma samples and are the starting point for a flexible partitioning into smaller blocks as can be seen in the figure above. For the splitting, only binary splits are used. Here, in contrast to previous approaches, binary splits into blocks of unequal size are supported. More precisely, a given rectangle of width W and height H can be split horizontally into two blocks of width W, where the first block has height αH and the second block has height (1-α)H. Here, the split ratio α is chosen out of the set

{ 1/2 , 1/4 , 3/4 , 1/3 , 2/3 , 3/8 , 5/8 , 1/5 , 2/5 , 3/5 , 4/5 }. 

Vertical splits are supported analogously. The rectangular blocks that result from the partitioning are used for prediction and transform coding of inter prediction residuals. 

The split is coded by a tree as illustrated in the figure above. First, a split flag indicating if a block is further split is transmitted. If the split flag is equal to 1, the split direction and the split ratio are coded. The split direction is signaled as either parallel or perpendicular to the last split. For the first split, i.e., the CTU-level split, perpendicular is defined as a vertical split and parallel as a horizontal split. The split ratio is coded using the binarization shown in the figure. Not all splits in the figure are always possible and two restrictions are imposed in the signalling. First, only splits that result in blocks whose width and height are integral multiples of 4 are allowed. Second, redundancy constraints are imposed in order to guarantee that each final partitioning of a CTU is achievable by only one consecutive sequence of splits.

References

  • A. Wieckowski, J. Ma, H. Schwarz, D. Marpe, and T. Wiegand, “Fast partitioning decision strategies for the upcoming Versatile Video Coding (VVC) standard,” in Proc. IEEE Int. Conf. Image Process. (ICIP), Taipei, Sep. 2019.
  • A. Wieckowski, J. Ma, V. George, H. Schwarz, D. Marpe, and 1043 T. Wiegand, “Generalized binary splits: A versatile partitioning scheme for block-based hybrid video coding,” in Proc. IEEE Picture Coding Symp. (PCS), Ningbo, China, Nov. 2019

Line-based intra coding

The line-based intra coding mode partitions a luma intra-block into 1-D lines. The prediction as well as the transform coding of the prediction residual are then carried out for each line individually where the intra prediction mode is the same for all lines. Here, the reconstructed samples of the previously processed line comprise a part of the input for the intra-prediction on a current line. Thus, the prediction quality is increased in comparison to the prediction on a larger block. An example can be seen in the figure below. 

We integrated the line-based intra prediction mode into state-of-the art video codecs. Here, we developed efficient algorithms in order to reduce the impact of the line-based mode on the encoder-runtime. Moreover, we introduced different processing orders for the one-dimensional blocks in the line-based coding mode in order to further reduce the distance between the input and the target of the intra prediction.

During standardization, we developed simplifications of line-based intra coding. The final result was the Intra Subpartition (ISP) mode that is part of the current working draft of the VVC standard. In the ISP-mode, the minimal number of samples that can be parallelly processed in the critical loop of intra prediction is not decreased in comparison to the case of non-ISP-intra prediction. Also, the memory access to reference samples can be handled without increased complexity.

References

  • S. De-Luxán-Hernández, H. Schwarz, D. Marpe, and T. Wiegand, “Line-Based Intra Prediction for Next-Generation Video Coding,” in Proc. IEEE Int. Conf. Image Process. (ICIP), Athens, Oct. 2018, pp. 221–225.
  • S. De-Luxán-Hernández, H. Schwarz, D. Marpe, and T. Wiegand, “Fast Line-Based Intra Prediction for Video Coding,” in Proc. IEEE Int. Symp. Multimedia (ISM), Taichung, Dec. 2018, pp. 135–138.