Fast Decision Algorithm of CU Size for HEVC Intra-Prediction Based on a Kernel Fuzzy SVM Classifier

Abstract

High Efficiency Video Coding (HEVC) achieves a significant improvement in compression efficiency at the cost of extremely high computational complexity. Therefore, large-scale and wide deployment applications, especially mobile real-time video applications under low-latency and power-constrained conditions, are more challenging. In order to solve the above problems, a fast decision method for intra-coding unit size based on a new fuzzy support vector machine classifier is proposed in this paper. The relationship between the depth levels of coding units is accurately expressed by defining the cost evaluation criteria of texture and non-texture rate-distortion cost. The fuzzy support vector machine is improved by using the information entropy measure to solve the negative impact of data noise and the outliers problem. The proposed method includes three stages: the optimal coded depth level “0” early decision, coding unit depth early skip, and optimal coding unit early terminate. In order to further improve the rate-distortion complexity optimization performance, more feature vectors are introduced, including features such as space complexity, the relationship between coding unit depths, and rate-distortion cost. The experimental results showed that, compared with the HEVC reference test model HM16.5, the proposed algorithm can reduce the encoding time of various test video sequences by more than 53.24% on average, while the Bjontegaard Delta Bit Rate (BDBR) only increases by 0.82%. In addition, the proposed algorithm is better than the existing algorithms in terms of comprehensively reducing the computational complexity and maintaining the rate-distortion performance.

1. Introduction

Recently, with the development of technology, in order to meet the compression requirements of high-definition and ultra-high-definition video, research on how to further improve the coding efficiency of next-generation video codecs has been carried out on a large scale. ISO/IEC (MPEG) and ITU-T (VCEG) have formed the Joint Collaborative Team on Video Coding (JCT-VC) to develop a next generation video coding standard, which is called High Efficiency Video Coding (HEVC) [1,2,3]. In recent years, with the promotion of 5G networks and the popularization of mobile smart terminal devices, video data services in video applications such as online education, video conferencing, online games, and video social interaction have exploded. Especially with the emergence of high-definition and ultra-high-definition video services, end users are increasingly demanding high frame rates, a high resolution, and a high dynamic range for real-time video interaction, which brings new challenges to the implementation of video coding. The latest report from Sandvin, an Internet smart solution provider, shows that in 2019, video traffic accounted for more than 60% of the global Internet downlink traffic [1]. The widely used H.264/AVC video coding standard can no longer meet the current real-time video coding needs. Compared with H.264/AVC, the video coding standard (H.265/HEVC) keeps the visual quality unchanged and the transmission bit rate is reduced by 50%, but the computational complexity is high. To improve the coding rate-distortion performance, the HEVC computational complexity evaluation is increased by nearly three times [4].

Accordingly, many coding efficiency improvement techniques, such as coding tree unit (CTU) coding (from 64 × 64 down to 8 × 8 Luma samples), prediction unit (PU) coding, transform unit (TU) tree coding, uniform intra-prediction and so on, are available in the current HEVC. More details can refer to [1,2,4]. Each picture frame in HEVC is partitioned into many square-shaped CTUs. A CTU represents the most basic processing unit, and each CTU can be recursively split into a smaller CU based on a quadtree structure. The CU sizes range from 8 × 8 up luma samples to 64 × 64. The coding depth order for CUs is referred to as the z-scan and is illustrated for an example in Figure 1.

Due to the extended prediction and transform block size with a flexible coding structure, HEVC can meet the coding requirements of general video sequences and can effectively code video sequences from low to high picture resolutions. Because up to 35 prediction modes are used in HEVC (e.g., mode 0 is used for PLANAR, mode 1 is used for DC and other angle modes) while only 9 modes are used in H.264/AVC, HEVC uses a more complex structure and has more accurate prediction accuracy, and its intra-frame prediction is significantly improved compared to H.264/AVC [3]. The significant increased number of angular intra-prediction modes in HEVC leads to a much higher compression efficiency. However, it also brings a tremendous computational burden to the mode decision process when the expensive rate-distortion optimization (RDO) process is used to search for the minimum rate distortion (RD) cost mode. Therefore, in the real implementation of HEVC codec, the main objective of the fast mode decision method is to reduce the computational complexity while maintaining high video coding RD performance.

Recently, many researchers devoted their efforts to the reduction in the complexity of HEVC for prediction coding. The main idea is to skip or terminate the non-optimal rate-distortion optimization mode selection processing in advance through prediction, avoiding the exhaustive search of RDO for coding unit depth size decision, prediction mode selection, and transform coding unit selection. The choice of decision-making strategies and thresholds is mainly determined by the temporal and spatial statistical characteristics of the video content and machine learning methods. The following two categories are introduced, respectively:

The method based on spatio-temporal statistical characteristics is mainly completed by manually extracting statistical features, including the spatio-temporal correlation video frames, the correlation of coding unit depth and prediction mode, the correlation of rate distortion, the correlation of content complexity, etc. [5,6,7,8,9,10,11,12]. According to the RD cost of each coding unit CU and the inter-mode prediction error, Shen et al. [5] used the Bayesian decision method to determine the coding unit CU partition in advance [6]. The gradient-based method reduces the range of candidate modes and uses the statistical characteristics of depth difference and least Hadamard transform-based costs (HAD costs) to make early decisions of the support vector coding unit. The fast quadtree pruning algorithm in [7] uses the prediction of residual statistics to reduce coding time. Lei et al. [8] distinguished between the natural content coding unit CU and the screen content coding unit CU for the extension of intra-prediction coding in screen content coding. Based on the depth and mode content statistical characteristics of the temporal and spatial adjacent coding units, the optimal prediction mode is predicted, and the quad-tree structure is divided to reduce the complexity of intra-frame coding. Q. Hu et al. [9] modeled the mode and CU size selection decision as a binary classification problem and used Neyman–Pearson’s rules to balance the rate-distortion performance loss and the complexity reduction rate. H.S. Kim et al. [10] proposed a fast CU size decision algorithm based on Bayesian decision rules. ** process of CU depth, where the unnecessary coding with the CU (marked with dotted lines) is simply bypassed. Similarly, for the complex content, the large CU sizes can also be skipped without affecting the encoding quality.

Otherwise, one can easily perceive that a large CU-sized CTU is more suitable for a homogeneous region, while a small CU-sized CTU, on the contrary, is more suitable for a region containing a complex object. In these cases, the combination of different CU sizes is expected to be the optimal prediction choice for LCU. In order to verify this observation, the RDO exhaustive mode decision of the HEVC standard reference software was used. By using the different video sequences listed in

Table 2. Depth range class distribution (%).

Video Sequences	Qps	Depth Range Category of LCU (%)
		C0	C1	C2	C3	C4	C5	C6
BQTerrace (1920 × 1080)	22	1.1	1.6	5.6	0.1	38.9	51.2	1.5
	27	3.6	4.5	5.4	0.1	41.5	44.5	0.4
	32	4.8	4.7	8.2	0.2	46.9	35.1	0.0
	37	10.3	6.3	10.4	0.2	49.0	23.8	0.0
BasketballDrill (832 × 480)	22	5.5	18.8	7.5	0.4	42.5	25.1	0.2
	27	8.0	26.7	11.6	0.2	38.8	14.7	0.0
	32	13.5	19.2	19.8	0.4	36.9	10.2	0.0
	37	22.2	19.2	18.0	0.0	32.7	7.8	0.0
Kimono (1920 × 1080)	22	9.2	10.0	24.6	1.7	35.4	19.2	0.0
	27	17.1	20.4	12.1	0.0	32.1	18.3	0.0
	32	31.7	10.4	10.8	0.0	32.1	15.0	0.0
	37	39.2	6.7	14.6	0.0	27.9	11.7	0.0

, a relatively extensive test experiment was carried out, and the statistical distribution results of the optimal partition structure of each CTU were obtained. The resulting data are shown in Table 2. This study strongly suggests that depth sets be grouped into different complexity classes in terms of the depth range from a Min value to a Max value. The classes that resulted from such depth grou** are established and summarized in

Table 3. The depth sets and their involved depths.

Depth Range Class	C0	C1	C2	C3	C4	C5	C6
Involved Depths	0	1	1, 2	2	2, 3	1, 2, 3	3

. This study clearly indicates that class C0, C1, C2 with low complexity and class C4, C5, C6 with high complexity are selected as the optimal partition with a high probability. Consequently, only the depths involved in each class are required to be checked.

2.2. Cost Relationship between CU Sizes

Similar to H.264/AVC, the RD optimization technique is performed in HEVC intra-prediction encoding, and the RD costs are computed for all the possible CU sizes to find the minimum RD cost. The RD cost is defined as follows:

$$J_{RD}=SSE\left(Qp\right)+{\lambda }_{Mode}R(Qp)$$

(1)

where SSE represents the sum of squared difference between the original and its reconstructed CU blocks, respectively, R denotes the total number of bits used for CU signaling, Qp is the quantization parameter, and ${\lambda }_{Mode}=0.85\times 2^{\left(Qp-12\right)/3}$ is the Lagrange multiplier.

In HEVC, the signaling of the side information for non-texture data, which includes quadtree split information for TU and CU, prediction modes for PU, filter parameters for the reconstructed PU, etc., becomes more important due to the adoption of many complex coding tools with more coding parameters compared to the conventional methods in previous video coding standards. In order to obtain the relationship between the non-texture cost and the texture cost, the bit rate R of CU was analyzed. The R is composed of:

$$R=R_{nontexture}+R_{texture}$$

(2)

where $R_{nontexture}$ denotes the total number of bits for the non-texture information, $R_{texture}$ represents the encoding bits for the transform residues which are derived from prediction, transform, quantization, and entropy coding. Substituting (2) into (1), the RDO cost can be represented as follows:

$$\begin{array}{l}{J}_{RD}=\underset{J_{R{D}_{texture}}}{\underbrace{SSE\left(Qp\right)+{\lambda }_{Mode}{R}_{texture}\left(Qp\right)}}\\ +\underset{J_{R{D}_{nontexture}}}{\underbrace{{\lambda }_{Mode}{R}_{nontexture}(Qp)}}\end{array}$$

(3)

where $J_{R{D}_{texture}}$ and $J_{R{D}_{nontexture}}$ are the texture cost and non-texture cost, respectively. The non-texture cost of the CUs has a strong relationship with the depth level of CTUs. As the number of the depth levels increases, more non-texture bits are required to mode the presentation correspondingly. Therefore, a fixed relationship can be determined:

$$J_{R{D}_{nontexture,dept{h}_i}}<J_{R{D}_{nontexture,dept{h}_{i+1}}}$$

(4)

where $dept{h}_i$ denotes the depth level $i$ of the current CU for $i=0,1,2$.

In the new standards, HEVC has introduced many complicated partition CTU and prediction modes, which has led to significant increases in the non-texture signaling bits. Assuming a certain depth level of a sub-block of a given CTU sample, performing different modes of segmentation under this level of sub-block will obtain different prediction and transformation results, and thus will result in different rate distortion costs. When the current depth level block is further sub-divided into multiple sub-blocks, compared with the current level block, the smaller the block can be described more accurately, and a more accurate prediction and transformation accuracy will be obtained; that is, smaller coding prediction residuals will be obtained. The set of supported sub-divisions for the current level block will produce a smaller bit rate and distortion but will increase the bit rate required to transmit more block prediction parameters. According to the observation, the variance of the residual will decrease proportionally with the growth of the depth level, which results in better prediction, i.e., ${\sigma }_{residual,dept{h}_i}^2>{\sigma }_{residual,dept{h}_{i+1}}^2$. With the assumption of the Laplace distribution of the residual signal [16], we have: $SSE\left({\sigma }_{residual}^2|Qp\right)\propto {\sigma }_{residual}^2$ and $R_{texture}\left({\sigma }_{residual}^2|Qp\right)\propto {\sigma }_{residual}^2$. This proportional relation of $\mathit{SSE}$, $R_{\mathit{texture}}$, and ${\sigma }_{residual}^2$ can be observed in Figure 2. It can be observed that both $\mathit{SSE}$ and $R_{\mathit{texture}}$ are monotonically increasing with ${\sigma }_{residual}^2$, so their summation should also be a monotonic increasing function.

Therefore, it easily follows that:

$$SSE\left({\sigma }_{residual}^2|Qp\right)+{\lambda }_{Mode}{R}_{texture}\left({\sigma }_{residual}^2|Qp\right)\propto {\sigma }_{residual}^2$$

(5)

and

$$J_{R{D}_{texture,dept{h}_i}}>J_{R{D}_{texture,dept{h}_{i+1}}}$$

(6)

According to (4) and (6), the relationships of the non-texture rate and texture RD cost across successive depth levels can be obtained:

$$\{\begin{array}{c}0<R_{nontexture,dept{h}_i}<R_{nontexture,dept{h}_{i+1}}\\ J_{R{D}_{texture,dept{h}_i}}>J_{R{D}_{texture,dept{h}_{i+1}}}>0\end{array}$$

(7)

A measure to evaluate the texture complexity of the current CU depth level is introduced, which is the texture cost percentage of the cost term (TCPOC), i.e.,

$$TCPO{C}_{dept{h}_i}=\frac{J_{R{D}_{textur{e}_i}}}{J_{R{D}_i}}$$

(8)

Here, $TCPO{C}_{dept{h}_i}$ can be viewed as an encoding cost weight ($0<TCPO{C}_{dept{h}_i}<1$) and can be used to determine whether the CU depth selected by RDO is the best level.

With (1) and (7), it is readily seen that:

$$\begin{array}{l}\frac{{\lambda }_{Mode}{R}_{nontexture,dept{h}_i}+J_{R{D}_{texture,dept{h}_i}}}{J_{R{D}_{texture,dept{h}_i}}}\\ <\frac{{\lambda }_{Mode}{R}_{nontexture,dept{h}_{i+1}}+J_{R{D}_{texture,dept{h}_{i+1}}}}{J_{R{D}_{texture,dept{h}_{i+1}}}}\end{array}$$

(9)

From (9), a consistent relationship can be derived for $dept{h}_i<dept{h}_{i+1}$ and $0<TCPO{C}_{dept{h}_i}<1$ as follows:

$$TCPO{C}_{dept{h}_i}\ge TCPO{C}_{dept{h}_{i+1}}$$

(10)

This relationship between $\mathit{TCPOC}$ and $\mathit{depth}$ can be verified in Figure 3, such as for the Class A sequence “Traffic”. As shown in Figure 3, four quantization parameters “22, 27, 32, 37” were used in the experiment, and the $\mathit{TCPOC}$ of all depth levels was obtained through actual coding. The $\mathit{TCPOC}$ data corresponding to each quantization parameter were averaged. The more obvious the decrease in $\mathit{TCPOC}$ between the levels, the deeper the depth level decreases; for example, the depth level “2” with the quantization parameter “22” is reduced from 0.888 to the depth level “3” 0.761. The monotonically decreasing relationship between $\mathit{TCPOC}$ and depth level is shown.