本文介绍一篇发表于2018DCC的论文，该论文针对多码率视频编码场景提出了一种基于贝叶斯推断的快速划分算法，本文中将该算法应用于AV1中，取得了较好的效果。
本文的研究背景是针对multi-rate下的视频编码，所谓multi-rate，即同样的一段视频使用不同的QP进行编码。另一个背景是AV1和HEVC具有不同的块划分结构，如右图所示，HEVC的CU划分是递归的四叉树划分，而AV1中一共有10种划分类型，当执行四叉树划分时子块可以递归划分，不同的块划分结构导致了相同的块划分快速算法如果不加以修改直接应用到不同的标准会有不同的性能表现，本文根据已有的HEVC算法经过改进推广到AV1中。
本文提出了一种基于贝叶斯的块划分推理模型，可以得到每一个块继续划分的后验概率，贝叶斯后验概率的计算公式如下式所示，等式右边的分子为似然乘以先验，分母为归一化因子。相比单纯的基于先验统计分析方法，基于贝叶斯的方法可以实时更新，取得更加准确的结果。本文中的推理模型本质上还是一种在RDO阶段的早停算法，可以在可忽略不计的BD-rate的损失情况下取得一定的编码复杂度的下降，最终性能是33.4%的复杂度下降，仅仅只有0.14%的BD-rate损失。
由于网络传输条件是动态变化的，通常视频内容需要使用自适应的码流，即同样的一段视频使用不同的QP进行编码，而客户端根据实际的网络传输条件选择对应的码率的码流。AV1本身的编码复杂度就很高了，再加上需要编码不同码率的码流，因此编码的复杂度就更大了，非常需要快速编码算法，而块划分是编码器复杂度的最大来源，因此也有很多工作针对其提出了各种快速划分算法。
关于multi-rate，因为是同一段视频输入到编码器，因此不同编码码率下有很多信息是可以共享的，用于后续的编码决策，降低RDO的复杂度。本文通过挖掘不同码率编码的统计相关性，主要是块划分的信息，构建了贝叶斯推断模型，在AV1上取得了较好的性能，并且可以推广到其它编码标准中。
在介绍具体的算法之前，需要先对一些推导中使用到的定义进行说明。这里提出了大部分关键的描述，包括reference 和local instance，depth，prime，overlap，split degree，remote frame和special frames，理解了这些概念会更容易理解后续的推导。
首先本文对编码中的一些统计结果进行了分析。第一个统计结果是prime块在不同深度和不同QP下所占的面积比例进行了统计，深度分别有depth<1, <2, <3和<4四种统计结果，它们之间是累加的关系，QP为从22到40，这里的图中使用了q-index的表示，这是为了更好的拟合。可以看出随着QP的增加，每种深度下所占的比例都在上升，并且呈现较好的线性关系，面积比例可以表示为每种深度下关于QP的函数，记为ad(q)。假设当前在第f‘帧中有一个块B，它的深度现在是d，我们可以推算出当前块会继续划分的概率，这是一个条件概率，根据条件概率的公式和ad(q)的定义得到公式(1)。因为当前块B的深度已经为d了，所以它的最优划分深度一定是≥d，因此公式可以直接作为深度的d的块继续划分的先验概率。
另外，作者还对dL和dR大小关系进行了统计。作者将使用最佳的QP=22参数进行编码的实例作为reference instance，其它QP下的实例则为local instance。dL代表在local instance中的帧fL中的任意prime块B的深度，fR指的是块B的remote frame，dR代表B块在remote frame中的split degree。可以看到，随着QP从22增加，dR<dL的可能性逐渐增加，dR>dL的可能性逐渐减小，这很容易理解，因为QP越大，local instance中的块划分的深度大概率是比reference instance中的深度要大。
作者还统计了不同分辨率下prime块在不同QP下的平均深度，结果显示更大分辨率通常有更小的平均深度，分辨率越高意味着在相同的尺寸下其纹理的复杂度是更低，更容易出现大块的划分。
下面介绍在HEVC中已有的multi-rate的快速块划分算法，同样还是选择使用最佳的QP参数22编码的实例为reference instance，还取了其它4个QP：27，32，37，42进行编码，即local instance，4个QP也正好可以计算BD-rate。算法的思想可以用一句话概括，即当local instance中的一个块B的深度已经达到了它在remote frame中的split degree，则当前块的划分早停，这很好理解，因为reference instance中的划分应该是最复杂的划分，其它local instance中对应位置的划分深度一般情况下不会超过reference instance中的划分深度。不过作者经过测试，直接将这种算法迁移到AV1，性能如original所示，和HEVC下的测试结果相比性能差了很多，作者推测应该是AV1和HEVC不同的块划分结构导致的，AV1的划分多达10种，reference instance提供的参考信息不足以给出好的估计。
作者进行了一种非常简单的改进，在AV1中隔一段帧数就会有一帧special frame，给后续帧的编码提供了重要的参考，所以对整体的编码性能起到了关键的作用，因此作者把local instance中所有的special frames都执行完整的RDO划分，其它帧还是通过reference instance的信息判决是否划分早停，性能如improved所示，可以看到这个简单的修改在复杂度和编码性能中取得了更好的trade-off。
上面证明了local instance中的special frame对编码性能有很大的影响，接下来会利用它的信息和refernce instance中的信息一起给出更好的划分概率估计。先给出一些公式中的定义，f是local instance中的non-special帧，B代表帧f中的深度为d的块，fL代表local instance中在帧f之前的最近的special frame，fR代表B块的remote frame，df'代表B块在帧f’的split degree。
贝叶斯划分的后验概率如下式所示，参考的信息是dfL和dfR，因为fL和fR都经过了完整RDO，是可靠的结果，并且f, fL和fR具有很强的相关性，这是构建贝叶斯推断模型的关键。根据贝叶斯后验概率的计算公式，可以得到等式右边的结果，分子中的p0代表先验，用公式(1)可以计算得到。分母将联合概率分解成边缘概率，因此只需要计算df＞d和df=d两种条件下(dfL, dfR)的概率。
对于上述的两个概率，作者对每个深度d都创建了两个2维表格，分别是Td+和Td-，分别用于记录(dfL, dfR)出现df>d和df=d的次数。如下图的表格示意，每个表格都有两个dfL, dfR索引，每次更新后表格中对应位置的值将会改变，因此概率可以通过表格计算出来，如下式所示。
算法的伪代码如右图所示，需要说明的是，作者引入了两个阈值τ1和τ2，τ1是判决的阈值，τ2是采样率，X是从(0, 1)均匀分布中采样的一个随机值。如伪代码所示，首先计算后验概率p和随机采样值X，然后判断早停划分还是进入正常的RDO流程。可以看出，即使后验概率p小于τ1，也不一定会直接早停，还必须满足X≥τ2的条件；如果进入了正常的RDO流程，则表格Td+和Td-进行更新，因为只有此时的结果才是可靠的；每次更新累加的值k与τ1和τ2有关。
作者进行一定的公式推导，证明更大的τ1，更小的τ2，会降低更多的编码复杂度，但是也会带来更多的编码质量损失，这也是符合直观的推理。作者将τ2固定为0.05，τ1分别取0.1，0.2和0.4进行了实验，可以看到更大的τ1的确节省更多的编码时间，带来更高的编码性能损失。并且还有一个有趣的现象，高分辨率的序列对更大的τ1有更高的容忍度，分辨率低的序列τ1稍一增加编码性能就会掉很多，这应该是由于高分辨率中的划分深度本身就相对更低，即使τ1的值较高，p≤τ1出现误判的概率也更小，所以性能损失并不大，这个现象也给作者调整阈值的设定提供了参考。
最终的性能如下表所示，采用τ2=0.05，较大分辨率的序列使用较大的τ1，取得了更好的trade-off，相比improved方法，在相同的BD-rate损失0.14%下，多节省了5%的编码时间。
本文提出的方法使用了贝叶斯推理，能够实时更新，取得了比较好的预测准确性，并且在相同思想的指导下可以将这种方法推广到其它标准中。但是也有一些缺点，比如方法的前提是在multi-rate编码条件下已经有reference instance编码了，才能提取到dfR信息，另外就是目前还只有一种复杂度和编码性能的权衡，不可调节，虽然可以直接通过调节τ1来调节判决阈值，但是阈值目前只考虑不同的分辨率，还有优化的空间。目前的推理模型只有dfL和dfR两个特征，更新的表格是2维的，而如果选取更多的特征，更新的复杂度会非常高，另外本文中未说明表格的初始化。
关 注 我 们 
  实验室网站：http://viplab.fudan.edu.cn/
  OpenASIC官方网站：www.openasic.org
  知乎专栏：http://zhuanlan.zhihu.com/viplab
  微信公众号：OpenASIC
继续阅读
阅读原文