# Machine Learning based Efficient QT-MTT Partitioning Scheme for VVC Intra
Encoders

Alexandre Tissier, Wassim Hamidouche, Souhaiel Belhadj Dit Mdalsi, Jarno
Vanne, Franck Galpin and Daniel Menard A. Tissier, S. Belhadj Dit Mdalsi, W.
Hamidouche and D. Menard are with INSA Rennes, Institute of Electronic and
Telecommunication of Rennes (IETR), CNRS - UMR 6164, VAADER team, 20 Avenue
des Buttes de Coesmes, 35708 Rennes, France. (emails: alexandre.tissier2@insa-
rennes.fr<EMAIL_ADDRESS>and dmenard@insa-rennes.fr).J. Vanne is
with with Tampere University, Korkeakoulunkatu 10, Tampere, 33720, Finland
(emails: jarno.vanne@tuni.fi).F. Galpin is with with InterDigital, Cesson-
Sévigné, 35051, France.

###### Abstract

The next-generation VVC standard introduces a new Multi-Type Tree (MTT) block
partitioning structure that supports Binary-Tree (BT) and Ternary-Tree (TT)
splits in both vertical and horizontal directions. This new approach leads to
five possible splits at each block depth and thereby improves the coding
efficiency of VVC over that of the preceding High Efficiency Video Coding
(HEVC) standard, which only supports Quad-Tree (QT) partitioning with a single
split per block depth. However, MTT also has brought a considerable impact on
encoder computational complexity. In this paper, a two-stage learning-based
technique is proposed to tackle the complexity overhead of MTT in VVC intra
encoders. In our scheme, the input block is first processed by a Convolutional
Neural Network (CNN) to predict its spatial features through a vector of
probabilities describing the partition at each 4$\times$4 edge. Subsequently,
a Decision Tree (DT) model leverages this vector of spatial features to
predict the most likely splits at each block. Finally, based on this
prediction, only the $N$ most likely splits are processed by the Rate-
Distortion (RD) process of the encoder. In order to train our CNN and DT
models on a wide range of image contents, we also propose a public VVC frame
partitioning dataset based on existing image dataset encoded with the VVC
reference software encoder. Our proposal relying on the top-3 configuration
reaches 46.6% complexity reduction for a negligible bitrate increase of 0.86%.
A top-2 configuration enables a higher complexity reduction of 69.8% for 2.57%
bitrate loss. These results emphasis a better trade-off between VTM intra
coding efficiency and complexity reduction compared to the state-of-the-art
solutions111The source code of the proposed method and the training dataset
will be made publicly available at
https://alexandretissier.github.io/QTMTT_VVC/..

###### Index Terms:

VVC, MTT, complexity reduction, CNN, DT.

##  I Introduction

The emerging video formats such as 4K/8K and 360-degree videos alongside the
explosion of IP video traffic [1] pushed organizations such as ISO/IEC, ITU-T
Joint Video Expert Team (JVET) and Alliance for Open Media (AOM) to propose
new video compression standards. AOM developed the AV1 codec released in 2018
as a successor to VP9 and JVET standardized Versatile Video Coding (VVC) ITU-T
H.266 $|$ MPEG-I - Part 3 (ISO/IEC 23090-3) [2] in July 2020 as a successor to
High Efficiency Video Coding (HEVC).

These two standards share the same hybrid video coding structure. Therefore,
during standardization different coding tools were integrated to improve the
intra and inter predictions, the in-loop filtering or to enhance the
partitioning of the block of pixels. The selection of specific coding tools
leads to different coding efficiencies and computational costs. Comparison
studies were conducted between VVC and AV1 [3], [4] based on subjective and
objective quality metrics including Peak Signal-to-Noise Ratio (Psnr) and
Video Multi-method Assessment Fusion (VMAF) which is a Machine Learning (ML)
based quality metric leveraging detail loss metric, visual information
fidelity measure and averaged temporal frame difference. Both works conclude
that VVC outperforms AV1 in terms of both objective and subjective quality
scores. However, computational cost of AV1 fluctuates around the VVC
complexity depending on the considered coding configuration.

The VVC reference software, named VVC Test Model (VTM), implements all
normative VVC coding tools allowing rate-distortion-complexity evaluation and
conformance testing. As the successor to HEVC, the VTM implementation brings
25.32% and 36.95% bitrate reductions at the expense of significant increases
in encoder computational complexity estimated to 2630% and 859% compared to
the Hevc test Model (HM) 16.22 [5] in All Intra (AI) and Random Access (RA)
configurations, respectively.

Compared to HEVC, which is based on a Quad-Tree (QT) block partitioning, VVC
integrates a nested Multi-Type Tree (MTT) partitioning scheme allowing in
addition to QT, horizontal and vertical Binary-Tree (BT) and Ternary-Tree (TT)
splits [6]. This new partitioning scheme is the most efficient tool integrated
in VVC [7] with 8.5% coding efficiency gain reached in RA configuration
compared to HEVC. Nevertheless, this coding efficiency improvement is brought
at the expense of a significant complexity increase. At each level of the
hierarchical partitioning process, up to five splits are tested by the
encoder, compared to the one split (i.e. QT split) for HEVC. Authors in [8]
have shown that disabling BT and TT splits, decreases the encoding time by
91.7%. Therefore, the partitioning process offers the highest opportunity in
terms of complexity reduction compared to other coding tools. In [9], up to
97.5% complexity reduction was reported when only the optimal split is tested
by the encoder at each level of the partitioning process compared to an
exhaustive search.

To enable real-time VVC encoder, the complexity of the QT-MTT partitioning
process must be significantly reduced. The aim of this work is to maximize the
complexity reduction while minimizing the Bjøntegaard Delta Bit Rate (BD-BR)
loss. A large body of literature has investigated the problem of block
partitioning for HEVC [10, 11, 12] and VP9 [13]. For instance, Xu et al. [14]
proposed a Convolutional Neural Network (CNN) to predict a hierarchical
partition map in order to avoid exploring improbable block depths. However,
such approaches cannot be directly applied to VVC as the new partitioning
scheme is significantly different and more complex with the multiplication of
available partitions which makes hard predicting the optimal block depth due
to the huge number of partitions that can lead to the same depth. Recently, a
number of complexity reduction methods tailored for VVC have emerged through
fast encoder strategies [6], probabilistic approach [15] or machine learning
based approach [16]. Deep learning techniques [17] provided a breakthrough in
video coding and especially in the complexity reduction domain. Li et al. [17]
proposed a CNN that predicts the most probable split through a multi
classification at each block depth. One of the drawbacks of this technique is
the time overhead due to the CNN inference performed at each depth. Indeed,
the CNNs computational complexity must be managed in order to not annihilate
the gain obtained by the complexity reduction technique. Authors in [18] have
recently proposed a CNN that processes a block to predict its partition
through a vector of probabilities. The average probability over edges of the
split is then compared to a fixed threshold to decide whether to perform the
split or not at each depth. The main drawbacks of this solution are first its
local decision which does not leverage all probabilities of the block edges
and second in comparing the average probability of the split edges to a fixed
threshold.

In this paper, we propose an efficient complexity reduction technique for the
QT-MTT partitioning. Our approach combines a moderate complexity CNN that
extracts spatial features of the block of pixels with multi-class classifiers
to derive the best partitions to evaluate in the Rate-Distortion Optimization
(RDO) process. A single CNN is used to process a $64\times 64$ block and
predicts as output the probability of each boundary of all the $4\times 4$
pixel blocks within the input $64\times 64$ block. At each level of the
hierarchical partitioning process, a multi-class classifier is used to predict
from the set of boundary probabilities the $N$-most likely splits to explore
by the encoder. One classifier is trained for each size of the 16 different
sub-blocks. At each depth, the number of tested partitions $N$ can be adjusted
from one to the total number of possible splits. This allows exploring wide
range of trade-offs between the complexity reduction and the quality loss. The
proposed solution with top-$N=3$ configuration reaches 46.6% complexity
reduction for a negligible BD-BR increase of 0.86%. The top-$N=2$
configuration enables in average a complexity reduction of 69.8% for 2.57% BD-
BR loss.

The rest of this paper is organized as follows. Section II introduces the
partitioning background and the state-of-the-art of complexity reduction
techniques. Section III describes the proposed two-stage method based on the
combination of two machine learning algorithms. The used dataset to train our
models is detailed in Section IV. The experimental setup and the training
processes for both CNN and Decision Tree (DT) models are presented in Section
V. Section VI presents the performance of the two machine learning models and
a comparison of our method against state-of-the-art techniques in terms of
complexity reduction and BD-BR increase. Finally, Section VII concludes the
paper.

##  II Background and Related work

###  II-A Frame partitioning in Versatile Video Coding (VVC)

The new block partitioning scheme proposed in VVC is the most efficient coding
tool integrated in the standard [19]. The partitioning starts the process on a
root block named Coding Tree Unit (CTU), i.e. a block of $128\times 128$
pixels in the VVC Test Model (VTM) All Intra (AI) configuration. The blocks
resulting from the partitioning process are named Coding Units (CUs) and may
have a size between $64\times 64$ and $4\times 4$. Fig. 1(a) presents the
splits supported by VVC. As High Efficiency Video Coding (HEVC), Quad-Tree
(QT) divides a CU in four equal sub-CUs. Moreover, VVC allows rectangular
shape for CU with its novel splits Binary-Tree (BT) and Ternary-Tree (TT). The
BT divides a CU in two sub-CUs while the TT divides a CU in three sub-CUs with
the ratio 1:2:1. Both BT and TT can split a CU horizontally or vertically.
Fig. 1(b) presents the splits of a CTU processed by VTM Rate-Distortion
Optimization (RDO). The RDO process relies on an exhaustive search that
calculates the Rate-Distortion (RD)-cost for each CU and selects the CTU
partition that results in the lowest RD-cost. In AI configuration, the VTM
forces the first split of the CTU to be a QT. Additional constraints are also
applied on CUs, for instance, QT is not allowed after a BT or a TT split.
Excluding the VTM restrictions, the encoder performs all possible splits on
each CU in order to select the optimal partition with the lowest RD-cost.

Figure 1: CTU partitioning in VVC. (a) VVC split types. (b) Example of a CTU
partition in MTT.

###  II-B Existing techniques for encoder complexity reduction

A brief review on complexity reduction methods proposed to speedup the
reference software encoders of the HEVC and VVC standards is provided in this
section. Authors in [9] have studied the complexity reduction opportunities in
the VTM 3.0 under the AI configuration. Several tools have been identified to
reduce the encoding complexity such as the partitioning process, the intra
mode prediction and the multiple transform selection. This study showed that
the partitioning process has the highest impact on encoder computational
complexity with 97.5% of complexity reduction followed by the intra mode
prediction with 65.2% and the multiple transform selection with 55.2%. This
study motivated the work of this paper that tackles the complexity reduction
of the partitioning process.

Meanwhile, several works have studied the complexity reduction of the intra
mode prediction [20] and the multiple transform selection [21]. In order to
reduce the complexity of the partitioning process, state-of-the-art solutions
rely on different approaches to compute features relevant for this problem
including handcrafted and learning-based techniques. The computed features are
then fed to a classifier such as Decision Tree (DT), Support Vector Machine
(SVM) or dense layers. It should be noted that the performance of the most
following techniques is provided under the AI coding configuration unless
otherwise specified.

####  II-B1 HEVC complexity reduction techniques

The complexity reduction of the HEVC recursive block partitioning has been
widely investigated in the literature. Min et al. [22] defined a complexity
score metric that predicts the spacial complexity of a block. The complexity
score is computed as the l1 norm of the differences between the luminance
pixel value at a position and the mean luminance value. This complexity score
is computed for the two sub-blocks obtained by dividing the block in
horizontal, vertical or in the two diagonals. The difference between the two
complexity values of the resulting sub-blocks is computed. This value is then
compared to a predefined threshold to decide whether the block should be
split, no split or undetermined. This solution reaches 52% of complexity
reduction at the expense of a slight Bjøntegaard Delta Bit Rate (BD-BR)
increase of 0.8%. Correa et al. [10] used three sets of decision tree trained
with features such as RD-cost, gradient, sum of pixels or variance of pixels.
These decision trees predict whether the CU, Prediction Unit (PU) or Transform
Unit (TU) must be split or not. By predicting these partitioning specific to
HEVC, this solution achieves 65% of computational complexity reduction for
1.36% BD-BR loss. Convolutional Neural Networks (CNNs) have already been
exploited for HEVC encoding complexity reduction [14, 11]. Xu et al. [14]
first used a CNN to predict a hierarchical CU partition map which provides an
efficient representation of the CU partitioning in intra mode. An Long-Short
Term Memory (LSTM) network was then integrated to predict the partition in
inter prediction mode. In AI configuration, this solution reduces the
complexity by 62% for 2.25% BD-BR increase. Under the low delay P coding
configuration, it reaches 54.2% of computational complexity reduction for 1.5%
BD-BR increase. Li et al. [11] claimed a real time CTU partition prediction
based on their previous proposed complexity reduction method presented in
[14]. They simplified the CNN by pruning the weights at different levels to
perform multiple approximations. These different configurations allow a
complexity control at CTU level by selecting the proper CNN. An estimation of
the CNN run time is performed at the frame level to enhance the stability of
complexity control. The CNN run time speedup is enhanced by 17 to 20 times
with a complexity control error of 2%.

####  II-B2 Joint Exploration Model (JEM) complexity reduction techniques

The JEM software was developed in early 2014 to study the potential coding
gain behind developing a new standard beyond HEVC. The JEM software is based
on Hevc test Model (HM) with new coding tools such as Multiple Transform
Selection (MTS) and BT proposed to enhance the partitioning efficiency at the
cost of higher computational complexity. Wang et al. [15] proposed a novel RD-
cost estimation scheme relying on motion divergence field. Based on the
estimated RD-cost, a probabilistic framework is developed to skip unnecessary
splits. The proposed algorithm reduces the complexity by 54.7% for 1.15% BD-BR
increase in Random Access (RA) configuration. The same authors proposed in
[23] as first step a dynamic parameters choice at CTU level based on
neighboring partitions. In a second step, both QT and BT decision tree
classifiers predict the probability of the different splits in order to derive
the proper partition. These two techniques enable 67.6% of complexity
reduction for 1.34% BD-BR increase in AI configuration. Jin et al. [24]
designed a multi-classification CNN that predicts the partition depth of a
$32\times 32$ CU. This method enables skipping unnecessary splits for the
partition depth predicted as outside the candidate depth range. The encoder
computational complexity is reduced by 42.8% for a BD-BR increase of 0.65%.

TABLE I: Main features of existing state-of-the-art complexity reduction techniques in All Intra coding configuration. Solution | Handcrafted | Decision Tree | Neural network | Software | Complexity reduction (%) | BD-BR (%)
---|---|---|---|---|---|---
Biao et al. [22] | ✓ | ✗ | ✗ | HM 10.0 | 52% | 0.8%
Xu et al. [14] | ✗ | ✗ | ✓ | HM 16.5 | 62% | 2.25%
Wang et al. [23] | ✓ | ✓ | ✗ | HM 13.0 QTBT | 67.6% | 1.34%
Jin et al. [24] | ✗ | ✗ | ✓ | JEM 3.1 | 42.8% | 0.65%
Fu et al. [25] | ✓ | ✗ | ✗ | VTM 1.0 | 44.8% | 1.02%
Yang et al. [26] | ✓ | ✓ | ✗ | VTM 2.0 | 52% | 1.59%
Chen et al. [27] | ✓ | ✓ | ✗ | VTM 4.0 | 51.2% | 1.62%
Li et al. [17] | ✗ | ✗ | ✓ | VTM 7.0 | 45.8% | 1.32%
Zhao et al. [28] | ✓ | ✗ | ✓ | VTM 7.0 | 39.4% | 0.87%

####  II-B3 VVC complexity reduction techniques

Even-thought VVC was recently standardized, several techniques have been
already proposed to tackle the problem of encoder complexity. Indeed, the
extension of the partitioning process with QT, BT and TT splits considerably
increases the encoding computational time. Predicting a split at each CU
becomes a real challenge due to the number of partition possibilities that
have increased significantly compared to HEVC. This situation raises the need
for lightweight partitioning process that decreases the encoder complexity
while preserving its coding efficiency for live applications. Fu et al. [25]
proposed a block partitioning algorithm through a Bayesian decision. This
technique explores information of previously tested BT H to skip vertical
splits. The TT H split can also be early skip relying on the BT information
and specifically the difference between the RD-cost of BT splits. This
technique reaches 44.8% of computational complexity reduction for 1.02% BD-BR
increase. Lei et al. [29] proposed a two-step look-ahead prediction method for
the intra prediction mode and partitioning process. This solution computes the
rate-distortion cost of only 7 intra modes out of 67 and if a CU has multiple
partitions, the RD-cost of partitioned CU are computed from the parent CU.
Moreover, this solution approximates the RD-costs of different partition
directions in order to skip unnecessary directions. Intra mode technique
combined with partitioning prediction technique allows a computational
complexity reduction of 45.8% for 1.03% BD-BR increase. Amestoy et al. [16]
proposed a cascade framework through random forest classifiers to determine
the probability of each split. In order to improve the accuracy of their
classifiers, the impact of each feature is evaluated such as Quantization
Parameter (QP), variance and mean of the block gradients. Furthermore, the
thresholds applied to the different classifiers are optimized. A risk interval
was proposed to limit the RD-cost increase by computing both splits of the
classifier output when the probability falls in this risk interval. In RA
configuration, this solution enables from 30.1% to 61.5% of complexity
reduction for respectively 0.61% to 2.22% BD-BR increase depending on the risk
interval configuration. Another cascade framework was proposed by Yang et al.
[26] with one binary classifier for each split mode. The authors used three
categories of features including global texture information, local texture
information and context information as input of their classifiers. A fast
intra mode decision using one dimensional gradient descent search is combined
with the CTU structure decision. This fast partitioning solution achieves 52%
of complexity reduction for 1.59% BD-BR increase. The intra mode decision
technique enhances the complexity reduction to 62.5% for 1.93% BD-BR loss.
Chen et al. [27] also used a supervised learning method. Instead of a cascade
framework, they designed six SVM models depending on the CU sizes which are
trained to skipped vertical and horizontal splits. SVM features are derived
from entropy, texture contrast and Haar wavelet of the current CU. This
solution reaches 51.2% of computational complexity reduction for 1.62% BD-BR
increase. Li et al. [17] proposed a deep learning approach to predict the CTU
partition with a binary or multi classification at each CU depth. To train the
CNN, they designed an adaptive loss function that defines penalty weights
based on split proportion that penalizes high difference between the RD-cost
for the split predicted and the minimum RD-cost of the parent CU. Based on the
prediction accuracy of the CU size, an adaptive threshold is compared to the
output of the CNN. This technique enables to reduce the complexity by 45.8%
for 1.32% BD-BR increase. Another CNN model is proposed by Zhao et al. in
[28]. First, the standard deviation of CU pixels is compared to an adaptive
threshold based on QP and CU depth in order to classify a block into complex
or homogeneous CU. The CU defined as homogeneous are no more split. Second,
for complex CU, a CNN is trained to predict whether the current CU must be
early terminated or not. This solution achieves 39.4% of computational
complexity reduction for 0.87% BD-BR increase.

Table I summarizes the features and performance of the aforementioned VVC
complexity reduction techniques. It can be noticed that different techniques
rely on artificial neural network especially CNN. Those techniques are showing
outstanding performance compared to other state-of-the-art techniques.

##  III Proposed two-stage VVC partition prediction solution

As described in Section I, VVC introduces BT and TT splits at the cost of a
high increase in computational complexity. This recursive partitioning process
computes the rate-distortion cost for a set of coding tools for each CU. The
proposed partitioning prediction technique is composed of a CNN for spatial
features extraction followed by a set of multi-class classifiers based on DTs
to predict the appropriate partitioning decision at different depths of the
partitioning tree. Fig. 2 illustrates the flow diagram of the proposed
partitioning prediction solution.

Figure 2: Workflow diagram of the proposed block partitioning scheme for VVC
AI coding. The input luminance block is first processed by a CNN to predict
$\mathbf{\tilde{p}}$, a vector of $N_{p}$ probabilities describing all edges
at each $4\times 4$ sub-block. The vector $\mathbf{\tilde{p}}$ is then
processed by a decision tree LightGBM to predict probabilities of the six
partitioning options through the vector $\mathbf{\tilde{c}}$. The top-N splits
of the highest probabilities are tested by the RD process of the encoder to
select the optimal split in terms of RD-cost.

###  III-A Overall presentation

Figure 3: Correspondence between the CNN output vector and a $64\times 64$ CU
partition. Figure 4: The CNN architecture with convolution layers in orange
and yellow, max-pooling layers in red and fully connected layer in purple.

Our method is a top-down solution that early terminates unlikely splits, i.e.
it follows the hierarchical process of the VVC encoder and skips split that
have a low probability to belong to the optimal partitioning. Our complexity
reduction method is composed of two components including spatial features
extraction and DT classifiers. The features extraction block consists of a CNN
that processes an input luminance block $\mathbf{B}$ to predict a vector of
probabilities $\mathbf{\tilde{p}}$ of splits at the $4\times 4$ block edges:

$\mathbf{\tilde{p}}=f_{\theta}(\mathbf{B}).$ (1)

where $f_{\theta}$ is a parametric function of the CNN with trainable
parameters $\theta$ and $\mathbf{B}$ is the input block of size $68\times 68$.

The block $\mathbf{B}$ consists of the current CU of size $64\times 64$ padded
with four rows and four columns on the top and left of the block resulting in
a block size of $68\times 68$. The left and top neighbor pixels are used as
reference samples in the intra prediction through the Mutiple Reference Line
(MRL) intra prediction [30]. Indeed, their pixels are used to derive the intra
mode of the current block. Therefore, it is important to include these samples
in the features extraction stage. The CNN predicts for each $N_{B}\times
N_{B}$ CU a vector of $N_{p}$ probabilities of a split at each $4\times 4$
edge of the block. The length $N_{p}$ of the predicted probabilities vector
$\mathbf{\tilde{p}}$ is computed as follows:

$N_{p}=\frac{N_{B}}{2}\left(\frac{N_{B}}{4}-1\right).$ (2)

In the case of CU size of $64\times 64$, $N_{p}$ is the length of the vector
$\mathbf{\tilde{p}}$ which is equal to 480. Fig. 3 presents the connections
between the probability vector components and the 480 $4\times 4$ edges of an
input CU. As highlighted in this figure, the first $\mathbf{p}_{1}$ and the
third $\mathbf{p}_{3}$ components of the vector correspond to the bottom
horizontal edges of the first and second $4\times 4$ blocks, respectively. For
a good partitioning prediction, these two components must have a value
(probability) close to 1 as a TT split is performed to split the sub-block.
The last component of the vector $\mathbf{p}_{N_{p}}$ has a value
(probability) close to 0 since no split is performed at this last vertical
edge of the CU as illustrated in Fig. 3.

The classifiers are then fed with the probabilities vector
$\mathbf{\tilde{p}}$ derived from the CNN to predict the split decision to
perform at each tree depth

$\mathbf{\tilde{c}}=g_{\omega_{i}}(\mathbf{\tilde{p}}),\;\;\forall
i\in\\{1,\dots,M\\},$ (3)

where $g_{\omega_{i}}$ is a parametric function of a classifier $i$,
${\omega_{i}}$ is its trainable parameters and $M$ is the number of considered
classifiers.

A separate multi-class classifier based on DT model is applied for each CU
size. The classifier takes as input the probability vector
$\mathbf{\tilde{p}}$ and predict a vector $\mathbf{\tilde{c}}$ of six
probabilities that correspond to the six possible splits performed by the VVC
encoder at each tree depth. This approach results in $M$ separate DT models
that are trained separately to enhance the prediction performance and enable
better convergence of the model with reduced number of trainable parameters.
Once the split probabilities are derived for the CU, a selection of the
highest probabilities is made based on the selected configuration. The
configuration specifies the $N$ value which defines the number of tested
splits by the encoder. Thus, the encoder performs only the $N$ first splits
corresponding to the highest probabilities (Top-N) predicted by the DT model.
The remaining splits with lower probabilities than the top-N candidates are
skipped by the encoder to reduce the encoding computational complexity. The
proposed spatial features extraction CNN model and the DT classifiers are
described in more detail in the next two sections, respectively.

###  III-B Spatial features extraction CNN model

Fig. 4 presents the adopted CNN architecture which is inspired by the ResNet
network [31]. The orange layers represent convolution layers with $3\times 3$
kernel (Conv $3\times 3$), whereas the yellow layers denote convolutions with
$1\times 1$ kernel (Conv $1\times 1$) that transform the input feature map
matrix to match the dimension of next layer which are then summed up (green
plus). The red layers correspond to the max pooling (Max Pool) that subsample
the input features map with a window of $2\times 2$ by selecting the maximum
over four values. The last layer in purple is a fully connected layer (Dense)
that predicts the 480 components vector. The sigmoid activation function is
used to predict the output values within the interval $[0,1]$. All these
layers result in a network with 226,088 trainable parameters. The input
consists of a $68\times 68$ luminance pixels of the CU currently processed
plus the QP value that highly influences the final partition. The QP is
provided as an external input to the last fully connected layer. The QP
parameter is crucial to save the memory bandwidth as it leads to only one
model shared for all QP values instead of adopting one model by QP value.
Therefore, our model can be efficiently used with a rate control mechanism
that adapts the QP value to the target bandwidth. The output is a 480
components vector that represents the fine-grain partitions ($4\times 4$) of
the $64\times 64$ CU. This solution has the advantage of predicting the whole
CU spatial features in one shot, which is very convenient to reduce the
complexity overhead and latency introduced by this step. Moreover, the
architecture of the network is less deep than state-of-the-art CNN
architectures [32], [33] and thus will require less time to predict the output
vector.

###  III-C Multi-class classifiers based on DT models

The decision approach adopted in our previous work [18] relied only on the
probability at the spatial location of a specific split. For instance, the BT
H split takes into account only the probabilities of the horizontal edges in
the middle of the CU. By leveraging only a restricted location of the CU, an
important information is omitted to determine the final split decision. In
order to take advantage of all probabilities inside the current CU, the DT
model is adopted to process the vector of probabilities predicted by the CNN
model. This vector of probabilities can be considered as spatial features
relevant for the block partitioning process. Therefore, the CNN inference is
carried-out once for each CU of size $64\times 64$ to predict the
corresponding probability vector $\mathbf{p}$, and then a specific DT model
processes this vector at each level of the partitioning tree to derive a set
of $N$ more likely splits to explore by the encoder. To predict split
probabilities at various CU sizes, multiple models are considered covering all
possible sizes of the rectangular sub-blocks from $64\times 64$ to $4\times 4$
excluded. As illustrated in Table II, sixteen CU sizes can be further split in
six to two different partitions including the no split option. The DT model is
fed with the probability vector $\mathbf{\tilde{p}}$ and the QP value. The
probability vector is then cropped into a sub-vector that includes only the
probabilities of the sub-block edges. The DT model performs a multi-class
classification by predicting a probability vector $\mathbf{\tilde{c}}$ of six
components corresponding to the probabilities of the six possible splits.
Therefore, the probabilities of non possible splits are set to zero during the
training process.

Several machine learning models have been investigated to solve this multi-
class classification problem including DT, random forest, SVM with different
kernels and Light Gradient Boosting Machine (LGBM) model [34]. This latter has
been retained for its good classification performance associated with low
complexity at both training and inference stages.

TABLE II: Possible splits according to the CU size Height Width | 64 | 32 | 16 | 8 | 4
---|---|---|---|---|---
64 | QT | -
32 | - | All |  BT, TT |  BT TT H |  BT H TT H
16 |  BT, TT | All
8 |  BT, TT V | BT |  BT H
4 |  BT V, TT V |  BT V | -

##  IV Proposed dataset for training

In this section, first, our dataset is presented through its representations.
Second, the process to balance the dataset is detailed for both soft and hard
representations.

###  IV-A Dataset for the learning process

TABLE III: Breakdown of our dataset by resolution. Resolution | 240p | 480p | 720p | 1080p | 4K | 8K | Total
---|---|---|---|---|---|---|---
Nb images | 500 | 500 | 579 | 2557 | 654 | 418 | 5208

The lack of public dataset providing encoded blocks with the VTM and their
corresponding partitions drives us to construct our training dataset to
optimize the proposed models weights. As our work focuses on AI configuration,
temporal relationship between frames is not considered. Therefore, five public
image datasets were selected including Div2k [35], 4K images [36], jpeg-ai
[37], HDR google [38] and flickr2k [39]. The resulting dataset presents a high
diversity of still image contents. However, since these datasets include more
images in high resolution (Full HD and 4K resolutions), a set of high
resolution images downscaled with a bilinear filter are added to the dataset.
This results in a dataset with around 5208 images at different resolutions as
detailed in Table III which gives the number of images per resolution. The
images of the same resolution are then concatenated to build a pseudo-video
sequence. This latter is encoded with the VTM encoder in AI configuration at
different QP values, QPs $\in\\{22,\,27,\,32,\,37\\}$.

It should be noticed that the VTM encoder includes multiple speed-up
techniques for the partitioning process to overcome the complexity brought by
the VVC partitioning process [6]. To achieve a high coding efficiency by
testing more partitioning configurations, these speedup techniques have been
disabled to build our dataset. Compared to the VTM anchor, disabling these
speed-up techniques enhances the coding efficiency with more accurate
partitioning configurations. Nevertheless, a higher encoding time is needed to
create the ground truth but only one encoding pass is required, so, increasing
the encoding time is not critical at this stage. The VTM in AI configuration
relies on the dual tree tool that performs separate partitioning for luminance
and chrominance components. The partitioning information of both components is
recorded while only the prediction of luminance partitioning is considered in
this paper since it takes the most part of the encoding complexity with more
than 85% of the total encoding time [8].

Figure 5: Representation of our dataset. (a) is a luminance $68\times 68$
input block $\mathbf{B}$. (b) is the optimal partitioning of the block
represented by a tree and transformed to the soft representation, i.e. a 480
elements vector $\mathbf{p}$. (c) is the hard representation, $K$ vectors
$\mathbf{c}$ of 6 probabilities, that define the optimal split for each of the
$K$ blocks in the tree. $K$ is the decision tree depth.

The optimal partitions computed by the VTM encoder is first saved as a tree.
Therefore, in order to integrate the dataset in our proposed method, two data
representations are defined as soft and hard representations as illustrated in
Fig. 5. Fig. 5-(a) shows a block $\mathbf{B}$ processed by the VTM encoder
which is a $64\times 64$ luminance block plus 4 rows and columns on top and
left of the block. These supplementary pixels are required for the MRL intra
prediction tool. Fig. 5-(b) illustrates the partition tree of the this block
which is converted to a 480 components vector. This soft representation of the
tree depicts the $64\times 64$ block luminance partition in $4\times 4$ blocks
in a single vector $\mathbf{p}$. The hard representation of our dataset is a
succession of $K$ vectors that defines all splits at each depth. Fig. 5-(c)
presents one of those vector $\mathbf{c}$ which defines the optimal split for
a specific CU size. The vector size is set to six as the maximum number of
splits defined by VVC. For instance, the $64\times 64$ CU size has only two
possible splits with QT and no split and thus the rest of four vector
components are set to zero. Instead, for a CU size of $32\times 32$, all
splits are available, so the vector size is 6 with QT, the two BTs, the two
TTs and no split.

###  IV-B Dataset processing

Figure 6: Breakdown of our dataset by partition classes. (a) Unbalanced
dataset. (b) Balanced dataset.

Our dataset includes more than 26 million instances of $64\times 64$ block
partition excluding any Common Test Conditions (CTC) sequence to insure a fair
comparison of our method against state-of-the-art techniques. In order to
analyze the dataset disparity, a first selection of 2 million instances are
picked randomly. Furthermore, to address the data heterogeneity issue of the
dataset, several classes are defined with 8 levels of depth partition from no
partition to deep partition. Fig. 6 gives the number of instances in the
dataset at each of these 8 depth levels which are defined based on the number
of edges activated in the $64\times 64$ CUs. Fig. 6-(a) represents the class
repetitions through 2 million instances before the dataset balancing. It can
be noticed that the class 0 without any split contains more than a third of
the 2 million $64\times 64$ CUs instances, while the last two classes which
illustrate deep partition are under-represented and must therefore be
increased. Fig. 6-(b) illustrates the depth distribution of block partitioning
over the eight classes after the dataset balancing. 1,200,000 instances
($64\times 64$ block) were selected at each QP value with a homogeneous
representation over the eight classes. The two last classes are slightly
under-represented as highly deep partitions are derived by the encoder only
for extremely complex blocks encoded at low QP values.

The hard representation is composed of sub-datasets separated by the different
CU sizes. These sub-datasets are also balanced to enhance their
representation. Indeed, we balanced individually each sub-dataset over the
available splits and the QPs. For instance, the $4\times 16$ CU size dataset
is balanced between the proportion of BT H, TT H and no split but also among
the 4 QPs.

##  V Training process and experimental setup

###  V-A CNN model

The CNN is trained from scratch with the proposed dataset described in Section
IV relying on the Keras framework [40] running on top of Tensorflow module
[41]. The weights $\theta$ of the CNN are updated at each batch iteration with
the ADAM stochastic gradient descent optimizer [42]. The loss function is
defined to optimize those weights by minimizing the mean squared error between
the predicted probability vector $\tilde{\mathbf{p}}$ and the corresponding
ground truth vector $\mathbf{p}$ as follows:

$\mathcal{L}_{cnn}=||\mathbf{p}-\tilde{\mathbf{p}}||^{2}_{2}.$ (4)

The batch size is set to 128 instances ($64\times 64$ CUs) and the learning
rate is equal to $10^{-3}$.

A hundred epochs are processed with a random shuffle of the dataset at each
epoch. The CNN training was carried out on a RTX 2080 Ti Graphics Processing
Unit (GPU).

###  V-B DT LGBM model

The DT models are implemented under the LGBM framework [34] version 2.3.1.
This latter is a gradient boosting framework based on decision tree developed
by Microsoft. LGBM has many advantages such as its low memory usage, the
capacity of handling large-scale data and the low inference computational
time. This last advantage is essential for our problem as the inference is
carried-out at each CU level.

LGBM is a DT method that sums the predictions of all the trees to get a richer
interpretation of the problem. The trees are optimized in a stage-wise way by
adding or updating one tree sequentially based on the error of the whole
ensemble learned so far. For DT classification, the loss function is defined
as follows

$\mathcal{L}_{dt}=-\sum_{i=1}^{6}\mathbf{c}_{i}\log{\tilde{\mathbf{c}}_{i}},$
(5)

where $c_{i}$ is the vector of ground truth split probabilities and
$\tilde{c}_{i}$ is the vector of split probabilities predicted by the model.

###  V-C Evaluation procedure and implementation details

All experiments are conducted with the VVC Test Model (VTM)version 10.2 in AI
coding configuration. We consider test video sequences defined in the VVC
Common Test Conditions (CTC) [43]. The CTC video sequences are separated in
seven classes as follows: A1 ($3840\times 2160$), A2 ($3840\times 2160$), B
($1920\times 1080$), C ($832\times 480$), D ($416\times 240$), E ($1280\times
720$), and F ($832\times 480$ to $1920\times 1080$). These video sequences are
encoded at four QP values: 22, 27, 32 and 37.

The proposed solution is assessed in terms of both coding efficiency and
computational complexity. The coding efficiency is measured with the BD-BR
metric [44] that measures the bitrate loss over four QPs in percentage with
respect to the anchor (ie. VTM 10.2) for the same Peak Signal-to-Noise Ratio
(Psnr) objective quality. The computational complexity reduction with respect
to the anchor is assessed by computing the $\Delta$ Encoding Time ($\Delta$ET)
as follows:

$\Delta ET=\frac{1}{4}\sum_{\lx@glossaries@gls@link{main}{qp}{\leavevmode
QP}_{i}\in\\{22,27,32,37\\}}\frac{T_{R}(\lx@glossaries@gls@link{main}{qp}{\leavevmode
QP}_{i})-T_{C}(\lx@glossaries@gls@link{main}{qp}{\leavevmode
QP}_{i})}{T_{R}(\lx@glossaries@gls@link{main}{qp}{\leavevmode QP}_{i})},$ (6)

where $T_{R}$ is the reference encoding time of the VTM anchor and $T_{C}$ is
the encoding time of the VTM with the proposed complexity reduction method.

Our complexity reduction technique has been integrated in the VTM 10.2 encoder
which is developed in C++ programming language. The CNN is built and trained
with Python under the Keras framework and then the model is converted to C++
code with the frugally deep framework [45]. The DT models are also trained in
python and then converted to C++ with the LGBM framework [34].

All encoding operations were carried out sequentially on an Intel Xeon E5-2603
v4 processor running at 1.70 GHz under Ubuntu 16.04.5 operating system (OS).

##  VI Experimental results

In this section the performance of the proposed method is assessed. The CNN
performance is analyzed through its accuracy and Receiver Operating
Characteristic (ROC) curves. The multi-class DT classifiers accuracy is
presented through its top-N accuracy. The complexity reduction proposed method
is then assessed in terms of both computational complexity reduction and BD-BR
increase with respect to the VTM. Multiple configurations of our method are
explored depending on the tested top-N DT LGBM output splits. There are
several existing techniques that have investigated the complexity reduction
induced by the new MTT partitioning in VVC. The proposed solution is compared
with four best performing state-of-the-art techniques including solutions
proposed by Fu et al. [25], Chen et al. [27], Yang et al. [26] and Li et al.
[17]. Finally, the inference overheads of both CNN and DT models are assessed.

###  VI-A CNN performance

Figure 7: Decreasing loss (in X) and increasing accuracy (in Y) as a function
of epoch for the training and test set.

Fig. 7 shows the loss and accuracy of the CNN model versus the training epochs
on both training and test datasets. The blue and orange decreasing curves
correspond to the losses computed by Eq. (4) over hundred of epochs of the
training. The green and red increasing curves represent the binary accuracy
computed after a shrinkage with a threshold of 0.5. It means that if a
predicted value is higher or lower than 0.5, the value is considered to be 1
or 0, respectively. This resulting value is compared to the ground truth and
the accuracy is computed over all components of the vector of probabilities.
The two curves in blue and green are from the training part and those in
orange and red are from the testing part. The goal of the training is to
update the model weights to minimize the loss at each iteration. We can notice
that the loss curves decrease from 0.105 to 0.094 over 100 epochs for both
training or test datasets. The test curve follows the training one which means
that the model generalizes well on the test set. The model accuracy reaches
more than 86% of good prediction, i.e. 86% of the estimated probabilities with
a threshold of 0.5 are equal to the ground truth.

Figure 8: Several CNN ROCs for different splits and sizes on the CTC video
sequences.

The CNN prediction performance is also analyzed under VTM with the ROC curves.
The ROC curves represent the true positive rate versus the false positive
rate. These curves select a target split to analyze versus all the other
possible splits. The split probabilities required to plot these ROCs are
determined by averaging all probabilities which are at the exact spatial
position of the split. Fig. 8 presents the ROC curves of QT, BT H and BT V
splits at different CU sizes computed on the CTC sequences. The QT ROC curves
show that the average probability is able to reach 0.8 of true positive for
approximately 0.1 of false positive rate, for both $64\times 64$ and $32\times
32$ CU sizes. Instead, the BT ROC curves are closer to the random guess curve
which is the diagonal one in blue. Indeed, the CNN pays more attention to
those probabilities. Moreover, the high CU sizes determine more easily the
split choice as it concerns more pixels. The ROC area under curve value are
given as a single score to compare the results among the graphs. As shown by
the curves, the ROC area under curve confirms the results by reaching scores
higher than 0.9 for the QT and less than 0.7 for the BT splits.

Figure 9: Example illustration of ground truth partitions and the
corresponding CNN predictions for the sequence MarketPlace with QPs 22, 27, 32
and 37.

Visual illustrations of partitions of a $64\times 64$ CU from ground truth and
predicted by the proposed CNN are given on the first and second rows of Fig.
9, respectively. On the top row, the optimal partitions derived by the VTM
anchor considered here as the ground truth. On the bottom row, the partitions
predicted by the CNN are displayed with color codes based on their
probabilities. The color code varies from red to blue with a probability
ranging between 0.3 and 1 and gray color for probabilities below 0.3. The
partitions for QP 37 is shallow with a maximum of three depths and two CUs of
size $32\times 32$. Its CNN prediction is relevant with each edge defined as a
split with a probability higher than 0.9. For the other edges that are not
defined as a split, the probability are lower than 0.3 except six edges
predicted with probabilities between 0.3 and 0.4. Compared to the QP 37
partition, the QP 27 configuration is partitioned deeper and is harder to
predict efficiently. The figure shows that each edge determined as a split
have a probability higher to 0.3 except the TT split and some CUs are
predicted deeper.

It should be noticed that the CNN output is not directly used in the VTM. The
CNN output is considered as spatial features and it is used as an input for
the DT LGBM models. The DT LGBM will benefit from all the probabilities that
have an impact on the CU partition.

###  VI-B DT LGBM performance

The second part of the proposed solution includes DT LGBM models that take
advantage of all spatial features predicted by the CNN to derive split
probabilities. As presented in Section IV, multiple models are trained to
handle the different CU sizes. The input element ranges start from one
probability plus the QP for $4\times 8$ or $8\times 4$ CU sizes to 480
probabilities plus the QP for $64\times 64$ CU size. The output is a vector of
six classes with QT, the two BTs, the two TTs and no split. For CUs with less
splits available due to VTM restrictions, a mask is applied on the predicted
vector to restrict the unsuited splits.

TABLE IV: Performance of every DT LGBM models with their defined size and number of output through top-1, top-2 and top-3 accuracy on the test set. Width | Height | Number of classes | Top-1 accuracy (%) | Top-2 accuracy (%) | Top-3 accuracy (%)
---|---|---|---|---|---
64 | 64 | 2 | 91.69 | - | -
32 | 32 | 6 | 59.94 | 78.38 | 88.87
32 | 16 | 5 | 58.50 | 77.96 | 89.85
16 | 32 | 5 | 56.55 | 77.48 | 89.24
32 | 8 | 4 | 54.80 | 80.22 | 94.11
8 | 32 | 4 | 54.91 | 80.45 | 94.40
32 | 4 | 3 | 66.64 | 87.80 | -
4 | 32 | 3 | 68.80 | 87.38 | -
16 | 16 | 6 | 50.95 | 71.27 | 84.60
16 | 8 | 4 | 62.89 | 82.74 | 94.05
8 | 16 | 4 | 62.36 | 83.25 | 94.39
16 | 4 | 3 | 68.96 | 90.12 | -
4 | 16 | 3 | 68.95 | 88.54 | -
8 | 8 | 3 | 81.46 | 93.05 | -
8 | 4 | 2 | 82.16 | - | -
4 | 8 | 2 | 86.26 | - | -
Average | 2 | 86.70 | - | -
3 | 70.96 | 89.38 | -
4 | 58.74 | 81.67 | 94.24
5 | 57.53 | 77.72 | 89.55
6 | 55.45 | 74.83 | 86.74
- | 67.24 | 82.97 | 91.19

Table IV presents the accuracy of the DT LGBM models on CTC test set. Three
values are reported to analyze the DT LGBM results based on the top-N accuracy
with $N\in\\{1,\,2,\,3\\}$. top-N accuracy is a metric that measures how often
the correct class falls in the top-N highest predicted probabilities. top-1
accuracy reaches in average 67.24% of correct prediction. Based on the number
of the output classes the prediction is different. It decreases in average
from 86.7% to 55.45% for 2 classes and 6 classes, respectively. The highest
top-1 accuracy is achieved with the $64\times 64$ CU binary classification
between QT and no split with 91.69%. All DT LGBM models have more than 50%
top-1 accuracy even with multi classification. The top-2 accuracy is presented
for models with at least three classes, which reach in average 82.97%. The
lowest accuracy is 71.27% obtained with the lowest CU size available for six
classes decision, i.e. $16\times 16$. Finally, top-3 accuracy achieves 91.19%
accuracy in average over the model with at least four classes. By skipping
half of the available splits, the top-3 configuration achieves 86.74% accuracy
for 6 classes. This enables to reduce the complexity by a factor of two with a
high confidence on the prediction. Theses results exhibit that the accuracy of
DT models with 3 classes depends on the available split. In fact, higher
accuracy is reached for the $8\times 8$ CU size model in top-1 and top-2 by at
least +12% and +3% respectively compared to other models with 3 classes. In
addition to the no split mode, two splits are in competition: either BT and TT
in the same direction or BT horizontal and vertical. As shown by the results,
the direction of a split is easier to predict than the difference between BT
and TT in the same direction.

###  VI-C Complexity reduction performance under the VTM

The two-stage proposed model is integrated in the VTM 10.2 AI encoder. For
fair comparison, the reference used to compute the BD-BR loss and the
complexity reduction is the VTM encoder including multiple native speed-up
techniques [6] for the partitioning process. These speed-up techniques reduce
significantly the execution time with a slight BD-BR degradation compared to
an exhaustive RDO process. Thus, these experiments exhibit the gain provided
by our approach compared to the common configuration of the VTM encoder.

To compare our method, the best performing state-of-the-art techniques in
terms of complexity reduction and BD-BR loss metric are selected. These state-
of-the-art techniques are not performed under the same VTM version, however,
the CTU partitioning tools have not been changed during the standardization.

TABLE V:  $\Delta$ET and BD-BR performance of the proposed solution in
comparison with state-of-the-art techniques in AI coding configuration.

Class Sequence Fu et al. [25], VTM 1.0 Chen et al. [27], VTM 4.0 Li et al.
[17], VTM 7.0 Ours top-3, VTM 10.2 Ours top-2, VTM 10.2 BD-BR $\Delta$ET BD-BR
$\Delta$ET BD-BR $\Delta$ET BD-BR $\Delta$ET BD-BR $\Delta$ET Class A1 Tango2
1.47% 54% 1.38% 48.7% 1.52% 40.8% 0.54% 46.7% 1.51% 66.4% FoodMarket4 1.01%
53% 0.84% 30.3% 1.26% 42.2% 0.53% 47.5% 1.45% 66.2% Campfire 1.06% 46% 1.29%
49.1% 2.02% 48.7% 0.74% 48.3% 2.01% 67% Average 1.18% 51% 1.17% 42.7% 1.6%
43.9% 0.6% 47.5% 1.66% 66.5% Class A2 CatRobot1 1.58% 43% 1.99% 50.4% 2.16%
45.4% 0.99% 46.1% 2.6% 66.9% DaylightRoad2 1.49% 49% 2% 54.1% 1.16% 49.4%
1.02% 50.6% 2.55% 73.5% ParkRunning3 0.58% 51% 0.8% 40.6% 1.15% 41.7% 0.38%
42.6% 0.95% 59.5% Average 1.22% 47.7% 1.6% 48.4% 1.49% 45.5% 0.8% 46.4% 2.03%
66.6% Class B MarketPlace 0.60% 52% - - 0.8% 46.6% 0.53% 55.6% 1.36% 75.8%
RitualDance 1.08% 45% - - 1.07% 44.9% 0.87% 51.7% 2.5% 73% Cactus 0.92% 44%
1.73% 49.8% 1.12% 49.3% 0.89% 49.4% 2.65% 72.4% BasketballDrive 0.89% 49%
1.54% 50.1% 1.64% 52% 0.92% 51.6% 2.57% 73% BQTerrace 0.78% 48% 1.4% 56% 1.11%
45.6% 1.06% 46.5% 2.82% 72% Average 0.85% 47.6% 1.56% 52% 1.15% 47.7% 0.85%
51% 2.38% 73.2% Class C RaceHorses 0.77% 42% 1.35% 50.6% 0.96% 46.5% 0.66%
46.2% 2.08% 74.5% BQMall 0.94% 39% 2.12% 58.9% 1.17% 49.8% 1.01% 47% 3.2%
75.8% PartyScene 0.53% 42% 1.01% 51% 0.61% 45.2% 0.58% 44.1% 2.21% 74.3%
BasketballDrill 1.91% 46% 2.05% 54.8% 1.63% 39.3% 1.6% 45.4% 4.75% 73% Average
1.04% 42.3% 1.63% 53.8% 1.09% 45.2% 0.96% 45.7% 3.06% 74.4% Class D RaceHorses
0.91% 39% 1.28% 54.7% 1.2% 41.6% 0.67% 43.6% 2.46% 65.6% BQSquare 0.51% 44%
0.75% 52.8% 0.74% 44.5% 0.61% 44.4% 2.49% 69.7% BlowingBubbles 0.61% 37% 1.4%
54.9% 0.92% 41.6% 0.64% 40.5% 2.48% 64.9% BasketballPass 0.75% 43% 1.77% 53.1%
1.41% 44.5% 0.9% 44.5% 2.94% 65.9% Average 0.7% 40.8% 1.3% 53.9% 1.07% 43.1%
0.7% 43.3% 2.59% 66.5% Class E FourPeople 1.26% 41% 2.71% 56.3% 1.33% 49.9%
1.2% 44.7% 3.64% 71% Johnny 1.44% 39% 2.77% 55.8% 2.33% 48.2% 1.42% 42.6%
3.97% 67.4% KristenAndSara 1.27% 40% 2.17% 52.8% 1.76% 50.5% 1.06% 44.4% 3.47%
68.5% Average 1.32% 40% 2.55% 55% 1.81% 49.5% 1.23% 43.9% 3.69% 69% Average
1.02% 44.8% 1.62% 51.2% 1.32% 45.8% 0.86% 46.6% 2.57% 69.8% Class F
ArenaOfValor - - - - - - 1.08% 22% 3.38% 49.7% BasketballDrillText - - 2.09%
56.3% - - 1.59% 22.5% 4.69% 52.5% SlideEditing - - 0.52% 45.4% - - 1.21% 27.3%
4.67% 58.8% SlideShow - - 2.11% 45.8% - - 1.5% 26% 4.85% 56.2% Average - -
1.57% 49.2% - - 1.34% 24.5% 4.4% 54.3%

Table V presents the BD-BR and complexity reduction performance of our method
compared to the state-of-the-art techniques [25], [27] and [17]. In this
table, two configurations are presented based on the top-2 and top-3
configurations. The results are illustrated for the CTC sequences from class
A1 to class F. The average is presented for each class independently and for
all the sequences from class A1 to class E. Class F is not taken into account
for the average as it includes specific sequences such as screen content.

In average, through all the sequences our top-3 configuration reaches 0.86%
BD-BR increase for a complexity reduction of 46.6%. Compared to Fu et al. [25]
and Li et al. [17], our solution achieves better performance in terms of both
BD-BR and complexity reduction. Chen et al. [27] solution reduces the
complexity by 4.6% at the expense of significant increase of 0.76% in BD-BR
compared to our top-3 configuration. This low gain in the complexity reduction
is not relevant compared to the increase in BD-BR which is almost doubled. The
second configuration with top-2 achieves in average 2.57% BD-BR increase with
69.8% of complexity reduction.

High video resolutions are the main interest in VVC development. In fact,
tackling high resolution complexity is particularly important as the encoding
time is proportional to the sequence resolution. Both A and B classes
represent high resolution sequences with 4K and full HD, respectively. Our
top-3 and top-2 configurations are able to reach 47% and 66.6% complexity
reductions for 0.7% and 1.85% BD-BR losses on class A sequences, respectively.
In both BD-BR and complexity reduction metrics our method is better than Chen
et al. [27] and Li et al. [17] techniques. Compared to these two techniques,
our top-3 configuration solution achieves in average enhancements of 0.69% and
0.85% in BD-BR and computational complexity reductions of 1.5% and 2.3%,
respectively. Fu et al. [25] solution enhances the complexity reduction by
2.4% at the expense of a high BD-BR increase of 0.5% compared to our top-3
configuration. Concerning the B class videos, our top-3 configuration is able
to halve the complexity reduction with 51% of complexity reduction for less
than one percent of BD-BR increase i.e. 0.85%. The closest to our method is Fu
et al. [27] technique achieving similar BD-BR scores but at lower complexity
reduction by 3.4%. Our top-2 configuration enables 73.2% complexity reduction
for 2.38% BD-BR increase. The highest performance in terms of both complexity
reduction and BD-BR increase are obtained for the MarketPlace sequence.
Indeed, the proposed method in top-3 and top-2 configurations reaches 55.6%
and 75.8% complexity reductions for 0.53% and 1.36% BD-BR increases,
respectively.

For lower resolution classes C to E, the top-3 configuration achieves in
average less than 1% BD-BR increase for a maximum of 47% complexity reduction.
Compared to Fu et al. [25], our method has lower BD-BR increase for higher
complexity reduction through all lower resolution classes. Li et al. [17] has
higher BD-BR increase for lower complexity reduction for class C and D
compared to our oop-3 configuration. For class E, Li et al. [17] solution
obtained 5.6% more complexity reduction but at the cost of 0.58% BD-BR
increase compared to our method. Chen et al. [27] almost doubled the BD-BR
loss with 1.76% for a complexity reduction increase of 9.9% compared to our
top-3 configuration through low resolution classes. In the case of the top-2
configuration, low resolutions have lower performance compared to high
resolutions. In fact, this approach on low resolution contents including
classes C, D and E reaches the complexity of high resolution contents (classes
A1, A2 and B) of 70.1% for higher BD-BR loss of 3.06% which is higher by
approximately 1% compared to the BD-BR loss of high resolutions contents
(2.09%). Low resolution contents result in deeper partitions, so the more the
complexity is reduced, the less space is available to skip splits. As the
global partition is composed of more split, the impact on BD-BR is more
significant at high complexity reductions.

The class F has specific sequences with screen content such as slides or
gaming content. Our method is not optimized for this type of contents, since
these contents have not been considered in the learning process. However, our
approach still achieves 24.5% complexity reduction for 1.34% BD-BR increase.
Chen et al. [27] are the only one to report results on class F with three out
of four sequences. In average, they got higher complexity reduction but for a
higher BD-BR increase. Adding screen content to the training dataset could be
a solution to overcome state-of-the-art techniques.

Figure 10: Complexity reduction versus BD-BR performance comparison between
the proposed method and state-of-the-art techniques on CTC classes except
class F (AI configuration). An interpolation cure over our fours
configurations is plotted in blue dot line

Fig. 10 shows the performance of our method in complexity reduction versus BD-
BR jointly with state-of-the-art techniques in a 2D plan on CTC classes except
class F. In addition to the configurations presented in the table, two new
specific configurations have been included. The selection of top-3 for the
multi-classification with 6 possibilities and top-4 for the other DT LGBM
models is defined as $C_{1}$. The top-3 configuration is defined as $C_{2}$.
The top-3 for all DT LGBM models except the multi-classification with 6
possibilities for which top-2 is used in configuration $C_{3}$, and finally,
top-2 for all DT models is defined as $C_{4}$. These several configurations
reach different trade-offs of complexity reduction for each specific BD-BR
loss which allows us to draw and interpolation curve over these four
configurations. This interpolation help us to compare the results since the
rate-distortion-complexity trade-offs are not linear. It allows a comparison
at each point of complexity reduction or BD-BR increase of our method. As
explained through the previous table, the figure confirms that our solution
outperforms the best performing state-of-the-art techniques. The points
representing the other solutions are all below the interpolation curve of our
approach. At the same BD-BR loss, we achieve a complexity reduction of 6.5%,
12.5%, 10.1% and 12.1% compared to Fu et al. [25], Li et al. [17], Yang et al.
[26] and Chen et al. [27] techniques, respectively. For the same complexity
reduction, we obtain a BD-BR gain of 0.21%, 0.49%, 0.54% and 0.61% against Fu
et al. [25], Li et al. [17], Yang et al. [26] and Chen et al. [27] techniques,
respectively.

The solution proposed in [18] is also illustrated in this figure to show the
interest of our new proposal in terms of performance gain. Two configurations
of the previous solution were selected with decision thresholds: $\beta=30$
and $\beta=40$. Our $C_{3}$ and $C_{4}$ configurations are better than the
$\beta=30$ and $\beta=40$ solutions with a gain in complexity reduction of
approximately 10% for a similar BD-BR loss. Compared to $\beta=40$ which
reaches 58.8% complexity reduction, our solution $C_{3}$ affords a significant
BD-BR gain of 1.02%.

###  VI-D Complexity overhead

TABLE VI: Overheads of the CNN and DT LGBM (in %) for $C_{2}$ configuration with respect to the execution time of the VTM anchor. | Class A1 | Class A2 | Class B | Class C | Class D | Class E | Class F | Average
---|---|---|---|---|---|---|---|---
CNN overhead | 2.7% | 1.2% | 1% | 0.6% | 0.5% | 1.4% | 1.2% | 1.2%
DT overhead | 2% | 1.7% | 1.7% | 1.6% | 1.6% | 1.8% | 1.6% | 1.7%
Total | 4.7% | 2.9% | 2.7% | 2.2% | 2.1% | 3.2% | 2.8% | 2.9%

In this section, the complexity overhead of the CNN and DT inference is
investigated under the VTM. Table VI presents the time spent in the CNN and in
the DT predictions for $C_{2}$ configuration in comparison with the VTM 10.2
anchor encoding time. These values are obtained by applying a ratio between
the CNN or DT time and the VTM reference encoding time. The execution time of
the CNN inference is in average lower than the execution time of the DT model.
Indeed, even if the CNN inference is higher, the DT infers at each CU size
unlike the CNN which is carried-out only once for each $64\times 64$ CU. The
execution time ratio of the CNN is higher in the Ultra High Definition (UHD)
classes especially the class A1. This can be a result of the early skip
methods integrated in the VTM that leads to shallow partition, i.e. less time
in the encoding process. Moreover, the results for the DT inference time is
homogeneous through all the CTC classes. In average, both execution times of
the CNN and DT are under 2% and taken together, they require less than 3% of
the encoding time. These results show that the prediction times are
negligible, especially since the CNN and DT models can be optimized,
accelerated or parallelized. Especially, the execution time of the CNN can be
significantly reduced by targeting a GPU or completely removed when
parallelizing the CNN inference with the RDO.

##  VII Conclusion

In this paper we have proposed a two stage CNN and DT method to reduce the
complexity of the VTM encoder in AI configuration. The CNN is designed to
predict a CU partition through a vector of probabilities based on the local
property of the block. This vector considered as spatial features is then
passed as input to the DT model that predicts the split probabilities at each
CU depth. The DT method integrated after the CNN inference benefits from all
the probabilities inside the CU instead of taking only the probabilities at
the spatial location of the split. Depending on the selected configuration, a
top-N probability selection is performed on the DT output to skip the unlikely
splits.

Our proposed method outperforms state-of-the-art techniques in terms of trade-
off between complexity reduction and coding loss. Concerning the top-3
configuration, our proposal assessed on the VVC CTC sequences enabled in
average 46.6% complexity reduction for a negligible BD-BR loss of 0.86%. The
top-2 configuration was able to reach a higher complexity reduction of 69.8%
for 2.57% BD-BR loss. These promising results motivated us to extend our
method to the RA configuration. This extension investigated as future work
will require to take advantage of the motion flow among adjacent frames.

## References

  * [1] Cisco,  “Cisco Visual Networking Index : Forecast and Trends, 2017-2022,”  Tech. Rep., 2019.
  * [2] H. O. Domínguez and K. R. Rao,  Versatile Video Coding Latest Advances in Video Coding Standards, pp. i–xxx,  2018\.
  * [3] D. García-Lucas, G. Cebrián-Márquez, and P. Cuenca,  “Rate-distortion/complexity analysis of HEVC, VVC and AV1 video codecs,”  Multimedia Tools and Applications, Aug. 2020.
  * [4] Fan Zhang, Angeliki V. Katsenou, Mariana Afonso, Goce Dimitrov, and David R. Bull,  “Comparing VVC, HEVC and AV1 using Objective and Subjective Assessments,”  arXiv:2003.10282 [eess], Mar. 2020,  arXiv: 2003.10282.
  * [5] Frank Bossen, Xiang Li, and Karsten Suehring,  “AHG report: Test model software development (AHG3),”  JVET-T0003, Oct. 2020.
  * [6] A. Wieckowski, J. Ma, H. Schwarz, D. Marpe, and T. Wiegand,  “Fast Partitioning Decision Strategies for The Upcoming Versatile Video Coding (VVC) Standard,”  in 2019 IEEE International Conference on Image Processing (ICIP), Sept. 2019, pp. 4130–4134.
  * [7] Edouard François, Michel Kerdranvat, Rémi Jullian, and Christophe Chevance,  “VVC PER-TOOL PERFORMANCE EVALUATION COMPARED TO HEVC,”  p. 14.
  * [8] Mario Saldanha, Gustavo Sanchez, Cesar Marcon, and Luciano Agostini,  “Complexity Analysis Of VVC Intra Coding,”  in 2020 IEEE International Conference on Image Processing (ICIP), Abu Dhabi, United Arab Emirates, Oct. 2020, pp. 3119–3123, IEEE.
  * [9] A. Tissier, A. Mercat, T. Amestoy, W. Hamidouche, J. Vanne, and D. Menard,  “Complexity Reduction Opportunities in the Future VVC Intra Encoder,”  in 2019 IEEE 21st International Workshop on Multimedia Signal Processing (MMSP), Kuala Lumpur, Malaysia, Sept. 2019, pp. 1–6, IEEE.
  * [10] G. Correa, P. A. Assuncao, L. V. Agostini, and L. A. da Silva Cruz,  “Fast HEVC Encoding Decisions Using Data Mining,”  IEEE Transactions on Circuits and Systems for Video Technology, vol. 25, no. 4, pp. 660–673, Apr. 2015.
  * [11] Tianyi Li, Mai Xu, Xin Deng, and Liquan Shen,  “Accelerate CTU Partition to Real Time for HEVC Encoding With Complexity Control,”  IEEE Transactions on Image Processing, vol. 29, pp. 7482–7496, 2020\.
  * [12] A. Mercat, F. Arrestier, M. Pelcat, W. Hamidouche, and D. Menard,  “Machine Learning Based Choice of Characteristics for the One-Shot Determination of the HEVC Intra Coding Tree,”  in 2018 Picture Coding Symposium (PCS), June 2018, pp. 263–267.
  * [13] Somdyuti Paul, Andrey Norkin, and Alan C. Bovik,  “Speeding up VP9 Intra Encoder with Hierarchical Deep Learning Based Partition Prediction,”  IEEE Transactions on Image Processing, vol. 29, pp. 8134–8148, 2020,  arXiv: 1906.06476.
  * [14] Mai Xu, Tianyi Li, Zulin Wang, Xin Deng, Ren Yang, and Zhenyu Guan,  “Reducing Complexity of HEVC: A Deep Learning Approach,”  IEEE Transactions on Image Processing, vol. 27, no. 10, pp. 5044–5059, Oct. 2018,  arXiv: 1710.01218.
  * [15] Z. Wang, S. Wang, J. Zhang, S. Wang, and S. Ma,  “Probabilistic Decision Based Block Partitioning for Future Video Coding,”  IEEE Transactions on Image Processing, vol. 27, no. 3, pp. 1475–1486, Mar. 2018.
  * [16] Thomas Amestoy, Alexandre Mercat, Wassim Hamidouche, Daniel Menard, and Cyril Bergeron,  “Tunable VVC Frame Partitioning Based on Lightweight Machine Learning,”  IEEE Transactions on Image Processing, vol. 29, pp. 1313–1328, 2020\.
  * [17] Tianyi Li, Mai Xu, Runzhi Tang, Ying Chen, and Qunliang Xing,  “DeepQTMT: A Deep Learning Approach for Fast QTMT-based CU Partition of Intra-mode VVC,”  arXiv:2006.13125 [cs, eess], July 2020,  arXiv: 2006.13125.
  * [18] A. Tissier, W. Hamidouche, J. Vanne, F. Galpin, and D. Menard,  “CNN Oriented Complexity Reduction Of VVC Intra Encoder,”  in 2020 IEEE International Conference on Image Processing (ICIP), Abu Dhabi, United Arab Emirates, Oct. 2020, pp. 3139–3143, IEEE.
  * [19] Meng Wang, Junru Li, Li Zhang, Kai Zhang, Hongbin Liu, Shiqi Wang, Sam Kwong, and Siwei Ma,  “Extended Coding Unit Partitioning for Future Video Coding,”  IEEE Transactions on Image Processing, vol. 29, pp. 2931–2946, 2020\.
  * [20] Qiuwen Zhang, Yihan Wang, Lixun Huang, and Bin Jiang,  “Fast CU Partition and Intra Mode Decision Method for H.266/VVC,”  IEEE Access, vol. 8, pp. 117539–117550, 2020.
  * [21] Ting Fu, Hao Zhang, Fan Mu, and Huanbang Chen,  “Two-Stage Fast Multiple Transform Selection Algorithm for VVC Intra Coding,”  in 2019 IEEE International Conference on Multimedia and Expo (ICME), Shanghai, China, July 2019, pp. 61–66, IEEE.
  * [22] Biao Min and Ray C. C. Cheung,  “A Fast CU Size Decision Algorithm for the HEVC Intra Encoder,”  IEEE Transactions on Circuits and Systems for Video Technology, vol. 25, no. 5, pp. 892–896, May 2015.
  * [23] Z. Wang, S. Wang, J. Zhang, S. Wang, and S. Ma,  “Effective Quadtree Plus Binary Tree Block Partition Decision for Future Video Coding,”  in 2017 Data Compression Conference (DCC), Apr. 2017, pp. 23–32.
  * [24] Z. Jin, P. An, L. Shen, and C. Yang,  “CNN oriented fast QTBT partition algorithm for JVET intra coding,”  in 2017 IEEE Visual Communications and Image Processing (VCIP), Dec. 2017, pp. 1–4.
  * [25] Ting Fu, Hao Zhang, Fan Mu, and Huanbang Chen,  “Fast CU Partitioning Algorithm for H.266/VVC Intra-Frame Coding,”  in 2019 IEEE International Conference on Multimedia and Expo (ICME), Shanghai, China, July 2019, pp. 55–60, IEEE.
  * [26] H. Yang, L. Shen, X. Dong, Q. Ding, P. An, and G. Jiang,  “Low Complexity CTU Partition Structure Decision and Fast Intra Mode Decision for Versatile Video Coding,”  IEEE Transactions on Circuits and Systems for Video Technology, pp. 1–1, 2019.
  * [27] Fen Chen, Yan Ren, Zongju Peng, Gangyi Jiang, and Xin Cui,  “A fast CU size decision algorithm for VVC intra prediction based on support vector machine,”  Multimedia Tools and Applications, July 2020.
  * [28] Jinchao Zhao, Yihan Wang, and Qiuwen Zhang,  “Adaptive CU Split Decision Based on Deep Learning and Multifeature Fusion for H.266/VVC,”  Scientific Programming, vol. 2020, pp. 1–11, Aug. 2020.
  * [29] M. Lei, F. Luo, X. Zhang, S. Wang, and S. Ma,  “Look-Ahead Prediction Based Coding Unit Size Pruning for VVC Intra Coding,”  in 2019 IEEE International Conference on Image Processing (ICIP), Sept. 2019, pp. 4120–4124.
  * [30] Benjamin Bross, Paul Keydel, Heiko Schwarz, Detlev Marpe, Thomas Wiegand, Liang Zhao, Xin Zhao, Xiang Li, Shan Liu, Yao-jen Chang, Huy-yu Jiang, Po-han Lin, Chi-chang Kuo, Ching-chieh Lin, and Chun-lung Lin,  “Multiple reference line intra prediction,”  JVET-L0283, Sept. 2018.
  * [31] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep Residual Learning for Image Recognition,”  arXiv:1512.03385 [cs], Dec. 2015,  arXiv: 1512.03385.
  * [32] Mingxing Tan and Quoc V. Le,  “EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks,”  arXiv:1905.11946 [cs, stat], May 2019,  arXiv: 1905.11946.
  * [33] Karen Simonyan and Andrew Zisserman,  “Very Deep Convolutional Networks for Large-Scale Image Recognition,”  arXiv:1409.1556 [cs], Apr. 2015,  arXiv: 1409.1556.
  * [34] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu,  “LightGBM: A Highly Efficient Gradient Boosting Decision Tree,”  Advances in Neural Information Processing Systems 30, p. 9, 2017\.
  * [35] Eirikur Agustsson and Radu Timofte,  “NTIRE 2017 Challenge on Single Image Super-Resolution: Dataset and Study,”  in 2017 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), Honolulu, HI, USA, July 2017, pp. 1122–1131, IEEE.
  * [36] Evgeniu Makov,  Dataset image 4k,  2019\.
  * [37] Iec Jtc and Itu-T Sg,  “Call for evidence on learning-based image coding technologies (JPEG AI),”  p. 15, 2020.
  * [38] Samuel W. Hasinoff, Dillon Sharlet, Ryan Geiss, Andrew Adams, Jonathan T. Barron, Florian Kainz, Jiawen Chen, and Marc Levoy,  “Burst photography for high dynamic range and low-light imaging on mobile cameras,”  ACM Transactions on Graphics, vol. 35, no. 6, pp. 1–12, Nov. 2016\.
  * [39] Radu Timofte and al.,  “NTIRE 2017 Challenge on Single Image Super-Resolution: Methods and Results,”  p. 12.
  * [40] François Chollet et al,  Keras,  2015\.
  * [41] Martın Abadi et al,  “TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems,”  p. 19.
  * [42] Diederik P. Kingma and Jimmy Ba,  “Adam: A Method for Stochastic Optimization,”  arXiv:1412.6980 [cs], Jan. 2017,  arXiv: 1412.6980.
  * [43] F. Bossen, J. Boyce, K. Suehring, X. Li, and V. Seregin,  “JVET common test conditions and software reference configurations for SDR video,”  JVET-M1010, Jan. 2019.
  * [44] Gisle Bjontegaard,  “Calculation of average PSNR differences between RD-curves,”  VCEG-M33, Apr. 2001.
  * [45] Tobias Hermann,  Frugally Deep,  2018\.