Dayong Wang
email: wangdayong@cqupt.edu.cn

Xin Lu
email: xin.lu@dmu.ac.uk

Yu Sun
email: yusun@uca.edu

Qianmin Wang

Member, IEEE Weisheng Li

Fellow, IEEE Frederic Dufaux
email: frederic.dufaux@l2s.centralesupelec.fr

Fellow, IEEE Ce Zhu

A Probability-Based Zero-Block Early Termination Algorithm for QSHVC

Keywords: SHVC, probability, AII-Zero Block, Partial-Zero Block. I

To seamlessly adapt to time-varying network bandwidths, the Quality Scalable High-Efficiency Video Coding (QSHVC) is developed. However, its coding process is overly complex, and this seriously limits its wide applications in realtime environments. Therefore, it is of great significance to study fast coding algorithms for QSHVC. In this paper, we propose a novel probability-based zero-block early termination algorithm for QSHVC. First, we observed that the generated residual coefficients follow the Laplace distribution if a CU is accurately predicted. According to this observation, we derive the sum of squared differences based All-Zero Block (AZB) decision condition. Second, we develop the Hadamard Transform (HT)based zero-valued quantized coefficient decision condition to obtain zero-valued quantized coefficients and the corresponding Partial-Zero Block (PZB). Third, the probability of each coding mode and coding depth being chosen as the best ones are combined with both AZBs and PZBs to derive the probabilitybased early termination condition. The experimental results show that the proposed algorithm can improve the average coding speed by 79.85% with a 0.34% decrease in BDBR.

pandemic crisis. Heterogeneous networks with time-varying channel bandwidths are used in visual communication, and bandwidth fluctuates even working under the same network environment. This requires video streams to be scalable to a variety of network bandwidths. Quality Scalable High-Efficiency Video Coding (QSHVC) is developed to effectively address this need [START_REF] Wang | Probability-Based Fast Intra Prediction Algorithm for Spatial SHVC[END_REF].

QSHVC is one of the scalable versions of the High Efficiency Video Coding (HEVC) standard. To achieve scalable quality, SHVC uses a Base Layer (BL) and one or more Enhancement Layers (ELs) to encode the same video sequence. Each layer is encoded with a different Quantization Parameter (QP) to achieve several video representations with different picture quality [START_REF] Boyce | Overview of SHVC: Scalable Extensions of the High Efficiency Video Coding Standard[END_REF]. The identical encoding process as in HEVC is applied on the BL, and the additional Inter-layer prediction is employed to encode the ELs, where Inter-Layer Reference (ILR) modes are introduced. Given that HEVC is quite complex, the computational complexity of QSHVC is even much greater than that of HEVC. This seriously prevents the extensive deployment of QSHVC in real-time scenarios. It is therefore of great significance to develop fast coding algorithms for QSHVC [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] Tohidypour | Online-Learning-Based Mode Prediction Method for Quality Scalable Extension of the High Efficiency Video Coding (HEVC) Standard[END_REF].

This paper proposes a novel probability-based zero-block early termination algorithm to alleviate the computational complexity of the QSHVC encoder. We first obtain the Sum of Squared Differences (SSD)-based All-Zero Block (AZB) decision condition, which is combined with the probabilities of various modes and depths being chosen as the best one, to derive the corresponding early termination conditions for individual modes and depths, thus terminating the evaluations early. For the remaining coding modes and depths, we then propose a Partial-Zero Block (PZB) detection method to obtain the proportion of zero-valued coefficients. The obtained proportion is employed on top of the possibility of each mode or depth being the best one to further refine the early termination conditions for the subsequent coding process. To the best of our knowlege, this is the first paper use both AZB and PZB and their probabilities to early terminate coding mode and depth selections.

The rest of this paper is organized as follows. Section 2 discusses related work. Section 3 presents an overview of the proposed algorithm. Section 4 proposes the probability-based AZB early termination. Section 5 introduces the probabilitybased PZB early termination. Section 6 discusses and analyses the experimental results. Finally, Section 7 concludes this research and indicates the plan for future work.

II. RELATED WORK

In SHVC, each Coding Tree Unit (CTU) can be divided using a quad-tree structure at four coding depths (0, 1, 2, 3) corresponding to the CU sizes of 64×64, 32×32, 16×16 and 8×8, respectively. Both ILR and Intra modes for all coding depths are evaluated to determine the best coding depth and mode. This encoding process ensures the best coding efficiency at the expense of significantly increased computational complexity. To speed up the encoding process, it is straightforward to early terminate the evaluations of coding modes and depths. The Rate-Distortion (RD) cost and residual coefficients are often considered to determine whether coding modes and depths can be early terminated.

(1) RD costs-based early termination Generally, a CU that generates a large RD cost is likely to be subdivided to a next coding depth, and vice versa. In [START_REF] Zhang | Fast Intra Mode Decision for High Efficiency Video Coding (HEVC)[END_REF], if the aggregation of the estimated RD cost of the sub-CUs in the current CU is larger than the RD cost of the current CU, the subdivision for the current CU is terminated. Cho et al. [START_REF] Cho | Fast CU Splitting and Pruning for Suboptimal CU Partitioning in HEVC Intra Coding[END_REF] used a Bayes decision rule to evaluate the probability of early termination for the current coding depth according to the RD cost, thus achieving the fast CU splitting and pruning. Zhang et al. [START_REF] Zhang | Two-Stage Fast Inter CU Decision for HEVC Based on Bayesian Method and Conditional Random Fields[END_REF] utilized the conditional random field to examine whether it is appropriate to apply early CU decisions. In [START_REF] Zhang | Fast Intra-Mode and CU Size Decision for HEVC[END_REF], Zhang et al. employed the ratio of the RD cost between the current CU and its neighboring CUs as the feature, and the weighted Support Vector Machine (SVM) is used to determine whether to proceed with next coding depths. To achieve an early termination for coding mode evaluation, Wang et al. [START_REF] Wang | Fast Depth and Inter Mode Prediction for Quality Scalable High Efficiency Video Coding[END_REF] proposed a few conditions based on the RD cost differences among square coding modes. Wang et al. [START_REF] Wang | Hybrid Strategies for Efficient Intra Prediction in Spatial SHVC[END_REF]- [START_REF] Wang | A NOVEL MODE SELECTION-BASED FAST INTRA PREDICTION ALGORITHM FOR SPATIAL SHVC[END_REF] first investigated RD cost distributions of ILR mode and Intra mode, and then used the distributions to determine whether ILR mode is the best mode thus skipping Intra mode.

(

2) Residual Coefficients-based Early Termination

To effectively exploit residual coefficients in early termination algorithms, research tends to focus on the expectation, variance, and distribution of residual coefficient, as well as AZB.

Expectation and variance of residual coefficients: In [START_REF] Tan | Fast Coding Quad-Tree Decisions Using Prediction Residuals Statistics for High Efficiency Video Coding (HEVC)[END_REF], a given CU comprising residual coefficients is divided into two parts in two structures: the top half and the bottom half, and the left side and the right side. The differences in variances between the two parts in both structures are calculated, respectively. If either of the differences is significant, the CU is divided further, and vice versa. Wang et al. [START_REF] Wang | Efficient Multi-Strategy Intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF] split a CU in the same way as in [START_REF] Tan | Fast Coding Quad-Tree Decisions Using Prediction Residuals Statistics for High Efficiency Video Coding (HEVC)[END_REF], however, hypothesis testing is introduced to examine the significance of the difference in variances.

Distribution of residual coefficients: Wang et al. [START_REF] Wang | Fast Depth and Inter Mode Prediction for Quality Scalable High Efficiency Video Coding[END_REF] [15] used the "kurtosis skewness test" to observe whether residual coefficients obey the Gaussian distribution. In the affirmative, the current mode is considered the best one and the evaluation of the remaining modes is therefore skipped. Otherwise, the remaining modes are required to undertake further evaluations. In [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF], the Chi-square distribution fitting test method was employed to check the distribution of residual coefficients, so as to decide whether the early termination is to be applied in the coding depth decision or not.

Usage of AZBs: When an AZB is presented, it generally indicates that a CU can be accurately predicted using the current coding mode and depth. The remaining selection process for coding mode and depth can therefore be skipped. In [START_REF] Jung | Fast Mode Decision Using All-Zero Block Detection for Fidelity and Spatial Scalable Video Coding[END_REF], Jung et al. utilized the inter-layer and spatial correlations to detect AZBs, thus terminating the mode decision process. Pan et al. [START_REF] Pan | Early MERGE Mode Decision Based on Motion Estimation and Hierarchical Depth Correlation for HEVC[END_REF] [START_REF] Pan | A CNN-Based Fast Inter Coding Method for VVC[END_REF] proposed that the coding mode is considered the best one when the quantized residual coefficients generated by the corresponding merge mode are all zero, then the mode decision process can be early terminated. Chiang et al. [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF] determined whether the inter-coding is an AZB based on the Sumof-Absolute-Difference (SAD) value to terminate the depth selection process early. Jiang et al. [START_REF] Fu-Jiang | Predictive skip mode based all zero block detection for AVS encoder[END_REF] derived the decision condition for the AZB detection to predict if the current mode is the best one. For three types of transform and quantization methods, Wang et al. [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF] theoretically derive the decision condition for DCT coefficients to be quantized to zeros. For different types of DCT and quantization implementations, Wang et al. [START_REF] Wang | Hybrid Model to Detect Zero Quantized DCT Coefficients in H.264[END_REF] first used the Gaussian distribution to propose multiple thresholds, and then further optimize the thresholds to sufficiently detect AZB. Wang et al. [START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF] proposed to use the Sum of Absolute Transformed Difference (SATD) to detect AZB. Lee et al. [START_REF] Lee | An All-Zero Block Detection Scheme for Low-Complexity HEVC Encoders[END_REF] used the relationship between Walsh Hadamard and DCT transform kernels to derive AZBs. Methods in [START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF]- [START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF] divided CUs into Genuine AZBs (G-AZB) and Pseudo AZBs (P-AZBs). For G-AZB, the AZB decision condition is directly derived from the residual distribution. For P-AZBs, the AZB decision condition is proposed according to the RD cost.

Despite the aforementioned research efforts, the following issues still need to be investigated. ( (3) The probability of each coding mode and coding depth being chosen as the best one is combined with both AZBs and PZBs to derive a probability-based AZB and PZB early termination conditions. For a mode or depth with a higher probability, looser early termination conditions can be used to improve coding speed; while for a mode or depth with a smaller probability, stricter early termination conditions are used to maintain coding speed.

III. OVERVIEW OF THE PROPOSED PROBABILITY-BASED ZERO-BLOCK EARLY TERMINATION

To early terminate the mode and depth selection processes, we propose a probability-based zero-block early termination algorithm, which includes a probability-based AZB early termination (PBAET) strategy and a probability-based PZB early termination (PBPET) strategy, respectively. The overview of the algorithm is illustrated in Fig. 1. The PBAET strategy and PBPET strategy as well as its corresponding sub-strategies are shown in the left part of Fig. 1.

We first use PBAET to determine whether the current mode or depth is the best one. In the affirmative, we further use PBPET to early terminate mode or depth selection. In PBAET, we first derive the SSD-based AZB determining condition based on residual coefficients following Laplace distribution. It is subsequently combined with the probabilities of modes and depths to study the corresponding early termination decision conditions. If this decision condition is satisfied, the coding process can be early terminated. Otherwise, PBPET is subsequently used to early terminate the mode or depth selection process.

In PBPET, we first predict zero-valued quantized coefficients based on SSD. As discussed in section 5, this prediction cannot obtain all zero-valued quantized coefficients. Therefore, we further derive the PZB prediction condition based on HT and predict zero-valued quantized coefficients by HT. In this process, if the subsequent HT coefficients are to be quantized to zero, we can early terminate the calculation for these HT coefficients. Therefore, we propose early termination of PZB based on energy conservation. Through the above process, the percentage of zero-valued coefficients in a CU is obtained. It is subsequently combined with the probabilities of modes and depths to obtain the corresponding early termination decision conditions to terminate the mode or depth selection process.

Extensive experiments are undertaken to justify the proposed algorithm. To cover various spatial resolutions, two video sequences were selected from each of video classes: B, C, D, and E. In particular, we used the following video sequences for validation: Sunflower and Tractor in class B; Park and Town in class C; Flowervase and PartyScene in class D; RaceHorses and BlowingBubbles in class E. These video sequences are representative, as they contain different levels of motion and textual complexity. Experiment parameters are set according to the Common Test Conditions (CTC) [START_REF] Li | JCTVC-M1009: Common SHM test conditions and software reference configurations[END_REF]. Specifically, the QP values of [START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF][START_REF] Pan | DACNN: Blind Image Quality Assessment via a Distortion-Aware Convolutional Neural Network[END_REF] are used for the BL while the QP values of [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] and [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF]) are adopted for the EL. As the divergence between [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] in EL and [START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF][START_REF] Pan | DACNN: Blind Image Quality Assessment via a Distortion-Aware Convolutional Neural Network[END_REF] in BL is greater than that between [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF] in EL and [START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF][START_REF] Pan | DACNN: Blind Image Quality Assessment via a Distortion-Aware Convolutional Neural Network[END_REF] in BL, if the algorithm performs well when QP values of [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] are employed in EL, there are grounds to believe that it performs better when QP values of [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF] are used in EL. Therefore, only QP values of [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] are used for EL in the training phase, while both QP values of [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF] and [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] are used for EL in the validation phase.

IV. PROBABILITY-BASED AZB EARLY TERMINATION

If residual coefficients presented in a CU are all zero after quantization, it indicates an accurate prediction is achieved. The corresponding mode or depth is very likely to be the best, and the mode or the depth selection process can therefore be early terminated. To achieve this, the condition to decide if a CU is an AZB should first be established. The AZB decision condition is so strict that the improvement in encoding time reduction is limited if the condition is applied directly for early termination. The decision condition of early termination is closely related to the probability of each mode or depth being selected as the best one.

For the modes or depths that are more likely to be chosen, we can set a looser decision condition to improve the encoding speed. Meanwhile, a stricter condition is chosen for the modes or depths that are less likely to be selected to maintain the coding efficiency. Therefore, the probability of each mode or depth being selected as the best one should be taken into consideration when we further develop the corresponding early

A. SSD-based AZB decision condition

Generally, if a CU is predicted with great accuracy, the generated residual coefficients follow the Laplace distribution with the expectation of 0 and the variance of 𝜎 2 , and the corresponding probability density function is [START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF]

𝑓 (𝑥) = 𝜆 2 𝑒 -𝜆| 𝑥 | (1)
where 𝜆 represents the scale parameter of the Laplace distribution. As the expectation is 0, the corresponding variance 𝜎 2 is:

𝐷 (𝑥) = 𝐸 𝑥 2 -(𝐸 (𝑥)) 2 = 𝜆 2 ∫ ∞ -∞ 𝑥 2 𝑒 -𝜆 |𝑥 | 𝑑𝑥 -0 = 2 𝜆 2 (2) According to Eq. (2), we have 𝜆 = √ 2 𝜎 (3)
Assuming that 𝑥 𝑖 𝑗 is the residual value at the position of (𝑖, 𝑗), the corresponding variance 𝜎 2 is calculated as follows:

𝜎 2 = 𝐷 (𝑥 𝑖 𝑗 ) = 𝐸 (𝑥 2 𝑖 𝑗 ) -𝐸 (𝑥 𝑖 𝑗 ) 2 (4)
where 𝐸 (𝑥 𝑖 𝑗 ) and 𝐷 (𝑥 𝑖 𝑗 ) represent the expectation and the variance of 𝑥 𝑖 𝑗 , respectively. As the expectation of the residual coefficient is 0, namely 𝐸 (𝑥 𝑖 𝑗 ) is 0.𝐸 (𝑥 2 𝑖 𝑗 ) can be calculated as follows:

𝐸 (𝑥 2 𝑖 𝑗 ) = 𝑁 -1 𝑖=0 𝑁 -1 𝑗=0 𝑥 2 𝑖 𝑗 𝑁 2 (5)
SSD is represented by

𝑁 -1 𝑖=0 𝑁 -1 𝑗=0
𝑥 2 𝑖 𝑗 . Combining Eqs. ( 4) and ( 5), we have

𝜎 2 = 𝑆𝑆𝐷 𝑁 2 (6)
The variance of the DCT coefficients at position (𝑢, 𝑣) is

𝜎 2 𝑑𝑐𝑡 (𝑢, 𝑣) = 𝜎 2 [ARA 𝑇 ] 𝑢𝑢 [ARA 𝑇 ] 𝑣 𝑣 (7)
where[•] 𝑢,𝑢 is the value of the coefficient at position (𝑢, 𝑢) in the matrix, 𝐴 is an DCT matrix, 𝐴 𝑇 represents the transpose of 𝐴, and 𝑅 is the correlation matrix. For a CU of size 8×8, the corresponding 𝑅 is

R =          1 𝜌 • • • 𝜌 7 𝜌 1 • • • 𝜌 6 . . . . . . . . . . . . 𝜌 7 • • • 𝜌 1          ( 8
)
where 𝜌 is the correlation coefficient of the matrix of residual coefficients, and its value ranges from 0.4 to 0.75 [START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF]. The value of 𝜌 used in [START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF] is 0.6. The average of 𝜎 2 𝑑𝑐𝑡 is:

𝜎 2 dct = 𝐸 [𝜎 2 [ARA 𝑇 ] 𝑢𝑢 [ARA 𝑇 ] 𝑣 𝑣 ] = 𝜎 2 (9)
Combining Eqs. ( 3),( 6) and ( 9), we obtain the parameters of the Laplace distribution based on the DCT transform as follows:

𝜆 𝑑𝑐𝑡 = √ 2𝑁 √ 𝑆𝑆𝐷 (10)
For the residual coefficients that follow the Laplace distribution, the number of non-zero coefficients generated from quantization is [START_REF] Lee | A Frame-Level Rate Control Scheme Based on Texture and Nontexture Rate Models for High Efficiency Video Coding[END_REF]:

𝑅(𝑞) = 𝑁 × 𝑁 × 𝑒 -(1-𝑓 )q𝜆dc𝑡 ( 11
)
where 𝑓 is the rounding offset parameter in the quantization process. In Intra prediction, 𝑓 generally takes the value of 1/3; while in Inter prediction, 𝑓 is 1/6. 𝑞 is the quantization step size. If 𝑅(𝑞) in the above equation is less than 1, it means that the coefficients in a block of size N×N are all quantized to zero. Therefore, we can use the following conditions to determine if a block is an AZB:

𝑁 2 𝑒 -(1-𝑓 )𝑞𝜆 dct + 0.5 < 1 (12)
where 0.5 is the rounding offset. If Eq. ( 12) holds, the quantized coefficients in an N×N block are entirely 0. Combining Eqs. ( 10) and ( 12), the decision condition for AZB based on SSD is deduced as:

√ SSD < √ 2 (1 -𝑓 ) 𝑞𝑁 ln2𝑁 2 (13)
The above AZB decision condition is deduced for 8×8 CUs. Similar decision conditions can be obtained for 16×16, 32×32 and 64×64 CUs.

As mentioned above, the coding mode or depth selections are closely related to their probabilities of being selected as the best ones. We need to combine the probability of each mode or depth being selected as the best one to obtain the corresponding decision condition. Suppose 𝛼 is a parameter, which is determined according to the probability of the current CU adopting a particular mode or depth, Eq. ( 13) can be revised as:

√ SSD < 𝛼 • √ 2 (1 -𝑓 ) 𝑞𝑁 ln2𝑁 2 (14)
It is a key problem to obtain the optimal value for 𝛼. Since there are mode selection and depth selection in SHVC, we combine with probabilities of mode and depth to obtain their corresponding optimal 𝛼 in the following sub-sections, respectively.

B. Mode probability-based ILR mode early termination

In our previous research [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF], we discussed how to obtain the probability of each particular mode being selected as the best one. We divided the probability range of [0%∼100%] into 5 equal intervals, namely [0%∼20%], [20%∼40%],

[40%∼60%], [60%∼80%], and [80%∼100%]. When the range is divided into more equal intervals, the calculation process is more complex while the accuracy is only improved negligibly. However, when fewer equal intervals are divided, the accuracy is significantly degraded. Therefore, we divide the probability range of [0%∼100%] into 5 equal intervals. Since probabilities in different intervals are significantly different, these five intervals are tested individually to obtain their corresponding optimal values.

As the coding process of ILR mode is relatively simple and the ILR mode is often adopted by most CUs as the best mode [START_REF] Wang | Efficient Multi-Strategy Intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF], we first evaluate the ILR mode to determine whether the early termination condition is satisfied, thus skipping the Intra prediction. To achieve the decision condition of AZB, 𝛼 in Eq. ( 14) is set to common values, e.g. 1, 2, 3, 4, 5, 6, etc when the probability of the ILR mode being selected as the best is 40%∼60%. For various 𝛼 values, the corresponding coding efficiency is shown in Table I, where BDBR [START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] measures the bitrate difference when identical PSNR is achieved in the EL. A positive or negative BDBR indicates either a loss or an increase in coding efficiency, respectively.

In general, the turning point is usually chosen as the optimal value of 𝛼. If 𝛼 is greater than the turning point, its corresponding BDBR will change. In other words, its corresponding accuracy will also change. Therefore, this 𝛼 is selected as the best one. As can be seen from Table I, there is a turning point for the "Flowervase" and "BlowingBubbles" sequences when 𝛼 is greater than 4. Therefore, 𝛼 = 4 is selected. In addition, as also can be seen in Table I, in many sequences, BDBR does not vary under different alpha values and only one decimal place changes. The reason for this is that the proportion of CUs from the interval of [40%∼60%] is quite small. In particular, the proportions of CUs in Sunflower, tractor, park, town, Flowervase, PartyScene, BlowingBubbles and RaceHorses are 4.3%, 3.6%, 8.1%, 5.7%, 6.7%, 5.1%, 5.6% and 4.7%, respectively. BDBR does not vary significantly under different alpha values and only one decimal place changes due to the small proportions.

The experimental results show that the average precisions are 92.46%, 91.05%, 90.45%, 90.05%, 87.91% and 87.13% when the 𝛼 values are 1, 2, 3, 4, 5 and 6, respectively; the average recalls are 25.80%, 40.00%, 51.55%, 60.79%, 67.91% and 73.91% when the 𝛼 values are 1, 2, 3, 4, 5 and 6, respectively. We can observe that as 𝛼 increases, the precision gradually decreases and the recall gradually increases. The reason for this is that in Eq. ( 14), as 𝛼 increases, the early termination condition is gradually loosened and more CUs are terminated early. As a result, the corresponding precision gradually decreases and the recall gradually increases.

Since 𝛼 = 4 is not optimal for all probabilities in [40%∼60%], we take 𝛼 = 4 as the optimal value for the median of [40%∼60%], namely 50%. In a similar manner, the optimal 𝛼 values for 10%, 30%, 70%, and 90% is 1, 3, 6, and 9, respectively. Concatenating the probability and its corresponding optimal value of 𝛼, we obtain a series of datasets: (10%, 1), (30%, 3), (50%, 4), (70%, 6), (90%, 9). To investigate the relationship between the probability 𝑥 and the corresponding optimal value of 𝛼, the polynomial regression is applied as follows:

𝛼 𝑖 = 𝑘 0 + 𝑘 1 𝑥 𝑖 + 𝑘 2 𝑥 2 𝑖 + • • • + 𝑘 𝑚 𝑥 𝑚 𝑖 + 𝜀 𝑖 (15)
We use 𝑖 = 1, 2, • • • , 5 to denote the five datasets. 𝑥 𝑖 and 𝛼 𝑖 are the probability and its corresponding optimal 𝛼 of the 𝑖-th set respectively. 𝜀 𝑖 is the error of the 𝑖-th dataset. 𝑘 𝑗 is the 𝑗-th coefficient, and 𝑚 is the greatest value of coefficient sunflower 0.20% 0.20% 0.20% 0.20% 0.20% 0.20% tractor -0.10% 0.00% 0,00% 0.00% 0.00% 0.00% park 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% town -0.10% -0.10% -0.10% -0.10% -0.10% -0.10% Flowervase -0.20% -0.20% -0.20% -0.20% -0.10% -0.10% PartyScene -0.10% -0.10% -0.10% -0.10% -0.10% -0.10% BlowingBubbles -0.10% -0.10% -0.10% -0.10% -0.20% -0.20% RaceHorses -0.20% -0.20% -0.20% -0.20% -0.20% -0.20% or power. To obtain the optimal value of 𝑘 𝑗 , and the minimal 𝜀 𝑖 , we have:

𝑓 = 5 ∑ 𝑖=1 𝜀 2 𝑖 = 5 ∑ 𝑖=1 𝑦 𝑖 -𝑘 0 -𝑘 1 𝑥 𝑖 -𝑘 2 𝑥 2 𝑖 -• • • -𝑘 𝑚 𝑥 𝑚 𝑖 2 ( 16
)
where 𝑓 is the sum of errors of the five datasets. To find the optimal value of 𝑘 𝑗 , we take the derivative of 𝑓 with respect to 𝑘 𝑗 and set it equal to zero:

𝜕 𝑓 𝜕𝑘 𝑗 = -2 5 ∑ 𝑖=1 𝑦 𝑖 -𝑘 0 -𝑘 1 𝑥 𝑖 -𝑘 2 𝑥 2 𝑖 -• • • -𝑘 𝑚 𝑥 𝑚 𝑖 𝑥 𝑗 𝑖 = 0 (17)
In order to achieve the optimal value of 𝑚, we have chosen a variety of different values, such as 1, 2, 3, 4, 5, 6, etc., for fitting. The fitting results suggest that the regression model has a similar fitting effect when 𝑚 ≥ 3 . Therefore, we use 𝑚 = 3 for fitting, and the corresponding expression of the fitting function is given as follows:

𝛼 = 20.83 • 𝑥 3 -25.89 • 𝑥 2 + 16.93 • 𝑥 -0.4268 (18)
Consequently, we can derive the corresponding optimal value of 𝛼 for any probability of 𝑥. Combining Eqs. ( 14) and [START_REF] Pan | Early MERGE Mode Decision Based on Motion Estimation and Hierarchical Depth Correlation for HEVC[END_REF], we obtain the probability-based early termination conditions for ILR mode as shown Eq. [START_REF] Pan | A CNN-Based Fast Inter Coding Method for VVC[END_REF].

√ 𝑆𝑆𝐷 < 20.83 • 𝑥 3 -25.89 • 𝑥 2 + 16.93 • 𝑥 -0.4268 • √ 2 (1 -𝑓 ) 𝑞𝑁 ln 2𝑁 2 (19)
If the inequality in Eq. ( 19) holds, the condition of early termination is satisfied, thus the Intra mode can be skipped; otherwise, the Intra mode is required to be examined for further prediction.

C. Depth probability-based early termination

In our previous work [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF], we managed to obtain the probability of each coding depth being selected as the best one. Again, we divided the probability range of [0%∼100%] into 5 equal intervals, namely [0%∼20%], [20%∼40%], [40%∼60%], [60%∼80%], and [80%∼100%]. Similar to the above ILR mode early termination, these five intervals were tested individually to obtain their corresponding optimal 𝛼.

Simulation results show that only very few CUs adopt the coding depth of 0. Therefore, we do not early terminate the coding depth of 0, as this only brings a limited improvement in coding speed. As the maximum coding depth is set to 3, it makes no sense to terminate the coding process at this depth. Therefore, we apply the early termination at coding depths of 1 and 2 only.

The same methodology as described in section (2) for ILR mode early termination is employed. When the coding depth is 1, we obtain a series of datasets: (10%, 1), (30%, 2), (50%, 3), (70%, 4), (90%, 7).

The polynomial regression is applied to the five datasets to investigate the relationship between the probability 𝑑 1 of coding depth 1 and its corresponding optimal value of 𝛼:

𝛼 = 14.63𝑑 3 1 -10.47𝑑 2 1 + 4.382𝑑 1 -0.8997 (20)
For coding depth of 2, the relationship between the probability 𝑑 2 of coding depth 2 and its corresponding optimal value of 𝛼 is given as

𝛼 = 14.83𝑑 3 2 -13.86𝑑 2 2 + 9.31𝑑 2 -1.071 (21)
The optimal value of 𝛼 for the coding depths of 1 and 2 can be obtained using Eq. ( 20) and Eq. ( 21), respectively. Substituting them into Eq. ( 14), we can derive the corresponding early termination decision conditions for coding depths to improve the coding speed.

Through the above process, we obtain AZB early termination conditions. However, the number of AZBs is limited. If blocks only contain partial zero quantized coefficients, their corresponding coding modes and depths are also possibly the best ones. Therefore, we further investigate PZB early termination as shown below.

V. PROBABILITY-BASED PZB EARLY TERMINATION

As mentioned above, the decision condition of early termination is closely related to the probability of each mode or depth being selected as the best one. Therefore, we propose an effective PZB prediction process, and this is consequently combined with the probability of each coding mode and coding depth being chosen as the best ones to obtain the corresponding early termination conditions.

A. PZB prediction process

To accurately calculate the percentage of zero-valued coefficients, we first count the number of zero-valued coefficients based on SSD in a CU. The SSD of the residual coefficients

                0.
                (24)
is greater than or equal to the actual sum of the residual coefficients. Therefore, the corresponding decision conditions using the SSD of residual coefficients are too strict. In other words, if a coefficient is predicted to be zero based on SSD, it is certainly quantized to zero. Therefore, we first predict zero-valued quantized coefficients. However, if a coefficient is predicted to be non-zero based on SSD, it still may likely be quantized to zero. Therefore, we further use the actual sum of residual coefficients to calculate zero-valued coefficients. Since the HT is similar to but much simpler than the DCT transform, we then derive the PZB prediction condition based on HT. Finally, we propose early termination based on energy conservation to improve coding speed.

1) Prediction of zero-valued quantized coefficients based on SSD: As mentioned in Eq. ( 7), the expectation and variance of the 𝐷𝐶𝑇 coefficient at position (𝑢, 𝑣) are 0 and 𝜎 𝐹 (𝑢, 𝑣), respectively. There is a probability of greater than 99% that a 𝐷𝐶𝑇 coefficient locates in the interval of (-3𝜎 𝐹 ,3𝜎 𝐹 ) [START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF]. To ensure the 𝐷𝐶𝑇 coefficient at position (𝑢, 𝑣) being zero after quantization, the following conditions must be met

3𝜎 𝐹 (𝑢, 𝑣) 𝑄 𝑠𝑡𝑒 𝑝 + 1 6 < 1 (22)
Combining Eqs. ( 6), ( 7) and ( 22), the PZB decision condition is derived as shown below.

√ 𝑆𝑆𝐷 ≤ 20𝑄 𝑠𝑡𝑒 𝑝 9 √ [ARA 𝑇 ] 𝑢𝑢 [ARA 𝑇 ] 𝑣 𝑣 (23)
The right part in Eq. ( 23) is given by a matrix in a numerical form as shown in Eq. [START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF].

Given the obtained matrix of thresholds, the zero-valued elements can be produced for quantized coefficients. If SSD is smaller than a threshold value in the matrix, scanning in the Zigzag order starting from the upper left corner towards the bottom right corner, the DCT coefficients from the upper left corner to the position of the thresholded value are quantized to be non-zero values, and the subsequent coefficients are quantized to zero [START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF]. For example, the quantized residual coefficients are all zeros if √ 𝑆𝑆𝐷 < 0.7219𝑄 𝑠𝑡𝑒 𝑝 is applied; the quantized residual coefficient at position (0, 0) is nonzero only if √ 𝑆𝑆𝐷 < 0.9439𝑄 𝑠𝑡𝑒 𝑝 is applied; the quantized residual coefficients at positions (0, 0), (0, 1) and (1, 0) are non-zero if √ 𝑆𝑆𝐷 < 1.2095𝑄 𝑠𝑡𝑒 𝑝 is applied, and so forth. All zero-valued quantized coefficients in a matrix can be predicted in the same way based on the threshold matrix [START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF].

2) PZB prediction condition based on HT: As mentioned above, The SSD-based decision conditions are so strict that it is possible for some predicted non-zero DCT coefficients to be quantized to zero-valued coefficients. Therefore, for those that do not satisfy the above decision conditions, we need to further predict DCT coefficients. HT is quite similar to DCT but much simpler. For both the HT coefficient and the DCT coefficient at the same position, if they are sufficiently close, we use HT rather than DCT to obtain the zero-valued coefficient. We use 𝑧 1 and 𝑧 2 to denote the DCT transformed coefficient and its corresponding HT coefficient at position (𝑢, 𝑣), respectively.

The corresponding decision condition is written as

𝑧 1 𝑄 𝑠𝑡𝑒 𝑝 - 𝑧 2 𝑄 𝑠𝑡𝑒 𝑝 ≤ 𝑘 (25)
From Eq. ( 25), we have:

|𝑧 1 -𝑧 2 | ≤ 𝑘𝑄 𝑠𝑡𝑒 𝑝 (26)
The DCT transformed coefficient 𝑧 1 and the HT transformed coefficient 𝑧 2 are given by

𝑧 1 = 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑥 𝑖 𝑗 𝑑 𝑗 𝑣 , 𝑧 2 = 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑒 𝑢𝑖 𝑥 𝑖 𝑗 𝑒 𝑗 𝑣 (27)
where 𝑑 𝑢𝑖 and 𝑒 𝑢𝑖 are the elements at position (𝑢, 𝑖) in the DCT and HT matrices, respectively, 𝑥 𝑖 𝑗 is the residual coefficient at position (𝑖, 𝑗) . From Eq. ( 27), we have

|𝑧 1 -𝑧 2 | = 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑥 𝑖 𝑗 𝑑 𝑗 𝑣 - 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑒 𝑢𝑖 𝑥 𝑖 𝑗 𝑒 𝑗 𝑣 = 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑑 𝑗 𝑣 -𝑒 𝑢𝑖 𝑒 𝑗 𝑣 𝑥 𝑖 𝑗 (28)
According to the Cauchy's inequality, we have

7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑑 𝑗 𝑣 -𝑒 𝑢𝑖 𝑒 𝑗 𝑣 𝑥 𝑖 𝑗 ≤ 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑑 𝑗 𝑣 -𝑒 𝑢𝑖 𝑒 𝑗 𝑣 2 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑥 2 𝑖 𝑗 (29)
From Eq. ( 29), we get (31) As the sum of squares of the coefficients in each row of the DCT and HT matrices is always 1, we get:

7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑑 𝑗 𝑣 -𝑒 𝑢𝑖 𝑒 𝑗 𝑣 2 √ 𝑆𝑆𝐷 ≤ 2 7 ∑ 𝑖=0 7 ∑ 𝑗=0 𝑑 𝑢𝑖 𝑑 𝑗 𝑣 2 + 𝑒 𝑢𝑖 𝑒 𝑗 𝑣 2 √ 𝑆𝑆𝐷 (30)
7 ∑ 𝑖=0 𝑑 2 𝑢𝑖 7 ∑ 𝑗=0 𝑑 2 𝑗 𝑣 + 7 ∑ 𝑖=0 𝑒 2 𝑢𝑖 7 ∑ 𝑗=0 𝑒 2 𝑗 𝑣 = 2 (32)
Combining Eqs. ( 26), ( 28) and ( 32), we have:

2 √ 𝑆𝑆𝐷 ≤ 𝑘𝑄 𝑠𝑡𝑒 𝑝 (33)
It can be written as:

𝑆𝑆𝐷 ≤ 𝑘 2 4 𝑄 2 𝑠𝑡𝑒 𝑝 (34)
If the condition in Eq. ( 34) holds, the quantized zero-valued coefficients can be calculated according to the HT transformed coefficients as shown below:

𝑧 2 𝑄 𝑠𝑡𝑒 𝑝 + 1 6 < 1 (35)
If the condition in Eq. ( 35) holds, 𝑧 2 is quantized to 0. In this way, we can predict all of the coefficients that are to be quantized to zero.

To find the optimal value of 𝑘, we evaluate a number of values. The QP values used for the BL and the EL are 26 and 20, and the corresponding error rate (ER) which is the percentage of the numbers of mistakenly predicted CUs to the total number of CUs is shown in Fig. 2.

In Fig. 2, the x-axis denotes the value of 𝑘, and the y-axis is the corresponding ER. When 𝑘 = 50, the corresponding ER is 4.9%. In Eq. ( 25), 𝑘 is the absolute difference between the quantized HT coefficient and the quantized DCT coefficient at the same position. Obviously, the greater the 𝑘 value, the greater the difference and the ER. Fig. 2 also verifies that ER increases gradually as the value of 𝑘 increases. Therefore, when 𝑘 is greater than 50, the corresponding ER should be greater than 4.9%. To ensure accuracy, 𝑘 = 50 is chosen as the optimal value. For a CU satisfying the condition in Eq. ( 34), HT is used for the calculation to determine whether the obtained HT transformed coefficient is a quantized zero-valued coefficient.

Through this process, we can obtain the quantized zerovalued coefficients. In this way, each HT coefficient also takes HT calculation cost. After some HT coefficients have been obtained, if we can early predict that the subsequent HT coefficients will be quantized to zero, we can skip the calculation for these HT coefficients. Therefore, we propose early termination PZB as shown below.

3) Early termination based on energy conservation: According to the law of conservation of energy, the sum of the squares of the coefficients in the residual matrix is equal to that in the matrix of transformed coefficients, which can be written as

𝑁 ∑ 𝑖=0 𝑟 2 𝑖 = 𝑁 ∑ 𝑖=0 𝑇 2 𝑖 = 𝑠 ( 36
)
where 𝑟 𝑖 and 𝑇 𝑖 are the 𝑖-th residual coefficient and the 𝑖-th HT coefficient scanned in Zigzag order. 𝑁 is the number of coefficients in the matrix. 𝑠 is the sum of the squares of all the residual coefficients in the residual matrix or the sum of the squares of all the TH coefficients in the TH coefficients matrix. This forms the basis of the proposed early termination. We first calculate the sum of the squares of all the residual coefficients in the residual matrix 𝑠, and the coefficients in the HT transformed matrix are then scanned in Zigzag order to examine if the condition in Eq. ( 37) holds or not.

𝑘 ∑ 𝑖=0 𝑇 2 𝑖 + 𝑇 2 𝑘 ≥ 𝑠 (37)
Combining Eqs. ( 36) and ( 37), we have:

𝑇 2 𝑘 ≥ 𝑁 ∑ 𝑖=𝑘+1 𝑇 2 𝑖 ( 38
)
Therefore, if Eq.( 38) holds, it means that 𝑇 𝑘 is greater than the subsequent HT coefficients. If 𝑇 𝑘 is zero after quantization, its subsequent HT quantized coefficients must be zero. The calculation process for the subsequent HT coefficients can be terminated. This early termination is developed for the HT coefficients. If a CU does not satisfy Eq. ( 34), we can calculate the DCT coefficients instead of the HT coefficients.

The above process deduces the PZB decision condition for 8×8 CUs. For 16×16, 32×32 and 64×64 CUs, they can be divided into several 8×8 CUs for calculation.

B. Mode probability-based PZB early termination

Following the above process, we can obtain the number of zero-valued quantized coefficients for the en- as the best one is in the range of between 40% and 60%, we test the above eight intervals respectively. The corresponding coding efficiency is presented in Table II.

It can be seen from Table II that a lower percentage of zero-value coefficients can lead to performance improvements. However, these performance gains come from prediction errors. We have analyzed the reasons for this in the last paragraph of this manuscript. Prediction errors sometimes decrease and sometimes increase the BDBR. For example, "Flowervase" and "BlowingBubbles" have positive BDBR, but the other sequences have negative BDBR. Clearly, a lower percentage of zero-valued coefficients does not give very good performance for all sequences. As the percentage of zero-valued coefficients increases, the corresponding CU is predicted more accurately by the current mode or depth, so the interval of 0.875∼1 can obtain very good performance across all sequences. Therefore, we choose the interval of [0.875∼1].

The experimental results show that the average precision under the intervals of [0∼0.125], [0.125∼0.25], [0.25∼0.375], [0.375∼0.5], [0.5∼0.625], [0.625∼0.75], [0.75∼0.875], and [0.875∼1] are 80.97%, 82.40%, 83.72%, 87.15%, 89.75%, 92.18%, 96.80% and 98.75% respectively; and the corresponding average recalls are 4.81%, 5.14%, 6.94%, 8.51%, 11.62%, 16.51%, 21.44% and 25.04% respectively. We can observe that, as the percentage interval of zero-valued coefficients increases, their corresponding precision gradually increases. This is because as the percentage of zero-value coefficients increases, the corresponding CU is predicted more accurately by the current mode or depth.

In a similar way as PBAET, the median of the interval of [0.875∼1], namely 0.9375, is taken as the optimal value for the mode probability between 40% and 60%. It is not suitable to take 0.9375 as the optimal value for the entire of [40%∼60%], so it is taken as the optimal value for the median of [40%∼60%], namely 50%. In a similar manner, we obtain five sets of data: (10%, 1), (30%, 1), (50%, 0.9375), (70%, 0.8125), (90%, 0.6875). Again, the polynomial regression is applied to establish the relationship between the probability of the ILR mode being selected as the best coding mode and the percentage of zero coefficients in an 8×8 CU:

𝑇 ℎ = -13.02 • 𝑝(𝐼 𝐿𝑅) 4 + 26.04 • 𝑝(𝐼 𝐿𝑅) 3 -17.45 • 𝑝(𝐼 𝐿𝑅) 2 + 4.115 • 𝑝(𝐼 𝐿𝑅) + 0.2758 (39)
where 𝑥 is the probability of the ILR mode being selected as the best coding mode, and 𝛽 represents the proportional threshold of zero-valued coefficients in an 8×8 CU. According to Eq. ( 39), we obtain the proportional threshold of the quantized zero-valued coefficient ratio of the probability of the current ILR mode. If the percentage of zero-valued coefficients in the current CU is greater than 𝛽, we skip the Intra mode. Otherwise, we need to use the Intra mode for further prediction.

C. Depth probability-based PZB early termination

The early termination is applied at the coding depths of 1 and 2 using the same process of the ILR mode. The probability of the current CU adopting the coding depth of 1 is divided into five intervals. The percentage of quantized zerovalued coefficients is divided into eight intervals. We obtain five datasets:(10%, 0.9375), (30%, 0.8125), (50%, 0.8125), (70%, 0.6875), and (90%, 0.4375).

The polynomial regression is applied to the five datasets to obtain the relationship between the probability (𝑑 1 ) of coding depth 1 being selected as the best depth and the corresponding percentage of quantized zero-valued coefficients (𝛽):

𝛽 = -2.107 • 𝑑 3 1 + 2.43 • 𝑑 2 1 -1.116 • 𝑑 1 + 1.008 (40)
In the same way, five datasets for coding depth 2 are obtained, namely (10%, 0.9375), (30%, 0.6875), (50%, 0.5625), (70%, 0.4375) and (90%, 0.1875). Applying the polynomial regression to the five datasets, the relationship between the probability (𝑑 2 ) of coding depth 2 being selected as the best depth and the corresponding percentage of quantized zerovalued coefficients (𝛽) is obtained:

𝛽 = -1.076 • 𝑑 3 2 + 1.427 • 𝑑 2 2 -1.317 • 𝑑 2 + 1.009 (41)
The thresholds of the zero-valued coefficient percentage of coding depths 1 and 2 can be obtained through Eqs. [START_REF] Zhao | An Ultra-Low Complexity and High Efficiency Approach for Lossless Alpha Channel Coding[END_REF] and [START_REF] Zhao | A Universal String Matching Approach to Screen Content Coding[END_REF]. If the percentage of quantized zero-valued coefficients in the current CU is greater than 𝛽 , we can early terminate the evaluation on coding depth; otherwise, we need to use subsequent depths for further prediction.

VI. EXPERIMENTAL RESULTS

To verify the effectiveness of the proposed algorithm, we employ the reference software (SHM 11.0) on a server with Intel (R) 2.0 GHz CPU and 30 GB memory for testing. The encoding parameters specified in CTC [START_REF] Li | JCTVC-M1009: Common SHM test conditions and software reference configurations[END_REF] are used. The QP factors for the BL are [START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF][START_REF] Pan | DACNN: Blind Image Quality Assessment via a Distortion-Aware Convolutional Neural Network[END_REF]. Two sets of QP factors [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] and [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF] are used for the EL. For simplicity, the QP factors of [START_REF] Chiang | Fast zero block detection and early CU termination for HEVC Video Coding[END_REF][START_REF] Wang | Prediction of Zero Quantized DCT Coefficients in H.264/AVC Using Hadamard Transformed Information[END_REF][START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF][START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] and [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF] are denoted as C1 and C2, respectively. The experimental performance is measured in terms of coding efficiency and coding speed. The coding efficiency is measured by BDBR [START_REF] Bjontegaard | Calculation of average PSNR differences between RDcurves[END_REF] and the coding speed is evaluated by TS, which represents the proportional reduction in encoding time for the EL.

The proposed algorithm includes the PBAET and the PBPET. It is observed that the two QP sets for the EL produced similar experimental results. We, therefore, present the results in Table III when the QP set of [START_REF] Wang | Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization[END_REF][START_REF] Fan | Hybrid Zero Block Detection for High Efficiency Video Coding[END_REF][START_REF] Pao | Modeling DCT coefficients for fast video encoding[END_REF][START_REF] Gao | Temporally Dependent Rate-Distortion Optimization for Low-Delay Hierarchical Video Coding[END_REF] is used for the EL.

It is seen from Table III that the coding speed improved by PBAET and PBPET for the EL is 75.03% and 79.75%, respectively. The BDBR is decreased by 0.27% and 0.31% for PBAET and PBPET, respectively. The experimental results show that the improvement in coding speed achieved by PBAET is more significant than that achieved by PBPET, and this is because PBPET needs additional computational overhead, which reduces the improvement of coding speed.

In order to further demonstrate the effectiveness of the proposed algorithms, the overall performance when combining the two proposed strategies, i.e. "PBAET" and "PBPET", is evaluated and compared with EMSIP [START_REF] Wang | Efficient Multi-Strategy Intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF], FDMDIP [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF] and HAZSQBD [START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF]. The early termination for modes and depths in EMSIP [START_REF] Wang | Efficient Multi-Strategy Intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF] and FDMDIP [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF] and the AZB decision conditions in HAZSQBD [START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF] are used to early terminate the mode and depth selection. To the best of our knowledge, EMSIP [START_REF] Wang | Efficient Multi-Strategy Intra Prediction for Quality Scalable High Efficiency Video Coding[END_REF] and FDMDIP [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF] represent the state-of-the-art performance in early termination for SHVC, and the best AZB decision condition is provided in HAZSQBD [START_REF] Cui | Hybrid All Zero Soft Quantized Block Detection for HEVC[END_REF]. Table IV and Table V compare the coding performance of the proposed algorithms with that of the state-of-the-art methods.

As can be seen from Table IV, the computation time of the proposed algorithm is decreased by 81.82%, and the computation time of EMSIP, FDMDIP and HAZSQBD are reduced by 59.10%, 71.30% and 50.16%, respectively. The BDBR of the proposed algorithm is -0.41, and the BDBRs of EMSIP, FDMDIP and HAZSQBD are -0.20, -0.25 and -0.22, respectively. Compared with EMSIP, FDMDIP and HAZSQBD, the proposed algorithm saves additional encoding time of 22.72%, 10.52% and 31.66%, with 0.21, 0.16 and 0.19 BDBR savings, respectively. As can be seen from Table V, the computation time of the proposed algorithm is decreased by 77.88%, and the computation time of EMSIP, FDMDIP and HAZSQBD is reduced by 59.82%, 70.82% and 51.84%. The BDBR of the proposed algorithm is -0.27, and the BDBRs of EMSIP, FDMDIP and HAZSQBD are -0.11, -0.36 and -0.23, respectively. Compared with EMSIP, FDMDIP and HAZSQBD, the proposed algorithm saves additional encoding time of 18.06%, 7.06% and 26.04% with 0.16, -0.09 and 0.04 BDBR savings, respectively.

Therefore, the proposed algorithm is effectively faster than the other three methods under the conditions of C1 and C2. This is because more unlikely modes and depths are skipped. Thus, the coding speed is significantly improved. In Table IV and Table V, the coding speed of all the four algorithms under the condition of C2 is slightly higher than that under the condition of C1. Because QP factors used in the condition of C2 are greater than those in C1, more AZB and PZB appear under the condition of C2.

From Table IV and Table V, we can observe that the coding speed is significantly improved. In quality SHVC, for a CU in the EL and its co-located CU in the BL, only the QP factors used in the different layers are different. Consequently, there is a strong inter-layer correlation and the ILR mode can be used to accurately predict the corresponding CU in the EL. Therefore, a great number of CUs adopt the ILR mode for prediction at a low coding depth, such as the coding depth of 0 or 1. Compared with the Intra mode and the deep coding depths, the ILR mode and low coding depths generally require less time for evaluation. The proposed PBAET and PBPET strategies can effectively skip the time-consuming evaluations for the Intra mode and the deep coding depths, thus significantly improving the coding speed.

The improvement in coding speed generally leads to a decrease in coding efficiency, namely an increase in BDBR. However, it is observed from Tables I to V that coding efficiency is occasionally improved compared with the SHM reference software. This can be attributed to the Intra prediction process, where CUs are predicted by reference pixels. It is apparent that when the texture of CUs and their reference pixels are more similar, the corresponding Intra prediction is more accurate, and the generated RD costs are smaller accordingly, and vice versa. For a particular CU to be coded, different methods lead to different neighboring CUs, which contain different reference pixels, and in turn, lead to different RD costs for the CU to be coded. In a word, this is caused by RD dependency among coding CUs [33] [34]. We have analyzed the reason why our method decreases and increases the BDBR at times in detail [START_REF] Wang | Fast Depth and Mode Decision in Intra Prediction for Quality SHVC[END_REF]. To further enhance coding efficiency, some optimized bit allocation schemes may be considered [35] [36].

VII. CONCLUSION

In order to improve the speed of the Intra coding process in QSHVC, this paper proposes an efficient probability-based zero block early termination algorithm. We first derive the AZB decision conditions based on the distribution of residual coefficients and develop the PZB predict process to obtain the proportion of zero-valued quantized coefficients, and then combine mode and depth probabilities to early terminate the process of mode and depth selections. The experimental results demonstrate that the proposed algorithm can significantly improve the speed of video coding with a noticeable increase in coding efficiency. These results show that the proposed algorithm can efficiently simulcast different quality versions of the same video content in one bit-stream, which is of great use for broadcasters and end-users alike. In future, we plan to develop zero-block algorithms for 3D-HEVC [START_REF] Pan | RDEN: Residual Distillation Enhanced Network-Guided Lightweight Synthesized View Quality Enhancement for 3D-HEVC[END_REF] [38], Multiview Video Coding [START_REF] Lei | Disparity-Aware Reference Frame Generation Network for Multiview Video Coding[END_REF] and Screen Content Coding [40] [41].

Fig. 1 :

 1 Fig. 1: Flowchart of the overall algorithm

Fig. 2 : 7 ∑ 𝑖=0 7 ∑𝑗=0𝑑

 277 Fig. 2: Relationship between 𝑘 and the error rate

  tire CU. According to the percentage of zero-valued quantized coefficients, we divide it into eight intervals, namely, [0∼0.125], [0.125∼0.25], [0.25∼0.375], [0.375∼0.5], [0.5∼0.625], [0.625∼0.75], [0.75∼0.875], and [0.875∼1]. Similar to the previous section, we divide the probability of the ILR mode being selected as the best one into five intervals: [0%∼20%], [20%∼40%], [40%∼60%], [60%∼80%], and [80%∼100%]. Consequently, each of these intervals is evaluated to select the optimal zero-valued quantized coefficient interval. When the probability of the ILR mode being selected

Frederic

  Dufaux (Fellow, IEEE) received the M.Sc. degree in physics and the Ph.D. degree in electrical engineering from EPFL in 1990 and 1994, respectively. He is the CNRS Research Director with Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des Signaux et Systèmes (L2S, UMR 8506), where he is the Head of the Telecom and Networking hub. His research interests include image and video coding, 3D video, high dynamic range imaging, visual quality assessment, video surveillance, privacy protection, image and video analysis, multimedia content search and retrieval, and video transmission over wireless network. He has authored or coauthored 3 books, more than 200 research publications, and 20 patents issued or pending. He was the Vice General Chair of ICIP 2014, the General Chair of MMSP 2018, and the Technical Program Co-Chair of ICIP 2019 and ICIP 2021. He served as the Chair of the IEEE SPS Multimedia Signal Processing Technical Committee in 2018 and 2019. He was a member of the IEEE SPS Technical Directions Board from 2018 to 2021. He is the Chair of the Steering Committee of ICME in 2022 and 2023. He was also a Founding Member and the Chair of the EURASIP Technical Area Committee on Visual Information Processing from 2015 to 2021. He was the Editor-in-Chief of Signal Processing: Image Communication from 2010 to 2019. Since 2021, he has been the Specialty Chief Editor of the section on Image Processing in the journal Frontiers in Signal Processing. He is also on the Executive Board of Systematic Paris-Region, a European competitiveness cluster that brings together and drives an ecosystem of excellence in digital technologies and DeepTech. Ce Zhu (Fellow, IEEE) received the B.S. degree in electronic and information engineering from Sichuan University, Chengdu, China, in 1989, and the M.Eng. and Ph.D. degrees in electronic and information engineering from Southeast University, Nanjing, China, in 1992 and 1994, respectively. He was a Postdoctoral Researcher 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 the 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, 3-D video, visual perception and applications. He is a co-recipient of multiple paper awards at international conferences, including the most recent Best Demo Award in IEEE MMSP 2022, and the Best Paper Runner Up Award in IEEE ICME 2020. 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 CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, IEEE TRANSACTIONS ON BROADCASTING, and IEEE SIGNAL PROCESSING LETTERS, an Editor of IEEE COMMUNICA-TIONS SURVEYS AND TUTORIALS, and an Area Editor of Signal Processing: Image Communication. He has also served as a Guest Editor of a few special issues in international journals, including as a Guest Editor in the IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING. He is an APSIPA Distinguished Lecturer from 2021 to 2022, and was also an IEEE Distinguished Lecturer of Circuits and Systems Society from 2019 to 2020.

TABLE I :

 I Coding efficiency, expressed by BDBR, under different 𝛼

	𝛼
	Sequence	1	2	3	4	5	6

TABLE II :

 II Coding efficiency, expressed by BDBR, for various percentage intervals of zero-valued coefficients

	Sequence	Intervals	0∼0.125 0.125∼0.25 0.25∼0.375 0.375∼0.5 0.5∼0.625 0.625∼0.75 0.75∼0.875 0.875∼1
	sunflower	-0.10%	-0.10%	-0.10%	-0.10%	0.00%	0.00%	0.00%	0.10%
	tractor	-0.20%	-0.20%	-0.20%	-0.20%	-0.10%	-0.10%	0.00%	0.00%
	park	-0.20%	-0.20%	-0.20%	-0.20%	-0.10%	-0.10%	0.00%	0.00%
	town	-0.40%	-0.40%	-0.40%	-0.30%	-0.30%	-0.20%	-0.10%	0.00%
	Flowervase	0.80%	0.80%	0.70%	0.50%	0.40%	0.30%	0.10%	0.00%
	PartyScene	-0.60%	-0.60%	-0.60%	-0.40%	-0.30%	-0.30%	0.00%	0.00%
	BlowingBubbles	0.60%	0.60%	0.60%	0.50%	0.40%	0.20%	0.10%	0.10%
	RaceHorses	-0.40%	-0.40%	-0.40%	-0.30%	-0.30%	-0.20%	-0.10%	-0.10%

TABLE III :

 III Performance Comparison between PBAET and PBPET

	Sequence	PBAET TS(%) BDBR(%) TS(%) BDBR(%) PBPET
	Traffic	77.11	-0.27	83.53	-0.38
	PeopleOnStreet 78.58	-0.22	82.81	-0.35
	Kimono	75.63	-0.23	83.69	-0.26
	ParkScene	73.51	-0.21	76.41	-0.20
	Cactus	72.78	-0.27	77.24	-0.30
	BasketballDrive 73.79	-0.37	78.10	-0.39
	BQTerrace	73.82	-0.29	76.44	-0.29
	Average	75.03	-0.27	79.75	-0.31

TABLE IV :

 IV Performance comparison among different algorithms under the condition of C1

	Sequence	Proposed BDBR(%) TS(%) BDBR(%) TS(%) BDBR(%) TS(%) BDBR(%) TS(%) EMSIP [15] FDMDI [16] HAZSQBD [28]
	Traffic	-0.53	85.01	-0.29	53.38	-0.44	77.18	-0.27	49.45
	PeopleOnStreet	-0.62	84.86	-0.26	46.13	-0.40	76.64	-0.27	49.11
	Kimono	-0.36	84.17	-0.21	69.17	-0.36	74.68	-0.21	51.47
	ParkScene	-0.24	77.52	-0.23	55.23	-0.29	67.61	-0.24	49.28
	Cactus	-0.36	77.43	-0.28	62.38	-0.23	69.06	-0.25	48.23
	BasketballDrive	-0.42	84.29	-0.03	66.41	0.01	69.41	-0.16	51.05
	BQTerrace	-0.33	79.49	-0.08	60.99	-0.06	64.53	-0.12	52.52
	Average	-0.41	81.82	-0.20	59.10	-0.25	71.30	-0.22	50.16

TABLE V :

 V Performance comparison among different algorithms under the condition of C2

	Sequence	Proposed BDBR(%) TS(%) BDBR(%) TS(%) BDBR(%) TS(%) BDBR(%) TS(%) EMSIP [15] FDMDIP [16] HAZSQBD [28]
	Traffic	-0.42	81.45	-0.17	49.95	-0.57	74.67	-0.27	53.12
	PeopleOnStreet	-0.43	82.32	-0.07	52.54	-0.39	73.95	-0.29	51.56
	Kimono	-0.34	82.20	-0.26	68.95	-0.40	72.84	-0.22	52.52
	ParkScene	-0.29	73.83	-0.04	58.12	-0.37	68.28	-0.27	52
	Cactus	-0.23	73.85	-0.09	64.58	-0.28	70.56	-0.25	51.21
	BasketballDrive	-0.09	78.01	-0.14	62.23	-0.37	70.29	-0.18	48.65
	BQTerrace	-0.11	73.52	-0.01	62.35	-0.13	65.14	-0.15	53.81
	Average	-0.27	77.88	-0.11	59.82	-0.36	70.82	-0.23	51.84

This work was supported in part by the National Natural Science Foundation of China under Grant U19A2052, Grant 62020106011, Grant 61972060, 62027827 and 62221005; in part by the Natural Science Foundation of Chongqing under Grant cstc2020jcyj-zdxmX0025 and cstc2020jcyj-msxmX0766; in part by the Science and Technology Research Program of Chongqing Municipal Education Commission under Grant KJZD-K202100604; in part by the Guizhou Provincial Science and Technology Plan Project under Grant Qiankehejichu-ZK[2023]Yiban252; and in part by the Shangrao Basic Research Program under Grant 2021F003. D. Wang is with Chongqing Key Laboratory on Big Data for Bio Intelli-


Robert Floyd. Assigning Meanings to Programs. 1967 Tony Hoare. An Axiomatic Basis for Computer Programming. 1969

STOP r ′ = 1 u ′ = 1 v ′ = u TEST r -n s ′ = 1 u ′ = u + v s ′ = s + 1 r ′ = r + 1 TEST s -r STOP r ′ = 1 u ′ = 1 v ′ = u TEST r -n s ′ = 1 u ′ = u + v s ′ = s + 1 r ′ = r + 1 TEST s -r u ← 1 for r = 0 to n -1 do v ← u for s = 1 to r do u ← u + v STOP r ′ = 1 u ′ = 1 v ′ = u TEST r -n s ′ = 1 u ′ = u + v s ′ = s + 1 r ′ = r + 1 TEST s -r precondition {n ≥ 0} u ← 1 for r = 0 to n -1 do v ← u for s = 1 to r do u ← u + v postcondition {u = n! } STOP r ′ = 1 u ′ = 1 v ′ = u TEST r -n s ′ = 1 u ′ = u + v s ′ = s + 1 r ′ = r + 1 TEST s -r precondition {n ≥ 0} u ← 1 for r = 0 to n -1 do invariant {u = r ! } v ← u for s = 1 to r do invariant {u = s × r ! } u ← u + v postcondition {u = n! } verification condition forall n:int. n >= 0 -> (0 > n -1 -> 1 = n!) /\ (0 <= n -1 -> 1 = 0! /\ (forall u:int. (forall r:int. 0 <= r /\ r <= n -1 -> u = r! -> (1 > r -> u = (r + 1)!) /\ (1 <= r -> u = 1 * r! /\ (forall u1:int. (forall s:int. 1 <= s /\ s <= r -> u1 = s * r! -> (forall u2:int. u2 = u1 + u -> u2 = (s + 1) * r!)) /\ (u1 = (r + 1) * r! -> u1 = (r + 1)!)))) /\ (u = ((n -1) + 1)! -> u = n!)))
and then what do we do with this mathematical statement? we could perform a manual proof (as Turing and Hoare did) but it is long, tedious, and error-prone so we turn to tools that mechanize mathematical reasoning • type polymorphism • variants

• limited support for higher order

• pattern matching • exceptions

• break, continue, and return

• ghost code and ghost data

• mutable data with controlled aliasing

• contracts • loop and type invariants 13 / 45

WhyML, a specification language

• polymorphism & algebraic types

• limited support for higher order

• inductive predicates

.. } ensures { (0 <= r < length a -> a[r] = v) /\ (r = -1 -> forall i. 0 <= i < length a -> a[i] <> v) }
let binary search (a: array int) (v: int) : (r: int) requires { ... the array a is sorted .

.. } ensures { (0 <= r < length a -> a[r] = v) /\ (r = -1 -> forall i. 0 <= i < length a -> a[i] <> v) }
the program can return -2 and yet be proved correct! let binary search (a: array int) (v: int) : (r: int) requires { ... the array a is sorted .

.. } ensures { -1 <= r < length a /\ 0 <= r < length a -> a[r] = v /\ r = -1 -> forall i. 0 <= i < length a -> a[i] <> v } let binary search (a: array int) (v: int) : (r: int) requires { ... the array a is sorted ... } ensures { -1 <= r < length a /\ 0 <= r < length a -> a[r] = v /\ r = -1 -> forall i. 0 <= i < length a -> a[i] <> v }
the program can return 42 and yet be proved correct! (missing parentheses)

good practice write and verify some client code let test () = let a = Array.init 5 (fun i -> i) in let r = binary search a 0 in assert { r = 0 }; let r = binary search a 5 in assert { r = -1 }; ...

Why3 logic is total

• recursive functions and predicates must terminate

  s -> if i=0 then x else lookup (i-1) (Zero s) | Zero s -> let (x0, x1) = lookup (i/2) s in if i%2 = 0 then x0 else x1 end for 200+ more examples, see https://toccata.gitlabpages.inria.fr/toccata/gallery/ • VC generation using WP or fast WP • 70+ VC transformations (≈ tactics) • support for 25+ ATP and ITP systems • GUI for autoactive verification • recorded proof sessions, batch replay • Why3 in your browser binary search let binary search (a: array int) (v: int) : (r: int) requires { ... the array a is sorted ... } ensures { ... r is an index where v appears, or -1 is there is no such index ... } let binary search (a: array int) (v: int) : (r: int) requires { ... the array a is sorted .

  they have the same weight, apart from one, which is lighter you are given a Roberval balance using the balance at most twice, determine the lighter ball


Dinis Moreira

Diana Gomes

Ricardo Graça
email: ricardo.graca@fraunhofer.ptdbanyay@kth.sepatricia@damel.pt

Dániel -3944-607x]

Bányay

Patrícia Ferreira

Real-time Surf Manoeuvres' Detection Using Smartphones' Inertial Sensors

Keywords: Surf, Manoeuvre Detection, Inertial Sensors, Monitoring System, Machine Learning, Smartphone, Sports Performance

Surfing is currently one of the most popular water sports in the world, both for recreational and competitive level surfers. Surf session analysis is often performed with commercially available devices. However, most of them seem insufficient considering the surfers' needs, by displaying a low number of features, being inaccurate, invasive or not adequate for all surfer levels. Despite the fact that performing manoeuvres is the ultimate goal of surfing, there are no available solutions that enable the identification and characterization of such events. In this work, we propose a novel method to detect manoeuvre events during wave riding periods resorting solely to the inertial sensors embedded in smartphones. The proposed method was able to correctly identify over 95% of all the manoeuvres in the dataset (172 annotated manoeuvres), while achieving a precision of up to 80%, using a session-independent validation approach. These findings demonstrate the suitability and validity of the proposed solution for identification of manoeuvre events in real-world conditions, evidencing a high market potential.

Introduction

Surf has been increasing its popularity worldwide, for both competitive and recreational levels. Minimal training and equipment makes this an appealing water sport for everyone [START_REF] Mendez-Villanueva | Physiological aspects of surfboard riding performance[END_REF]. Paddle, stationary, wave riding and some miscellaneous events are the four main activities of a surf session [START_REF] Mendez-Villanueva | Physiological aspects of surfboard riding performance[END_REF][START_REF] Minghelli | Time-motion analysis in surf: benefits[END_REF]. Despite the exponential increase in the field of sports trackers, there have not been significant

Financial support from project TexBoost -less Commodities more Specialities (POCI-01-0247-FEDER-024523), co-funded by Portugal 2020, framed under the COMPETE 2020 (Operational Program Competitiveness and Internationalization) and European Regional Development Fund (ERDF) from European Union (EU).

developments in the specific surf area [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF]. Although performing manoeuvres is the ultimate goal in surfing, there are few solutions available for surfers' assistance, especially concerning the characterization of rotational movements and performed manoeuvres.

Tools that can track and measure surfers' progress over time are quite appealing and needed for surf practitioners, specially when no external guidance is provided [START_REF] Mendez-Villanueva | Physiological aspects of surfboard riding performance[END_REF][START_REF] Farley | Performance analysis of surfing: A review[END_REF]. However, the analysis of the events that occur during wave riding periods can be a challenge. Moreover, even if a great part of surf session analytics (e.g. paddle duration, wave counting) are currently being performed by some commercial solutions, these still lack manoeuvre identification and evaluation, which is a relatively new and unexplored domain [START_REF] Mendez-Villanueva | Physiological aspects of surfboard riding performance[END_REF][START_REF] Farley | Performance analysis of surfing: A review[END_REF].

Most of these surf monitoring systems generate biofeedback based on sensor data retrieved during the training session, and are capable of providing some additional information about the executed movements [START_REF] Farley | Performance analysis of surfing: A review[END_REF][START_REF] Chambers | The use of wearable microsensors to quantify sport-specific movements[END_REF][START_REF] Mendes | Sensor fusion and smart sensor in sports and biomedical applications[END_REF]. Currently, most of these solutions can only count the number of waves and paddle time, estimate speed, distance and movements pattern during the session using Global Positioning System (GPS) and/or Inertial Measurement Units (IMU) measurements [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF][START_REF]Rip curl search gps[END_REF][START_REF]Glassy pro[END_REF][START_REF] Coutts | Validity and reliability of gps devices for measuring movement demands of team sports[END_REF]. However, they lack detail during the most important surf eventwave riding [START_REF] Farley | Performance analysis of surfing: A review[END_REF]. Moreover, and specifically for manoeuvre detection purposes, there is a low number of available studies and real-world validations [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF][START_REF] Dos Santos | Surf biomechanics and bioenergetics[END_REF]. As such, there is a gap in the market concerning surf manoeuvre detection.

Surf manoeuvres may be difficult to distinguish, especially for non-experts [START_REF] Scarfe | The science of surfing waves and surfing breaks-a review[END_REF]7]. Thus, the automatic analysis of these events may be considered a difficult task. Differences between two manoeuvres are often only evident in the "dynamics" or "elegance" in their execution. Even in surf competitions, the evaluation process made by the judges is usually subjective and based on the average of their opinions, highlighting even more the importance of having a solution capable of thorough identification, characterisation and evaluation all of the performed manoeuvres [7].

This context motivated the development of a new algorithm for the detection and characterisation of the the performed manoeuvres during wave riding periods in real-world conditions, solely resorting to the inertial sensors embedded in a smartphone. In this sense, this manuscript proposes a novel approach for the segmentation and identification of the performed manoeuvres for moderate to experienced surfers.

The remainder of the paper is organised as follows: section 2 describes prior work conducted in this field; section 3 describes the dataset and proposed methodology of the study; sections 4 and 5 report and discuss the main findings of this study, respectively; section 6 highlights the main conclusions and points out possible directions for future work.

Related Work

There are only a few commercially available solutions for surf monitoring purposes, and even less if we only consider manoeuvre detection and analysis. Most of the current commercially available solutions are only based in GPS data. Thus, these solutions can only extract top-level information about the surf session, such as wave count, travelled distance or wave speed. Detecting more complex surfing movements, such as in-wave manoeuvres, is hard or even impossible to perform with this type of solutions given the single source of available data. One example of this type of commercially available solutions is the Rip Curl Search GPS watch. Additionally, some mobile applications have also been developed such as Surf Track [START_REF]Surf track app[END_REF], Dawn Patrol [START_REF]Dawn patrol[END_REF] and WavesTracker [START_REF]Waves tracker[END_REF], but very little information regarding their functioning, validity or system setup is provided.

The combined use of GPS and inertial sensor data, i.e. accelerometer, gyroscope and magnetometer sensors, has been widely reported in the literature to effectively increase overall robustness and precision of human activity recognition applications [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF]. Therefore, other solutions that make use both of GPS and inertial sensor data, such as the GlassyPro wristband [START_REF]Glassy pro[END_REF] or Xensr Air [START_REF]Xensr air[END_REF] surfboardmounting device, are some of the commercially available solutions that currently combine several sources of data. However, they may not be entirely suitable for manoeuvre detection purposes. Wrist-worn devices, like the GlassyPro, may be practical and easy to use, but due to their positioning on the body, may be insufficient for manoeuvre detection and characterization purposes. Torso and board rotations are important metrics for wave performance analysis and extremely important when trying to identify and evaluate certain manoeuvres, and wristmounted sensors may not be suitable for this task. There are also devices that were designed to be mounted in the surfboard, like Xensr Air and Trace Up. However, to the best of the authors' knowledge, these devices are currently not available for purchase. Moreover, these can be associated with some safety issues due to its size and attachment to the surfboard, and they do not track the surfer's actual movements.

Besides the commercially available solutions, some research studies were also conducted, aiming surf monitoring and/or performance analysis. Madureira et al. [START_REF] Madureira | Comparison of number of waves surfed and duration using global positioning system and inertial sensors[END_REF] proposed an algorithm comparing the use of GPS sensor alone and together with inertial sensors data for wave detection. Similarly, Hoettinger et al. [START_REF] Hoettinger | Activity recognition in surfing-a comparative study between hidden markov model and support vector machine[END_REF] proposed a machine learning based approach for differentiating wave from non-wave events, using sliding windows of 2.0 seconds with 75% overlap, also achieving accurate results. However, none of these studies performed any type of analysis related to manoeuvre identification or characterisation, highlighting the novelty of this study.

Methodology

Data annotation

The dataset reported in [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF] was used to conduct this study, featuring raw data from the accelerometer, gyroscope and magnetometer during all of the recorded surf sessions. This dataset had already been annotated for several surf events, including wave riding periods. We selected the sessions of the 5 advanced-level surfers in the dataset, since appropriately performing manoeuvres during wave riding is a demanding task in the sport, characteristic of experienced surfers.

A dual-source data annotation tool enabling synchronized signal and video visualization was created to finely annotate manoeuvre periods in each wave. Manoeuvre annotation was a challenging process, due to the similarity between some manoeuvres, the particular technique of each surfer, and lack of clear view of the surfer in some situations (e.g. agitated sea, distance). Moreover, annotations were performed by non-specialists in this area and therefore, can be subjective and prone to human error. To minimize its influence, we opted not to consider events in which the annotator was unsure of the label to assign or the temporal limits of the movement, and unsuccessful manoeuvres, i.e. ending in a fall. 1 provides an overview of the final dataset with annotated manoeuvres. The most represented manoeuvres were cutback and snap. A snap consists in a radical change of trajectory in the pocket or on the top of the wave; when performed abruptly, it produces spectacular and flashy buckets of spray. A cutback consists in riding up the wave shoulder, turning back towards the breaking part of the wave without losing speed and ending up with a re-entry in the critical section of the wave.

Data processing

Figure 2 presents a graphical overview of the processing steps used in this study. A thorough explanation of each of these steps is provided in the following subsections. Data stream segmentation An overlapping sliding window approach was implemented for data stream segmentation (Figure 3). Since the selection of window size may be considered an empirical and task-oriented problem, highly related with the duration of the event of interest and/or the maximum expected recognition latency, different window sizes were evaluated, considering the distribution of manoeuvre duration in our dataset, presented in Table 1: 2.0, 2.5, 3.0, and 3.5 seconds, with fixed overlap of 25%. Each time-window with over 70% of match with a certain annotated manoeuvre was assigned a positive class label. All remaining samples were assigned a negative class label.

Annotated ground truth manoeuvres' windows were also considered for the pipeline optimization step. Feature extraction A set of generic and domain-specific features were extracted from each of the 3-axis orientation components (heading, pitch, roll) obtained after sensor fusion using the gradient descent-based algorithm of [START_REF] Madgwick | Estimation of imu and marg orientation using a gradient descent algorithm[END_REF], the magnitude of the 3-axis linear acceleration, and the magnitude of the XY components of the linear acceleration for each time-window.

Time-domain features such as minimum, maximum, variance, skewness, kurtosis, mean cross ratio, waveform length [START_REF] Lotte | A new feature and associated optimal spatial filter for eeg signal classification: Waveform length[END_REF] and interquartile range values were calculated for each time window.

Features based on the wavelet transformation of the input signals were also calculated. Wavelet transform decomposes a signal according to the frequency, representing the frequency distribution in the time domain [START_REF] Rhif | Wavelet transform application for/in non-stationary time-series analysis: A review[END_REF]. We used the implementation of the Wavelet Packet Transform of the PyWt library [START_REF] Lee | Pywavelets: A python package for wavelet analysis[END_REF], with Daubechies 2 (db2) as mother wavelet and a maximum decomposition level of 3, for performing a time-frequency analysis of the linear acceleration and orientation signals, respectively. For each resolution level, the relative wavelet energy was calculated for each associated frequency band [START_REF] Salwani | Relative wavelet energy as a tool to select suitable wavelet for artifact removal in eeg[END_REF][START_REF] Rosso | Wavelet entropy: a new tool for analysis of short duration brain electrical signals[END_REF]. A metric based on the statistical variance of the wavelet coefficients was also calculated for each resolution level and associated frequency bands [START_REF] Ziaja | Fault detection in rolling element bearings using wavelet-based variance analysis and novelty detection[END_REF].

A set of other features which intended to describe the rotational dynamics of the movements were also extracted from the heading orientation signal. All local extremas were identified to generate minima-maxima-minima and minimamaxima-minima-maxima sequences (Figure 4). These domain-specific features The feature extraction step resulted in a total of 199 features for each time window.

Pipeline optimization A domain-specific resampling strategy was implemented to handle dataset imbalance, since the number of instances from the positive class was always inferior to the number of instances from the negative class for all tested window sizes. This strategy consisted in discarding non-manoeuvre segments with the highest percentages of manoeuvre match successively until the classes were balanced.

The optimization and selection of the learning pipeline was performed using a tool called Feature-based Machine Learning (FbML), created at Fraunhofer AICOS. This tool is based on the open-source project auto-sklearn [START_REF] Feurer | Efficient and robust automated machine learning[END_REF], and allows a search space initialization via meta-learning (search similar datasets and initialize hyper-parameter optimization algorithm with the found configuration) while providing a vast list of options for data pre-processing (balancing, imputation of missing values, re-scaling), feature transformation, and feature and classifier selection. As such, we explored pipelines generated with the following combinations of methods: At each new test, the results and parameters of the 5 best classification pipelines were stored for further evaluation.

Leave-one-session-out validation

In order to study model generalization for different acquisition conditions (i.e. sessions), we implemented a leave-onesession-out validation approach. At each iteration i, where i ∈ [1, N ] and N represents the total number of different sessions, all of the instances from the surf session S i were selected for testing while the remaining ones were used for re-fitting the pipeline. The pipeline was defined by the best combination of methods and hyperparameters which resulted from the FbML optimization with cross-validation.

While this approach allows us to assess the performance of the method under session-independent conditions, it will still not be enough to fully assess performance in real-world conditions, since consecutive windows containing data from a same manoeuvre should be merged in order to deliver a proper count and useful information to the user. As such, we created a methodology (post-processing step of Figure 2) which merges consecutive positive predictions in pairs, setting them to correspond to a same manoeuvre M . If, after two windows are already merged, a new and single positive prediction occurs, this window may also be considered to belong to M if its classification probability is greater than that of the previous window. Otherwise, it will be set to correspond to a new manoeuvre.

Manoeuvre detection results were computed considering the predictions per window (for selection of the best window size and an overall assessment of pipelines' performance) and after considering the post-processing needed for utilization in real-world conditions (predictions per manoeuvre), as Figure 2 indicates.

Results

Table 2 combines the results of the best set of pipelines generated by the FbML after the leave-one-session-out validation considering the predictions per window, for different window sizes with a fixed overlap of 25%. These results support that the best overall performance was attained with windows of 2 s, associated with a F1-score (optimization metric) of 0.91. This segmentation approach was thus selected and used in all further experiments. Table 2: Average performance of the top 5 classification pipelines obtained by the FbML considering the predictions per window, using leave-one-session-out validation.

Window

Average ± Standard Deviation Size (s) F1-score Precision Recall Accuracy 2 0.91 ± 0.01 0.92 ± 0.02 0.90 ± 0.01 0.91 ± 0.01 2.5 0.86 ± 0.02 0.88 ± 0.01 0.84 ± 0.03 0.86 ± 0.02 3.0 0.88 ± 0.01 0.89 ± 0.01 0.86 ± 0.01 0.88 ± 0.01 3.5 0.84 ± 0.02 0.85 ± 0.02 0.83 ± 0.03 0.83 ± 0.02

Table 3 exhibits the final manoeuvre detection results, after the post-processing step. True positives (TP) correspond to detected manoeuvres' time segments which overlap with annotated manoeuvres' periods. False positives (FP) correspond to detected manoeuvres' periods which do not overlap with annotated manoeuvres. False negatives (FN) correspond to annotated manoeuvres which were not detected (do not overlap) with any positive prediction segment. All of the top 5 pipelines derived from the FbML optimization process relied on an Adaboost classifier, and performed a feature scaling step. The pipelines which implemented univariate feature selection are associated with the highest F1-scores (0.88). All pipelines were able to detect at least 95% of the annotated manoeuvres, despite the demanding circumstances under which the tests took place, since session-independence was preserved. The impact of false positives was also taken into consideration: the lowest precision was 0.76.

Discussion of results

The results reported in Table 2 enabled a reasoned selection of the best segmentation approach and an overall understanding of the performance of the method. Our results support that, out of the experimented window sizes, windows of 2 s are the most appropriate for manoeuvre segmentation and classification. Windows of 2 s led to the highest number of samples in the dataset. Moreover, considering the average manoeuvre duration in our dataset, it is reasonable to conclude that keeping segments of 2 s and an overlap of 25% between consecutive samples guarantees that most manoeuvre periods are contained in 1 window or 2 consecutive windows. This approach was, thus, selected as segmentation method.

Overall, the results obtained using the predictions per window were considered very promising towards adequate manoeuvre detection using our method. However, the performance metrics exhibited in Table 3 are the most critical to understand if the method generates reliable and intelligible information for the surfer in terms of manoeuvre detection in real-world conditions.

We were able to correctly identify over 95% of all annotated manoeuvres in the dataset, while achieving a precision of up to 80%. False positive occurrences were mostly related with the following situations: 1) finishing wave riding with a failed manoeuvre, ending in a fall; 2) segments which most likely corresponded to manoeuvres, but corresponding to times when the annotator did not have clear sight of the surfer; 3) conservative annotation process which only considered periods of absolute certainty as ground truth manoeuvres. Optimizing the trade-off between false positive and negative predictions is a well-known challenge of machine learning problems. As such, and considering the aforementioned situations, we consider that the reported results are appropriate and support the adequate performance of the method in real-world conditions.

Another important detail of this study is that it maintained a session-independent validation approach. Thus, the attained results support the appropriate generalization of the method for different users and different acquisition conditions, including sea level and agitation variation and slightly different positioning of the smartphone in the users' back.

Challenges and Limitations of the Study

Despite the comprehensive amount of collected sessions available in the dataset of [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF], we were only able to use the sessions from 5 surfers, since these were the only users with the necessary level of expertise to perform in-wave manoeuvres. Our dataset was finally mainly composed of cutback and snap manoeuvres, with very little representation of the remaining ones. This can be considered a limitation of the study, as there is no certainty of the performance of the method for unseen manoeuvres.

Another limitation is related with the fine time limits for ground truth manoeuvre annotation, and the challenges of the annotation process (discussed above), which may impair a full reliable quantification of the performance of the method [START_REF] Alsallakh | A visual analytics approach to segmenting and labeling multivariate time series data[END_REF]. A second annotation round with surf experts may be an adequate approach to tackle this limitation, followed by a comparative analysis of the expected improvements.

The labelling criteria for each time-window may also be a source of error of the method, as the definition of these criteria was empirically performed. It would also be interesting to implement and test dynamic data stream segmentation techniques, and assess if it would be possible to achieve improved fits of the generated time segments with annotated manoeuvre periods using such techniques.

Conclusions

This manuscript details the development of a surf manoeuvre detection algorithm, using data from the smartphone's inertial sensors and a machine learning pipeline optimized for the problem in hands. Several time-window sizes were tested, and windows of 2 s with 25% overlap delivered the best results. Manoeuvres were detected with up to 88% F1-score under our real-world conditions validation, which is very promising for a real-world application and should have a high market potential.

As future work, we intend to combine the outcome of this study with the work of [START_REF] Gomes | Surf session events' profiling using smartphones' embedded sensors[END_REF] to create a full surf monitoring solution which simultaneously detects surf session events (namely, waves), and further segments these periods to deliver more performance metrics to the surfer concerning fine events, i.e. in-wave manoeuvres.

Fig. 1 :

 1 Fig. 1: Snapshot frames of the execution of the detected manoeuvres: snap (top) and cutback (bottom).

Fig. 2 :

 2 Fig. 2: Data processing operations overview.

Fig. 3 :

 3 Fig. 3: Example of two consecutive sliding windows.

Fig. 4 :

 4 Fig. 4: Heading evolution over time for a wave riding period with several annotated manoeuvres (top) and a manoeuvre time-window with local extrema detection (bottom).

Table 1 :

 1 Dataset description.Table

	No. sessions		8
	No. users		5
	No. waves		165
	Wave duration (avg ± std)		9.73 ± 5.43 s
			Snap	71
	No. manoeuvres	172	Cutback 94
			Other	7
	Manoeuvre duration (avg ± std)		2.45 ± 0.75 s

Table 3 :

 3 Manoeuvre detection performance after application of the timewindows' merging criteria (real-world conditions) for each of the top 5 pipelines derived from the FbML optimization process.

	Pipeline Scaler Selection Classifier TP FP FN Recall Precision F1-Score
	1	Min-Max	-		168 54 4	0.98	0.76	0.85
	2	Robust	-		164 45 8	0.95	0.78	0.86
	3	Min-Max Univariate	Adaboost	167 42 5	0.97	0.80	0.88
	4	Min-Max	-		164 41 8	0.95	0.80	0.87
	5	Min-Max Univariate		165 40 7	0.96	0.80	0.88