开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 论文阅读：MID-DEPTH BASED BLOCK STRUCTURE DETERMINATION FOR AV1 -> 正文阅读

[数据结构与算法]论文阅读：MID-DEPTH BASED BLOCK STRUCTURE DETERMINATION FOR AV1

论文来源：ICASSP 2019

论文概要：AV1是一个开源并且版权免费（royalty-free）的视频压缩格式，是VP9发展的延续。由于帧结构的不同，现有的CU快速算法没办法应用于AV1标准。本文提出一种新型的基于中间深度的AV1块划分快速算法，从中间深度中提供信息去估计划分决策的后验概率分布，并对PU划分进行剪枝。实验结果证明所提出的方法可以在0.95%BD-rate的增益下节省29.06%的时间。

Introduction

AV1的块划分有10种，如图1所示。此外，AV1的LCU尺寸是128x128，更高灵活度的块划分结构提高了ME的性能，但是也带来了很高的复杂度。块划分是编解码标准里面时间花销最大的技术，已经有很多基于分类的块划分快速算法用来加速（expedite）块划分决策过程。AV1的参考软件里面已经集成了一些针对PU划分的快速算法，包括基于RD成本的快速算法等。但是这些快速算法都是利用标准的编码顺序进行加速，随着编码的进行可能没办法提供可靠的特征去进行分类。本文提出的新型放啊发会首先检查中间深度，而不是自上而下地对编码进行加速。子CU的预测信息会被用作对ME和PU划分进行加速。

提出的方法

收到[13]的启发，我们从中间深度出发，利用决策信息去决定是否去检查更高的深度或者更低的深度层，剪枝过程可以变成双向的。这个框架可以用图3表示。假设编码器冲深度 $d_{m}$ 出发，很明显可以看出 $d_{m}$ 越大，节省的编码时间越多的同时视频的质量越差。为了使得时间节省和视频质量达到不错的平衡，我们设置初始 $d_{m}=2$ 。

?为了避免歧义，我们定义一个预测单元的绝对深度如公式(1)所示，其中 $D_{W}$ 和 $D_{H}$ 分别是宽度和高度上的深度，W和H分别表示当前PU的宽和高， $\bar{W}$ 和 $\bar{H}$ 分别表示当前CU的宽和高。

?一个快速结构选择贝叶斯推断模型

[5]已经证明了MV的方差对PU划分决策和CU划分决策来说是一个很有效的参考工具，[5]中的MV来自于下采样帧的光流估计，nxn大小的块X的MV方差可以表示为公式(2)。其中 $m_{i}$ 表示在点i出的MV，并且 $\bar{m}=\sum_{}^{}m_{i}/n^{2}$ 。

我们可以利用块的MV代替光流MV。不过块级MV不如光流MV准确并且有时候帧内块是不存在MV的。另一种选择是我们利用块的划分程度去代替MV的方差（如果块中的每个点共享一个MV那这个块就不会被划分），块的分割程度越大，MV的方差就很有可能越大。

?为了更好的理解MV散度和划分程度的关系，我们进行以下分析。不划分的MV散度设为0，一旦一个块开始划分，MV散度就变为正数。如果X的子块Y又被分割成了两部分Y1和Y2，Y1和Y2的面积都是S，Y在不划分情况下的MV为 $m_{Y}$ 。其他划分方式比如水平A划分和水平B划分的情况可以看做是这种情况的进一步划分。给定两个独立的二维正态分布的随机变量 $\varepsilon _{1},\varepsilon _{2}\sim N(0,0,\varrho ^{2},\varrho ^{2},0)$ ,块X中每个点的新的MV可以用(3)表示，即把块X本身的MV和分块后的MV的插值看成是符合正态分布的，然后新的MV方差就可以用(4)表示，其中 ${\bar{m}}'=\sum {m_{}}'/n^{2}=\bar{m}+\bar{\varepsilon }$ , $\bar{\varepsilon }=(\varepsilon _{1} + \varepsilon _{2})/n^{2}$ （这里我算了一下这个分子上应该有个S才对。。），然后MV的方差的变化就可以用(5)表示。

?将(2)和(4)代入(5)，可以得到(6)(7)，从而得到(8)，其中 $\tau _{1}$ 表示一个常量， $\tau _{2}$ 表示一个常MV。

?可以看出 $\bar{\epsilon }$ 也是服从正态分布的并且 $\bar{\epsilon }\sim N(0,0,2\sigma ^{2}/n^{4},2\sigma ^{2}/n^{4}, 0)$ ，因此很明显的 $\Delta -C>0$ 概率大于1/2，又因为C>0，因此 $\Delta >0$ 的概率也就大于1/2，换言之当划分程度增加时MV的方差也会增加。[5]中提到的是高MV方差代表着划分的可能性很大，我们假设PU的划分程度与CU划分程度也是正相关的，我们用(9)来表示一个CU的PU划分程度（感觉这个计算方法有点像计算信息熵那样，只不过是用面积占比来算信息熵，以及(9)有点写错了，应该有个除以2才对），其中w表示PU所占CU的面积。这样算出来不划分、竖直划分、竖直A划分和四叉树划分的划分程度分别是1,1.5,1.75,2.0和2.0（我算出来是0,0.5,0.75,1.0和1.0）。

?为了证明PU划分程度和选择划分模式的关系，本文用Johnny序列的100帧在QP=27时做了统计，图4就是当CU大小为128x128和64x64的时候统计的CU选择划分或者不划分和划分程度之间的关系，可以看出当划分程度增加的时候选择划分的概率也增加了，与预期相符合。

?在大块CU的决策错误会带来性能损失，本文又引入了贝叶斯风险决策那一套逻辑去进行分析。把一个CU的决策分类成两类，一类是需要检查更高层的深度，记为CHECK，另一类是跳过检查过程，记为SKIP。当预测正确的时候是0风险，但是当实际是SKIP但是预测为CHECK时损失记为 $L_{c,s}$ ,表示不必要的RDO过程带来的时间开销，反之当实际是CHECK但是预测为SKIP时损失记为 $L_{s,c}$ ,，表示RD的性能损失。贝叶斯风险用公式(10)(11)表示。因此选择SKIP的条件就变成了 $R(s\mid P_{D}) < \varepsilon R(c\mid P_{D})$ ，选择CHECK也是同理，不过这里的 $\varepsilon$ 是个平衡因子，应该跟前面的 $\varepsilon$ 没啥关系。

?通过贝叶斯原理，我们通过公式(12)计算所需要的先验概率，然后决策规律就可以用(13)表示。

?但是由于很难衡量时间节省和RD性能之间的关系，就很难确定一个合适的 $\varepsilon$ 。不过从图4已经可以看出当PU划分程度增加时 $p(P_{D}\mid s)/p(P_{D}\mid c)$ 减小，因此假设(13)的右边是固定的，那me只需要为每个深度选一个合适的阈值 $\eta$ ，当划分程度大于这个值时选择SKIP，否则选择选择CHECK。由于还需要限制RD损失，因此设置一个错误率阈值 $\alpha$ ，这个阈值比较小就可以减小RD损失，当这个阈值比较大就可以增大时间节省。

由于要提前知晓划分深度和最终决策的相关性的先验知识，每当场景变换时前5帧不进行快速算法。这样就确保了大多数帧能够被加速，同时模型还可以不断更新。

改进的PU划分剪枝算法

AV1中已经有一些基于RD成本对PU划分进行剪枝的快速算法，本文提出了一种基于划分程度的PU划分快速算法。我们将非方形划分方式基于划分程度分成3类，水平和竖直一刀被分到类别1，水平AB和竖直AB被分成类别2，水平4和竖直4倍分成类别3。

对于类别1和类别2，之前已经分析过当子CU的划分程度很大时将两个子CU结合成一个矩形PU的可能性很小。表1记录了划分程度小于2的位于PU中两个子CU没有进一步分裂的概率，可以看出平均概率超过了94.3%。

?如果最优的划分模式属于类别3，最直接假设就是子CU硬要有一个具有方向特点的划分，我们定义的划分程度并不能区分方向，因此我们定义水平和垂直两个方向的划分划分程度 $P_{W}$ 和 $P_{H}$ 。在实验中我们发现，当 $P_{W}>1.25$ 时，选择水平四划分的概率降低至12.7%，相同的，当 $P_{H}>1.25$ 时，选择竖直4划分的概率降低至10.7%。因此水平和竖直上的划分程度可以用来跳过水平4和竖直4的决策过程。1.25就成为了禁止掉水平和竖直4模式划分的阈值。?