title: Rate distortion optimization over large scale video corpus with machine learning
authors: Sam John Akshay Gadde Balu Adsumilli
text: 
  
  
  [NO \title GIVEN]
      [NO \author GIVEN]
      December 30, 2023
  ======================
  
  
  
  We present an efficient codec-agnostic method for bitrate allocation over a large scale video corpus with the goal of minimizing the average bitrate subject to constraints on average and minimum quality. Our method clusters the videos in the corpus such that videos within one cluster have similar rate-distortion (R-D) characteristics. We train a support vector machine classifier to predict the R-D cluster of a video using simple video complexity features that are computationally easy to obtain. The model allows us to classify a large sample of the corpus in order to estimate the distribution of the number of videos in each of the clusters. We use this distribution to find the optimal encoder operating point for each R-D cluster. Experiments with AV1 encoder show that our method can achieve the same average quality over the corpus with 22% less average bitrate.   
  
  
  
  rate distortion optimization, clustering, machine learning, adaptive streaming, YouTube
  
  
  
  
  
  
  § INTRODUCTION
  
  
  
  
  For massive video streaming platforms such as YouTube, it is desirable to deliver the best video quality with minimum bitrates since it directly contributes to the streaming cost for these platforms as well to the data cost and quality of experience of the users. These platforms have various types of video content ranging from song lyrics and simple animations to sports and gaming <cit.>. For a given video encoder, we can compute the rate-distortion (R-D) curve of a video by encoding the video at different bitrates and plotting the distortion achieved for each bitrate. The R-D characteristics for each content type is significantly different than others. Even within one video, R-D characteristics can vary significantly over time. A video can be divided into chunks and a separate R-D curve can be obtained for each chunk. Given the R-D curves for each chunk in a video corpus, we can define a problem of finding the optimal bitrate for encoding each chunk such that an aggregate measure of distortion is minimized subject to a constraint on average bitrate (or average bitrate is minimized subject to a constraint on quality). Solving such an optimization problem directly at a large scale such as YouTube's, which contains millions of hours of videos <cit.>, is infeasible since it would involve encoding each chunk at multiple bitrates to get the R-D curve and then solving a non-linear optimization problem in millions of variable. Moreover, it is necessary to encode each video chunk into multiple representations at different bitrates and resolutions for adaptive streaming over networks of varying bandwidth <cit.>. This introduces additional complexity to the problem since we need to find the optimal bitrates for all representations. 
  
  
  The problem of R-D optimal bitrate allocation over coding units given their R-D characteristics has been studied before <cit.>. The authors show that the optimal bitrate allocation is such that the marginal gain in quality achieved by spending one extra unit of bitrate is equal for all coding units. However, they do not consider bitrate allocation over different representations of a coding unit. Toni et al. <cit.> consider the problem of selecting optimal representation of a video for adaptive streaming taking into account network dynamics. The problem of finding optimal bitrates for different representations of a video chunk subject to constraint on average delivered quality considering the distribution of user bandwidths and viewports is studied by Chen et al. <cit.>. All of these methods assume that the R-D curves of all coding video chunks in the corpus are known and that the number of encoding bitrates to optimize is small. These assumptions are not feasible for R-D optimization over a large scale video corpus.
  
  We propose a new efficient codec-agnostic method for allocating bitrates for all video chunks in a large scale corpus with the goal of minimizing the average bitrate while maintaining aggregate quality. Our method does not require encoding of all chunks in the corpus at multiple bitrates to get their R-D curves. This reduces the computational complexity significantly, especially at scale. Instead we use simple video complexity features obtained from encoder pass-log to predict the R-D curve of a chunk using machine learning. We cluster the video chunks in the corpus into multiple categories based on their approximate R-D curves. We demonstrate that the number of clusters required to model the variation in the R-D characteristics across the corpus is much less than the size of the corpus. Because all video chunks in a category have similar R-D characteristics, we can optimize for bitrates over categories instead of individual chunks. This requires solving a relatively small non-linear optimization problem with dimensionality equal to the number of clusters. 
  
  The proposed rate allocation method is outlined in Figure <ref>.
  
  
  
  
  The rest of the paper is organized as follows. In Section <ref>, we describe the proposed R-D curve prediction method based on R-D curve clustering and video classification using video complexity features. Section <ref> explains our R-D optimization formulation to compute the optimal bitrates for all video categories. Experimental results in Section <ref> show the efficacy our proposed approach. We conclude the paper in Section <ref>.
  
  
  
  § R-D CURVE MODELING
  
  
  
  
  Our method attempts to categorize the video chunks in the corpus such that all video chunks in one category have similar R-D curves. We do this using a two step approach (see Figure <ref>). In the first step, we cluster the R-D curves of training video chunks that are randomly sampled from the corpus. In the second step, we build a classification model to predict which R-D cluster a chunk belongs to using simple video complexity features obtained by fast one-pass analysis of the chunk with an encoder (i.e., encoder pass-log). R-D optimization is done over these clusters using their centroid R-D curves.
  
  
  
  
  
   §.§ Clustering Video Corpus Based on R-D Curves
  
  
  Let n be the number of training video chunks selected from the corpus. We obtain s points on the R-D curve of each training video chunk by encoding the chunk at fixed encoder operating points, [q_1, …, q_s]. Each operating point q_j corresponds to a quantization parameter (QP) or a constant rate factor (CRF) used by the encoder. Encoding a chunk i at operating point q_j results in a representation with bitrate r_j and distortion d_j for a chunk. The R-D curve samples for chunk i can then be represented by a vector 𝐱_i ∈ℝ^2s of rate-distortion values, [r_1, …, r_s, d_1, …, d_s].
  
  We normalize each component of 𝐱 as x_j^norm = (x_j - m_j)/σ_j, where m_j and σ_j are sample mean and sample standard deviation of x_j respectively. We cluster the vectors 𝐱_1^norm, …, 𝐱_n^norm into k (≪ n) clusters 𝐂 = {C_1, …, C_k} using k-means.
  
  L^2 distance between normalized R-D points is used to define the cost function for clustering. It is reasonable to normalize and compute the distances for each component of 𝐱 across different video chunks since each component corresponds to a fixed encoder operating point.
  
  We use the centroid μ_l of cluster C_l to get curves ρ_l(q) and δ_l(q) for mapping an operating point q to bitrate and distortion values respectively. These centroid curves are expected to be a good approximation for bitrate r_i(q) and distortion d_i(q) for any video chunk i ∈ C_l.
  
  
  
  
  
  
  The number of clusters, k, needed to capture all the variation in the R-D characteristics in the corpus is determined empirically. Figure <ref> shows the mean relative error between the R-D points for a corpus sample of n chunks and their corresponding cluster centroids (i.e., ∑_i 𝐱_i^norm - μ_l/∑_i 𝐱_i^norm) as function of k for different values on n. The data points are obtained by encoding video chunks at different CRF values with AV1 encoder <cit.>. It shows that approximating the corpus R-D points by the corresponding cluster centroids results in a small relative error that reduces slowly as the number of clusters exceeds 10. Moreover, the number of clusters needed to achieve this small error does not increase with the sample size n. 
  
  Figure <ref> show the plots of bitrate vs. CRF, distortion vs. CRF and distortion vs. bitrate for different cluster centroids for k = 10. These plots show that the marginal reduction in distortion achieved by allocating higher bitrate varies significantly across clusters. Therefore, the optimal operating point for achieving the best rate-distortion tradeoff will be different for each cluster.
  
  
  
  
  
  
  
   §.§ Predicting the R-D Cluster for a Video
  
  
  It is not feasible to sample the R-D curve for every video chunk in the corpus in order to determine its R-D cluster C_l since it involves encoding each chunk multiple times at different operating points.
  
  In order to circumvent this problem, we train a support vector machine (SVM) classifier to predict the R-D cluster of a chunk using video complexity features that are computationally much cheaper to obtain. 
  
  Specifically, we use 22 of the passlog features given by the AV1 encoder. AV1 encoder generates this passlog by doing an analysis pass over a video without fully encoding it. The features include statistics related to prediction modes (inter or intra), prediction errors, reference frames used for inter prediction and motion vectors for each frame in the video <cit.>. These features are a good indicator of the spatial and temporal complexity of a video. Therefore, they are useful for predicting the R-D characteristics of the video (see Figure <ref>).
  
  In order to train the classifier, the ground truth class labels for video chunks in the training set are obtained by clustering their R-D curves.
  
  Therefore, centroid R-D curve of the predicted cluster of a video is expected to be good approximation for the R-D curve of the video.
  
  
  
  
  
  
  
  
  
  The idea of clustering the R-D curves and building a model for R-D cluster prediction was proposed independently by Ling et al. <cit.>. However, our method and the method in <cit.> have some key differences. Firstly, the method in <cit.> uses the Bjontegaard Delta (BD) rate between the PSNR vs. bitrate curves as the distance metric in clustering. The problem with using this metric is that two R-D curves with substantially different slopes may have a very small BD rate distance. However, taking these differences in slopes into account is critical for efficient rate utilization. Ling et al. also use different features for predicting the R-D curve cluster. We find that using the encoder pass log features is computationally efficient and allows accurate R-D cluster prediction.  
  
  
  
  § R-D OPTIMIZATION OVER VIDEO CORPUS
  
  
  
  
  Our goal is to find the optimal encoder operating points for all R-D clusters so that the average corpus bitrate is minimized while the average and worst-case distortions remain below certain thresholds. 
  
  In order to compute these averages, we need to estimate the distribution of the number of video chunks in different clusters. 
  
  
  We do this by classifying a large sample of the video corpus into different clusters using the SVM model proposed in Section <ref>. 
  
  
  We can use this distribution to compute the average bitrate and distortion for the corpus for a given set of operating points for the clusters based on their centroid R-D curves. 
  
  Let 𝐪 = [q_1, …, q_k] be the encoder operating points for clusters C_1, …, C_k respectively. Let ρ_l(q_l) and δ_l(q_l) denote the bitrate and distortion obtained by encoding a video chunk in cluster C_l at operating point q_l as given by the centroid R-D curves for C_l. The optimal value of 𝐪 is defined as the solution to the following problem:
  
      𝐪minimize    ∑_l = 1^k w_l ρ_l(q_l)  
      subject to    ∑_l = 1^k w_lδ_l(q_l) ≤ D_avg
         max_l ∈{1, …, k}δ_l(q_l) ≤ D_max,
  
  where w_l is the fraction of video chunks in cluster C_l. Note that ∑_l w_l = 1. The solution to the above problem, 𝐪^⋆, will minimize the total bitrate while maintaining the given constraints on distortion. Any video chunk in cluster C_l is encoded using the optimal operating point q_l^⋆ for that cluster. 
  
  
  
  
  
  
  
  § EXPERIMENTS
  
  
  
  
  In order to evaluate the performance of the proposed method, we use a set of n=14000 videos at 480p resolution randomly sampled from the YouTube corpus. We sample a 5 second long chunk from each video. Using short chunks ensures that the R-D characteristics do not change significantly within one chunk. We use the AV1 encoder developed by AOM <cit.> to generate the R-D points for each chunk. This is done by encoding each chunk in constant quality (CQ) mode of the AV1 encoder at s=13 CRF values. 
  
  We cluster the vectors of R-D points into 10 clusters as explained in Section <ref>.
  
  We train an SVM classifier for predicting the R-D cluster of a video using the features given by the first pass log of the AV1 encoder <cit.>. 80% of the data is used for training and the remaining 20% is used for testing. We use the radial basis function (RBF) kernel in the SVM classifier. Optimal hyper-parameters of the SVM (namely, the regularization parameter and γ used in RBF kernel <cit.>) are computed with grid search using 5-fold cross-validation. The classifier gives an accuracy of 69% on the test set.
  
  
  
  The distribution of number of videos in different clusters (i.e., the weights w_l) is estimated by classifying a large sample of videos using the SVM model. It is shown in Figure <ref>.
  
  
  
  
  
  
  
  
  
  
  
  
  
  We use the weights w_l and the R-D points for cluster centroids to solve optimization problem in Eq. (<ref>). 
  
  In order to get a baseline, we use the same CRF value for all R-D clusters. For each baseline CRF q, we compute average, ∑_l = 1^k w_l δ_l(q) and maximum, max_l ∈{1, …, k}δ_l(q), distortions. We then use these values to set the constraints D_avg and D_max in Eq. (<ref>) and compute optimal CRFs, [q_l^⋆], for all clusters. The expected baseline and optimal average bitrates are given by ∑_l = 1^k w_l ρ_l(q) and ∑_l = 1^k w_l ρ_l(q_l^⋆) respectively. We repeat this for multiple baseline CRF values to get baseline and optimal rate-distortion sweeps.
  
  Figure <ref> shows the plots of expected average and maximum distortion vs. expected average bitrate. Based on these plots, for AV1 encoder, using optimal CRF for each cluster is expected to improve the BD rate by 22% compared to using the same CRF for all clusters for the same average distortion.
  
  We check robustness of the optimization against the inaccuracies in the R-D class prediction model and the approximation errors in centroid R-D curves. This is done by classifying each chunk in the data using the SVM classifier and then computing the bitrate and distortion at the optimal CRF for its predicted class using the actual R-D curve of the chunk. Baseline is obtained using the same CRF for all chunks. Plots of average distortion, 1/n∑_i=1^n d_i(q_i), and maximum distortion, max_i ∈{1, …, n} d_i(q_i) vs. average bitrate, 1/n∑_i=1^n r_i(q_i), computed over all chunks using optimal and baseline CRFs is shown in Figure <ref>. These plots also show that using optimal CRFs improves the BD rate by 22% compared to the baseline for the same average distortion, thus indicating that the BD rate savings persist even with modelling errors. Figure <ref> also shows the plots of average and maximum distortions vs. average bitrate obtained by optimizing the bitrates directly for all chunks in the data (blue solid and dotted lines respectively). 
  This can be considered the best rate allocation for the given chunks. 
  The plots show that clustering based rate allocation achieves the smallest possible average distortion for given average bitrate. However, the maximum distortion is larger than the smallest maximum distortion possible. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § CONCLUSION
  
  
  
  
  We presented an efficient method for optimal rate allocation over a large scale corpus using machine learning. Our method clusters the videos in the corpus based on their R-D characteristics and finds the optimal encoder operating points for all clusters. We developed a machine learning model to predict the R-D cluster of a test video using encoder pass log features that are easy to obtain. In the future, we would like to develop a model for finding the optimal encoder parameters using features that are even simpler to compute and reduce the amount of R-D data needed for training. It would be also interesting to integrate the playback statistics in our framework to optimize bitrates for multiple formats of the same video used for adaptive streaming.
  
  
  
  IEEEbib
  
  
  
  