Weisheng Zhu

Frédéric Li

Dufaux

Ce Zhu

D Wang

W Li

F Dufaux

Keywords: SHVC, coding depth, coding mode, mode prediction, early termination

  L'archive ouverte pluridisciplinaire

Abstract-The scalable high efficiency video coding (SHVC) is an extension of high efficiency video coding (HEVC), which introduces multiple layers and inter-layer prediction, thus significantly increases the coding complexity on top of the already complicated HEVC encoder. In inter prediction for quality SHVC, in order to determine the best possible mode at each depth level, a coding tree unit can be recursively split into four depth levels, including merge mode, inter2Nx2N, inter2NxN, interNx2N, interNxN, in-ter2NxnU, inter2NxnD, internLx2N and internRx2N, intra modes and inter-layer reference (ILR) mode. This can obtain the highest coding efficiency, but also result in very high coding complexity. Therefore, it is crucial to improve coding speed while maintaining coding efficiency. In this research, we have proposed a new depth level and inter mode prediction algorithm for quality SHVC. First, the depth level candidates are predicted based on interlayer correlation, spatial correlation and its correlation degree. Second, for a given depth candidate, we divide mode prediction into square and non-square mode predictions respectively. Third, in the square mode prediction, ILR and merge modes are predicted according to depth correlation, and early terminated whether residual distribution follows a Gaussian distribution. Moreover, ILR mode, merge mode and inter2Nx2N are early terminated based on significant differences in Rate Distortion (RD) costs. Fourth, if the early termination condition cannot be satisfied, non-square modes are further predicted based on significant differences in expected values of residual coefficients. Finally, inter-layer and spatial correlations are combined with residual distribution to examine whether to early terminate depth selection. Experimental results have demonstrated that,

I. INTRODUCTION

W ITH the rapid development of science and technol- ogy, video applications have been widely used in our daily life. Various video applications, such as digital TV broadcasting, video conferencing, wireless video streaming, and smart phone communications, have become ubiquitous. These applications are also characterized by heterogeneous environments with a wide variety of devices. These devices may have different screen resolutions, processing capabilities, and network bandwidth requirements. In addition, different networks, such as broadband networks and wireless networks, may have different characteristics. Even within the same network, network bandwidths may also vary in different conditions. Consequently, video streaming should be able to adapt to different devices and network bandwidths. Scalable Video Coding (SVC), an extension of H.264/AVC, can efficiently solve these problems [START_REF] Schwarz | Overview of the scalable video coding extension of the H.264/AVC standard[END_REF]. In order to provide scalability, SVC consists of a base layer (BL) and one or more enhancement layers (ELs). A SVC stream may support temporal, spatial and quality scalability, or a combination thereof. Scalability in temporal, spatial and quality refer to frame rate from low to high, spatial resolution from low to high and SNR from low to high, respectively. In recent years, the newest video coding standard, HEVC, has been developed. Since HEVC uses more advanced features and higher-efficiency coding tools, it has better coding efficiency than previous video coding standards. HEVC only uses about half the bit rate in comparison with H.264/AVC, while maintaining the same video quality level [START_REF] Correa | Performance and Computational Complexity Assessment of High Efficiency Video Encoders[END_REF]. Since HEVC has very high coding efficiency, it attracts extensive attention and has wide applications. In order to accommodate heterogeneous device capabilities, network conditions and client applications, Scalable High Efficiency Video Coding (SHVC), an extension of HEVC, has been proposed. Similar to SVC, SHVC also supports scalability in temporal, spatial, and quality. In addition, it also provides bit-depth scalability, and color gamut scalability [START_REF] Boyce | Overview of SHVC: Scalable Extensions of the High Efficiency Video Coding Standard[END_REF].

HEVC achieves very high coding efficiency, but at the cost of a very high encoding complexity, with an increase by about two to four times when compared to H.264/AVC [START_REF] Correa | Performance and Computational Complexity Assessment of High Efficiency Video Encoders[END_REF]. In SHVC, multiple layers need to be encoded using inter-layer prediction, in addition to the same encoding process as that of HEVC for each layer. Thus, SHVC is even more complex than HEVC. Therefore, it is highly desirable to improve the coding speed, especially for wireless and real-time applications.

For this purpose, a new algorithm to improve the coding speed of inter prediction for quality SHVC (QS) is proposed in this work. The contributions of the proposed algorithm are: [START_REF] Schwarz | Overview of the scalable video coding extension of the H.264/AVC standard[END_REF] inter-layer correlation is combined with spatial correlation and its correlation degree in prediction; [START_REF] Correa | Performance and Computational Complexity Assessment of High Efficiency Video Encoders[END_REF] inter-layer reference (ILR) mode and merge mode are predicted based on depth correlation and residual distribution; (3) Square partitions, including ILR mode, merge mode and inter2Nx2N, are early terminated based on their RD-cost differences; (4) Non-square partitions are predicted based on the difference in expected values of the residual coefficients of square partitions; [START_REF] Li | Fast mode decision algorithm for interframe coding in fully scalable video coding[END_REF] inter-layer and spatial correlations are combined with residual distribution to predict depth early termination.

The remainder of this paper is organized as follows. Section II discusses related work. Section III presents an overview of our proposed algorithm. Section IV, Section V and Section VI describe the proposed depth prediction, mode prediction and depth early termination in details. Experimental results are presented in Section VII and we draw conclusions in Section VIII.

II. RELATED WORK

Since both SHVC and H.264/SVC are related to scalable video coding, they share many similarities. Besides, as SHVC is the scalable extension of HEVC, they certainly have close relationship. Therefore, we first discuss fast algorithms for H.264/SVC, then for HEVC, and finally for SHVC.

To improve the coding speed for H.264/SVC, the authors of [START_REF] Li | Fast mode decision for spatial scalable video coding[END_REF][START_REF] Li | Fast mode decision algorithm for interframe coding in fully scalable video coding[END_REF][START_REF] Lin | Fast mode decision algorithm for interframe coding in fully scalable video coding[END_REF] use inter-layer correlation to predict candidate macroblock (MB) modes and skip unlikely modes in EL. Kim et al. [START_REF] Shen | Efficient skip mode detection for coarse grain quality scalable video coding[END_REF] use both inter-layer and spatial correlations to predict the SKIP mode of the current MB in EL. The research in [START_REF] Park | A statistical approach or fast mode decision in scalable video coding[END_REF] statistically derive the Rate-Distortion (RD) cost expectations of each mode, and encode the modes according to this expectation from small to large. Then, the RD cost is compared with a preset threshold to determine whether to early terminate the coding process. Yeh et al. [START_REF] Yeh | Fast mode decision algorithm for scalable video coding using Bayesian theorem detection and Markov process[END_REF] use Bayesian theorem to predict the best mode of the current MB. If the best mode cannot be obtained by the Bayesian theorem, the Markov process is then used to further estimate and refine the best mode. Jung et al. [START_REF] Jung | Fast mode decision using all-zero block detection for fidelity and spatial scalable video coding[END_REF] propose a fast mode decision algorithm for SVC which uses All-Zero Block (AZB) detection. Based on empirical analysis of inter-layer and spatial correlations of an AZB, a prediction is made of whether a MB in the EL would be an AZB. Then, the AZB detection algorithm is adopted to examine and terminate the predicted MBs. Zhao et al. [START_REF] Zhao | H.264/SVC mode decision based on optimal stopping theory[END_REF] initialize the candidate mode list based on interlayer and spatial correlations, and then early terminate the coding process by a constrained model with optimal stopping. Based on motion activities, picture detail levels, inter-layer and spatial correlations, Lu et al. [START_REF] Lu | Fast mode decision algorithm for the H.264/AVC scalable video coding extension[END_REF] predict candidate modes and early terminate the encoding process. According to interlayer and spatial correlations, the work in [START_REF] Wang | A fast mode decision algorithm applied to coarse-grain quality scalable video coding[END_REF] estimates likely modes, skips unlikely modes, and then early terminates the coding process based on the RD cost and residual coefficients. Generally speaking, these algorithms use correlations to either predict candidate modes or use early termination, or jointly exploit mode prediction and early termination to improve the coding speed.

To reduce the coding complexity of HEVC, several methods have been proposed. Pan et al. [START_REF] Pan | Early MERGE mode decision based on motion estimation and hierarchical depth correlation for HEVC[END_REF] uses the mode of depth correlation, AZB, and motion estimation information to early detect merge mode. The authors of [START_REF] Vanne | Efficient mode decision schemes for HEVC inter prediction[END_REF] divide modes into symmetric motion partition (SMP) modes and asymmetric motion partition (AMP) modes, and then propose three optimization techniques to predict SMP modes and AMP modes. The research in [START_REF] Shen | An effective CU size decision method for HEVC encoders[END_REF] predicts candidate depths based on the previous frame and neighboring CUs, and then early terminate unnecessary CUs according to motion homogeneity checking, RD cost checking and SKIP mode checking. Zhang et al. [START_REF] Zhang | Machine learning-based coding unit depth decisions for flexible complexity allocation in High Efficiency Video Coding[END_REF] combine coding features with a weighted support vector machine (SVM), and jointly optimize the complexity allocation at CU level with given rate-distortion (RD) cost constraints, to predict candidate depths. Chen et al. [START_REF] Chen | Efficient CU and PU Decision Based on Motion Information for inter prediction of HEVC[END_REF] propose an adaptive early termination decision for CU and PU, and also develop an adaptive search range determination according to the motion vector (MV), to reduce computational demand.

Some research focus on improving the coding speed of SHVC. Tohidypour et al. use the RD cost of the neighboring blocks of current block in EL, RD costs of the corresponding block and its four neighboring blocks in BL, to predict the RD cost of the to-be-encoded CU in EL [START_REF] Tohidypour | Content adaptive complexity reduction scheme for quality/fidelity scalable HEVC[END_REF][START_REF] Tohidypour | Content Adaptive Complexity Reduction Scheme for Quality/Fidelity Scalable HEVC[END_REF]. They use the neighboring blocks' modes of current block in EL and the co-located block's mode of current CU in BL to predict current block's candidate modes in EL for quality SHVC [START_REF] Tohidypour | Fast mode assignment for quality scalable extension of the High Efficiency Video Coding (HEVC) standard: A Bayesian approach[END_REF]. The research in [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF] uses spatial and inter-layer correlations to propose a probabilistic approach to predict the quad-tree structure of coding tree units (CTUs) for quality and spatial scalable SHVC. In [START_REF] Tohidypour | An encoder complexity reduction scheme for qual-ity/fidelity scalable HEVC[END_REF], when at least one of the parent CUs in previous depth layers of the current CU select the merge mode, the depth and scalable layer of the current CU in the EL are jointly used to predict candidate modes. Moreover, inter-layer and spatial correlations are also exploited to further eliminate candidate modes. In this manner, the coding speed can be improved. Tohidypour et al. use coding information of relative CUs including neighboring CU in EL and the colocated CU in BL to build a probabilistic model, and then uses this model to predict the candidate modes of the current CU in EL to improve the coding speed [START_REF] Tohidypour | Online-Learning-Based Mode Prediction Method for Quality Scalable Extension of the High Efficiency Video Coding (HEVC) Standard[END_REF]. Wang et al. [START_REF] Wang | Efficient Multi-Strategy intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF] predict candidate depths. In each candidate depth, if ILR mode early termination condition is satisfied, intra mode prediction can be skipped; otherwise intra mode prediction needs to be checked. Afterwards, if depth early termination is satisfied, other depth levels can be directly skipped to improve the coding speed. Yeh et al. [START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF] propose a coding unit complexity (CUC)based prediction method to improve the coding speed of HEVC-to-SHVC transcoding for quality scalability. Yeh et al. [START_REF] Yeh | Fast prediction for quality scalability of High Efficiency Video Coding Scalable Extension[END_REF] use encoded Coding Unit (CU) sizes, prediction modes, motion vectors and Rate-Distortion Costs (RD-Costs) in BL and encoded CU sizes in EL to accelerate the coding speed of quality SHVC. Shen et al. [START_REF] Shen | Content-based adaptive SHVC mode decision algorithm[END_REF] use conditional probability of a SKIP/Merge mode, motion activity and mode complexity to describe the video content to predict the EL mode decision to improve the coding speed.

Although SHVC and SVC are very similar, their specific coding features are different. Algorithms developed for SVC may not suitable for SHVC or cannot significantly improve coding speed of SHVC. Since both SHVC and HEVC use the same advanced coding tools, the complexity reduction algorithms developed for HEVC can also be utilized for SHVC. As HEVC has only one coding layer, these algorithms developed for HEVC do not consider and exploit inter-layer correlations, and thus they cannot effectively improve SHVC's coding speed. In addition, the fast inter coding algorithms developed for SHVC only predict either CUs part or modes part. Since only one part is predicted, the coding speed improvement is limited. In addition, mode prediction is always predicted in the same approach without considering different features for different modes. It is obvious that using the same prediction method without any adaptation to different mode features is not always efficient, and thus, the improvement of coding speed is limited to some degree.

Based on the above considerations, in this paper, we propose a new fast depth and mode inter prediction for quality SHVC. In order to improve the coding speed, we divide the problem into the depth part and mode part. In the depth part, we propose depth prediction and depth early termination. In the mode part, we divide modes into three categories and separately develop their own methods for predictions. Experimental results demonstrate that our algorithm can significantly improve the coding speed with negligible losses in coding efficiency.

III. OVERVIEW OF THE PROPOSED MULTI-STRATEGIES FRAMEWORK

In order to improve coding speed and maintain coding efficiency for inter prediction in QS, we propose five strategies: Correlation-Based Depth Prediction (CBDP); Distribution-Based ILR and Merge Mode Decision (DB-IMMD); RD Cost Based Square Mode Early Termination (RCB-SMET); Expected Values Based Non-Square Mode Prediction (EVB-NSMP); and Correlation and Distribution Based Depth Early Termination (CDB-DET). The overview of the proposed algorithm is summarized in Fig. 1. The left side of Fig. 1 shows the five proposed strategies. First, depth candidates are predicted through CBDP. For the selected current depth candidates, DB-IMMD determines whether the best mode is in ILR and Merge Modes. In the affirmative, the other modes do not need to be checked; otherwise inter2Nx2N mode is checked and RCB-SMET is used to determine whether the best mode is in square modes. In the affirmative, the non-square modes do not need to be checked; otherwise EVB-NSMP is used to predict candidate non-square modes. After the depth has been checked, the residuals of the likelihood depth predicted by correlations are examined by CDB-DET to determine whether it is the best depth for early termination.

IV. CORRELATION-BASED DEPTH PREDICTION (CBDP)

Similar to HEVC, the maximum size of CU in SHVC is 64, and the range of depth levels is from 0 to 3. Since every depth contains the whole inter and intra mode prediction process, and the inter prediction includes eight partitions, the induced coding complexity is very high. In quality SHVC, a CU's content in EL and the co-located CU in BL are exactly the same, thus inter-layer correlation is very strong. In addition, since strong spatial correlations exist in natural video content, thus spatial correlation is also very strong. Therefore, we can use inter-layer and spatial correlations to predict candidate depths and skip depths with low likelihood to improve the coding speed. The relative CUs of the current CU, which are used to predict candidate depths of the current CU, are shown in Fig. 2. C, L, U, UL and UR are the current, left, upper, upper-left and upper-right CUs in the EL respectively. Accordingly, BC, BL, BU, BUL and BUR are the collocated CUs of C, L, U, UL and UR in the BL, respectively.

In order to develop the fast inter prediction algorithm for quality SHVC, extensive experiments have been conducted to investigate related features and test corresponding methods. To meet the requirement of different resolutions, in our experiments, we use two sequences from class B (Tractor and Sunflower), class C (PartyScene and Flowervase), class D (RaceHorses and BlowingBubbles) and class E (Town and Parkruner). According to common SHM test conditions (CSTC) [START_REF]Common SHM Test Conditions and Software Reference Configurations[END_REF], we encode each test sequence under the Random Access (RA) main configuration. The QPs used for the BL are [START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF][START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF][START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF][START_REF] Xiong | A New Multiplication-Free Block Matching Criterion[END_REF], and the corresponding QPs used for the EL are [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF][START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF][START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF][START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF]. Based on these experiments, we propose our efficient fast decision methods below.

A. Inter-Layer Correlation Prediction

As mentioned above, inter-layer correlation is very strong and can be used to predict candidate depths of current CU. Using the above experimental conditions, inter-layer correlation in depth between BL and EL is obtained by calculating proportions of the four depths used by C in EL given the depth used by BC in BL. The results are reported in Table I, where higher values indicate that the corresponding depths have higher possibilities to be used, namely stronger depth correlations.

In Table I, BC refers to a depth used by CU BC in BL, C refers to depths used by CU C in EL. From Table I, we can observe the following features:

(1)When BC in BL uses depth 0, C in EL has high probability to select depths 0 and 1, and has low probability to select depths 2 and 3. (2)When BC in BL uses depth 1, C in EL has high probability to select depths 0, 1 and 2, and has low probability to select depth 3. (3)When BC in BL uses depth 2, C in EL has high probability to select depths 2 and 3, and has low probability to select depths 0 and 1. (4)When BC in BL uses depth 3, C in EL has high probability to select depths 2 and 3, and has low probability to select depths 0 and 1. According to these observations, we can conclude that C in EL has high probability to select depth of BC and its neighboring depths, and other depths have low probability to be selected. Since a CU's content in EL and the co-located CU in BL are exactly the same, when a CU in BL uses a depth, the co-located CU in EL is more likely to use similar depths.

B. Spatial Correlation Prediction

Due to high similarity in motion and textural features for neighboring CUs, their spatial correlations are very strong. Therefore, we can predict the current CU's coding depth from its neighboring CUs'depths. Since the degrees of correlation between the current CU and its neighboring CUs may be vary, it is not appropriate to straightforwardly predict the current CU's depth from its neighboring CUs' depths. In this paper, we propose to first obtain spatial correlation degrees, then to combine neighboring CUs with their correlation degrees in prediction. The key point is how to obtain the correlation degrees between the current CU and its neighboring CUs in the EL. As the contents of CUs in the BL and the co-located CUs in the EL are the same, if two neighboring CUs' depths in BL are more similar, the co-located CUs' depths in EL will more likely be the same. To justify this, we tested the possibility of the co-located CUs in EL having the same depth given by the absolute differences (0, 1, 2 and 3) between two neighboring CUs' depths in BL. The experimental results of the sequence "BlowingBubbles" are listed below.

In Table II, correlation degree refers to the absolute differences between two neighboring CUs' depths in BL, spatial correlation denotes as the possibility of the co-located CUs having the same depth in EL. QPB, QPE refer to QPs in BL and EL, respectively. 0, 1, 2 and 3 refer to the absolute differences between two neighboring CUs' depths in BL. From Table II, we can find that when the absolute differences between two neighboring CUs' depths in BL is 0, 1, 2 and 3 in BL, the average possibility of the co-located CUs having the same depth is 70.75%, 46.5%, 28.25% and 23.5% in EL, respectively. As a result, when neighboring CUs'spatial correlation degrees in the BL are very strong, then depths of the co-located CUs' depths in the EL should be very similar, and vice versa. Undoubtedly, spatial correlation degrees are inversely proportional to absolute depth differences among neighboring CUs in BL. We know that the maximum absolute difference of neighboring CUs in depth is 3. Therefore, the spatial correlation degrees d can be written as

d = 3 -|h bn -h bc | (1)
where h bc represents the depths of the co-located CUs of the current CU in BL, and h bn represents the depth of one of its neighboring CUs in BL. The spatial correlation degree d is defined as spatial correlation weight. Through the above process, we can obtain each neighboring CU's spatial correlation weight. Then, we can calculate the weights of all depths by summing the weights with the same depths. Subsequently, we compute the probability of each depth by

p h = w h 3 h=0 w h (2)
where h refers to the h-th depth, w h denotes the spatial weight of the hth depth, and p h denotes the spatial probability of the hth depth. Obviously, the larger p h is, the larger the probability of the hth depth to be selected.

C. Combine Spatial and Inter-Layer Correlations to Predict Candidate Depths

Through the above process, we can obtain the inter-layer depth distribution and the spatial probabilities of all depths. Since depth selection has strong relationship with both spatial and inter-layer correlations, we first predict depth likelihoods based on inter-layer correlation, and then predict depth likelihoods based on spatial correlation. If one or more depths are predicted to have a high probability to be selected based on inter-layer correlation, and they are also predicted to have a high probability to be selected based on spatial correlation, we can only check these depths and skip the other ones. The details are described below.

As mentioned above, if BC use a depth, the co-located CU C in EL is very likely to select the depth and its neighboring depths. We can then combine their spatial probabilities to determine whether to only select these depths or to further check the other depths. For example, when BC uses depth 0, C in EL is very likely to use depths 0 and 1 based on interlayer correlation. Then, we combine the spatial probabilities of depths 0 and 1 to decide whether further checking is needed. If depths 0 and 1 are very likely to be selected, the sum of their spatial probabilities should be at least equal to or greater than 0.5. Thus, we have selected 0.5, 0.6, 0.7, 0.8 and 0.9 under the above condition for experiments. From Table I, when BC in BL uses depth 0, C in EL has the largest sum of depths 2 and 3 in sequence "RaceHorses", so skipping depths 2 and 3 has the greatest impact for this sequence. In other words, if our method obtains very good coding efficiency for "RaceHorses", then we could definitely achieve better coding efficiency for the other sequences. Thus, through testing this sequence, we could obtain the optimal sum of the spatial probabilities for depth 0 and depth 1. The sum of their spatial probabilities and the corresponding coding efficiency losses are shown in Fig. 3.

In Fig. 3, the horizontal axis represents the sum of spatial probabilities of depth 0 and 1, and the vertical axis represents the coding efficiency loss denoted by BDBR, which represents the bitrate difference at an equal PSNR [START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF]. A negative BDBR represents an increase in coding efficiency when compared to the reference software. From Fig. 3, we observe that there is a turning point when the sum is equal to 0.7. If the sum is smaller than 0.7, the corresponding coding efficiency changes dramatically. When sum is greater than or equal to 0.7, the coding efficiency stays approximately constant. Moreover, as we know, the smaller the sum is, the larger the encoding speed increases. Therefore, the sum is set to 0.7. The other depths are predicted in a similar way. Then, our depth prediction methods of C in EL are proposed as follows:

( Fig. 4: Flowchart of the depth selection.

0 and 1 and the sum of these probabilities is equal or greater than 0.7, only these two depths are selected; else go to (3). (3) If three depths with the largest spatial probabilities are 0, 1 and 2 and the sum of these probabilities is equal or greater than 0.8, only these three depths are selected; else all the four depths need to be checked. (4) Since depth 0 is usually seldom used, when depth of BC is 2 and 3, the possibility of selecting depth 0 is further decreased. Depth 0 is directly skipped, and other three depths need to be checked. The flowchart in Fig. 4 illustrates the depth selection algorithm.

Since neighboring CUs may have different spatial correlation degrees, we combine neighboring CUs with spatial correlation degrees in prediction. In addition, we also integrate inter-layer correlation in prediction. Therefore, the proposed inter-prediction is very efficient.

V. PROPOSED SQUARE AND NON-SQUARE MODE DECISION

In every coding depth of SHVC, a CU is predicted by square and non-square modes. Square modes include ILR mode, merge mode, inter2Nx2N and intra2Nx2N mode. Nonsquare modes include 2NxN, Nx2N, 2NxnU, 2NxnD, nLx2N and nRx2N. As NxN is only used when depth is 3, we have not considered this mode for the sake of simplicity. More specifically, we have developed two methods to improve the coding speed for square and non-square modes, respectively.

A. Square partition mode prediction

For square partition, we have conducted experiments to obtain the proportions of the four modes (ILR mode, merge mode, inter2Nx2N mode, intra2Nx2N mode). Based on these experiments, the proportion of modes in square partition are listed in Table III. From Table III, we can observe that: (1) ILR and merge modes have the highest probability; (2) inter2Nx2N has a smaller probability but remains non-negligible; (3) intra2Nx2N has a very small probability. Therefore, ILR and merge modes always need to be checked, and intra2Nx2N can be skipped directly. Regarding inter2Nx2N, if the mode is always checked, much unnecessary time would be spent. On the contrary, if the mode is skipped directly, the coding efficiency would be obviously degraded. Therefore, we first check ILR and merge modes, and decide whether they are the best modes. In the affirmative, we can only select these modes and skip inter2Nx2N mode. Otherwise, we still need to check inter2Nx2N mode and compare the difference of RD costs between ILR & merge modes and inter2Nx2N mode. If the difference is not significant, square modes provide a good prediction and non-square modes can be skipped directly. Otherwise, non-square modes need to be further checked. Base on the above analysis, in this paper, we develop ILR and merge modes prediction and square modes early termination. The details are presented below.

1) Distribution-Based ILR and Merge Modes Decision (DB-IMMD): Since their depths are strongly correlated, the parent CU and its children CUs may use similar modes [START_REF] Pan | Early MERGE mode decision based on motion estimation and hierarchical depth correlation for HEVC[END_REF]. In order to investigate the depth correlation degree between parent CU and its children CUs in ILR and merge modes, we have conducted experiments using the same conditions mentioned above. Based on these experiments, the depth correlation degrees of ILR and merge modes are listed in Table IV.

In Table IV, depth correlation degree refers to the probability that children CUs select ILR or merge modes given parent CU using ILR or merge modes. From Table IV, we can observe that the average depth correlation degree is 96%. In other words, when a parent CU uses ILR or merge modes, its children CUs basically also use ILR or merge modes. However, depth correlation degrees are slightly lower in some cases, such as "RaceHorses" whose degree is only 92.3%. Consequently, when a parent CU uses ILR or merge modes, if its children CUs only check ILR and merge modes, the coding efficiency may degrade to some extent. In order to improve the coding speed and maintain coding efficiency, when a parent CU uses ILR or merge modes, we first encode ILR and merge modes in its children CUs, and then determine whether residual coefficients satisfy early termination condition. In the affirmative, we can skip the other modes. Otherwise, we have to further check other modes. As we know, residual coefficients normally follow a certain distribution if the prediction is accurate [START_REF] Wang | Hybrid model to detect zero quantized DCT coeffcients in H.264[END_REF]. Thus, by analyzing the distribution of residual coefficients, we can decide if the early termination condition is met. Generally, a Gaussian distribution [START_REF] Cho | Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[END_REF][START_REF] Hu | Fast motion estimation based on confidence interval[END_REF] or a Laplacian distribution [START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF] are normally used to model residual coefficients. Through our experiments, we found out that Gaussian distribution can better model residual coefficients, when compared to Laplacian distribution. Therefore, we adopt Gaussian distribution in this research. In [START_REF] Wang | Efficient Multi-Strategy intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF], we proposed a test for intra prediction, which is based on skewness and kurtosis detection, to check whether residual coefficients follow the Gaussian distribution. Here, we apply this test to decide whether residual coefficients for inter prediction follow a Gaussian distribution.

Let x 1 , x 2 ,...,x n represent residual coefficients, the moment estimator G 1 for skewness and the moment estimator G 2 for kurtosis are obtained by

G 1 = B 3 B 3 2 2 , G 2 = B 4 B 2 2 , (3)
where B k represents the sample central moment for order k (k=2,3,4). We can calculate B k as

B k = n i=1 (x i -x) k n , (4)
where x denotes the average of x i . G 1 and G 2 usually follow Gaussian distribution when n is relatively large (generally more than 100). Thus, we can approximated G 1 and G 2 by

G 1 ∼ N µ 1 , σ 2 1 = N 0, 6 (n -2) (n + 1) (n + 3) , G 2 ∼ N µ 2 , σ 2 2 = N 3 - 6 n + 1 , 24n (n -2) (n -3) (n + 1) 2 (n + 3) (n + 5) , (5)
where σ 1 and σ 2 are the variances of G 1 and G 2 respectively, and µ 1 and µ 2 represent the expected values of G 1 and G 2 . Then, we can decide if the residual coefficients follow the Gaussian distribution with expected values and variances according to

µ 1 = G 1 σ 1 , µ 2 = G 2 -µ 2 σ 2 . ( 6

BDBR(%)

Za

RaceHorses Fig. 5: z α and the corresponding coding efficiency losses for ILR and merge modes.

Based on statistical hypothesis testing, a significance level α indicates the probability of falsely rejecting the null hypothesis, i.e. the distribution is Gaussian. Through the table of Gaussian distribution, we can obtain the corresponding critical test value z α . The conditions of following Gaussian distribution are described by

| µ 1 | z α , | µ 2 | z α . (7)
Residual coefficients are regarded to follow a Gaussian distribution if the two above conditions are met. In this case, our algorithm considers ILR or merge modes as the best modes, and then skips the other modes. Obtaining optimal α and the corresponding z α is essential for effectively improving coding speed while maintaining coding efficiency. We observe in Table IV that "RaceHorses" has the lowest depth correlation degree. Therefore, if we terminate the prediction of ILR and merge modes early, we can obtain the greatest effect on "RaceHorses". As explained before, if we achieve good coding efficiency on "RaceHorses", we could obtain better coding performance on the other sequences. Therefore, we use "RaceHorses" in our experiments to find out the optimal values for optimal α and z α . In our expriments, we select some commonly used values α, including 0.025, 0.015, 0.0125, 0.0075, 0.0055, 0.0045, 0.0035, 0.0025 and 0.0015. Correspondingly, the common values of z α are 1.96, 2.17, 2.24, 2.43, 2.54, 2.61, 2.70, 2.81 and 2.96.

The resulting coding efficiency is shown in Fig. 5, where the horizontal axis represents the value of z α , and the vertical axis indicates the coding efficiency loss, in terms of BDBR. It is obvious that there exists a turning point (z α =2.81) in Fig. 5. We can observe that the corresponding coding efficiency losses are almost the same when z α is less than or equal to 2.81. When z α is greater than 2.81, the coding efficiency loss obviously increases. Besides, the greater z α is, the larger the encoding speed increases. Based on the above analysis, z α is set to 2.81 and α is set to 0.0025. Thus, when a parent CU uses ILR or merge mode, its children CUs are first encoded by ILR and merge modes. If their residual coefficients satisfy the early termination condition, the other modes can be skipped in these children CUs. Otherwise, the other modes need to be further checked.

2) RD Cost Based Square Modes Early Termination (RCB-SMET: When the condition of DB-IMMD is not satisfied or the parent CU of the current CU does not use ILR or merge modes, inter2Nx2N needs to be checked. As mentioned above, after all square modes have been checked, if their RD cost difference is not significant, it indicates that square modes provide a good prediction. Therefore, we only need to check square modes and skip non-square modes directly. In order to determine whether they have a significant difference, we can compare their quantized residual coefficients. If the differences of their quantized residual coefficients between ILR & merge modes, and inter2Nx2N mode are very small, then their RD costs are not significantly different [START_REF] Ren | Computationally efficient mode selection in H.264/AVC video coding[END_REF]. Since every CU consists of multiple 4x4 blocks, we calculate quantized residual coefficients in a 4x4 block and derive the decision as follows. For a DCT coefficient w, its quantized value z is

z (i, j) = w (i, j) Q step + 1 6 , (8)
where Q step is the quantization step. As we know, if the condition ( 9) is met, no information needs to be coded,

(w 1 (i, j) -w 2 (i, j)) Q step 1, (9)
where w 1 (i, j) is the DCT coefficients at the (i,j) position of ILR and merge modes, and w 2 (i, j) is the DCT coefficients at the (i,j) position of inter2Nx2N mode. Thus, we can consider that difference is not significant. As a result, we can derive

|w 1 (i, j) -w 2 (i, j)| Q step . (10)
In SHVC, DCT coefficient w (i, j) which is the DCT coefficients at the (i,j) position of a 4x4 block is computed as

w (i, j) = 3 u=0 3 v=0 h (i, u) x (u, v) h (v, j) 128 × 128 . ( 11
)
where h (i, u) refers to the value in the integer DCT transform matrix at the (i,u) position in SHVC, and x (u, v) refers to the residual value in the residual matrix at the (u,v) position.

According to [START_REF] Zhao | H.264/SVC mode decision based on optimal stopping theory[END_REF], we can derive

w 1(x, j) -w 2(x, j) < 3 u=0 3 v=0 |h (i, u) h (v, j)| |x 1 (u, v) -x 2 (u, v)| 128 × 128 , (12)
In integer DCT transform of HEVC, h (i, u) can be set to 64, 83 or 36, so the maximum value of |h (i, u)| is 83. Combining [START_REF] Jung | Fast mode decision using all-zero block detection for fidelity and spatial scalable video coding[END_REF] and [START_REF] Lu | Fast mode decision algorithm for the H.264/AVC scalable video coding extension[END_REF], we obtain

3 u=0 3 v=0 |x 1 (u, v) -x 2 (u, v)| < 2.5Q step . (13)
From ( 13), we can derive

3 u=0 3 v=0 |x 1 (u, v)| - 3 u=0 3 v=0 |x 2 (u, v)| < 2.5Q step . ( 14
) (a) (b) (c) (d) (e) (f)
Fig. 6: Non-square partition Sum of Absolute Difference (SAD) of two 4x4 blocks is obtained by [START_REF] Pan | Early MERGE mode decision based on motion estimation and hierarchical depth correlation for HEVC[END_REF] and can be written as

|S AD 1 -S AD 2 | < 2.5Q step . (15)
Since ( 15) is developed for 4x4 blocks, each 16x16 CU includes 16 4x4 blocks, we can derive

|S AD 1 -S AD 2 | < 40mQ step . ( 16
)
Where m is the number of 16x16 CUs included in the current CU. Accordingly, each 32x32 CU includes 4 16x16 CUs, each 64x64 CU includes 16 16x16 CUs, thus m is set 16, 4, 1, corresponding to 64x64, 32x32, 16x16 CU, respectively. In order to maintain coding efficiency, we have not further tested 8x8 CUs.

Since SAD costs have strong relationship with RD costs, for convenience purposes, we have replaced SAD costs with RD costs, and ( 16) can be written as

|RD 1 -RD 2 | < 40mQ step . (17)
If the above condition is met, we can only select square modes and skip non-square modes directly. Otherwise, we still need to check non-square modes.

B. Expected Values Based Non-Square Mode Prediction (EVB-NSMP)

Non-square modes include inter2NxN, interNx2N, in-ter2NxnU, inter2NxnD, internLx2N, internRx2N, as shown in Fig. 6. In general, if the prediction is efficient, residual coefficients will obey a certain distribution. Therefore, we can also predict the best partition by studying the distribution of residual coefficients. As mentioned above, residual coefficients are modeled using a Gaussian distribution in this research. Suppose residual coefficients of a CU obey a Gaussian distribution, we can divide a CU into two parts and decide whether they have a significant difference to select the corresponding partition mode. More precisely, hypothesis testing is used to determine if the two parts for each division present a significant difference. For this purpose, t-test is used, which is the test statistics to investigate the significance of the difference between two sampled expected values. The expected values of the CU residual coefficients can be calculated by

X 1 = 3 u=0 3 v=0 r i j M × N , (18)
where M and N are the width and height of the partitioned CU respectively, and r i j is the residual value in the residual matrix at the (i, j) position. For the sake of simplicity, we only consider CUs with sizes of 64x64, 32x32 and 16x16. According to the knowledge of mathematical statistics, if the residual coefficients of a CU, obeying a Gaussian distribution, are divided into two parts, these two parts will also obey a Gaussian distribution [START_REF] Lee | A low complexity encoding scheme for coarse grain scalable video coding[END_REF]. We can model the residual coefficients of two parts in each division as

X 1 ∼ N µ 1 , σ 2 1 , X 2 ∼ N µ 2 , σ 2 2 , (19)
where X 1 and X 2 are two parts of a Gaussian distribution, µ and σ 2 are their respective expected value and variance. We can compute the test statistics t by

t = X 1 -X 2 -(µ 1 -µ 2 ) S w 1 n 1 + 1 n 2 , (20)
where n 1 and n 2 are the number of coefficients in the first and second parts respectively, and S w is calculated by the expression

S w = (n 1 -1) s 2 1 + (n 2 -1) s 2 2 n 1 + n 2 -2 , (21)
where s 2 1 and s 2 2 are the variances of the first and second parts respectively. Assuming µ 1 =µ 2 , the condition can be expressed as

X 1 -X 2 t α 2 (n 1 + n 2 -1) S w 1 n 1 + 1 n 2 , ( 22
)
where α is the significance level value. For any α, we can check T distribution table to obtain the corresponding threshold t α 2 (n 1 + n 2 -1). For the sake of simplicity, we use a unified value for all six non-square modes. If the condition is satisfied, we can assume that there is no significant difference, and we do not need to check the corresponding modes. For example, in Fig. 6. (a), if top and bottom parts have a significant difference, then inter2NxN needs to be checked. Similarly, in Fig. 6. (b), if the left and right parts have a significant difference, then inter Nx2N need to be checked. The other modes are selected in the same way.

The optimal α and t α 2 (n 1 + n 2 -1) can be obtained through experiments. We have performed experiments using the same conditions as above. Commonly used values for α are 0.5, 0.4, 0.3, 0.2, 0.1, 0.05, 0.02, 0.01 and 0.005, and the corresponding threshold values for t α 2 (n 1 + n 2 -1) 0.674, 0.842, 1.036, 1.282, 1.645, 1.96, 2.326, 2.576 and 2.807, are tested.

In Fig. 7, the horizontal axis represents the value of t α 2 (n 1 + n 2 -1), abbreviated as t, and the vertical axis indicates the coding efficiency loss denoted by BDBR. From Fig. 7, we can observe that there are no obvious change rules in the loss of coding efficiency under different t, and all the losses of coding efficiencies are very small. Obviously, the higher the threshold is, the greater the coding speed improves. Therefore, the highest threshold value, 2.807, is selected. In the above described process, both inter-layer and spatial correlations are used to predict candidate depths and skip depths with low probabilities to improve the coding speed and maintain the coding efficiency. In each candidate depth, DB-IMMD, RCB-SMET and EVB-NSMP are used to further improve the coding speed. To this end, the residual coefficients of a candidate depth are used to test for depth early termination. As mentioned above, if the prediction is accurate, the residual coefficients will obey a Gaussian distribution. Since different depths may have different likelihoods to be selected, if residual coefficients are directly used in prediction, we may not obtain optimal thresholds that meet all conditions very well. Therefore, we combine both inter-layer and spatial correlations in prediction. When both inter-layer and spatial correlations predict a depth that has a high probability to be selected, we further use residual coefficients in prediction. Thus, we can improve the coding speed and maintain the coding efficiency. Based on the above analysis, we propose depth early termination as follows:

(1)If depth of BC is 0, go to (2); else if depth of BC is 1 go to (3). ( 2)If two depths with the largest spatial probabilities are 0 and 1, these two depths have high probability to be selected. After depth The experimental parameters are set according to the CSTC [START_REF]Common SHM Test Conditions and Software Reference Configurations[END_REF]. The proposed algorithm is developed for RA coding structure. The QPs in the BL are set to [START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF][START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF][START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF][START_REF] Xiong | A New Multiplication-Free Block Matching Criterion[END_REF], and the corresponding QPs in the ELs are set to [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF][START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF][START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF][START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF] and [START_REF] Tohidypour | Content Adaptive Complexity Reduction Scheme for Quality/Fidelity Scalable HEVC[END_REF][START_REF] Tohidypour | Online-Learning-Based Mode Prediction Method for Quality Scalable Extension of the High Efficiency Video Coding (HEVC) Standard[END_REF][START_REF] Shen | Content-based adaptive SHVC mode decision algorithm[END_REF][START_REF] Cho | Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[END_REF], respectively. We have used the eight training sequences (Sunflower, Tractor, Flowervase, PartyScene, BlowingBubbles, RaceHorses, Parkruner and Town) in the four proposed strategies: CBDP, DB-IMMD, EVBNSMP and CDB-DET. More precisely, these training sequences have been used to tune the proposed approach. This demonstrates that our algorithm performs well for various sequences with diverse video content.

The proposed algorithm includes five strategies: "CBDP", "DB-IMMD", "RCB-SMET", "EVB-NSMP", and "CDB-DET". It is very complicated to separately test them. Since the proposed algorithm is developed for depth and mode predictions, the five strategies are divided into depth and mode predictions. Since both "CBDP" and "CDB-DET" are related to the depth, we combine these two strategies, referred to as "Depth", in our performance evaluation. As "DB-IMMD", "RCB-SMET", and "EVB-NSMP" are related to mode, we also integrate these three strategies in our experiments, and referred to it as "Mode". We have tested both "Depth" and "Mode" for the EL with [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF][START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF][START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF][START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF]. We adopt BDBR to evaluate the coding efficiency loss. It measures the difference of coding efficiency between the proposed algorithm and the reference software. A negative BDBR indicates that our algorithm achieves a bitrate saving. We measure the coding time in EL, and "TS" represents the coding time savings (in percentage). Table V presents the performance of the different methods.

From Table V, we find that the average coding speed improvements in "Depth", "Mode" and "Non-Square mode" are 25.78% , 60.38% and 31.30%, respectively. The average coding efficiency losses in "Depth", "Mode" and "Non-Square Mode" are 0.14% ,1.04% and 0.83%, correspondingly. After testing "Depth", "Mode" and "Non-Square Mode" methods, we further evaluate the overall performance of our proposed algorithm. We combine the five proposed strategies, i.e. CBDP, DB-IMMD, RCB-SMET, EVB-NSMP, and CDB-DET, and compare it with Hamid's algorithm [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF] as well as Shen's algorithm [START_REF] Shen | Content-based adaptive SHVC mode decision algorithm[END_REF]. For fair comparisons, all these three algorithms are implemented on the same computing platform. Two settings of QPs: Q1 = [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF][START_REF] Yeh | Coding unit complexity-based predictions of coding unit depth and prediction unit mode for efficient HEVC-to-SHVC transcoding with quality scalability[END_REF][START_REF] Bjontegaard | Calculation of average PSNR difference between RDcurves[END_REF][START_REF] Lee | Modeling rates and distortions based on a mixture of Laplacian distributions for inter predicted residues in quadtree coding of HEVC[END_REF] and Q2 = [START_REF] Tohidypour | Content Adaptive Complexity Reduction Scheme for Quality/Fidelity Scalable HEVC[END_REF][START_REF] Tohidypour | Online-Learning-Based Mode Prediction Method for Quality Scalable Extension of the High Efficiency Video Coding (HEVC) Standard[END_REF][START_REF] Shen | Content-based adaptive SHVC mode decision algorithm[END_REF][START_REF] Cho | Fast CU splitting and pruning for suboptimal CU partitioning in HEVC intra coding[END_REF] From these results, we can conclude that our algorithm can significantly improve the coding speed with small increase in coding efficiency loss. In addition, we can observe that the coding efficiency (BDBR) with Q2 is obviously degraded when compared to BDBR with Q1. This is because the QP difference between BL and EL is 6 in Table VII, whereas it is 4 in Table VI. The larger QP difference causes the weaker inter-layer correlation. Therefore, coding efficiency is obviously degraded with Q2.

When compared with Hamid's algorithm, the running time of the proposed algorithm with Q1 is improved by 10.52% in EL, while the coding efficiency loss is increased by 0.14% in terms of BDBR. With Q2, the running time of the proposed algorithm is improved by 11.97% in EL, while the coding efficiency loss is increased by 0.03% in terms of BDBR, when compared with Hamid's algorithm. When compared with Shen's algorithm, the running time of the proposed algorithm with Q1 is improved by 4.71% in EL and the coding efficiency is increased by 0.4%; the running time of the proposed algorithm with Q2 is improved by 3.86% in EL and the coding efficiency is increased by 0.6%. Therefore, we can draw the following conclusion: (1) when compared with Hamid's algorithm, the proposed algorithm's coding speed is significant faster with negligible coding efficiency loss; (2) when compared with Shen's algorithm, the proposed algorithm's coding speed is faster with significant coding efficiency increase. All these results further demonstrate the robust performance of the proposed algorithm.

The BDBRs of "BQTerrace" and "Cactus" obtained by the proposed method are larger than those obtained by Hamid's method. They correspond to the two largest differences in BDBRs between both methods. Therefore, the RD curves of these two sequences for the proposed method, Hamid [START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF], and the original SHVC are presented in Fig. 9.

From Fig. 9, we observe that RD curves for "BQTerrace" and "Cactus" for the three methods are essentially overlapping one another. In other words, the proposed method does not introduce any noticeable coding efficiency loss when compared to Hamid and the original SHVC. This also holds for other sequences which have smaller BDBR differences among these three methods.

In order to demonstrate the subjective performance, the 15th decoded video frame of Cactus and BQTerrace are shown in Fig. 10 and Fig. 11, respectively. Fig. 10 demonstrates subjective performance of the 15th frame (Cactus) using the proposed method and Hamid's method. Since the BDBR between these two methods is very small, it is extremely difficult to notice a subjective difference. Similar observations are made in Fig. 11. Therefore, we can conclude that the decoded video frames obtained by the proposed method and Hamid method have no noticeable subjective differences.

The greatly reduced complexity of the proposed algorithm is mainly due to the following reasons: (1) skipping and early terminating depths with low likelihood, based on the inter-layer and spatial correlation and residual distribution; (2) combining depth correlation and residual distribution to skip inter2Nx2N and non-square modes; (3) skipping non-square modes through comparing the difference of square modes' RD costs, and (4) skipping non-square modes with low likelihoods through testing expected values of residual coefficients.

Experiments show that both coding efficiency and coding speed under RA are significantly better than those under low-delay (LD) coding structure. Indeed, due to the worse prediction of LD structure, its residual coefficients are larger LD. As we focus on high coding efficiency and low encoding complexity in this paper, we will not further pursue the fast schemes suitable for LD structure.

VIII. CONCLUSION

In this paper, we have proposed a novel and effective inter prediction algorithm for Quality SHVC. The algorithm mainly includes depth and mode predictions. In depth prediction, the inter-layer and spatial correlations are combined to predict candidate depths and skip depths with low likelihoods. Then depths are further early terminated through combing correlations with residual distribution. In mode prediction, we first encode ILR and merge modes, and then combine depth correlation and residual distribution to skip inter2Nx2N and non-square modes. Second, we encode inter2Nx2N, and then compare RD costs of square modes to skip non-square modes. Third, we test residual coefficients to skip non-square modes with low probabilities. Since many strategies have been proposed, the proposed algorithm can significantly improve the coding speed with small encoding efficiency losses

In addition, the coding speed of depth prediction is not very high, but its coding efficiency loss is also very small. In order to improve the coding speed, we could select larger thresholds, but then its coding efficiency loss would also increase. Indeed, there is a tradeoff between coding efficiency and coding speed, and we can select the most suitable thresholds according to application requirements. The proposed algorithm can be further improved by combining with other methods [START_REF] Zhu | Enhanced hexagonal search for fast block motion estimation[END_REF][START_REF] Xiong | A New Multiplication-Free Block Matching Criterion[END_REF][START_REF] Zhu | Transform-Exempted Calculation of Sum of Absolute Hadamard Transformed Differences[END_REF]. Machine learning, especially deep learning, is attracting sig-nificant research interest, we will use these technologies to further improve the coding speed of SHVC in the future.

Fig. 1 :

 1 Fig. 1: Flowchart of the overall proposed algorithm.

Fig. 3 :

 3 Fig.3: Sum of probabilities of depth 0 and 1 and the corresponding coding efficiency loss.

Fig. 7 :

 7 Fig. 7: t and the corresponding coding efficiency for Nonsquare mode prediction

Fig. 8 :

 8 Fig. 8: Flowchart of the depth early termination

Fig. 9 :

 9 Fig.9: RD curves for the proposed method, Hamid[START_REF] Tohidypour | Probabilistic approach for predicting the size of coding units in the quad-tree structure of the quality and spatial scalable HEVC[END_REF] and the original SHVC

Fig. 11 :

 11 Fig. 11: BQTerrace -the 15th decoded frame

Dayong

  Wang Dayong Wang received the Ph.D. degree in computer science from the University of Electronic Science and Technology of China in 2010. He was a Lecturer with the Hubei University of Arts and Science from 2010 to 2012. He held a postdoctoral research position with the Graduate School, Shenzhen, Tsinghua University, from 2012 to 2015. He is currently an Associate Professor with the Chongqing University of Posts and Telecommunications, and also a Post-Doctoral Fellow with the University of Electronic Science and Technology of China. His main research interest is video coding. Yu Sun Yu Sun received the B.S. and M.S. degrees in computer science from the University of Electronic Science and Technology of China, and the Ph.D. degree in computer science and engineering from the University of Texas at Arlington in 2004. She is currently a Professor with the Department of Computer Science, the University of Central Arkansas, USA. Her main research interests include video compression, multimedia communication, and image processing. Her research work in these areas has been published in over 70 technical papers in refereed journals and conferences. She is a member of the IEEE Multimedia Communications Technical Committee and was a Co-Editor of the IEEE Distributed Systems Online. She has served as a session chair, a member of organizing committees and technical program committees for over 55 international conferences. Ce Zhu Ce Zhu (M'03-SM'04-F'17) received the B.S. degree from Sichuan University, Chengdu, China, in 1989, and the M.Eng and Ph.D. degrees from Southeast University, Nanjing, China, in 1992 and 1994, respectively, all in electronic and information engineering. He held a post-doctoral research position with the Chinese University of Hong Kong in 1995, the City University of Hong Kong, and the University of Melbourne, Australia, from 1996 to 1998. He was with Nanyang Technological University, Singapore, for 14 years from 1998 to 2012, where he was a Research Fellow, a Program Manager, an Assistant Professor, and then promoted to an Associate Professor in 2005. He has been with University of Electronic Science and Technology of China, Chengdu, China, as a professor since 2012. His research interests include video coding and communications, video analysis and processing, 3D video, visual perception and applications. He has served on the editorial boards of a few journals, including as an Associate Editor of IEEE TRANSACTIONS ON IMAGE PROCESSING, IEEE TRANSACTIONS ON BROADCASTING, IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, IEEE SIGNAL PROCESSING LETTERS, an Editor of IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, and an Area Editor of SIGNAL PROCESSING: IMAGE COMMUNICATION. He has also served as a Guest Editor of four special issues in international journals, including as a Guest Editor for an ongoing special issue of "Perceptiondriven 360-degree Video Processing" in the IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING. He is an IEEE Distinguished Lecturer of Circuits and Systems Society (2019-2020) and of Broadcast Technology Society (2012-).

  Fast Depth and Inter Mode Prediction for Quality Scalable High Efficiency Video Coding Dayong Wang, Yu Sun, Member, IEEE, Ce Zhu, Fellow, IEEE, Weisheng Li, Member, ACM, and Frederic Dufaux, Fellow, IEEE

TABLE I :

 I Inter-layer depth distribution between BL and EL

	BC			0				1				2			3
	C		0	1	2	3	0	1	2	3	0	1	2	3	0 1	2	3
	Sunflower		90	6	3	1	35 27 18 20	25 24 21	30 5 6	7	83
	Tractor		52	24 15 10	27 28 27 18	11 18 30	42 4 8 15	73
	Flowervase	81	10	5	3	9	74 10	6	8	13 25	53 3 3 14	81
	PartyScene	66	12	9	12	20 47 29	4	1	6	21	71 1 1	7	91
	BlowingBubble 48	22 16 14	26 27 38	9	1	2	52	46 1 1	7	91
	RaceHorses	25	35 24 16	33 12 52	3	0	2	30	68 1 1	6	92
	Parkrunner	55	12 16 17	27 16 43 15	1	1	60	38 0 1 14	85
	Town		80	11	6	3	21 23 33 23	1	1	73	25 0 0	7	92
	Average		62	16 12 10	25 32 31 12	6	8	39	47 2 3 10	85
	LU		U	RU
	L	C
	BLU BU BRU
	BL BC

Fig. 2: Relative CUs of current CU.

TABLE II :

 II Spatial Correlation under different correlation degrees

	QPB, QPE	0	1	2	3
	26, 22	82.0	61.0	48.0	40.0
	30, 26	71.0	49.0	25.0	21.0
	34, 30	64.0	35.0	25.0	19.0
	38, 34	66.0	41.0	15.0	14.0
	Average	70.75	46.5	28.25	23.5

TABLE III :

 III The proportions of modes in square partition

	Sequence	ILR and Merge inter 2Nx2N	intra 2Nx2N
	Sunflower	83.45	15.4	1.2
	Tractor	86.1	12.9	1.0
	Flowervase	79.0	19.9	1.1
	PartyScene	84.5	14.2	1.3
	BlowingBubble	82.9	16.5	0.6
	RaceHorses	81.1	17.5	1.4
	Parkrunner	87.5	12.1	0.4
	Town	88.1	11.6	0.3
	Average	84.1	15.0	0.9

TABLE IV :

 IV The depth correlation degree of ILR and merge modes

	Sequence	Depth Correlation Degree
	Sunflower	98.1
	Tractor	95.4
	Flowervase	97.8
	PartyScene	94.7
	BlowingBubble	95.4
	RaceHorses	92.3
	Parkrunner	96.0
	Town	98.5
	Average	96.0

  )

	0.5
	0.4
	0.3
	0.2
	0.1
	0
	1.9	2.1	2.3	2.5	2.7	2.9	3.1

TABLE V :

 V Performance comparison of the different methods

	Sequence	Depth BDBR	TS	Mode BDBR	TS	Non-Square Mode BDBR TS
	Traffic	0.1% 31.40% 1.0% 61.06% 0.9%	31.76%
	PeopleOnStreet 0.1% 10.09% 0.9% 60.64% 0.6%	28.88%
	Kimono	0.1% 32.23% 0.5% 60.43% 0.4%	25.60%
	ParkScene	0.2% 26.77% 1.0% 61.02% 0.9%	33.37%
	Cactus	0.2% 25.87% 0.9% 60.14% 0.6%	32.20%
	BasketballDrive 0.2% 26.55% 1.2% 59.13% 0.8%	30.45%
	BQTerrace	0.1% 27.57% 1.8% 60.26% 1.6%	36.86%
	Average	0.14% 25.78% 1.04% 60.38% 0.83% 31.30%

TABLE VI :

 VI Performance comparison with Q1

	Sequence	Proposed BDBR TS	Hamid [22] BDBR TS	Shen [28] BDBR TS
	Traffic	1.2% 71.21% 1.3% 59.12% 1.5%	70.0%
	PeopleOnStreet 1.0% 67.93% 0.97% 55.96% 1.9%	57.0%
	Kimono	0.8% 72.34% 0.77% 62.23% 0.9%	64.0%
	ParkScene	1.2% 72.98% 1.17% 65.79% 1.8%	69.0%
	Cactus	1.2% 71.42% 0.96% 54.26% 1.3%	67.0%
	BasketballDrive 1.5% 71.86% 1.35% 65.83% 2.1%	67.0%
	BQTerrace	2.1% 70.26% 0.68% 61.16% 2.1%	71.0%
	Average	1.27% 71.14% 1.13% 60.62% 1.67% 66.43%

TABLE VII :

 VII Performance comparison with Q2

	Sequence	Proposed BDBR TS	Hamid [22] BDBR TS	Shen [28] BDBR TS
	Traffic	2.5% 66.86% 2.2% 54.11% 3.50% 68.00%
	PeopleOnStreet 2.2% 65.14% 2.4% 53.23% 2.40% 54.00%
	Kimono	1.8% 67.92% 1.9% 56.17% 1.90% 60.00%
	ParkScene	2.1% 68.87% 2.2% 60.74% 3.20% 67.00%
	Cactus	2.1% 66.14% 2.0% 52.18% 2.20% 64.00%
	BasketballDrive 2.3% 68.27% 2.6% 52.21% 3.30% 64.00%
	BQTerrace	2.1% 68.86% 1.8% 59.63% 3.20% 68.00%
	Average	2.21% 67.43% 2.18% 55.46% 2.81% 63.57%

  are used. The overall performance of our algorithm and Hamid's algorithm are listed in Table VI and Table VII, with Q1 and Q2 respectively. From Table VI and Table VII, it can be observed that the proposed algorithm can reduce coding time by an average of 71.14% and 67.43% for Q1 and Q2, respectively. The average BDBR increases by 1.27% and 2.21%, respectively.

This work was supported in part by the Natural Science Foundation of China under Grant 61401247, 61571102, U1713213, and 61972060, in part by Chongqing science and Technology Commission Project under Grant cstc2016jcyjA0543, cstc2017jcyjAX0142, cstc2018jcyjAX0525, cstc2018jcyjAX0225 and cstc2018jszx-cyzdX0124, in part by the Key Project of Sichuan Provincial Department of Science and Technology under Grant 2018JY0035, in part by Project of Sichuan Provincial Department of Science and Technology under Grant 2018RZ0072, in part by Open Project of Hubei University of Arts and Science under Grant XK2018013, in part by International Science and Cooperation Project of Hubei Province under Grant 2019AHB059, in part by faculty sabbatical leave fund from Uni. of Central Arkansas.

Frederic is a Fellow of IEEE. He is Chair of the IEEE SPS Multimedia Signal Processing (MMSP) Technical Committee and Chair of the EURASIP Special Area Team on Visual Information Processing. He has been involved in the standardization of digital video and imaging technologies, participating both in the MPEG and JPEG committees. He is the recipient of two ISO awards for his contributions.

His research interests include image and video coding, 3D video, high dynamic range imaging, visual quality assessment, and video transmission over wireless network. He is author or co-author of 3 books ("High Dynamic Range Video", "Digital Holographic Data Representation and Compression", "Emerging Technologies for 3D Video"), more than 200 research publications and 20 patents issued or pending.


Mourad Aklouf
email: maklouf@ektacom.com

Marc Leny
email: mleny@ektacom.com

Frederic Dufaux
email: frederic.dufaux@l2s.centralesupelec.fr

Michel Kieffer
email: michel.kieffer@l2s.centralesupelec.fr

LOW COMPLEXITY VERSATILE VIDEO CODING (VVC) FOR LOW BITRATE APPLICATIONS

Keywords: Versatile Video Coding, video compression, optimization, low complexity, low resolution, low bitrate

The new Versatile Video Coding (VVC) standard is currently under development, targeting more efficient compression, especially for 4K and 8K contents. Nevertheless, some application scenarios still require low resolution and low bitrate encoding, e.g., live video streaming over unstable bandwidth-limited wireless networks. In addition, embedded applications also require low complexity and low power consumption solutions. As VVC is not designed for these conditions, it may not necessarily achieve the optimal tradeoff between complexity and compression efficiency. This paper proposes an optimization framework to determine the efficiency at lowresolution and low-bitrate of some of the new coding tools introduced in VVC. We show that in such coding conditions, significant reduction in terms of encoding complexity (up to 56% at 384 × 216 resolution) may be obtained by disabling some of the VVC coding tools, with a negligible impact in terms of compression efficiency (less than 1.88% increase in BDrate).

INTRODUCTION

Video traffic over Internet is continuously increasing. Video is foreseen to represent 82% of all consumer Internet traffic by 2021, 26% of which will be Internet video-to-TV traffic. Moreover, Content Delivery Network (CDN) traffic will carry 71% of all Internet traffic by 2021 [START_REF]Cisco visual networking index: Forecast and trends, 2017-2022[END_REF].

This congestion is mainly due to users expecting better quality of experience, including High Definition (HD) and Ultra-High Definition (UHD) video content. UHD, including 3840 × 2160 (4K) and 7680 × 4320 (8K) formats, is expected to become mainstream. For instance, 4K TVs are already available since 2014, and 8K consumer TVs are expected in 2020. Even portable devices are expected to handle UHD in the next few years, due to increasing hardware power and efficiency of IP networks. In this context, the need for new efficient video compression tools is clear, on one hand to decrease the load on transmission channels and storage servers, and on the other hand to provide high-quality content to end-users.

The High-Efficiency Video Coding (HEVC) standard [START_REF] Sullivan | Deployment status of the HEVC standard[END_REF] is the latest standard developed by the Joint Collaborative Team on Video Coding (JCT-VC) of VCEG and MPEG. It is effectively deployed worldwide and compares favorably with competing solutions [START_REF] Grois | Performance comparison of av1, jem, vp9, and hevc encoders[END_REF]. Nevertheless, more efficient video compression techniques are still desired. With this goal in mind, the new Versatile Video Coding (VVC) standard is currently under development by the Joint Video Exploration Team (JVET) of VCEG and MPEG and is expected to be finalized by 2020 [START_REF] Convenor | N17482: Versatile video coding project starts strongly in the joint video experts team[END_REF].

While the above standards are mainly focused on HD and UHD content, efficient video compression solutions are also requested for streaming Standard Definition (SD) video (or even lower resolutions) over unstable bandwidth-limited networks. Indeed, whereas HD video is now the standard on the Internet, low-resolution contents are still used, especially 480p and 360p. In this paper, we specifically consider use cases such as the acquisition and live streaming of low-resolution (less than HD) sport events (e.g., car races and sailing races) over relatively unstable wireless networks including LTE and satellite transmissions. For such use cases, transmission bandwidth when using common wireless networks is typically in the range of 50 to 700 kbps. Moreover, low computational complexity and low power consumption solutions are highly desired for embedded systems.

As current VVC developments are not designed for such use cases, some of the design choices for HD and UHD may not be optimal for lower resolutions and low-bitrates. More precisely, a variety of encoding tools available at the VVC encoder may entail a significant burden in terms of computational complexity. Moreover, some of these tools may not be suited in the case of low resolution and low bitrate scenarios. In particular, the cost of syntax elements to signal the activation of these tools may represent a non-negligible overhead at low bitrates.

The contribution of this paper is two fold. We first propose an optimization framework with the objective to tune VVC for lowresolution and low-bitrate scenarios. More specifically, we investigate the usefulness of some of the new coding tools in VVC. Second, we experimentally show that significant complexity reduction can be achieved (up to 56.06% reduction for Johnny sequence at 384 × 216 resolution) by disabling some of these tools, while preserving coding efficiency (less than 1.88% increase in BDrate). To the best of our knowledge, this is the first study to investigate VVC at low resolutions and low-bitrates, and to report such complexity reduction results.

The remaining of this paper is structured as follow. Some related works are first reviewed in Section 2. Section 3 provides a brief overview of the technical features of the VVC standard and the coding tools in the VVC Test Model (VTM). The problem formulation and proposed optimization framework are introduced in Section 4. Experimental results are reported in Section 5. Finally, we draw some conclusions in Section 6.

RELATED WORKS

The problem of encoder optimization has already been largely addressed in the literature. In particular, many proposals have considered the simplification of the Rate Distortion Optimization (RDO) process of the HEVC encoder. Targeting the Coding Unit (CU) size and depth decision, an algorithm to quickly determine the CU size has been proposed in [START_REF] Zhang | An effective cu size decision method for hevc encoders[END_REF] for both Intra and Inter modes. To reduce the number of Intra mode candidates, [START_REF] Zhao | Fast mode decision algorithm for intra prediction in hevc[END_REF] uses the coding information of the neighboring blocks. Conversely, [START_REF] Da Silva | Fast HEVC intra prediction mode decision based on EDGE direction information[END_REF] introduces a decision algorithm, which compute the dominant edge of the Prediction Unit (PU) using the local samples. Targeting the Motion Vectors (MVs) search in Inter prediction, [START_REF] Sampaio | Motion vectors merging: low complexity prediction unit decision heuristic for the inter-prediction of HEVC encoders[END_REF] presents an heuristic to determine the PU partition by checking all CUs among the neighboring NxN partition.

All the previous approaches make algorithmic modifications to the non-normative encoding process. In this paper, our aim is to identify coding tools which can be ignored in low-bitrate use cases, with a greatly reduced complexity and a preserved coding efficiency. This could lead to the definition of application-oriented profiles, where some tools are automatically disabled in the highlevel syntax.

VERSATILE VIDEO CODING (VVC)

VVC [START_REF]Versatile video coding (vvc)[END_REF] is a new video coding standard designed by JVET, which goal is to provide significant improvements in compression performance over the existing HEVC standard, with a target of 50% bitrate saving. VVC is expected to deliver UHD services (4K and 8K) at approximately the same bit rates used today to carry HDTV. The requirements for VVC include capabilities of encoding 4K and 8K sequences of up to 120 fps [START_REF] Convenor | N15340: Requirements for a future video coding standard v1[END_REF]. In what follows, some of the coding tools in VTM5.0 are overviewed [START_REF] Chen | Jvet-n1002-v1: Algorithm description for versatile video coding and test model 5 (vtm 5)[END_REF].

Partitioning

Each frame is divided into a sequence of coding tree units (CTUs) just as in the HEVC standard, although the maximum size of the Luma CTU is up to 128 × 128. For each CTU, a Quad-Tree with nested Multi-Type Tree (MTT) using Binary and Ternary splitting structures is used (QTBT-TT). The CTU is first partitioned recursively using a quad-tree structure into square shapes. Then, the quad-tree leaf nodes can be further partitioned horizontally or vertically by a binary or ternary splitting structure. The final nodes are called Coding Units (CUs). They have either a square or rectangular shape and are used directly for prediction and residual coding. Lastly, I-slices can have separate block tree structures for Luma and Chroma (DualTree).

Intra-Picture Prediction

VTM5.0 supports 65 angular intra-prediction modes, in addition to the planar and DC modes. Some conventional angular modes are replaced with wide-angle intra-prediction modes for the non-square blocks. A Multiple Reference Line (MRL) intra prediction is also proposed to use two additional lines (reference line 1 and reference line 3) in angular prediction. VTM5.0 also extends the Most Probable Modes (MPM) list to 6 candidates.

VTM5.0 introduces three new ways of Intra predicting a block: (1) the Cross-Component Linear Model (CCLM) prediction mode, in which the Chroma samples are predicted based on the reconstructed Luma samples of the same CU, using a linear model; [START_REF] Sullivan | Deployment status of the HEVC standard[END_REF] The Intra Sub-Partitions (ISP) where the Luma CB is vertically or horizontally divided into 2 or 4 sub-partitions. All sub-partitions share the same intra mode, however the processing is performed gradually sub-partition by sub-partition downwards (horizontal split) or rightwards (vertical split), so each one uses the previous reconstructed samples to generate the prediction of the current sub-partition; (3) The Matrix-based Intra Prediction (MIP) takes one line of reconstructed neighboring samples, from the left and above blocks as input vectors, and after some pre-processing, performs linear interpolation in the vertical and horizontal directions.

Inter-Picture Prediction

Motion prediction is performed at a sub-CU level to improve the precision. VTM5.0 supports currently a Sub-Pu Temporal Motion Vector Prediction (SbTMVP). Furthermore, an AFFine motion compensation prediction (AFF) can be applied to cope with irregular motions like zoom in/out and rotation, where a sub-block is described by two or three motion vectors.

The bi-prediction mode is extended beyond simple weighted averaging, by using up to five predefined weights (Generalized Bi-prediction (GBI)) and a pixel level motion refinement (Bi-Directional Optical Flow (BDOF)) may be performed on top of it. In order to increase the accuracy of the MVs of the merge mode, a refined operation may be performed around the initial MVs in both reference picture lists L0 and L1 using the Decoder side Motion Vector Refinement (DMVR). Motion vectors are stored at 1/16th-Luma-sample precision for Luma. In addition, the Adaptive Motion Vector Resolution (AMVR) allows the Motion Vector Difference (MVD) of the CU to be coded in one of the three resolutions: Quarter-luma-sample, Integer-luma-sample, and Four-luma-sample (or 1/16 luma-sample in AFF).

Finally, the VTM5.0 inter coder introduces these new concepts: (1) the Triangular prediction (Triang) in which a CU may be further split into two triangular units, in either diagonal or inverse diagonal direction. Each of the two units is predicted using its own Uni-directional MV; (2) Combined Inter and Intra Prediction (CIIP) is proposed to improve the Intra mode in inter pictures, by combining the decided Intra mode with an extra merge indexed prediction;

(3) Merge with MVD scheme (MMVD) is used for skip and merge modes with a new motion vector expression method with simplified signaling: The expression method includes starting point, motion magnitude, and motion direction; (4) Symmetric MVD (SMVD), which derives the MVD of reference list 1 from reference list 0, based on the assumption of linear motion in bi-prediction mode.

Quantization

The maximum Quantization Parameter (QP) is extended from 51 to 63, and a new concept of quantization is introduced: The Dependent Quantization (DepQuant), in which the reconstruction value for a transform coefficient depends on the value of the transform coefficient that precedes it in the reconstruction order.

Transform

Large block-size transforms, of up to 64x64 pixels, are used. Highfrequency transform coefficients are zeroed out, so that only the lower-frequency coefficients (top-left 32 × 32 block) are retained. VTM5.0 uses Enhanced Multiple Transform (EMT), where two new transform matrices are added in addition to DCT-II, namely the DST-VII and the DCT-VIII. Moreover, to reduce the size of the matrices of transformed coefficients, a Low-Frequency Non-Separable Transform (LFNST) is applied between transform and quantization at encoder and between de-quantization and inverse transform at decoder side.

In-loop Filtering

Besides deblocking filter and Sample Adaptive Offset (SAO) used in HEVC, the Adaptive Loop Filter (ALF) is applied directly on the reconstructed samples of the SAO process, where one filter among 25 filters is selected for each 4 × 4 block, based on the direction and activity of local gradients. Nevertheless, the Luma Mapping with Chroma Scaling (LMCS) is performed before the in-loop filtering. This tool adjusts the input luma signal by redistributing it across the dynamic range using a piecewise linear mapping function and scale the chroma residuals according to the average value of the corresponding luma samples. For an inter-predicted CU, the Sub-Block Transform for inter blocks (SBT) may be used instead of EMT to code only a part of the residual block with inferred adaptive transform and the other part of the residual block is zeroed out.

Entropy Coder

VVC still uses the same entropy coding method used in HEVC (Context-adaptive binary arithmetic coding (CABAC)), but with some changes: The CABAC engine uses a 2-state model with variable probability updating window sizes, instead of the pre-computed LUT of the HEVC. The transform coefficients within a Coefficient Group (CG) are coded according to pre-defined scan orders in five passes. And finally, the selected probability model and binarization models depend on the local neighborhood, where the template used to specify the local neighborhood is defined by the 5 nearby samples in the left-bottom of the current coefficient. For more information about VVC CABAC, refer to [START_REF] Chen | Jvet-n1002-v1: Algorithm description for versatile video coding and test model 5 (vtm 5)[END_REF].

VVC is mainly targeting 4K and 8K video resolutions. The added coding tools compared to HEVC imply new syntax elements in the bitstream, including flags. While this is not an issue at high resolutions and high-bitrates, it may represent an unnecessary overhead at low resolutions and low-bitrates.

PROPOSED METHODOLOGY

Our aim in what follows is to identify the subset of coding tools that may be disabled in low-resolution and low-bitrate use cases, to provide a significant reduction in terms of coding complexity, while preserving compression efficiency. This can be formulated as a constrained optimization problem, which is solved using a branch-andprune approach. This technique identifies the individual tools and combination thereof that may be safely disabled, and those that have to be kept activated.

Problem Formulation

Consider a set of video sequences V = {v1, . . . , vN }. The performance of a video encoder can be measured by the rate R (in Kbps) required to store the compressed videos, the resulting distortion D of the decoded videos (typically measured using the weighted average PSNR of the three components Y, U, and V [3]), and the complexity C of the encoding process (approximated by the run-time, measured in seconds). The values of the triple (R, D, C) depend on the input video sequence vn and on the encoding parameter vector p = p1, . . . , pn p of the video coder as follows

(R, D, C) = f (vn, p) , (1)
where f is some (unknown) nonlinear function describing the behavior of the considered video coder. The components of p represent the coder input parameters, which may be adjusted to get different trade-offs between R, D, and C. The parameter vector p may be partitioned into subvectors. One may identify:

-pT representing binary-valued parameters indicating whether some tools are activated or remain unused;

p C representing a finite-valued of configuration inputs for the preceding tools, e.g., the TargetBitrate and InitialQP must be specified for the Rate Control, both are integer values;

p O corresponding to other parameters which do not belong to any tool, e.g., GOP size and GOP type configurations.

To properly evaluate the performance of a coding tool, several target values of the rate R have to be considered. In our work, we use the Bjontegaard Delta Rate (BDrate) [START_REF] Hanhart | Calculation of average coding efficiency based on subjective quality scores[END_REF] to evaluate the loss of a set P1 = {p } of values of the parameter vector. The vectors p (i) j ∈ Pj, j = 1, 2 share the same components pT,j, pC,j, and pO,j, but take distinct QP values QP (i) , i = 1, . . . , nDR, with nDR ≥ 4.

Sets of parameter vectors Pj are called parameter configuration sets (PCS) in what follows.

Consider some reference PCS P, corresponding, e.g., to the best rate-distortion compromise for a set of video sequences. Our aim is to find a PCS P such that

P = arg min P C (P) (2)
such that BDrate(v, P, P) ∆rate,

R (i) , D (i) , C (i) = f v, p (i) , p (i) ∈ P (3)
where ∆rate > 0 is the largest tolerated loss in terms of BDrate and C (P) = n DR i=1 C (i) . P is a PCS minimizing the complexity, while keeping good compression performance compared to the optimal parameter set.

Search for a good Parameter Configuration Set

In what follows, we propose a method to solve the optimization problem (2) in an approximate way. Our approach concentrates on finding the subvector pT,j indicating the activated and disabled tools.

Consider p (i) T ∈ P, the parameter vectors indicating the set of tools activated in the reference PCS. First, one builds all candidate PCS P1,j = {p where the numerator of λj is the relative complexity decrease provided by the PCS P1,j. Third, the set P1 is split into two parts P2, containing the n2 n 1 first elements of P1 and P3 containing the remaining elements. The set P2 contains the most promising candidates PCS with a single tool disabled compared to P. The greedy approach presented in Algorithm 1 is then used to combine candidate PCS, i.e., disable more tools, while satisfying (3). In Algorithm 1, assuming that P1 = {p Algorithm 1 progressively disable tools corresponding to the PCS in P2, starting with the most promising PCS. When disabling a tool results in a complexity reduction while satisfying (3), the PCS is updated. Tools, when disabled, do not reduce the complexity or lead to a large loss in BDrate are kept activated.

(i) T,j , p (i) T ) = 1,
Finally, a branch-and-prune approach presented in Algorithm 2 is considered, starting from the PCS P1 provided by Algorithm 1 to select additional tools to disable corresponding to PCS in P3. One tries first to disable a single additional tool from P1 corresponding to the various PCS in P3. All PCS P ∈ P3 such that P1 ∧ P leading to a performance decrease compared to P1 are discarded from P3. Then pairs, triples, etc. of PCS remaining in P3 are considered. Then the PCS P = P1 ∧ P2 is an approximate solution of (2).

Input

PERFORMANCE EVALUATION

Experimental setup

We selected 14 JVET test sequences defined in the Common Test Conditions (CTC) [START_REF] Suzuki | Jvet-d1002 : Work plan for assessment of test material[END_REF], each one of the sequences has at most 300 images. In a first phase, 7 sequences were considered to apply our approach and identify the best PCSs. Then, in a second phase, tests are conducted on all sequences to evaluate the performance obtained with the previously identified best PCSs.

All sequences have been temporally sub-sampled at 30 fps and spatially sub-sampled using FFmpeg [START_REF]ffmpeg tool (build: ffmpeg-20180716-8aa6d9a-win64-static)[END_REF] resulting in frames of 384 × 216, 512 × 288, and 640 × 360 pixels. A Random Access (RA) configuration is selected according to JVET CTC [START_REF] Suzuki | Jvet-d1002 : Work plan for assessment of test material[END_REF] and QP values are chosen in {27, 32, 37, 42}. VTM5.0 is used in the experiments and run on a PC with 2 Intel Xeon CPU E5-2670 v3 24 cores @ 2.30 GHz running under Linux. The threshold ∆rate is fixed to 2% as we have noticed that this loss is subjectively unnoticeable. The value of n2 helps to get a trade-off between complexity and accuracy in the search for P. Here, we take n2 = n 1 /2. The new tools of VTM5.0 we have tested in this work are listed in Table 1 1. New tools of VTM5.0 tested in this work

Analysis

In this section, we present experimental results in order to illustrate the proposed approach. Table 2 presents the detailed BDrate and complexity reduction C when disabling one tool at a time for the Johnny sequence of resolutions 384×216, 512×288 and 640×360. These percentages are calculated relative to VTM5.0 with all tools activated (a negative BDrate indicates a gain with respect to VTM5.0).

From Table 2, one observes that disabling tools related to interframe coding (e.g., AFF, MMVD, and Triang in resolutions 384 × 216) and inloop filtering (ALF, LMCS) leads to significant gains in complexity. Other tools related to transform operations such as LFNST and EMT also lead to a significant complexity decrease. Disabling a tool can sometimes lead to an improved BDrate when operating at low resolutions and low-bitrates, such as LMCS, SMVD

and AMVR.

Table 3 shows the BDrate and complexity reduction C for the best combination of disabled tools as obtained by the method de-scribed in Section 4.2 for seven test sequences and three resolutions. When several tools are disabled, the complexity gains accumulate in most of the cases. Nevertheless, this observation does not hold for BDrate, due to the complex dependency among tools and their influence on the coding efficiency. Considering Johnny at the resolution of 384 × 216, jointly disabling the tools: { LMCS GBI LFNST MMVD MIP CIIP SMVD MRL SBT Triang AFF AMVR SbTMVP }, leads to a complexity reduction of 56.06%, with a BDrate loss of 1.88%. For resolutions of 512 × 288 and 640 × 360, a complexity reduction of 57.01% and 55.24% is achieved with a BDrate loss of 1.97% and 1.92% respectively. Similar results are obtained when applying the same methodology on other sequences such as, BasketballDrive, DaylightRoad2, BQMall, Drums, RaceHorses and Kimono.

These results are obtained by merely disabling tools and without algorithmic optimization. Nevertheless, the combination of tools that provide the optimal complexity reduction is different from one sequence to the other and even from one resolution to the other. The amount of complexity reduction is also varying. This is due to the spatial and temporal properties of sequences.

Yet, for each resolution, using the results of Table 3, it is possible to identify one common combination of tools satisfying constraint (3) for all sequences. Accordingly, these PCSs are: {LMCS GBI LFNST MMVD EMT MIP CIIP} for resolution 384 × 216, {LMCS CIIP MMVD SMVD EMT LFNST} for 512 × 288, and {LMCS MIP CIIP EMT SMVD MRL GBI MMVD} for 640 × 360. Table 4 shows the BDrate and complexity reduction C for the previously identified PCSs considering the 14 test sequences. We observe that the constraint (3) is satisfied in most cases. Thus, putting these PCSs in separate profiles for each resolution will be beneficial for use cases with real-time and low-bitrate constraints. We conclude that the PCS identification approach presented in this paper provides results that are likely to be generalized to a larger set of video sequences.

CONCLUSIONS

This paper proposes an optimization of the next generation VVC targeting low-resolution video sequences encoded at low-bitrates (less than 700 kbps). The aim is to identify a set of coding tools which may be disabled while preserving coding efficiency. For this purpose, a branch-and-prune approach is proposed to determine the set of coding tools which provide the best complexity reduction, while satisfying a constraint on the BDrate degradation.

Experimental results show that significant reduction of encoding complexity can be achieved, with negligible BDrate loss. For instance, the joint disabling of the tools { LMCS MMVD AFF MIP Triang SMVD AMVR GBI CIIP MRL SbTMVP SBT LFNST } leads to a complexity reduction of 56%, with a loss of 1.88% in BDrate, for Johnny at a 384 × 216 resolution. Moreover, a common combination of tools to disable for each resolution was determined. Our experimental results show that these common PCSs most likely cause less than 2% BDrate loss with good reduction in terms of encoding complexity, which is beneficial for use cases with real-time and low-bitrate constraints.

1 }

 1 compared to another set P2 = {p (1) 2 , . . . , p (n DR ) 2

( 1 )

 1 j , . . . , p (n DR ) j }, j = 1, . . . , n1 with subvectors p (i) T,j obtained by disabling a single tool activated in p (i) T , i.e., dH(p

1 }

 1 and P2 = {p

2 } 1 :

 21 , the notation P1∧ P2 corresponds to the PCS P3 = P1 ∧ P2 = {p Initialization: extract P1, the first element of P2; while P2 = ∅ do Extract P2, the next element of P2; if C (P1 ∧ P2) C (P1) and BDrate(v, P, P1 ∧ P2) ∆rate then P1 = P1 ∧ P2; end end Algorithm Evaluating the best PCS

  where dH is the Hamming distance. Only the candidate PCS such that (3) is satisfied are further considered, the others are pruned.

	Second, assuming that n 1	n1 PCS satisfy (3), these PCS are
	sorted. PCS with gains in terms of BDrate are sorted first, and then
	PCS with a good complexity reduction and a small BDrate loss. Let
	P1 = P 1,1 , . . . , P 1,n 1	be the ordered set of these PCS. The PCS
	providing a gain in terms of BDrate (negative BDrate) are ordered first
	in P1 by decreasing BDrate gain. Then, the PCS providing a BDrate
	loss (positive BDrate) are ordered by decreasing value of

λj =

C P -C (P1,j) /C P BDrate(v, P, P1,j) ,

  .

	DualTree Separate Partitioning for Luma & Chroma in I-slice
	CCLM	Chroma prediction based on linear model
	MRL	Multiple Reference Line intra prediction
	MIP	Matrix-based Intra prediction
	ISP	Intra Sub-Partitions
	CIIP	Combined Inter and Intra prediction
	SbTMVP	Sub-Pu Temporal Motion Vector Prediction
	AFF	AFFine inter motion compensation
	MMVD	Merge with MVD
	SMVD	Symmetric MVD
	Triang	inter predictions for Triangular Units
	GBI	Generalized Bi-prediction
	BDOF	Bi-Directional Optical Flow
	DMVR	Decoder Side Motion Vector Refinement
	AMVR	Adaptive MV Resolution
	EMT	Enhanced Multiple Transform
	LFNST	Low-Frequency Non-Separable Transform
	SBT	Sub-Block Transform for inter blocks
	LMCS	Luma Mapping with Chroma Scaling
	ALF	Adaptive Loop Filter
	Table

Table 2 .

 2 BDrate and complexity reduction C in "Johnny" test sequence when disabling one tool at time

		Johnny at 384x216				Johnny at 512x288			Johnny at 640x360
	Disabled Tools	BDrate%	C%	λ	Disabled Tools	BDrate%	C%	λ	Disabled Tools	BDrate%	C%	λ
	LMCS	-0.42	10.77	-	LMCS		-0.40	13.28	-	BDOF	-0.29	13.20	-
	SMVD	-0.01	8.30	-	SMVD		0.02	8.98	422.56	SMVD	-0.08	9.67	-
	AMVR	-0.01	8.46	-	MMVD		0.15	15.56	104.76	LMCS	-0.07	9.85	-
	GBI	0.01	8.74	1544.07	BDOF		0.14	10.83	77.86	MMVD	0.10	15.67	161.51
	CIIP	0.03	7.98	271.58	ISP		0.37	20.55	55.37	CIIP	0.06	7.65	121.65
	MMVD	0.20	14.21	72.12	CIIP		0.14	7.46	52.16	AMVR	0.15	10.06	66.67
	AFF	0.29	16.59	57.98	AFF		0.58	19.87	34.48	AFF	0.58	18.72	32.06
	MIP	0.14	8.30	57.41	AMVR		0.26	8.60	33.43	Triang	0.41	11.39	28.00
	Triang	0.28	10.04	36.47	Triang		0.39	11.69	29.77	MIP	0.45	9.30	20.75
	MRL	0.20	7.23	36.01	SBT		0.31	6.72	21.92	SbTMVP	0.28	4.54	16.50
	SbTMVP	0.14	4.81	34.35	MIP		0.45	7.81	17.32	SBT	0.24	3.80	15.60
	SBT	0.07	1.64	24.45	MRL		0.39	6.38	16.27	EMT	0.42	6.05	14.49
	EMT	0.34	7.01	20.77	SbTMVP		0.32	5.08	16.04	GBI	0.69	9.71	14.04
	ALF	1.60	28.15	17.55	GBI		0.78	9.72	12.45	ISP	0.49	5.88	11.94
	LFNST	0.87	12.30	14.12	LFNST		1.07	12.89	12.03	LFNST	1.36	12.69	9.33
	BDOF	0.76	9.56	12.65	EMT		0.51	5.89	11.45	ALF	2.11	18.04	8.56
	ISP	0.55	6.35	11.59	ALF		1.98	20.55	10.38	MRL	0.74	5.81	7.87
	DMVR	0.59	5.30	8.95	CCLM		0.82	6.28	7.70	CCLM	0.88	5.46	6.18
	CCLM	0.79	5.94	7.50	DMVR		0.91	4.35	4.76	DMVR	0.78	4.48	5.72
	DualTree	0.29	-2.29	-7.94	DualTree		0.32	-1.71	-5.37	DualTree	0.70	-3.00	-4.32
	Resolution	Video	R Kbps	BDrate%	C%	Disabled Tools
		Johnny	18-72		1.88	56.06	LMCS GBI LFNST MMVD MIP CIIP SMVD MRL SBT Triang AFF AMVR SbTMVP
		Basketball	48-368		1.97	37.07	LMCS GBI LFNST EMT MIP CIIP SMVD
		DaylightRoad2	48-367		2.00	48.91	LMCS GBI LFNST MMVD EMT MIP CIIP MRL SBT Triang
	384x216	BQMall	50-331		1.98	44.93	LMCS GBI MMVD EMT MIP CIIP SMVD AFF CCLM
		Drums	89-538		1.74	43.27	LMCS GBI LFNST EMT MIP CIIP SMVD MRL AFF SbTMVP
		RaceHorses	50-403		2.00	38.82	LMCS GBI LFNST MMVD EMT MRL SBT
		Kimono	27-271		1.91	51.21	LMCS GBI LFNST MMVD EMT SMVD MRL AFF ISP
	Average	-	-		1.93	45.75	-
		Johnny	23-102		1.97	57.01	LMCS CIIP MMVD AFF Triang SBT ISP BIO AMVR
		Basketball	75-576		1.81	35.25	LMCS CIIP EMT LFNST SMVD MRL MIP SBT
		DaylightRoad2	75-575		1.88	48.37	LMCS CIIP EMT LFNST MMVD MRL MIP GBI Triang SBT
	512x288	BQMall	71-477		1.82	34.92	LMCS CIIP EMT MMVD SMVD MRL GBI CCLM
		Drums	125-661		2.00	35.25	CIIP EMT LFNST SMVD AFF CCLM SbTMVP
		RaceHorses	78-763		1.79	34.34	LMCS CIIP EMT LFNST SMVD AFF CCLM SbTMVP
		Kimono	41-427		1.84	47.78	LMCS CIIP EMT LFNST MMVD SMVD MRL ISP AFF IMV
	Average	-	-		1.87	41.85	-
		Johnny	30-148		1.92	55.24	LMCS MIP SMVD CIIP MMVD AFF Triang AMVR BIO
		Basketball	99-700		1.89	32.45	LMCS MIP SMVD EMT LFNST SbTMVP
		DaylightRoad2	100-702		1.89	41.68	LMCS MIP SMVD MRL GBI EMT MMVD LFNST SBT
	640x360	BQMall	95-639		2.00	36.99	LMCS MIP SMVD MRL GBI EMT MMVD CCLM
		Drums	164-789		1.83	41.26	LMCS MIP SMVD MRL GBI CIIP AFF SbTMVP
		RaceHorses	109-631		1.30	40.17	LMCS MIP SMVD MRL GBI EMT CIIP MMVD SBT ISP
		Kimono	54-531		1.80	45.77	LMCS SMVD MRL GBI CIIP LFNST AFF Triang
	Average	-	-		1.80	41.94	-

Table 3 .

 3 BDrate and complexity reduction C of best PCS for tested resolutions and sequences; Selected common tools are in bold

		384x216		512x288		640x360
	Common Tools	LMCS GBI LFNST MMVD EMT MIP CIIP	LMCS CIIP MMVD SMVD EMT LFNST	LMCS MIP CIIP EMT SMVD MRL GBI MMVD
	Video	BDrate%	C%	BDrate%	C%	BDrate%	C%
	Johnny	2.34	38.76	2.13	39.13	0.99	42.01
	Basketball	2.00	37.95	1.83	24.57	1.57	26.03
	DaylightRoad2	0.68	38.96	0.94	35.26	0.98	35.44
	BQMall	1.24	37.81	1.59	35.73	1.33	35.31
	Drums	1.87	37.94	1.63	34.12	1.21	35.12
	RaceHorses	1.87	35.65	1.56	33.96	0.33	26.45
	Kimono	0.94	41.60	1.83	38.24	2.39	35.47
	ParkScene	0.90	42.25	0.77	41.26	0.85	42.71
	KristenAndSara	1.99	38.62	1.87	38.93	0.96	39.32
	CatRobot	1.42	42.58	1.41	37.39	1.27	23.79
	Tango	1.20	38.55	1.58	36.06	0.95	35.18
	ToddlerFountain	1.20	38.55	1.58	36.06	1.43	39.89
	SlideShow	1.52	27.20	1.44	23.61	2.88	23.03
	SlideEditing	1.09	41.68	0.63	39.72	1.64	40.25
	Average	1.45	38.44	1.49	35.29	1.34	34.29

Table 4 .

 4 BDrate and complexity reduction C when disabling the common combinations of tools. Highlighted cells do not satisfy (3).