Yuyang Liu

Ce Zhu

Fellow, IEEE Min Mao

Fangliang Song

Frederic Dufaux

Fellow, IEEE Xiang Zhang

Video Analytical Coding: When Video Coding Meets Video Analysis

Keywords: Video analysis, video analytical coding, analytical distortion, rate distortion optimization

Leveraging on the properties of human visual system, most of the well-designed video coding standards utilize rate-distortion optimization techniques by maximizing a fidelity cost function (e.g. peak signal noise ratio, PSNR) under an available bit rate budget constrain. However, a huge amount of video data is consumed by computers rather than by human beings in several application scenarios. In view of this, this paper proposes a new coding framework called video analytical coding (VAC) for video analysis.

We use the term "analytical distortion" to denote the difference of video analysis performance when video quality degrades and analytical distortion is estimated by compression distortion. Meanwhile, we develop a new rate-analytical-distortion optimization (RADO) method to trade off the bit rate and the analytical distortion. Specifically, we consider moving object detection as the analysis task and develop a novel rate analytical distortion (RAD) model and a quantization parameter adaptation strategy for video coding, where the analytical distortion is related to the object detection performance represented as F1measure. Experimental results show that the performance of the video analysis task can be significantly improved (up to 40% reduction of analytical distortion).

Introduction

The increasing availability of portable or installed cameras and the introduction of new multimedia applications to fulfill emerging needs, have given rise to new requirements on video compression and communication. As for many multimedia applications, e.g. surveillance, video content is not only presented to human beings but also analyzed by computers for variously applicable purposes, such as object detection, tracking, recognition, and so on. In other words, computers have become as viewers of the videos. Meanwhile, the considerable amount of generated videos need to be efficiently compressed due to the cost-effective storage and bandwidth limitation.

Currently, the main goal of most studies on video coding is to achieve high coding efficiency. Most of the widely deployed video coding standards, such as H.264/MREG-4 AVC (Advanced Video Coding) [START_REF] Wiegand | Overview of the H. 264/AVC video coding standard[END_REF] and HEVC (High Efficiency Video Coding) [START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF], are designed under the assumption that human beings are the target viewers. Meanwhile, traditional rate distortion optimization (RDO) framework is applied into the video coding standards by optimizing the trade-off between the entropy of the discretized representation (rate) and the error arising from the quantization (distortion). However, applying the traditional RDO framework during video compression may be suboptimal when the video is intended for machine analysis. The critical issue is that resulting compression distortion may bring a negative impact on the video analysis performance. This point is shown in Fig. 1. More precisely, a foreground extraction algorithm is run on the same frame without and with compression. Obviously, it can be observed that the extraction results are quite different, especially for the region in red box in Fig. 1(d). Generally, more compression distortion lead to more differences. Additionally, research on video analysis mainly aims to improve the video analysis performance and pays little attention to the negative impact introduced by compression distortion. In view of this, two problems should be addressed [START_REF] Korshunov | Critical video quality for distributed automated video surveillance[END_REF]: (i) How different the video analysis results will be depending on different video quality levels? (ii) How much bandwidth can be saved? Obviously, there is a trade-off between video quality and accuracy of the video analysis algorithms. To solve above problems, we propose a new coding framework, namely video analytical coding (VAC). We develop a new rate-analytical-distortion optimization (RADO) method, where the term "analytical distortion" represents the difference of the video analysis algorithms' performance when video quality degrades. The compression distortion is measure by Sum of Absolute Difference (SAD) in this paper and SAD of each non-I (P or B) frame is estimated by that of an I frame according to the temporal relationship. The analytical distortion is predicted by the compression distortion. Specifically, we choose to focus on one fundamental video analysis task, moving object detection. Accordingly, we develop a rate analytical distortion (RAD) model and an object based quantization parameter (QP) adaptation strategy for video coding. Our proposed method is fully standard compatible and the encoded bit-stream can be decoded by any HEVC decoder. This paper is an extension of our previous work in [START_REF] Liu | Analytical distortion aware video coding for computer based video analysis[END_REF] and the following are the contributions of this paper.

 We propose a novel coding framework VAC for video analysis and accordingly develop a new RADO method to trade off video quality and accuracy of the video analysis algorithm.

 To avoid a two-pass coding procedure, we introduce a model to predict the compression distortion.

Meanwhile, we use the predicted compression distortion to estimate analytical distortion.

 We propose an object based QP adaptation strategy where the object area is compressed using a relatively smaller QP compared with the background.

The reminder of the paper is organized as follows. We review related work in section 2. In section 3, we first present the VAC framework and the compression distortion prediction model for non-I frame.

Then, a brief review of our previous work in [START_REF] Liu | Analytical distortion aware video coding for computer based video analysis[END_REF] is presented including the RADO method and the weighting parameter selection. Our proposed object based QP adaptation strategy is presented in section 3.5. Section 4 experimentally evaluates the proposed method. Section 5 concludes the paper.

Related Work

A considerable amount of work in video coding aims at improving the coding efficiency. The state-ofthe-art video coding standard HEVC can achieve a near 50% bit rate reduction, while keeping comparable perceptual quality, compared with its predecessor H.264/MPEG-4 AVC. Besides, there are many developed RDO schemes for HEVC standard [START_REF] Li | QP determination by lambda value[END_REF]- [START_REF] Zeng | Perceptual adaptive Lagrangian multiplier for high efficiency video coding[END_REF]. In [START_REF] Li | QP determination by lambda value[END_REF], a multiple QP optimization scheme is introduced, where multiple QP candidates are checked to find the best one by minimizing the ratedistortion cost. Such multiple QP optimization scheme will definitely increase the coding complexity since the video codec needs extra time to find the best QP from the QP candidates. In our previous work [START_REF] Gao | Temporally dependent rate-distortion optimization for low-delay hierarchical video coding[END_REF][START_REF] Li | Lagrangian multiplier adaptation for rate-distortion optimization with inter-frame dependency[END_REF], we investigated a RDO scheme taking the inter-frame dependency into account, where the impact of coding performance of the current coding unit on that of the following frames is considered. However, the above RDO schemes do not consider the fact that human visual system pays more attention to region-of-interest (ROI) or foreground objects [START_REF] Itti | Automatic foveation for video compression using a neurobiological model of visual attention[END_REF]. To address this problem, researchers investigate a few coding methods for some specific video applications, such as teleconference and surveillance.

 Teleconference: In conferencing applications, the face area in the video usually attracts the viewers and the background is stationary in most cases. Leveraging on this property, a few ROI based coding methods are developed to further save the transmission bandwidth. Liu et al. [START_REF] Liu | Region-of-interest based resource allocation for conversational video communication of H.264/AVC[END_REF] introduced an efficient face ROI determination method using skin color combined with direct frame difference. A relatively larger portion of bits and more computational power were assigned to encode the detected ROI. Xiong et al. [START_REF] Xiong | Face Region Based Conversational Video Coding[END_REF] used a motion based face detection method combined with an active contour model to find the well-located and compact face regions. Then, they proposed a facial feature priority based bit allocation method for ROI conversational video coding. Zhao et al. [START_REF] Zhao | Region-of-interest based coding scheme for synthesized video[END_REF] proposed a ROI coding scheme for synthesized video aiming at achieving better and consistent quality given a target bit rate. However, there are two major problems in ROI coding methods: 1) the detection and segmentation of the ROI, and 2) more computing power at the encoder side.

 Surveillance: In video surveillance, there is typically little camera motion so that the background parts are mainly static. In order to take advantage of this property, some research has been done recently that selects or generates a picture as a special reference for coding the background regions. Tiwari et al. [START_REF] Tiwari | Selection of long-term reference frames in dual-frame video coding using simulated annealing[END_REF] proposed a long-term reference selection method using simulated annealing, where the selected reference is compressed with high quality. Pushkar et al. [START_REF] Pushkar | Skip decision and reference frame selection for low-complexity H. 264/AVC surveillance video coding[END_REF] selected a coded picture by taking the usage of skip mode into account. Paul et al. [START_REF] Paul | A long-term reference frame for hierarchical B-picture-based video coding[END_REF] modeled pixels of many pictures at the same position as a Gaussian mixture distribution and generated a background picture using the most probable pixel value. Zhang et al. [START_REF] Zhang | Optimizing the hierarchical prediction and coding in HEVC for surveillance and conference videos with background modeling[END_REF] generated a background picture by simply averaging many pictures pixel by pixel. Chen et al. [START_REF] Chen | Block-composed background reference for high efficiency video coding[END_REF] proposed an approach that generates a background picture by updating pixels in some blocks instead of the whole picture. However, these methods have some drawbacks. First, it is often impossible to select a picture as the background reference, which contains the entire background content. Second, generating a picture needs extra processing time and delay to look ahead many future frames or wait for many decoded frames. Furthermore, the generated picture must be compressed with high quality and transmitted to the decoder side. Finally, it is still a problem for these methods to deal with video sequence containing many moving foreground objects, as the foreground pixels are difficult to be filtered out from the background.

The above-mentioned schemes may be suboptimal when video content is consumed by computers rather than human beings. In this context, recent research work focuses on feature-preserving coding, where only feature descriptors are transmitted to the server side. It can be categorized into two paradigms: compress-then-analysis (CTA) and analysis-then-compress (ATC). Redondi et al. [START_REF] Redondi | Compress-then-analysis vs. analysisthen-compress: Two paradigms for image analysis in visual sensor networks[END_REF] compared the performance of CTA and ATC for image analysis in visual sensor networks and found out that the performance of ATC paradigm was better. Baroffio et al. [20] proposed a coding architecture for coding local features (e.g. SIFT, SURF) extracted from a video sequence, which can be adopted to implement the ATC paradigm. Both intra and inter-frame coding modes were applied in the proposed coding architecture and the final coding mode was determined by comparing the costs of two coding modes. In their later work [START_REF] Baroffio | Coding binary local features extracted from video sequences[END_REF], the coding architecture was applied to coding binary local features. As only features are transmitted, video content cannot be watched at the server side. It is inapplicable in some scenarios (e.g. video surveillance) where it is necessary to visualize the video content. By contrast, Chao and Steinbach [START_REF] Chao | Keypoint encoding for improved feature extraction from compressed video at low bitrates[END_REF] proposed a novel framework, in which keypoints extracted from a video were encoded and transmitted along with the compressed video. However, this framework needs more bits to transmit the feature descriptors.

Few studies have addressed the impact of video compression on video analysis. Korshunov and Ooi [START_REF] Korshunov | Critical video quality for distributed automated video surveillance[END_REF] proposed a formal rate-accuracy optimization framework, where the encoding parameters in distributed video surveillance systems could be determined given a target bit rate or accuracy. Furthermore, they denoted that there exists a sweet spot where reducing the bit rate would not significantly affect the accuracy of face recognition and tracking algorithms. Kokiopoulou and Frossard [START_REF] Kokiopoulou | Semantic coding by supervised dimensionality reduction[END_REF] proposed a supervised dimensionality reduction scheme which provides a tradeoff between compression and discriminant feature extraction. Liao et al. [START_REF] Liao | An analysis-oriented ROI based coding approach on surveillance video data[END_REF] proposed an analysis-oriented ROI based coding approach to reduce the impact of video compression on the performance of video analysis.

However, the approach in [START_REF] Liao | An analysis-oriented ROI based coding approach on surveillance video data[END_REF] needs prior knowledge to detect ROI, which cannot always be obtained in practice.

Video Analytical Coding

In section 3.1, our proposed video analytical coding framework is presented. In the following, the compression distortion prediction model is introduced in section 3.2 and a brief review of our previous work is presented in section 3.3. In section 3.4, our proposed parameter adaptation procedure is described.

Finally, section 3.5 illustrates the proposed object based QP adaptation strategy.

Video Analytical Coding Framework

The flow chart of our proposed video analytical coding framework is shown in Fig. 2. In our framework, the QP of an I frame will be refined according to our proposed QP adaptation strategy (see section 3.5) and traditional RDO technique is used to compress the I frame. Then, the compression distortion of an I frame denoted as SADI can be calculated after decoding. The compression distortion (SAD) of a non-I frame (P or B frame) is predicted by SADI according to the compression distortion prediction model (see section 3.2). The predicted compression distortion is then used to obtain the analytical distortion which denotes the difference of video analysis performance when video quality degrades. Meanwhile, a simple frame subtraction algorithm is utilized to obtain the moving object area (foreground) of the current frame. The object area is used for updating the weighting parameter (see section 3.4) and the QP offset of the foreground coding blocks in P or B frame. Finally, the non-I frame is compressed by our proposed RADO method (see section 3.3). In our previous work [START_REF] Liu | Analytical distortion aware video coding for computer based video analysis[END_REF], a two-pass encoding procedure is applied to obtain the compression distortion. In order to reduce the encoding complexity, we introduce a prediction model to estimate the compression distortion of a non-I frame according to the temporal relationship. The following section will present the details of the prediction model. In the state-of-the-art video coding standard HEVC, hierarchical coding structure is adopted to improve the coding efficiency. Fig. 3 shows the hierarchical coding structure under low delay P (LDP) configuration. Frames in different temporal layers are highlighted by different colors. In temporal layer 0, an I or IDR frame is denoted by a black bar. Frames in temporal layer 1, 2 and 3 are represented by blue, purple and orange bars respectively. In the following, an I frame and the following P frames are denoted by layers Li, where i indexes the temporal layers from 0 to 3. Meanwhile, it can be easily seen that frames in a lower temporal layer (e.g. 0 and 1) are directly or indirectly referenced by frames in higher temporal layers.

Compression Distortion Prediction Model

In view of this, the temporal relationships are investigated in terms of distortion between I frame and other frames in different layers [START_REF] Yang | An efficient Lagrangian multiplier selection method based on temporal dependency for rate-distortion optimization in H.265/HEVC[END_REF]. The experiments are conducted on the HEVC test model HM 16.7 The relationship in the average distortion between the layer L0 and other layers (i > 0) is shown in Fig. 4. From Fig. 4, it can be seen that the average distortion of higher layer (i > 0) increases linearly with that of layer 0. The compression distortion prediction model is therefore formulated by a linear equation with {1, 2,3} ∈ i Using Eq. ( 1), the resulting predicted compression distortion is used to predict the analytical distortion [START_REF] Liu | Analytical distortion aware video coding for computer based video analysis[END_REF]. Then, the predicted analytical distortion is used in our proposed RADO method which is presented in the following section.

0 i i i L L L L D k D b = ⋅ + , (1)

Rate Analytical Distortion Optimization

Nowadays, a large amount of generated videos are consumed by computers running video analysis algorithms for some application-related purposes, such as face detection and recognition. However, most of the videos are compressed in a lossy way to further raise the compression ratio, which may decline the analysis algorithms' performance. In addition, the goal of the well-known RDO technology is to minimize the compression distortion under an available bit rate budget constrain [START_REF] Sullivan | Rate-distortion optimization for video compression[END_REF][START_REF] Ortega | Rate-distortion methods for image and video compression: An overview[END_REF], without considering the above-mentioned scenarios. In this section, we address this issue and present our proposed RADO approach. Specifically, the difference of video analysis performance caused by video compression is denoted as analytical distortion and we use the term "DA" to represent it.

In order to reduce the negative effect introduced by lossy compression while maintaining the video coding efficiency, we formulate the RADO problem by jointly minimizing the compression distortion DC in pixel domain and the analytical distortion DA at a given bit rate R 1 . It can be written as min .

.

C A T D D s t R R τ + ≤ , ( 2
)
where τ is a weighting parameter and RT is the available bit rate budget. Obviously, Eq. ( 2) will be reduced to the traditional RDO formulation when τ = 0. Employing the Lagrangian multiplier method [START_REF] Everett | Generalized Lagrange multiplier method for solving problems of optimum allocation of resources[END_REF], the constrained RADO problem in Eq. ( 2) can be converted into an unconstrained form, which can be written as min { }, where

new new C A new J J D D R τ λ = + + , ( 3
)
where Jnew is the cost function and new λ is the Lagrangian multiplier. As so far, it is difficult to get the optimal solution in Eq. ( 3) without modeling the interaction between DA and R. In view of this, we empirically design a derivable RAD model, which can be expressed as

2 1 e A C D R C = , (4)
where 1 C and 2 C are constant parameters. One more thing, we do not change the rate model in HEVC codec, so R is differentiable with respect to DC. Consequently, the minimal cost new J is obtained when

0 new C A new J D D R R R τ λ ∂ ∂ ∂ = + + = ∂ ∂ ∂ , ( 5
) C A new D D R R λ τ ∂ ∂ = - - ∂ ∂ . (6)
Actually, the derivation of DC with respect to R can be directly obtained from the HEVC codec. When the weighting parameter τ = 0, it represents the Lagrangian multiplier of traditional RDO problem which is represented by the term HM λ . Then, Eq. ( 6) can be rewritten as

A new HM D R λ λ τ ∂ = -∂ . ( 7
)
Finally, we build the relationship between new λ and HM λ , which can obtain a fast solution of new λ .

Furthermore, once the weighting parameter τ is determined, the Lagrangian multiplier new λ can be calculated from Eq. ( 7). In the subsequent section, the weighting parameter adaptation procedure is presented in details. 1 In this paper, we do not aim at studying the absolute performance of a video analysis algorithm itself. Rather, we are more specifically concerned with how the analysis algorithm behaves when video quality degrades. For instance, if the video analysis algorithm can achieve the same performance when applied on the full quality video and the degraded video, the analytical distortion is considered to be zero. Besides, the analytical distortion is predicted by a linear model [START_REF] Liu | Analytical distortion aware video coding for computer based video analysis[END_REF].

Weighting Parameter Adaptation

Obviously, the optimal Lagrangian multiplier λ new in Eq. ( 10) cannot be obtained without setting the weighting parameterτ . Therefore, the weighting parameter τ plays an important role in our proposed RADO method. In order to explore the impact of τ on the proposed framework, we test a set of values where τ ranges from 0.1 to 0.9. Four QP values (22, 27, 32, 37) are selected and all the experiments are conducted under LDP configuration. Besides, four reference video clips (Clip 1-4) are selected, including three indoor video clips (Clip 1-3) from PETS2006 [START_REF] Thirde | Overview of the PETS2006 challenge[END_REF] and one outdoor video clip (Clip 4)

from PETS2009 [START_REF] Ferryman | Pets2009: dataset and chanllenge[END_REF]. Clip 1 to Clip 4 are captured by stationary cameras without any zooming.

Meanwhile, the selected video clips all have 600 frames at a frame rate of 30fps, and have resolution of 720x576 except for Clip 4 which is of size 768x576. Fig. 5 shows the thumbnails of the four reference video clips. Specifically, we consider a task of moving object detection, which is a fundamental component many application scenarios. The moving object detection algorithm in [START_REF] Lei | Robust object detection with interleaved categorization and segmentation[END_REF] is selected to study the tradeoff between the accuracy of moving object detection and the coding rate. Meanwhile, we choose the F1measure to evaluate the performance of moving object detection task [START_REF] Powers | Evaluation: from precision, recall and F-measure to ROC, informedness, markedness & correlation[END_REF]. Besides, we consider the moving object detection problem as a binary classification scheme [START_REF] Dhome | A benchmark for background subtraction algorithms in monocular vision: a comparative study[END_REF]. Then, positives and negatives are counted at the pixel level. In the following, True and False Positives (denoted by TP and FP respectively) refer to the number of detected positives according to ground truth, and similar for True and False Negatives (denoted by TN and FN). In particular, we take the detection result of pristine video as the ground truth by considering two aspects. On the one hand, the difference of detection results (analytical distortion) between the pristine video and the compressed video can be directly indicated in this way, since we are more specifically concerned with analytical distortion as aforementioned. On the other hand, it is difficult to obtain the ground truth in practice.

Basically, the F1-measure consists of two parts, namely recall and precision, which are calculated by the number of TP/FP and the number of TN/FN. The precision pr and recall re can be calculated by Eq. ( 8) and Eq. ( 9) respectively. Using F1-measure, the analytical distortion of the i-th frame i A D can be expressed as

1 = - i A i D F , (11)
where Fi the F1-measure value of the i-th frame. Then, the average analytical distortion S A D over the video sequence S can be written as

1 1 = =  N S i A A i D D N , ( 12
)
where N is the total number of frames. In the following of this paper, the analytical distortion is represented as S A D .

Fig. 6 shows the experimental results of four video clips under different values of τ . As a first observation, the average analytical distortion S A D of three indoor video clips (Clip 1-3) is more or less constant whenτ increases. The second observation is that the average analytical distortion S A D of Clip 4 oscillates along with the increase of τ . There are two reasons. First, illumination changes will reduce the robustness of object detection algorithms. The analytical distortion will increase along with the increase of the differences between the detection results of the frame subtraction algorithm applied in our proposed method and that of the object detection algorithm in [START_REF] Lei | Robust object detection with interleaved categorization and segmentation[END_REF]. Otherwise, the analytical distortion will be reduced as shown in the experimental results. Second, the weighting parameter τ has an impact on the mode decision process, which will influence the detection results of the object detection algorithm in [START_REF] Lei | Robust object detection with interleaved categorization and segmentation[END_REF]. Meanwhile, we find that the object area also has a great impact on the analytical distortion and the weighting parameter τ is updated according to the detected object area of each frame [START_REF] Liu | Analytical distortion aware video coding for computer based video analysis[END_REF]. The weighting parameter τ is updated by exp( )

τ ρ = × × Area w h , ( 13
)
where w and h denote the frame width and frame height, Area represents the total detected object area of each frame and ρ is a constant parameter. In this paper, ρ is set to be 0.1 according to the experimental results shown in Fig. 6.

Object Based QP Adaptation Strategy

According to the work in [START_REF] Itti | Automatic foveation for video compression using a neurobiological model of visual attention[END_REF], compression distortion has more influence on analytical distortion in the object area than that in background. In view of this, we develop an object based QP adaptation strategy.

It can be expressed as , ,

f i f QP QP if i object QP QP QP if i object -∆ ∈   =  + ∆ ∉   , ( 14
)
where i QP and f QP represent the quantization parameter of the i-th coding tree unit and the frame level QP, and ∆QP denotes the QP offset. Specifically, according our previous work in [START_REF] Gao | Temporally dependent rate-distortion optimization for low-delay hierarchical video coding[END_REF][START_REF] Li | Lagrangian multiplier adaptation for rate-distortion optimization with inter-frame dependency[END_REF], the coding performance of an I frame may have a strong impact on that of the following frames. Therefore, we also set a QP offset to the I frame in this paper, which can be expressed as

I B I QP QP QP = -∆ , (15)
where

Experimental Results and Discussion

In

Rate-Analytical-Distortion Performance

The RAD curve comparison of VAC against HEVC on each video clip is shown in Fig. 7. It is worth noting that the bit-streams generated by the proposed scheme is still HEVC compliant as none of the syntax structures is changed in our proposed scheme.

As a first observation in Fig. 7, it can be seen that VAC can reduce the analytical distortion effectively.

In the best scenario (Fig. 7(c)), up to 40% reduction in terms of average analytical distortion can be achieved. Meanwhile, Fig. 8 illustrates the detection results of VAC and HEVC. It can be seen that the detection results of VAC are better than that of HEVC. Due to the proposed QP adaptation strategy, the object area is compressed by relatively smaller QP, which makes the reconstruction quality higher compared with that in HEVC. This could help improve the performance of object detection algorithm. As a second observation, it should be pointed out that the RAD performance of VAC is a little bit worse than that of HEVC under low bit rate in Fig. 7(d). From Fig. 8 (see the third row), it can be seen that the performance of VAC may not be satisfactory when the object is small. There are two main reasons.

First, prediction errors exist in the prediction steps for the estimation of SAD and the analytical distortion, which will negatively influence the performance of VAC. Second, due to the frame subtraction algorithm used in this paper, small objects could not be detected in some cases. The resulting undetected object will be compressed by a relatively lager QP, which will decrease the reconstruction quality and further The second column shows the detection results of the original frames. The third and the fourth column denote the detection results on their compressed versions when using HM 16.7 and VAC respectively.

Rate-Distortion Performance

Table 1 illustrates the RD performance gain of VAC HEVC in terms of BD-rate saving. It can be observed that VAC can achieve about 4.2% BD-rate savings in average over the HEVC HM 16.7, with over 4.9% and 6.3% BD-rate savings for Clip 5 and Clip 8 respectively. Fig. 9 shows the RD curve comparisons on four test video clips. It can be observed that VAC can achieve better RD performance that HEVC. The main reason is that our proposed object based QP adaptation strategy refines the QP of an I frame as well as that of the background and the object area.

Complexity Evaluation

Table 2 shows the complexity comparison between the HEVC HM 16.7 and the proposed scheme in terms of encoding time under LDP coding structure. The test is done with Intel Core i5-4570 CPU and only one core is used to run the programs for making the running of all sequences under a similar workload. Encoding time for each clip is averaged over four test QPs. From the experimental results, it can be observed that the proposed scheme requires a slightly increased encoding time compared with HM 16.7, since some additional time is spent on the additional procedures such as frame subtraction and compression distortion prediction. However, this increase remains reasonable.

Conclusion

In this paper, we propose a new coding framework called video analytical coding for video analysis.

We use the term "analytical distortion" to denote the difference of video analysis performance when video quality degrades and develop a new rate-analytical-distortion optimization (RADO) method.

Typically, analytical distortion is estimated by compression distortion. To show the effectiveness of our proposed method, we consider moving object detection as the analysis task and develop a novel rate analytical distortion (RAD) model for video coding, where the analytical distortion is related to the object detection performance represented as F1-measure. Experimental results show that the performance of the video analysis task can be significantly improved. In our future work, we will extend our framework to other scenarios such as object detection in camera motion case, tracking and recognition. Furthermore, we will also focus on the parameter adaptation, including for the weighting parameter and QP offset.

Acknowledgment

This work was supported in part by the National Natural Science Foundation of China under Grant 61571102 and in part by the Other Funds under Grant 2015AA015903 and Grant ZYGX2014Z003.

Fig. 1

 1 Fig. 1 Foreground extraction results on the same frame, without and with compression

Fig. 2

 2 Fig.2 Flow chart of the proposed framework

Fig. 3

 3 Fig. 3 Graphical presentation of hierarchical coding structure and the reference structure in HEVC low delay P configuration

[

  26]. Two video clips (Clip 1 and Clip 2) are encoded under LDP configuration. In the experiments, the QP is set as 22, 27, 32 and 37. The other coding parameters are set as the default use case. Meanwhile, the distortion is measured by SAD and the distortion of each layer ( 0 i ≥ ) at each QP point is averaged over the frames in the same layer.

DFig. 4

 4 Fig. 4 Distortion dependency between temporal base layer and higher temporal layers

Fig. 5

 5 Fig. 5 Thumbnail for each video clip

Fig. 6

 6 Fig. 6 Experimental results of S A D with four video clips under different values of τ . (a), (b), (c) and (d) show the results at four

  quantization parameter of an I frame and the initial QP, and ∆ I QP denotes the QP offset.

8 Fig. 7 RAD

 87 Fig. 7 RAD curve comparison of VAC against HEVC in LDP configuration

Fig. 8

 8 Fig. 8 Illustration for the detection results of four test video clips. The first column shows the thumbnails of Clip 5-8 respectively.

  this section, we conduct comparative experiments on the HEVC test model (HM 16.7). Video sequences are encoded under LDP configuration. The other coding parameters are set as the default case. Clip 5 to Clip 8 are captured by stationary cameras without any zooming. Besides, Clip 5 to Clip 7 have 600 frames at a frame rate of 30fps, and have resolution of 720x576. Clip 8 has 200 frames at the same frame rate and has resolution of 800x600.

	Four QP values (22, 27, 32, 37) are selected. Both QP offsets QP ∆	and	I QP ∆	(see Eq. (14) and Eq. (15))
	are set to be 2. The rate-distortion performance of the proposed method is measured in terms of BD-rate
	saving over the HM 16.7.
	In order to show the rate analytical distortion performance of VAC, another 4 test video clips (Clip 5-
	8) are chosen, including 3 indoor video clips from PETS2006 and 1 outdoor video clip from CAVIAR
	[35].

Table 1 RD

 1 Performance gain of VAC over HEVC in terms of BD-rate saving Fig. 9 RD curve comparison of VAC against HEVC in LDP configuration

	Video Clip	BD-Rate (%)
	Clip 5	-4.9
	Clip 6	-2.5
	Clip 7	-3.0
	Clip 8	-6.3
	Average	-4.2

Table 2

 2 Complexity comparison between VAC and HEVC in terms of encoding time (sec.)

	Encoding Time (Sec.)	Clip 5	Clip 6	Clip 7	Clip 8
	HEVC	4106.001	4384.378	3905.945	1486.276
	VAC	4241.163	4472.652	3980.182	1537.996


Mohsen Abdoli

Félix Henry
email: felix.henry@orange.com

Senior Member, Patrice Brault
email: patrice.brault@l2s.centralesupelec.fr.

Fellow, IEEE Pierre Duhamel
email: pierre.duhamel@l2s.centralesupelec.fr.

Fellow, IEEE Frédéric Dufaux
email: frederic.dufaux@l2s.centralesupelec.fr.

L2s

Short Distance Intra Prediction of Screen Content in Versatile Video Coding (VVC)

Keywords: Intra prediction, VVC, Screen content coding

A novel intra prediction algorithm is proposed to improve the coding performance of screen content for the emerging Versatile Video Coding (VVC) standard. The algorithm, called In-Loop Residual coding with Scalar Quantization (ILR-SQ), employs in-block pixels as reference rather than the regular out-block ones. To this end, an additional in-loop residual signal is used to partially reconstruct the block at the pixel level, during the prediction. The proposed algorithm is essentially designed to target high detail textures, where deep block partitioning structure is required. Therefore, it is implemented to operate on 4 × 4 blocks only, where further block split is not allowed and the standard algorithm is still unable to properly predict the texture. Experiments in the Joint Exploration Model (JEM) reference software show that the proposed algorithm brings a BD-rate gain of 13% on synthetic content, with a negligible computational complexity overhead at both encoder and decoder sides.

I. INTRODUCTION

Applications of synthetic videos, such as remote screen sharing, online gaming, animated movies, virtual reality, have become more popular in the past few years. This has drawn the attention of standardization committees to dedicate specific compression tools to this type of content. In the High Efficiency Video Coding standard, i.e. H.265/HEVC, these tools have formed an extension called HEVC Screen Content Coding (SCC) [START_REF] Xu | Overview of the emerging HEVC screen content coding extension[END_REF]. This extension has brought significant coding gain on synthetic videos by using four major tools: Intra Block Copy (IBC) [START_REF] Xu | Intra block copy in HEVC screen content coding extensions[END_REF], Palette mode [START_REF] Guo | Palette mode for screen content coding[END_REF], Adaptive Color Transform (ACT) [START_REF] Zhang | Adaptive color-space transform in HEVC screen content coding[END_REF] and Adaptive Motion Vector Resolution (AMVR) [START_REF] Li | Adaptive motion vector resolution for screen content[END_REF].

In the development of the next generation video codec, the Versatile Video Coding (VVC), a new standardization action has started in late 2015. For this purpose, the ITU-T Video Coding Expert Group (VCEG) and the ISO Motion Picture Expert Group (MPEG) have jointly initiated a committee, called Joint Video Exploration Team (JVET). The agenda of this committee is to significantly exceed the performance of HEVC and explore video compression capabilities beyond it. The outcome of this action, expected to be standardized in 2020, is supposedly a universal replacement for HEVC and all of its extensions, including SCC [START_REF] Wien | Preliminary joint call for evidence on video compression with capability beyond HEVC[END_REF].

A. New tools and features

JVET consists of an exploration phase and a standardization phase. In each phase, different reference softwares are used to evaluate the performance of new tools. During the exploration phase, the Joint Exploration Model (JEM) was developed, in order to reach maximum performance before the actual standardization phase. In early 2018, two other reference software, the VVC Test Model (VTM) and the BenchMark Set (BMS), were released for the standardization phase. The VTM is mostly based on HEVC test Model (HM), with many tools removed and a few added, and improves HEVC by 12% in compression performance. The BMS and JEM, however, benefit from quite similar tools and both bring about 30% to 35% compression gain over the HM with different complexity overhead [START_REF] Sidaty | Emerging video coding performance: 4K quality monitoring[END_REF]. Here is the list of major tools and contributions that are currently under consideration for the VVC:

• Partitioning: Nested multi-type tree including quad-tree, binary-tree and ternary-tree [START_REF] Chen | Algorithm description of joint exploration test model 7 (JEM7)[END_REF] [9] [10] [START_REF] Chen | Algorithm description for versatile video coding and test model 1 (vtm 1)[END_REF]. • Inter prediction: Bi-directional Optical Flow (BIO [START_REF] Alshin | Bi-directional optical flow for future video codec[END_REF]), Overlapped Block Motion Compensation (OBMC) [START_REF] Chen | Algorithm description of joint exploration test model 7 (JEM7)[END_REF]. • Intra prediction: 67 Intra Prediction Modes (IPM), Position Dependent Prediction Combination (PDPC [START_REF] Said | Position dependent prediction combination for intra-frame video coding[END_REF]), Cross-component linear model prediction [START_REF] Chen | Algorithm description of joint exploration test model 7 (JEM7)[END_REF]. • Transform coding: Large block-size transforms with highfrequency zeroing, Non-Separable Secondary Transforms (NSST [START_REF] Zhao | Nsst: Non-separable secondary transforms for next generation video coding[END_REF]), Adaptive Multiple Transforms (AMT [START_REF] Zhao | Enhanced multiple transform for video coding[END_REF]), Adaptive Multiple Core Transforms. • Filters: Adaptive Loop Filter (ALF), Four-tap intra prediction filter, Bilateral in-loop filtering [START_REF] Chen | Algorithm description of joint exploration test model 7 (JEM7)[END_REF].

B. Distant reference inaccuracy of intra prediction

To model angular textures more accurately, the size of the IPM set is doubled in the JEM. This new set shares the DC and Planar IPMs with HEVC, but extends the set of angular modes from 33 to 65 IPMs, thus covering the same angular range with double precision. Although the extended IPM set has brought a significant coding gain, it is still unable to properly predict high detail content with complex textures [START_REF] Abdoli | Intra prediction using in-loop residual coding for the post-HEVC standard[END_REF]. This is due to the low correlation between distant outblock references and in-block prediction pixels. This problem, called the Distant Reference Inaccuracy (DRI) in the rest of this letter, may be eased by further block partitioning. However, deeper block partitioning always comes with the cost of extra block level syntax elements to transmit. More importantly, the DRI often happens at the 4 × 4 blocks, where further partitioning is not allowed. Fig. 1 depicts some texture examples from natural and synthetic video sequences. As can be seen, in both cases, the local content change makes the inblock pixels quite uncorrelated to their out-block references. However, due to the solid edges in the synthetic videos, the in-block pixel correlation is stronger than natural content.

Previous research works have studied a similar problem. In Combined Intra Prediction (CIP), an additional in-block pixel prediction is combined with the traditional prediction using a weighted average [START_REF] Gabriellini | Combined intra-prediction for high-efficiency video coding[END_REF][START_REF] André | Improved combined intra prediction for higher video compression efficiency[END_REF]. In Short Distance Intra Prediction (SDIP), use of further block splitting is proposed to achieve excessive thin block in order to reduce the distance from reference pixels [START_REF] Cao | Short distance intra coding scheme for HEVC[END_REF]. Finally, Residual Differential Pulse-Code Modulation (RDPCM) uses residual prediction with immediate neighbors inside the same block, in order to further decorrelate signal [START_REF] Tan | Residual DPCM for lossless coding in HEVC[END_REF]- [START_REF] Joshi | Ahg8: Residual DPCM for visually lossless coding[END_REF]. From this aspect, the proposed algorithm shares a common concept with RDPCM. However, instead of residual signal, it performs the DPCM-based prediction on the pixel values directly.

In this letter, a novel intra prediction algorithm is proposed, which is well suited for synthetic blocks presenting the DRI problem. The algorithm, called In-Loop Residual coding with Scalar Quantization (ILR-SQ), is integrated as an additional tool in the JEM and its usage requires signaling by the encoder. The ILR-SQ uses in-block reference pixels to apply a DPCMbased prediction. To exploit in-block references, an additional residual is coded. From this perspective, the proposed idea shares the same objective as our previous research that adopts a Vector Quantization (VQ) technique, called ILR-VQ [START_REF] Abdoli | Intra prediction using in-loop residual coding for the post-HEVC standard[END_REF]. It is also important to note that the fact that ILR-SQ is designed and implemented within the framework of VVC does not harm its generalizability. In other words, ILR-SQ can be adopted by all hybrid block-based video coding standards.

The rest of this letter is organized as follows. In section II, the ILR-SQ algorithm and its different modules are described in detail. In section III, the block level algorithm competition between the JEM and the proposed ILR-SQ is explained. In section IV, experimental results of embedding the ILR-SQ in the JEM are presented. Finally, section V concludes the letter.

II. INTRA PREDICTION BY IN-LOOP RESIDUAL CODING

AND SCALAR QUANTIZATION In this section, the in-block prediction to address the DRI problem is introduced. For this purpose, first, the main obstacle for using in-block reference pixels is discussed. Then, block prediction by ILR-SQ is described in detail. Finally, the proposed residual coding scheme is presented.

A. Data Dependency for In-Block References

The major obstacle for using in-block references is a data dependency between prediction and residual signals. More precisely, at the time of block prediction, the closest fully reconstructed references are the regular out-block pixels from previous blocks, as used in the conventional intra prediction. Therefore, exploiting in-block references requires reconstructing them beforehand or during the prediction. This makes the residual a prerequisite to the prediction phase, while the residual signal is traditionally accessible after the prediction phase is finished at the block level. In other words, the prediction signal depends on the residual signal and conversely, the residual signal also depends on the prediction signal. In order to address this problem, an additional In-Loop Residual (ILR) signal is computed during the prediction and transmitted to the decoder alongside the regular out-loop residual (OLR).

The ILR signal is responsible for pixel reconstruction right after prediction at the pixel level. This enables in-block references for the prediction of next pixels. In order to draw a distinction from the regular pixel reconstruction by the OLR, this step is called pixel "correction" in the rest of this letter.

B. In-Block Pixel Prediction and ILR Calculation

Without loss of generality, let us assume that we are given a square block of size N with its out-block reference pixels. We are also given a scan order (e.g. raster scan) to determine the order of pixel prediction inside the block. Let the matrix O N ×N represent the input original signal, P N ×N the output prediction signal and I N ×N the decodable ILR signal to be calculated during the prediction. Also, let R (N +1)×(N +1) be the concatenation of the out-block reconstructed and the inblock corrected references. For simplicity, the first row and column of matrix R contain the out-block reference pixels and are indexed by -1 instead of 0. From these signals, the entire O matrix as well as the first row and first column of R matrix are filled prior to the prediction phase whereas the remaining matrices are calculated during the prediction phase.

Starting from pixel index (x = 0, y = 0), the goal is to fill P by predicting all pixels in the block, meanwhile calculating elements in matrix R. For this purpose, the algorithm traverses the pixels according to the scan pattern and performs the following five steps at each pixel index (x, y):

1) Access three reference pixels at left A = R (x-1,y) , top B = R (x,y-1) and top-left C = R (x-1,y-1) . According to the above descriptions, these references can either be out-block or in-block pixels.

2) Predict the pixel by the LOw COmplexity LOssless

COmpression for Images (LOCO-I) function [START_REF] Weinberger | The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS[END_REF]: The LOCO-I function was first adopted in the JPEG-LS image compression standard. It aims at pixel-level edge detection in the vertical and horizontal directions (i.e. the first two conditions of Eq. 1, respectively). Moreover, if no edge is detected, it applies a linear filter on the references (i.e. the last condition of Eq. 1). 3) Calculate the error:

P (x,y) =      min(A, B), if C ≥ max(A, B). max(A, B), if C ≤ min(A, B). A + B -C, Otherwise. (1)
ε = O (x,y) -P (x,y) . (2)
4) Calculate ILR by quantizating the error in the spatial domain:

I (x,y) = Q(ε). (3)
Here, Q is a linear scalar quantizer with the parameter sQP shown in Fig. 2, where sQP determines the compression rate of the ILR. This parameter is a function of the regular quantization parameter QP which is applied in the transform domain coefficients. For this purpose, the quantization scheme used in the Transform Skip Mode (TSM) of HEVC is adopted. In the TSM, due to a similar problem of residual quantization in the pixel domain, proper normalization and shift is performed to adapt the quantization step size in the pixel domain [START_REF] Mrak | Improving screen content coding in hevc by transform skipping[END_REF].

5) Correct the pixel by adding the ILR value to the predicted value: R (x,y) = P (x,y) + I (x,y) .

By performing the above five steps on the pixel at index (x, y), the corresponding values of all matrices P , I and R are determined. Therefore, from now on, the corrected pixel at R (x,y) can act as an in-block reference during remaining iterations of the prediction phase.

C. ILR Coding

To reproduce the same prediction signal at the decoder side, the ILR signal in I must be transmitted. For this purpose, individual ILR values in I are divided by sQP to produce integer symbols. These amplitude symbols are then binarized and compressed, while their signs are bypassed-coded.

1) Binarization:

After thoroughly studying the distribution of numerous ILR signals in different situations, the truncated unary representation is selected as the binarization scheme of ILR coefficient magnitudes. To perform the binarization, the matrix I is scanned. For each coefficient with magnitude X, the truncated unary code is produced as a sequence of X + 1 bins, including X intermediate bins of '1', followed by a single bin of terminal '0'. Fig. 3 visualizes the binarization process for a 4×4 block example.

2) Compression: After the magnitude binarization is finished for the entire block, the bins are compressed using Context-Adaptive Binary Arithmetic Coding (CABAC), with suitable context models. For this purpose, the maximum magnitude is set to 15, limiting the number of dedicated CABAC contexts to 16. In other words, all bins after the first 16 bins of unary codes would share the last CABAC context for encoding and decoding.

III. BLOCK-LEVEL COMPETITION ALGORITHM

The ILR-SQ algorithm targets high detail blocks with the DRI problem that the state-of-the-art is unable to efficiently address. Such blocks usually occupy a noticeable portion of the picture in synthetic video content and the IRL-SQ is able to reduce their rate-distortion cost significantly. However, the other portion of the picture which contain smoother and more regular texture is still coded more efficiently by the conventional intra prediction algorithm than the ILR-SQ. Therefore, we integrate the ILR-SQ alongside the regular algorithm and allow the rate-distortion optimization to choose the best one as summarized in Fig. 4. Such flexibility of having multiple options at the block level imposes both rate and complexity overhead. Regarding the rate, the encoder has to transmit one flag per block to explicitly indicate the selected algorithm. For this purpose, this syntax element is compressed by CABAC and transmitted to the decoder before all the other block-level syntax elements. Moreover, deciding about the flag value for each block requires the encoder to actually apply both JEM and ILR-SQ algorithms for each eligible block. This increases the complexity of the rate-distortion optimization (RDO) loop, in which all possible combinations of the encoding tools are evaluated.

Fig. 5 visualizes result of the competition algorithm in two sequences. As expected, complex textures with high detail edges in each sequence, are coded by ILR-SQ, where plain areas and regular patterns are coded by the JEM algorithm.

ChinaSpeed SlideEditing

IV. RESULTS

In this section, experimental results are provided to evaluate performance of ILR-SQ. Due to the fact that until the last stages of this research, only the JEM was available, this reference software was used as the anchor reference for the implementation. However, since the JEM and the BMS references share most of their tools, the same level of performance is also expected in the BMS.

For the test, 14 synthetic video sequences from the SCC Common Test Conditions (CTC) [START_REF] Yu | Common conditions for screen content coding tests[END_REF] and Class F of the JVET CTC [START_REF] Suehring | JVET common test conditions and software reference configurations[END_REF] were used. As recommended in both CTCs, all frames of the sequences are coded. Table I compares the average selection rate of ILR-SQ blocks at different QPs by the JEM5.0.1. As can be seen, in all QPs, a significant portion of the blocks are encoded by the ILP-SQ. This proves the claim that the conventional intra prediction of the JEM is not efficient for synthetic textures. version based on Vector Quantization, called ILR-VQ [START_REF] Abdoli | Intra prediction using in-loop residual coding for the post-HEVC standard[END_REF].

In this algorithm, instead of Scalar Quantization, a set of QP-dependent codebooks of size 128 are used to code ILR signal. According to Table II, there is a consistent improvement against the JEM5.0.1 with an affordable computational complexity overhead. The lower performance of the ILR-SQ on the Robot sequence is also reflected in a very low block selection rate at all four QPs where less than 1 percent of the blocks are coded by the ILR-SQ. This is due to the low texture complexity of the content.

The RDPCM tool uses a similar prediction scheme to that of ILR-SQ, except that it is applied on residual values [START_REF] Tan | Residual DPCM for lossless coding in HEVC[END_REF]- [START_REF] Joshi | Ahg8: Residual DPCM for visually lossless coding[END_REF]. Therefore, its use was also tested for the performance evaluation of the ILR-SQ, in order to provide a clear view of compression efficiency. For this purpose, "JEM"+"ILR-SQ" was compared against "JEM"+"RDPCM". This resulted in 11% BD-rate gain in favor of ILR-SQ, which means that the correlation that it is capturing by pixel prediction cannot be captured with the residual prediction of RDPCM.

Other tests were also carried out to confirm the efficiency of ILR-SQ. In Random Access (RA) and Low Delay (LD) modes, ILR-SQ was able to improve BD-rate gain by 8.7% and 6.9%, respectively. Moreover, the natural sequences in the JVET CTC were coded by ILR-SQ in AI mode. In this test an average BD-rate gain of 0.2% was achieved.

V. CONCLUSION An intra prediction algorithm, named In-Loop Residual coding with Scalar Quantization, is proposed to improve the coding efficiency of synthetic video content. In this algorithm, the distant reference inaccuracy problem in case of in-block content change is targeted. To address this problem, the algorithm uses an additional in-loop residual to enable shortdistance pixels from inside the block, rather than outside, as references. The proposed technique achieves an average gain of approximately 13% in terms of BD-rate.

Fig. 1 .

 1 Fig. 1. Example in-block content changes from synthetic (ChinaSpeed and SlideEditing) and natural (Kimono and BQTerrace) sequences.

Fig. 2 .

 2 Fig. 2. Linear scalar quantization function with sQP= 64.

Fig. 3 .

 3 Fig. 3. An example 4 × 4 quantized ILR coefficient block at left and the visual representation of its truncated unary codes at right.

Fig. 4 .

 4 Fig. 4. The intra prediction competition algorithm at the block level. Here, OLR is the regular out-loop residual and Recon is the reconstructed signal.

Fig. 5 .

 5 Fig. 5. Texture coded by ILR-SQ (bright) and JEM (dark).

TABLE I AVERAGE

 I SELECTION RATE OF THE ILR-SQ AT DIFFERENT QPS.

		Quantization Parameter
		22	27	32	37
	Among 4 × 4 blocks 51%	73%	75%	77%
	Among all blocks	29%	41%	39%	38%

Table II

 II

compares the coding performance of ILR-SQ against the JEM in all intra (AI) mode (4×4 blocks only). As another benchmark, ILR-SQ is also compared to its previous

TABLE II PERFORMANCE

 II OF THE PROPOSED ILR-SQ AND THE ILR-VQ AGAINST JEM, IN TERMS OF BD-RATE GAIN (%) AND CODING TIME (%).

	Res.	Sequence Name	ILR-SQ BD-rate ET/DT	ILR-VQ BD-rate ET/DT
	2560 Basketball Sc	-9.26	105/102	-1.58	209/99
	×	MissionCtrlClip2	-10.00	104/101	-1.62	206/101
	1440	Average	-9.63	105/102	-1.6	207/100
		FlyingGraphics	-8.59	107/103	-1.42	225/102
		Desktop	-26.01	103/103	-1.59	220/101
		Console	-33.64	105/103	-1.78	198/102
	1920 ChineseEditing	-12.71	101/102	-1.70	234/100
	×	MissionCtrlClip3	-9.88	106/105	-1.42	221/100
	1080 Robot	-0.32	114/103	-1.08	209/100
		ChinaSpeed	-12.94	107/103	-1.29	107/100
		Average	-14.87	106/103	-1.47	217/101
		Web browsing	-14.75	101/104	-1.67	195/100
	1280 Map	-3.42	110/103	-0.89	229/101
	×	Programming	-13.98	106/104	-1.46	216/100
	720	SlideShow	-14.44	109/103	-1.65	179/98
		SlideEditing	-13.68	104/102	-1.47	229/100
		Average	-12.05	107/103	-1.47	208/100
		Total Average	-13.11	105/103	-1.49	213/100