{'fraction_non_alphanumeric': 0.03739308152297328, 'fraction_numerical': 0.0109000075694497, 'mean_word_length': 4.562947368421052, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cross-Block Difference Guided Fast CU Partition for VVC Intra Coding

In this paper, we propose a new fast CU partition algorithm for VVC intra coding based on cross-block difference. This difference is measured by the gradient and the content of sub-blocks obtained from partition and is employed to guide the skipping of unnecessary horizontal and vertical partition modes. With this guidance, a fast determination of block partitions is accordingly achieved. Compared with VVC, our proposed method can save 41.64% (on average) encoding time with only 0.97% (on average) increase of BD-rate.


I. INTRODUCTION
The versatile video coding (VVC) [1] adopts a number of advanced coding techniques. With these techniques, VVC achieves higher rate-distortion (R-D) performance than the high efficiency video coding (HEVC) [2]. However, the adoption of these techniques makes VVC suffer from higher complexity. Reducing the complexity of VVC is so necessary to make it more applicable.
The QTMT structure used in the coding unit (CU) partition of VVC makes the block partition more flexible and contentadaptive, which offers considerable coding gain. Similar to the quadtree (QT) structure-based partition in HEVC, the QTMTbased one also determines the best CU partition by the R-D cost and the best mode is determined by the lowest R-D cost. Compared with the QT structure of HEVC, the QTMT structure introduces two new tree structures, i.e., the binary tree (BT) and the ternary tree (TT), which compose the multitype tree (MTT) structure. Adopting MTT in VVC results in a rather complicated partition determination and dramatically increases the encoding time. Therefore, accelerating the determination of CU partition is one of the most effective solutions to reduce the complexity for VVC.
Over the past few years, both the learning-based and nonlearning-based methods have been proposed to implement the fast CU partition for VVC intra coding. In the learning-based methods, the shape-adaptive convolutional neural network (CNN) was employed to rapidly process various CU partition shapes for VVC [3]. A low-complexity coding tree unit (CTU) structure decision algorithm was proposed in [4], where the CU partition was modeled as a multi-classification problem and both the texture information and context information were used as the classification features. The support vector machine was also introduced in the fast prediction of the CU splitting direction [5]. Meanwhile, the Bayesian rule-based classifier was employed to achieve the fast CU partition in [6] which used the partition types and intra prediction modes of children CUs as the classification features. Although the learning-based solution is popular in the design of the fast CU partition methods, these proposed methods either suffer from the heavy training workload or rely on the accuracy of classifier, which limits their applications. Compared with the learning-based methods, the non-learning-based ones are normally implemented with lower workload based on the texture information of video frame. For instance, the block variance and gradient were utilized to accelerate the rectangular partition [7].
In this work, we propose a fast CU partition method for VVC intra coding based on the cross-block difference which is measured by the gradient and the content of sub-blocks obtained from partition. With our method, the unnecessary horizontal and vertical partitions of both the BT and TT structures can be effectively skipped without the R-D costbased determination.

A. Background
The QTMT structure is introduced in VVC to achieve a fine block partition. There are six splitting modes in the QTMT-based partition. The first four modes are binary tree horizontal splitting (BHS), binary tree vertical splitting (BVS), ternary tree horizontal splitting (THS) and ternary tree vertical splitting (TVS). Besides these modes, there are two additional modes, i.e., quadtree splitting (QTS) and no splitting (NOS).
The previous works [6], [7] demonstrate that the block partition is related to the texture characteristic of block. The texture information can be employed to guide the partition targeting a low complexity. More specifically, the smooth and homogeneous areas should be split into blocks with larger sizes, whereas the areas with complicated textures are usually split into blocks with smaller sizes.
In this work, we aim to achieve a fast mode determination by skipping the horizontal and vertical partitions based on the difference between sub-blocks obtained from a split block. With four horizontal and vertical partition modes in VVC, i.e., BHS, BVS, THS and TVS, we can separate a block into two or three sub-blocks which have different shapes as shown in Fig.1. To compare the difference between sub-blocks, we define the cross-block difference as where p 1 and p 2 are measurement parameters for two compared sub-blocks. Note that M (p 1 , p 2 ) approximates 1 if p 1 and p 2 are close enough, while M (p 1 , p 2 ) will be large if p 1 and p 2 are quite different. In our work, we utilize M (p 1 , p 2 ) to determine which partition modes should be skipped based on the characteristic of sub-blocks.

B. Gradient difference between sub-blocks
We firstly study the relationship between the partition strategy and the sub-block gradient. Given a sub-block A, we can obtain its four directional gradients, i.e., the horizontal gradient G (h) , vertical gradient G (v) , diagonal gradient G (d) and antidiagonal gradient G (a) , by performing the Sobel operator [8] on it as where ⊛ denotes the convolution operation and S is the corresponding Sobel operator to obtain a directional gradient. We study the relationship between the partition strategy and the sub-block gradient based on some coded frames. Specifically, we select four video sequences from class D, including BasketballPass, BlowingBubbles, BQSquare and RaceHorses, and encode 50 frames of each sequence with the all-intra (AI) configuration. Four coding scenarios are adopted in our experiment, where the quantization parameters (QPs) are specified as {22, 27, 32, 37}, respectively. For all the scenarios and all the encoded frames, we compare the difference of sub-blocks based on their directional gradients. For each subblock, the average gradient along a specific direction over all the pixels is utilized as its directional gradient. According to Fig. 1, we use the notations listed in Table I to denote four directional gradients for a sub-block which obtained by the horizontal separation (HS) or vertical separation (VS) of a block with binary tree or ternary tree.
To obtain the optimal partition mode for a block, all the candidate modes will be attempted and the one with the lowest R-D cost will be selected as the optimal mode. Besides the optimal partition, we can also separate each block into two or three sub-blocks along the horizontal or vertical directions with binary tree or ternary tree, which is like the BHS, BVS, THS and TVS-based partition. For each separation, we calculate the directional gradient differences between the sub-blocks and present the corresponding results in Table II-V. According to the results presented in Table II-V, it is found that splitting a block along a specific direction is highly related to the gradient differences of the resulting sub-blocks. For example, the sub-blocks obtained by the BHS-based partition always have bigger M (G bh2 ) than the ones obtained by the partition of These results indicate that we may determine an effective partition for a block based on the gradient differences of the sub-blocks.

C. Content difference between sub-blocks
Compared with the BT-based splitting, fewer TT-based partition modes will be attempted in practical VVC coding [9]. Therefore, we intend to develop a more accurate partition for the BT-based mode by with the guidance of both the gradient difference and the content difference between sub-blocks. We evaluate content difference between a w 1 × h 1 sub-block b 1 and a w 2 × h 2 sub-block b 2 as According to Eq. (3), when the contents of b 1 and b 2 are similar, the average pixel-levels of them will also be similar and their difference will be small. It indicates that the employed splitting mode generates sub-blocks with similar contents. As a result, this mode should be skipped.

III. OUR PROPOSED METHOD
In this section, we propose a fast CU partition scheme for VVC intra coding by skipping the unnecessary horizontal and vertical partitions based on the cross-block difference.

A. Fast determination for the binary tree-based partition
Our previous results in Section II reveals that the crossblock difference, especially the gradient difference, is highly related to the partition mode. Inspired by this fact, we define the gradient-based difference flags, i.e., d and where T 1 is the pre-defined threshold. Note that d (g) bh = 0 or d (g) bv = 0 indicates that the resulting sub-blocks split by using the BHS mode or the BVS mode will generate two similar subblocks. Therefore, the corresponding partition mode should be skipped. When d where T 2 is the pre-defined threshold. According to Eqs. (6) and (7), if bh 1 and bh 2 are different enough, i.e., d (c) bh = 1, the block prefers to be split horizontally and the vertical splitting is accordingly skipped. Similarly, if bv 1 and bv 2 are different enough, i.e., d (c) bv = 1, splitting block along the vertical direction should be more effective and the horizontal separation should be skipped.
We summary our binary tree-based partition algorithm in Algorithm 1, where skip bh = 1 and skip bv = 1 indicate skipping the BHS mode and BVS mode, respectively.

B. Fast determination for the ternary tree-based partition
The TT-based partition will divide a block into three parts and calculate the R-D cost for each of them, which makes the partition more complicated than the BT-based one. Compared with the BT-based splitting, fewer TT-based partition modes will be attempted in VVC coding [9]. Therefore, to reduce the complexity as much as possible, we decide how to skip the TT-based splitting modes with fewer restrictions than the BT-based modes.
It is found from Table IV that THS has the largest difference when the gradient direction is vertical. It indicates that the vertical difference is more related to the THS compared with the other gradient-based differences. Similarly, when the gradient direction is horizontal, the TVS has the largest difference, as presented in Table V. As a result, the horizontal gradient difference is more related to the TVS compared with the other gradient differences. Based on this fact, we determine the skip flags for THS and TVS as Algorithm 1: Proposed binary tree-based partition where T 3 is the pre-defined threshold, and skip th = 1 and skip tv = 1 indicate skipping the THS mode and the TVS mode, respectively. Based on Eqs. (8) and (9), if the gradients of two sub-blocks are similar along a specific direction, the block will not be split along this direction.

IV. EXPERIMENTAL RESULTS
We apply our proposed method to the coding of luminance (Y) component in VVC and verify its effectiveness on both VTM-5.0 and VTM-9.3. VTM-5.0 is employed in the simulations so that we can make a fair comparison with the adaptive CU split decision (ADSD) method [3] which is implemented based on VTM-5.0. VTM-9.3 is adopted in our work because we developed our method based on it. The AI configuration is used in this work and QPs are specified as {22, 27, 32, 37}. We compress 100 frames of each test video sequence from class A1 to E. Compared with VVC, the BD-rate saving and the encoding time saving (TS) are employed to evaluate the R-D performance and the complexity, respectively. Meanwhile, the thresholds {T 1 , T 2 , T 3 } used in our method are empirically specified as {1.165, 3.500, 2.000} and {1.180, 3.500, 2.000} for VTM-5.0 and VTM-9.3, respectively.
We firstly present some experimental results in Table VI to compare our method with the ADSD method [3]. To make a fair comparison, we only offer the results for the same test video sequences used in [3]. One can see from Table  VI that our proposed method saves more time and achieves better R-D performance than the ADSD method. We integrate our proposed method in VTM-9.3 to make a comprehensive verification of its effectiveness. The corresponding results are presented in Table VII. Comparing the results presented in Tables VI and VII, one can find that integrating our proposed method in VTM-5.0 and VTM-9.3 achieves similar performances, which demonstrates the effectiveness and robustness of our proposed method.

V. CONCLUDING REMARKS
In this paper, we propose a new fast CU partition algorithm for VVC intra coding based on the cross-block difference which is measured by the gradient difference and the content difference of sub-blocks belonging to a separated block. This cross-block difference is used to guide the skipping of unnecessary partition modes, which accordingly leads to a fast determination for CU partition. Compared with VVC, our proposed method save 41.64% (on average) encoding time with only 0.97% (on average) increase of BD-rate.