For further information please contact D.J. Ringis<EMAIL_ADDRESS>
# Per-clip adaptive Lagrangian multiplier optimisation
with low resolution proxies

Daniel J. Ringis  Sigmedia Group, Electronic and Electrical Engineering Dept.,
Trinity College Dublin, Ireland  François Pitié  Sigmedia Group, Electronic
and Electrical Engineering Dept., Trinity College Dublin, Ireland  Anil
Kokaram  Sigmedia Group, Electronic and Electrical Engineering Dept., Trinity
College Dublin, Ireland

###### Abstract

Optimising the parameters of a video codec for a specific video clip has been
shown to yield significant bitrate savings. In particular, per-clip
optimisation of the Lagrangian multiplier in Rate controlled compression, has
led to BD-Rate improvements of up to 20% using HEVC. Unfortunately, this was
computationally expensive as it required multiple measurement of rate
distortion curves which meant in excess of fifty video encodes were used to
generate that level of savings. This work focuses on reducing the
computational cost of repeated video encodes by using a lower resolution clip
as a proxy. Features extracted from the low resolution clip are then used to
learn the mapping to an optimal Lagrange Multiplier for the original
resolution clip. In addition to reducing the computational cost and encode
time by using lower resolution clips, we also investigate the use of older,
but faster codecs such as H.264 to create proxies. This work shows the
computational load is reduced by up to 22 times using 144p proxies, and more
than 60% of the possible gain at the original resolution is achieved. Our
tests are based on the YouTube UGC dataset, using the same computational
platform; hence our results are based on a practical instance of the adaptive
bitrate encoding problem. Further improvements are possible, by optimising the
placement and sparsity of operating points required for the rate distortion
curves. Our contribution is to improve the computational cost of per clip
optimisation with the Lagrangian multiplier, while maintaining BD-Rate
improvement.

###### keywords:

Video Compression, Video Codecs, Adaptive Encoding

##  1 INTRODUCTION

The amount of user generated video content has increased significantly [1] to
the point that it represents almost 80% of all internet traffic [2]. Hence
video compression for video streaming applications has become even more
important in the last decade since the development of H.264. Recent efforts in
the community have led to the rapid deployment of next generation codecs e.g.
H.265 (HEVC) [3] and VP9 [4] and these are projected to displace H.264 in
devices and browsers in the near future [5]. Further iterations of these
codecs already exist (H.266/VVC and AV1), but they are not yet in widespread
use. This paper concentrates on performance of H.265 and VP9.

The key challenge facing any codec is the trade-off between rate and
distortion. The accepted approach to controlling this trade-off is to express
both terms in a cost $J$ as follows.

$J=D+\lambda R$ (1)

$J$ combines both a distortion $D$ (for a frame or macroblock) and a rate $R$
(the number of coded bits for that unit) through the action of the Lagrangian
multiplier $\lambda$. The Lagrange multiplier approach was advocated by
Sullivan et al [6] and that has been the adopted view in codec implementations
since 1998. Any adjustment to the Lagrangian multiplier would lead to a change
in the Rate-Distortion trade-off. This has an impact throughout the codec, as
the idea is applied to many internal operations e.g. motion vectors, block
type (Skipped/Intra/Inter), and bit allocation at the frame and clip levels
[7]. The choice of $\lambda$ was determined experimentally in the early days
of codec research [8]. A small dataset (less than 5 videos) was used to
determine this potentially optimal choice of $\lambda$. This small dataset may
have been an adequate representation of videos at that time (1990s) but may
not be ideal with the large range of user generated video content today.

###  1.1 Contributions in this paper

This paper explores the idea that a better $\lambda$ exists for an individual
video clip which improves the BD-Rate compared to the current defaults used in
existing implementations of the codecs considered.

To generate results which are meaningful in modern day content at high
resolutions, our first contribution is establish a reference of possible
improvements for both VP9 and x265 on a large dataset of approximately 10,000
UGC video clips, by direct optimisation of $\lambda$ per clip.

Second, as computational complexity is of key importance given the amount of
video data being processed, we explore the use of proxy videos (different
codec, different resolution, different codec settings) for estimating the
optimised $\lambda$ at higher resolutions.

In addition to these direct optimisation schemes, we investigate the use of
Machine Learning methods to directly predict the optimal $\lambda$ from the
bitstream features.

Results show up to 25% gain in BD-Rate using direct optimisation, and up to
13% with Machine Learning methods specifically Random Forests. The next
section presents a more detailed background and a review of recent work.

##  2 Background

The rate distortion algorithm [9] establishes a balance between the quality of
the media and the transmission or storage capacities of the medium. As
mentioned above, seminal work of Sullivan and Wiegand [6] laid the foundation
for an empirical approach to choosing an appropriate $\lambda$. This work
established a relationship between the quantisation step size $Q$ and the
distortion $D$ in a frame. Through minimising $J$, this leads to a
relationship between $\lambda$ and $Q$ expressed as $\lambda=0.85\times
Q^{2}$. A similar approach is deployed in the rate distortion algorithm for
VP9. Which has a RD Cost multiplier directly proportional to $Q^{2}$ depending
on the frame type [10]. Updates to those experiments then yielded similar
relationships for H.264 and H.265 (HEVC). Because of the introduction of bi-
directional (B) frames the constants are all different and three different
relationships were established for each of the Intra (I), Predicted (P) and B
frames as follows.

$\displaystyle\lambda_{I}$ $\displaystyle=(0.57)2^{(Q-12)/3}$
$\displaystyle\lambda_{P}$ $\displaystyle=(0.85)2^{(Q-12)/3}$
$\displaystyle\lambda_{B}$
$\displaystyle=(0.68)\max(2,\min(4,(Q-12)/6))2^{(Q-12)/3}$

###  2.1 Adaptive Rate Control

There exists a limited amount of work on adaptation of $\lambda$ in the rate
distortion equation. In all cases, results support the idea that adjusting
$\lambda$ leads to improvement in codec performance per clip. The idea is
typically to adjust $\lambda$ away from the codec default by using a constant
$k$ as follows.

$\lambda_{\textrm{new}}=k\times\lambda_{\textrm{orig}}$ (2)

where $\lambda_{\textrm{orig}}$ is the default Lagrangian multiplier estimated
in the video codec, and $\lambda_{\textrm{new}}$ is the updated Lagrangian.
The algorithms for estimating $k$ can be classified as Online and Offline. In
Online processing, $k$ is updated continuously during encoding, usually per
GOP. In contrast, Offline processing is effectively a two pass process
requiring an initial analysis stage followed by the use of a modified encode.

Offline:  Ma et al [11] used a Support Vector Machine to determine $k$. The
perceptual feature set included scalars representing Spatial Information and
Temporal Information, and a texture feature exploiting a Gray Level
Concurrence Matrix. Details can be found in [11]. Their focus was on Dynamic
textures and they used the DynTex dataset[12] of 37 sequences. They reported
up to 2dB improvement in PSNR and 0.05 improvement in SSIM at equal bitrates.
Hamza et al [13] also take a classification approach but using gross scene
classification into indoor/outdoor/urban/non-urban classes. They then used the
same $k$ for each class. Their work used the Derfs dataset[14] and reported up
to 6% BD-Rate improvement.

Online:  Zhang and Bull [15] used a single feature ${D}_{P}/{D}_{B}$, the
ratio between the MSE of P and B frames. This feature gives some idea of
temporal complexity. Experiments based on the DynTex database yielded a choice
for $k$ as follows.

$k=a({D}_{P}/{D}_{B}+d)^{b}+c$ (3)

where $a,b,c\textrm{ and }d$ were experimentally calculated and different for
each codec tested (H.264 and H.265). In their work, $k$ was updated every GOP
and they report up to 11% improvement in BD-Rate. They modified $\lambda$
implicitly by adjusting the quantiser parameter $Q$. Papadopoulos et al[16]
exploited this and applied an offset to Q, in HEVC, based on the ratio of the
distortion in the P and B frames. Each QP was updated from the previous Group
of Pictures (GOP) using $\textrm{QP}=a\times({D}_{P}/{D}_{B})-b$ where $a,b$
are constants determined experimentally. This lead to an average BD-Rate
improvement of 1.07% on the DynTex dataset, with up to 3% BD-Rate improvement
achieved for a single sequence.

Yang et al [17] used a combination of features instead of just the MSE ratio
above. In their work, they used a perceptual content measurement $S$ to model
$k$ with a straight line fit $k=aS-b$. Here again $a,b$ were determined
experimentally using a corpus of the Derfs dataset. The loss in complexity of
the fit is compensated for by the increase in complexity of the feature. They
report an average BD-Rate improvement of 6.2%.

Recent work by Ling et al [18] indicated that the rate distortion performance
of a video can be categorised. They have indicated that information about the
video clips, in particular chrominance information, may lead to better RD-
categorisation and subsequently improved RD-optimisation.

###  2.2 Direct Optimisation of the Lagrangian Multiplier

As shown in equation 2 previous work attempts to adjust the rate control
parameter $\lambda$ adaptively in some way. However there is no effort to
establish a ground-truth best possible $k$. In our recently published work
[19] we introduce the use of direct optimisation to maximise BD-Rate
improvement w.r.t $k$ for a given clip. This can be used as ground truth for
developing a computationally more efficient approach with Machine Learning
and/or proxies. We present a summary of that previous work to set the context
for our new contributions.

In order to show that there is something to be gained in varying $k$ per clip,
figure 1 shows BD-Rate vs $k$ for four different clips. There are two
observations to be made. Firstly, the relationship between $k$ and BD-Rate
varies substantially between clips. This reinforces the view that the
traditional one size fits all approach is sub-optimal. Secondly, the general
shape of the curves shows a global minimum. That minimum represents the
maximum BD-Rate improvement available.

Figure 1: BD-Rate vs $k=[0.2:0.2:3]$ for four different clips
(LiveMusic_1080P-6d1a, MusicVideo_480P-6fb6, NewsClip_720P-7e56 and
Animation_1080P-2fff). The best performing BD-Rate gain is achieved at a
different value for $k$ in each clip. Hence per-clip optimisation is sensible.
The curve shape shows a global minimum implying that classic optimisation
strategies would be successful.

We directly minimise BD-Rate [20] with respect to $k$ ($B_{r}(k)$) using a
scalar optimisation strategy, Brent’s Method111Although any optimisation
technique could be used. [21]. We denote that estimate as $k_{D}$. The
objective function, $B_{r}(k)$, is therefore as follows.

$B_{r}(k)=\int_{D_{a}}^{D_{b}}(R_{1}(D)-R_{k}(D))dD$ (4)

Here the integral is evaluated over the quality range $D_{a}..D_{b}$.
$R_{1}(D),R_{k}(D)$ are the RD curves corresponding to the default ($k=1$) and
the evaluated multiplier $k$ respectively. Each RD operating point is
generated at a constant quality. The overall optimisation process is then as
follows.

  1. 1.

Generate an RD curve using $\lambda_{orig}$ and using 5 operating points (CRF
22,27,32,37,42).

  2. 2.

Define our BD-Rate objective function as specified above in equation 4. We use
the same polynomial-log fit for evaluating the integral as recommended by
Bjontegaard[20]. PSNR is used for the Distortion criterion.

  3. 3.

Starting from $k=1.0$, minimise $B_{r}(k)$ wrt $k$ using Brent’s method.[21]

Note that for every evaluation of $B_{r}(k)$, five (5) encodes are required as
well as the subsequent BD-Rate calculation itself. Optimisation was terminated
when $B_{r}(k)$ reduced by less than 0.05%.

Figure 2 shows the points visited in the optimisation search using Brent’s
method for two other clips (Animation_1080P-01b3 and LiveMusic_1080P-76fa).
This shows the optimisation being successful in each case, leading to a BD-
Rate improvement of 2.02% and 0.61% respectively. In the next sections we use
a much expanded corpus to generate a statistically meaningful baseline of
performance and then focus on computational complexity.

Figure 2: BD-Rate(%) vs $k$ for two clips (Animation_1080P-01b3 and
LiveMusic_1080P-76fa). Only the points visited using the optmisation scheme
(Brent’s Method) are shown to give an idea that the process does converge.
This leads to an improvement of 2.02% and 0.61% respectively.

Figure 3: Example frames from different classes in the YouTube dataset.

##  3 Generating Ground Truth Optimal Lambda Values

Using this direct optimisation technique, we estimated in our previous
work[19], the optimal value $k$ for a corpus of 77 clips for the x265 and
showed that an improvement of 21% could be obtained by fine tuning the
Lagrangian Multipliers. We propose here to extend the study to a much larger
dataset of 10K clips from the YouTube UGC dataset, covering thus a much wider
range of use cases. We also extend the study by considering both x265 and VP9.

###  3.1 Dataset

Previous work used a small corpus size (approximately 40 clips[11][15] (up to
300 frames per clip)) as well as 77 clips in our own previous work[19]. Also
the types of content used in previous corpora are not necessarily a good
representation of modern material. Therefore, in this work, we use an expanded
dataset of 9,476 5-second clips. This includes the recently published YouTube
dataset [1] representing 12 classes of video as specified by the YouTube team.
A sample of each class of the clips can be seen in Figure 3. In addition we
use clips from other publicly available datasets, these include Netflix
dataset (Chimera and El Fuente)[22], DynTex dataset[12], MCL[23] and Derfs
dataset[14]. Multiple DASH segments (clips) of 5 seconds (150 frames) were
created from each sequence. Table 1 shows the database composition by clip
categories. There are 9,746 video clips at varying resolutions with a wide
range of video content, representative of typical usage. This represents more
than a 100 fold increase in the amount of data used for our experiments.

Table 1: Composition of the dataset. Each segment is 150 frames (5 seconds) chosen to represent a typical DASH streaming segment length.  Subset | Segments | Resolution
---|---|---
Youtube UGC [1] | 8000 | 320p to 1080p
MCL [23] | 220 | 1080p
Dyntex [12] | 650 | 240p
Derfs [14] | 796 | 240p to 1080p
Netflix [22] | 80 | 1080p
Total | 9746 |

###  3.2 Implementation

The codebase for x265 and VP9 was modified to take $k$ as an argument. This
allows the default $\lambda_{orig}$ to be modified according to equation 2. We
use the VideoLAN [24] implementation of H.265, x265222Version:
3.0+28-gbc05b8a91 and the WebM Project [10] implementation of VP9333Version:
v1.8.1-152-g65c439523. It is important to note that this work does not aim to
compare HEVC and VP9, but to improve both codecs relative to their default
behaviour. The following command invocations were used:

HEVC: x265 --input SEQ.y4m --crf <XX> \--tune-PSNR --psnr --output OUT.mp4

VP9: vpxenc -p 1 --end-usage=vbr --cq-level <XX> \--tune=psnr --psnr -o
OUT.mkv SEQ.y4m

where SEQ and OUT are the filenames for the raw input file and output encoded
video. Clips were encoded with <XX> in the range 22:5:42.

###  3.3 Results

For our corpus of video clips we minimise BD-Rate w.r.t. $k$ following the
algorithm in the previous section, applied to the original resolution data
(system S0). The cumulative distribution of the resulting maximum improvement
(minimum BD-Rate using the optimal $k=k_{D}$) is shown in Figure 4. That
figure actually shows a summary of improvements using proxies as well but in
this section we are only interested in the curve labelled S0 in blue. As can
be seen the distribution is long tailed implying that most clips show moderate
improvement (1.87%, 1.324% (HEVC, VP9) on average) and in fact approximately
20% of clips encoded using $k_{D}$ had a BD-Rate improvement of 1% or more.
The best improvement for HEVC and VP9 was 23.41% and 22.13% respectively. Of
course there are still a number of video clips where the original Lagrangian
multiplier was the best. Using a BD-Rate improvement of 0.01% as the minimum
level of improvement, 93% of clips encoded with HEVC and 75.6% encoded with
VP9 showed improvement. This is consistent with our previous work[19] which
had up to 21% BD-Rate improvement for HEVC with 87% of the clips encoded
having an improvement.

This direct optimiser (S0) took on average 11.7 iterations, which would mean
$11.7\times 5\approx 60$ video encodes. This is manageable at small
resolutions, but is computationally intensive at modern resolutions (720p and
higher) and at scale. The next sections introduce our approaches to address
this problem.

|
---|---
(a): HEVC | (b): VP9
Figure 4: Cumulative distribution of BD-Rate improvement over 9,746 clips
using $k$ calculated from various versions of the data or different codec
invocations. Left: HEVC and right: VP9. The best performing systems would be
nearest to the top right of the plot. In blue is the BD-Rate distribution
using the original resolution and $k_{D}$ i.e. the ground truth best
performance possible. Using faster video encodes but at the original
resolution (system S2 yellow) yields almost identical performance to ground
truth but with improvement in speed of 6% for VP9 and 300% for HEVC. The other
curves show use of smaller resolutions and/or H264 as the codec. They are much
faster (up to $\times 22$) but as can be seen achieve about 33% of the
possible gains on average.

##  4 Improving computational cost

In order to make direct optimisation more computationally efficient, we
consider both using a proxy video encode and Machine Learning methods using
low bandwidth video features. Using proxies can be either an encoding of the
raw video at a smaller resolution or using faster codec settings or using an
older/faster codec (eg H264). Each of these would represent a reduction in
computational cost, even when using the same direct optimisation algorithm
previously outlined. The invocations used in this work are as follows.

HEVC:

x265 --input SEQ.y4m --tune psnr --psnr --crf Q --frames 150 --output OUT.mp4

VP9:

vpxenc -p 1 --end-usage=cq --threads=7 --tune=psnr --psnr --cq-level=Q OUT.mkv
SEQ.y4m

H264:

x264 --frames 150 --tune psnr --psnr --crf Q --output OUT.264 SEQ.y4m

We present our new systems next.

###  4.1 Using Proxies

We use clips at 144p as well as using the faster preset for the codecs
(“ultrafast” (H265) or “rt”(VP9)). We also consider using H264 at original
resolution as an alternate but faster codec. We organise the use of these
proxies in the following systems.

  1. S0:

$k_{\textrm{D}}$ estimated at original resolution/codec provides the reference
best performance i.e. ground truth. This was presented in the previous
section.

  2. S1:

$k_{\textrm{144}}$ estimated at 144p and used for encoding at the original
resolution

  3. S2:

$k_{\textrm{Dfast}}$ estimated using the “ultrafast” (H265) or “rt”(VP9)
setting in the codec and used for encoding at the original resolution

  4. S3:

$k_{\textrm{264}}$ estimated using H264 and used for encoding in the original
codec

We implement the direct optimisation algorithm as in Section 2.2 for our three
proxy systems (S1,S2,S3). FFMPEG is deployed with bicubic interpolation for
downsampling the video corpus to 144p resolution for S1. We use the
“ultrafast” preset for x265 and VP9 for S2, and we modify x264444Version:
0.157.x in a similar fashion to x265 by inserting our own multiplier $k$.

####  4.1.1 Speed Gain with Proxies

In order to quantify the savings in compute time achieved by using a proxy we
encoded 250 DASH clips (150 frames) of the sequence Elephants Dream at 720p
with each proxy. This time was measured on the same machine (Intel(R) Xeon(R)
CPU E3-1240 v5 @ 3.50GHz with 16GB RAM) and the relative performance of a
single iteration in each system is shown in Table 2.

Table 2: Processing time comparison of VP9 and H265 with faster codec settings and smaller resolutions as well as H264  System | Time (s) | per clip | Speedup
---|---|---|---
HEVC: S0 | 4871 | 19.48 | 1
HEVC: S1 | 222 | 0.89 | 21.94
HEVC: S2 | 1585 | 6.34 | 3.07
HEVC: S3 | 1348 | 5.39 | 3.61
VP9: S0 | 12573 | 50.29 | 1
VP9: S1 | 1406 | 5.62 | 8.94
VP9: S2 | 11796 | 47.18 | 1.07
VP9: S3 | 1348 | 5.39 | 9.33

From table 2, we can see that using the smaller resolution videos gives us the
biggest improvement in speed with the time to encode being 22x faster with
x265 and 9 times faster with VP9. Encoding using x264 also shows a significant
improvement in encode time with 3.7x and 9.3x (HEVC, VP9) times improvement.
The smallest savings are found when using the faster encoding presets for each
codec with 3.1x and 1.1x (HEVC, VP9) improvements being found using the
“ultrafast” and “rt” presets respectively. If we are able to get comparable
BD-Rate savings using these proxies it would indicate a significant
improvement in compute time for the direct optimisation methods applied.

####  4.1.2 Performance Gains with Proxies

Figure 5 shows that for the majority of clips there is a close correlation
between ground truth $k=k_{D}$ generated at original resolution and $k$
generated at 144p. This is because the scatter plots are close to the
$k=k_{D}$. This holds true for all three systems S1, S2 and S3 for both HEVC
and VP9. $k$ is most similar to the original estimates when using the faster
codec settings at the original resolution (S2) and least similar using H264 to
estimate (S3).

Figure 5:  $k_{D}$ vs $k_{\tt Alt}$ determined from a proxy video or codec
LEFT: x265, RIGHT: VP9. Ideally, we would want points to lie on the line y=x.
We can see a strong correlation between $k$ and $k_{\tt Alt}$ determined by S2
(green) and S0.

Figure 4 summarises the BD-Rate performance gains over the whole corpus. The
Cumulative density distribution of each system is reported there. Using the
fast presets at the original resolution (S2) gives us very similar performance
to our original direct optimisation algorithms in both HEVC and VP9. Using a
different codec (H264) to estimate $k$ however, gave the worst results. A
summary of our findings using systems S1, S2, S3 can be found in table 3.

Table 3:  Summary of BD-R Gains results using Direct Optimisation with Proxies. This shows the $\%$ of clips which have no improvement, $\>0.1\%$ and $\>1\%$ improvement, as well as the best and average BD Rate improvement. * indicates which system we believe provides us with the best balance between speedup and maintaining BD-Rate improvement  System | Clips with BD-R gain of | Best | Avg | Speedup
---|---|---|---|---
$=0\%$ | $>0.1\%$ | $>1\%$ | Gain | Gain
S0: x265 | 8% | 87.00% | 46.24% | 23.86% | 1.87% |  $\times$1.0
S1: x265 | 9% | 78.17% | 45.23% | 20.46% | 0.54% |  $\times$21.9
S2: x265 * | 9% | 86.57% | 18.75% | 20.59% | 1.54% |  $\times$3.1
S3: x265 | 9% | 74.21% | 14.13% | 20.12% | 0.58% |  $\times$3.6
S0: VP9 | 22% | 74.00% | 38.75% | 22.13% | 1.63% |  $\times$1
S1: VP9 | 22% | 73.00% | 35.73% | 20.60% | 0.5% |  $\times$8.9
S2: VP9 | 22% | 74.00% | 38.75% | 22.13% | 1.32% |  $\times$1.1
S3: VP9 * | 22% | 66.00% | 12.85% | 19.36% | 1.19% |  $\times$9.3

In all the proposed systems, the majority of clips show some BD-Rate
improvement. The average BD-Rate improvement is in the range of 1% across the
corpus. We see in Table 3 that the best tradeoff is system S3 for VP9 (1.19%
BD-Rate avg gain out of a possible 1.63% with S0, thus 73% of the potential
average BD-Rate gains at $\times$ 9.3 speed) and S2 for HEVC (83% of the
possible average BD-Rate gains from S0 at $\times$ 3.1 speed).

Using the direct optimisation methods still requires a large number of video
encodes for a given clip regardless of resolution. Hence the next level of
performance is to use a Machine Learning approach.

###  4.2 Machine Learning

We investigate an Offline process in which the first step measures video
features that are mapped to $k$ through an ML algorithm. This significantly
reduces computational complexity. Our proposed feature set consists of 17
features: Overall Bitrate, Overall PSNR, PSNR for Y, U and V channels, Avg
bitrate for I, P and B frames, Avg PSNR (Y,U,V) for I, P and B frames, Frame
height and width. Similar to Covell et al [25], non linear extensions of the
feature set were created from products of feature elements by taking the
product of a subset of feature pairs. The final feature vector therefore
contains 49 elements.

We use $k_{D}$ as ground truth for training our ML process. Note that $k$ was
range limited $0<k<6$ and we hold out 10% of the dataset for testing. With the
remaining corpus, cross validation with five (5) folds was done for the
training to minimize over-fitting. We tested 19 ML methods (including Logistic
and Linear Regression SVMs, Decision Trees) and found that Random Forests
yielded best results. We can denote these additional systems created using
machine learning results as follows:

  1. ML0:

$k_{\textrm{M}}$ using features estimated at original resolution/codec

  2. ML1:

$k_{\textrm{M144}}$ using features estimated at 144p and used for encoding at
the original resolution

  3. ML2:

$k_{\textrm{Mfast}}$ using features estimated using the “ultrafast” (H265) or
“rt”(VP9) setting in the codec and used for encoding at the original
resolution

Using ML0, the random forest model as stated above, we find that 64.74%, 62.38
% (HEVC, VP9) of the possible BD-Rate gain at original resolution (i.e. S0)
was achieved. Furthermore, 66.96%, 58.22 % (HEVC, VP9) of the video corpus
showed an improved BD-Rate. Similar results were found with ML2, which used
the results from the ”ultrafast“ encodes with 63.48%, 57.79 % (HEVC, VP9) of
the possible BD-Rate gain at S0 were achieved.

The biggest savings in computational time would be ML1, where we extract
features at 144p, and use these to estimate $k$, ($k_{\textrm{Msmall}}$), and
encode at the original. We find that 56.82%, 54.27% (HEVC, VP9) of the video
corpus showed a BD-Rate improvement. Overall this implied that 64.24%, 67.72%
(HEVC, VP9) of the possible gain was achieved.

Table 4 shows a summary of the findings for systems ML1, ML2 and ML3. With
nearly half of clips showing no improvement, we can see that this needs more
work. Determining what features of the video are best suited to predict the
appropriate $k$ for RD optimisation is a challenge. However, this work shows
promise by being sixty (60) times faster than the direct optimisation methods
in the previous section as only a single video encode is required to predict
$k$ for a given clip.

Table 4:  Summary of BD-R Gains Results using Machine Learning with Proxies. This shows the $\%$ of clips which have no improvement(including those which performed worse), $\>0.1\%$ and $\>1\%$ improvement, as well as the best and average BD Rate improvement  System | Clips with BD-R gain of | Best | Avg | Speedup
---|---|---|---|---
$=0\%$ | $>0.1\%$ | $>1\%$ | Gain | Gain
ML0: x265 | 33% | 27.5% | 2.2% | 8.54% | 0.19% |  $\times$60
ML1: x265 | 43% | 26.8% | 2.1% | 11.83% | 0.18% |  $\times$1314
ML2: x265 | 37% | 26.6% | 2.4% | 13.93% | 0.19% |  $\times$186
ML0: VP9 | 41% | 44.1% | 3.1% | 9.62% | 0.14% |  $\times$60
ML1: VP9 | 45% | 39.7% | 3.2% | 10.09% | 0.14% |  $\times$534
ML2: VP9 | 42% | 40.1% | 3.3% | 8.41% | 0.14% |  $\times$66
|
---|---
(a): HEVC | (b): VP9
Figure 6: Cumulative distribution of BD-Rate improvement over 9,746 clips
using $k$ calculated using the various Machine Learning systems. Left: HEVC
and right: VP9. The best performing systems would be nearest to the top right
of the plot. In blue is the BD-Rate distribution using the original resolution
and $k_{D}$ i.e. the ground truth best performance possible. Over a third of
the clips do not show any BD-Rate improvement. The three ML systems did not
provide comparable gains to the direct optimisation scheme (S0), although they
have an order of magnitude lower computational cost.

##  5 Conclusion

In this paper, we have presented seven computationally efficient systems which
estimate optimal $k$ in a variety of ways which rely on proxies and ML for
estimation. It is important to note that this work does not aim to compare
HEVC and VP9, but to improve both codecs using the same methods, with respect
to their default configurations. Our best performing system wrt BD-Rate gain
alone is direct optimisation (S0) at the target resolution. Gains of up to 23%
can be achieved here. That was used as the ground truth or upper limit of
performance against which six more efficient systems were evaluated. We find
that using proxies is useful and in fact can achieve comparable results at
much faster speeds. It seems that S2 provides the closest estimate, but ML1
gives us the biggest improvement in compute time. Finally, we note that our
corpus is more appropriate for modern use cases. The size of the data tested
is significantly larger than previous work in this area. Future work will
involve the exploration of more complex inference engines like DNNs.

###### Acknowledgements.

This work was supported in part by YouTube, Google and the Ussher Research
Studentship from Trinity College.

## References

  * [1] Wang, Y., Inguva, S., and Adsumilli, B., “Youtube UGC dataset for video compression research,” in [2019 IEEE 21st International Workshop on Multimedia Signal Processing (MMSP) ], 1–5 (Sep. 2019).
  * [2] Cass, S., “The age of the zettabyte cisco: the future of internet traffic is video [dataflow],” IEEE Spectrum 51(3), 68–68 (2014).
  * [3] Sullivan, G. J., Ohm, J.-R., Han, W.-J., and Wiegand, T., “Overview of the high efficiency video coding (HEVC) standard,” IEEE Transactions on circuits and systems for video technology 22(12), 1649–1668 (2012).
  * [4] Mukherjee, D., Bankoski, J., Grange, A., Han, J., Koleszar, J., Wilkins, P., Xu, Y., and Bultje, R., “The latest open-source video codec VP9-an overview and preliminary results,” in [2013 Picture Coding Symposium (PCS) ], 390–393, IEEE (2013).
  * [5] Zhang, T. and Mao, S., “An overview of emerging video coding standards,” GetMobile: Mobile Computing and Communications 22(4), 13–20 (2019).
  * [6] Sullivan, G. J. and Wiegand, T., “Rate-distortion optimization for video compression,” IEEE signal processing magazine 15(6), 74–90 (1998).
  * [7] Wiegand, T. and Girod, B., “Lagrange multiplier selection in hybrid video coder control,” in [Proceedings 2001 International Conference on Image Processing ], 3, 542–545, IEEE (2001).
  * [8] Ortega, A. and Ramchandran, K., “Rate-distortion methods for image and video compression,” IEEE Signal processing magazine 15(6), 23–50 (1998).
  * [9] Wiegand, T., Lightstone, M., Mukherjee, D., Campbell, T. G., and Mitra, S. K., “Rate-distortion optimized mode selection for very low bit rate video coding and the emerging H. 263 standard,” IEEE Transactions on Circuits and Systems for Video Technology 6(2), 182–190 (1996).
  * [10] Project, T. W., “The WebM Project, VP9 Project Summary.”  https://www.webmproject.org/vp9/.
  * [11] Ma, C., Naser, K., Ricordel, V., Le Callet, P., and Qing, C., “An adaptive lagrange multiplier determination method for dynamic texture in HEVC,” in [2016 IEEE International Conference on Consumer Electronics-China (ICCE-China) ], 1–4, IEEE (2016).
  * [12] Ghanem, B. and Ahuja, N., “Maximum margin distance learning for dynamic texture recognition,” in [European Conference on Computer Vision ], 223–236, Springer (2010).
  * [13] Hamza, A. M., Abdelazim, A., and Ait-Boudaoud, D., “Parameter optimization in H. 265 rate-distortion by single frame semantic scene analysis,” Electronic Imaging 2019(11), 262–1 (2019).
  * [14] Xiph.org, “Xiph.org Video Test Media.”  https://media.xiph.org/video/derf/.
  * [15] Zhang, F. and Bull, D. R., “Rate-distortion optimization using adaptive lagrange multipliers,” IEEE Transactions on Circuits and Systems for Video Technology 29, 3121–3131 (Oct 2019).
  * [16] Papadopoulos, M. A., Zhang, F., Agrafiotis, D., and Bull, D., “An adaptive QP offset determination method for HEVC,” in [2016 IEEE International Conference on Image Processing (ICIP) ], 4220–4224 (Sep. 2016).
  * [17] Yang, A., Zeng, H., Chen, J., Zhu, J., and Cai, C., “Perceptual feature guided rate distortion optimization for high efficiency video coding,” Multidimensional Systems and Signal Processing 28(4), 1249–1266 (2017).
  * [18] Ling, S., Baveye, Y., Callet, P. L., Skinner, J., and Katsavounidis, I., “Towards perceptually-optimized compression of user generated content (ugc): Prediction of ugc rate-distortion category,” in [2020 IEEE International Conference on Multimedia and Expo (ICME) ], 1–6 (2020).
  * [19] Ringis, D. J., Pitie, F., and Kokaram, A., “Per clip lagrangian multiplier optimisation for (HEVC),” Electronic Imaging 2020(12) (2020).
  * [20] Bjontegaard, G., “Calculation of average PSNR differences between rd curves; VCEG-M33,” tech. rep. (2001).
  * [21] Flannery, B. P., Press, W. H., Teukolsky, S. A., and Vetterling, W., “Numerical recipes in C,” Press Syndicate of the University of Cambridge, New York 24, 78 (1992).
  * [22] Netflix, “Netflix Open Content.”  https://opencontent.netflix.com/.
  * [23] Lin, J. Y., Jin, L., Hu, S., Katsavounidis, I., Li, Z., Aaron, A., and Kuo, C.-C. J., “Experimental design and analysis of jnd test on coded image/video,” in [Applications of digital image processing XXXVIII ], 9599, 95990Z, International Society for Optics and Photonics (2015).
  * [24] VideoLAN, “x265, the free H.265 encoder.”  https://www.videolan.org/developers/x265.html.
  * [25] Covell, M., Arjovsky, M., Lin, Y.-C., and Kokaram, A., “Optimizing transcoder quality targets using a neural network with an embedded bitrate model,” Electronic Imaging 2016(2), 1–7 (2016).