本次介绍关于帧间快速算法的几篇论文，目标是缓解HEVC/VVC中复杂划分和编码带来的巨大复杂度提升。
第一篇论文于2014年发表在TMM，题目是《A Fast HEVC Inter CU Selection Method Based on Pyramid Motion Divergence》，针对的是HEVC标准，题目中提到的Pyramid Motion Divergence后面会有详细解释。
公式(1)给出了判决CU划分与否的依据，J代表RD损失，公式(2)用SSD对RD损失进行了估计，忽略了划分flag对应bit的影响，其中m’代表了当前CU的运动矢量。公式(3)进一步将当前CU中的每一个像素用前一帧中的像素表示，每个像素的运动矢量用m_x表示。接下来需要进行一些近似，利用到了相邻像素的相似性，并且距离越近的像素具有越高的相关性，两者的距离可以用||m’-m_x||2表示，再通过泰勒展开对式子进行化简，得到公式(6)。我们的最终目标是最小化J，则m’为当前CU中所有像素的运动矢量的平均值，因此最小RD损失J_min和当前CU中每个像素的运动矢量的方差成正比。
每个像素的运动矢量，也就是光流，指的是每个像素的瞬时速度，可以使用基于逐次超松驰successive over-relaxation (SOR)的算法得到。由前文可知最小RD损失和MV方差成正比关系，图一给出了实际编码的统计结果，横坐标表示MV的方差，由SOR算法得到，纵坐标表示cost，由实际编码得到，两者符合正比关系。
较大的MV方差意味着剧烈且不一致的运动，较小的MV方差意味着微弱或一致的运动，如图2所示。图3给出了实际的光流场和划分情况，注意到物体的边缘部分，由于运动情况的不一致，通常是用小块进行编码；而背景通常用大块进行编码，这进一步证明了运动矢量越发散，则CU编码尺寸越小。
作者提出了PMD，直译为金字塔运动散度，如右上图所示，由两部分组成，第一组为父块的MV方差，第二组为四个QT子块各自的MV方差，记为P_X。公式(1)给出了一种映射关系，通过父块和4个子块的RD cost得到划分的判决。根据前文可以将RD cost转化为MV方差，这就构成了所谓的PMD，PMD的每一项可以由公式(3)和(4)计算得到。
之后作者做了一个统计，统计当前CU和其相邻块的划分和PMD的关系。公式(5)中Pi和Pj指的是相同size的两个CU对应的PMD，且Pi和Pj是相邻的CU，具备一定的相似性。公式(6)进一步量化了PMD的相似性。右图做了一个统计，横坐标表示ndist，纵坐标表示具有相同划分的CU所占的比例。从图中可以看出，具有相似的PMD意味着大概率相同的划分情况。
前文统计中使用到的光流计算方法能够比较准确地计算出每一个像素的MV，但是复杂度太高了，本身我们就是为了降低划分判决的复杂度，如果光流估计消耗了大量时间则得不偿失。本文中使用 1/16 下采样的帧来降低光流计算复杂度，水平和垂直方向分别4倍下采样。这也是考虑到4x4是HEVC中最小的PU尺寸。这样复杂度大大地降低了，对于64x64的CU来说，计算次数从4096下降到256。
由前文知道，相似PMD的CU通常使用相同的划分策略，因此本文提出了如右图所示的流程。首先进行下采样并估计光流，计算出当前CU的PMD，并计算不同PMD的Euclidean 距离作为相似性的衡量，如公式(1)所示。
具体而言当前CU的划分策略通过比较已编码CU的PMD来决定。通过公式(1)找到与当前CU最相似的k个CU，然后进行分类讨论，如公式(2)所示：如果所有的k个CU都继续执行划分，则当前CU也执行划分；如果所有的k个CU都是不划分，则当前CU不划分；否则需要正常编码划分和不划分两种情况。
在比较相似性的过程中我们需要限制比较的CU数目以节约时间。本文中使用两个相同长度的FIFO队列分别存储不划分和划分的CU。为了保证有足够的初始CU，第一帧P使用常规编码，不使用快速算法。
本文在LDP和LDB两种配置下进行了测试。不同的K对应不同的复杂度和BD-rate如右图所示，作者选择将K设置为5。FIFO队列长度设置为300。最终的性能如下表所示，在LDP下，时间节省42.81%，BD-BR增加1.9%；在LDB下，时间节省40.33%，BD-BR增加2.2%。作者还统计了计算光流所消耗的时间，可以看到，即使已经对光流估计通过下采样进行化简，但是仍然消耗了约9%的时间。
接下来介绍一篇2018 ICIP的论文，论文使用了CNN来快速判决QTBT划分。QT的最小size为16，MaxBTDpth = 4，因此DepthCU的范围是{0, 10]，计算公式如下所示，不同论文对Depth的定义也略有区别。作者统计了不同的Temporal Layer的帧在不同QP下，64x64CU的划分深度，如下表所示。可以观察到，更小的QP和更小的Temporal Layer，意味着更深的划分。因此可以限制划分的深度以避免不必要的划分，达到减小复杂度的目的。
由于QTBT的划分类型比较复杂，作者并不预测具体的划分类型，而是将预测QTBT划分深度建模为一个多分类问题。为了简化问题，这里仅仅标记了6个分类而不是10个分类，减轻了网络的训练压力。
预测网络结构如左图所示，首先通过运动补偿将64x64的原始块转化为残差块，这是因为帧间的划分更趋向于依赖原始块和预测快的关系而非原始块本身，然后对残差块进行去均值的操作，之后送入三层卷积网络中，最后的全连接网络中加入了QP和Temporal Layer的信息。损失函数为L2损失，并加入了权重的惩罚项防止过拟合。并且如果划分和不划分仅仅带来微小RD cost差异，这样的样本被去除在训练集之外，减轻网络的训练压力。
右图是算法的流程图。对于一个128x128的CTU，首先对4个64x64子块执行网络推理，得到预测的划分深度d。为了降低预测错误的风险，这里对参考帧的相同位置的CTU也执行了一次网络推理，得到预测划分深度d‘，此时我们已知该CTU的真实划分深度，所以可以观测该CTU的推理误差，如果推理正确，即D’-d‘为0，则从侧面说明之前我们预测的划分深度d是比较可靠的，否则对d做出修正，修正方法是加上Max{D’-d’,0}。得到修正后的d，则开始正式编码，需要分类讨论。如果4个64x64的预测划分深度都为0，则对128x128的CTU执行QT或者执行两次BT，划分深度需要小于2。注意这里的depth是对于CTU而言，而不是64x64的子块。如果仅仅只有一个子块的d不为0，则该子块执行划分类型的遍历而其它的子块不划分。否则，直接执行QT，且每个子块划分遍历到对应的预测深度。
最后本文的性能如下表所示，在JEM 7.0上测试，使用RA配置。大约降低了35%的编码时间，提升了0.55%的BD-rate。网络推理的时间不到3%，在可接受的范围内。
下面介绍一篇2022 ICME的论文，使用了随机森林的方法进行划分判决。算法的流程如左图所示，先做常规的Merge预测，得到变换系数，如果直流值和交流绝对值和都为0，即所有变换系数都为0，则直接判决为不划分，这种思想是很朴素的。否则根据CU的尺寸选择对应的随机森林模型进行推理。
对于模型的训练，特征选取很重要，本文一共选取了5个特征，其中前三个特征和帧间编码密切相关，需要更加注意。fac：较大的fac对应于当前CU的较小SSE，这意味着更好的匹配，更可能提前停止划分。D_diff：如果D_diff很大，则匹配块覆盖的区域下的划分深度大于当前CU的深度，这意味着匹配块可能跨越多个CU。由于时间域中存在相关性，因此当前的CU更倾向于继续划分。norm:具有激烈运动的区域更有可能分为较小的CU。其它两个特征比较常规，和变换系数和量化参数相关，和帧内编码或者帧间编码无关，在两者的快速算法中都经常使用。
性能如右表所示，anchor为VVenC 1.0，配置为RA，GOP设置为32。由于VVenC已经对VTM进行了复杂度的优化，所以本文相对于VVenC的复杂度降低并不高。
接下来介绍一篇2022 MMSP的论文。处理流程如左图所示，首先提取一系列特征，然后依次判决是否QT、水平/垂直、二叉树/三叉树划分。一共有四类特征被提取：空间域纹理特征，时域运动信息，残差域信息，中间编码信息特征。
需要注意的是，因为此时没有执行真正的运动矢量搜索，有的信息无法拿到，所以使用了pre-coding的方法（时间占比约0.5%），例如计算所有4x4块的motion field和残差。中间编码信息包括了AF_Merge的信息，所以需要提前执行AF_Merge，和其它帧间模式不同。每一类特征选取还是比较常规的，例如平均值、最大/最小值、方差、均一性等，还利用一些相邻块的统计信息和QP等信息。特征选择使用的判别标准依旧是信息熵，最终共选择了17个特征。对于temporal layer的问题，本文对每种layer都设计了对应的分类器。
右表给出了性能表现，在VTM-7.0上测试，51%的性能损失带来了1.65%的BD-rate上升。
接下来介绍一篇发表于2022 ICCE的论文，本文使用的是传统方法实现MTT划分的剪枝。本文一共提出了两种方法。
方法一是基于图像特征，使用了Canny边缘检测的方法，统计当前CU不同位置的“边缘”像素数量来判断跳过某些划分。例如如果边缘像素所占的比例小于一定的阈值，则跳过TT划分。进一步地，如果BTH划分的上半部分或者下半部分的边缘像素的数目为0，则跳过TTV划分；对于BTV划分同理在满足一定条件下可以跳过TTH划分。
方法二利用了时域的关系限制当前CU划分的深度。Ref0和Ref1是离当前帧最近的两个参考帧的相同位置的CTU。Offset为2，是一个经验值。
这篇论文比较简单，想法比较朴素，而且没有对帧间编码做特殊的优化，和普通的帧内编码快速算法类似，但是多参考帧的问题确实是帧间快速算法中的一个经常被忽略的问题。
接下来介绍一篇发表于2019 APCCAS的论文，本文也采用传统的方法进行划分判决。对于帧内编码，本文使用Canny边缘检测算子，统计当前块中位于边缘的像素，包括位置信息和数量信息，判断是否继续划分。这种思想和上一篇论文很像，不过本文仅用于帧内，相比上一篇论文更加合理一点，因为边缘算子并不一定是物体边缘，有可能是物体内部的纹理，并不适合用于帧间划分判决，这里不多介绍。对于帧间编码，本文的核心思想就是找出连续三帧中几乎不动的物体，因为如果不动的话可以很容易找到参考帧中匹配的块，大概率不会继续划分。中间的公式给出了计算某一个块是否在连续三帧都保持不动。r越高则意味着当前块大多数像素都没有发生改变。阈值设置为0.95（即当前块中有95%的像素都是不动的）。当r大于0.95时，当前块将提前终止划分。该方法的性能如右表所示，在VTM-4.0上进行测试，RA配置。大约节省了31.43%的编码时间，带来了1.34%的BD-rate上升。
 关 注 我 们 
实验室网站：http://viplab.fudan.edu.cn/
OpenASIC官方网站：www.openasic.org
知乎专栏：http://zhuanlan.zhihu.com/viplab
微信公众号：OpenASIC
继续阅读
阅读原文