本文主要针对HM中的快速算法，以及HEVC相关的论文进行简要介绍。将主要分成三个模块进行介绍：
1.编码器的遍历过程；
2. HM中的快速算法；
3.相关论文分享。
首先介绍下HM中对与预测信息的一个遍历过程。对于一个CTU来说，首先要遍历各种划分深度，在不同的划分深度上，对预测模式进行测试，包括Skip/Merge模式，或者Inter模式，以及用帧内的方式进行预测。对于不同的预测模式还需要搜索对应的预测信息，对帧内的话搜索角度模式，对帧间的merge模式要搜索对应的索引，对于inter模式要经过IME以及FME搜索最佳的MV。整个遍历搜索过程可以用这样三个For循环来简要进行表示。对于快速算法，也就是在这三个for循环里，进行各种剪枝，早停的措施。接下来介绍HM中的一些快速算法，这些快速算法是在这个循环里加了一些条件来减少这个遍历的计算量。
第一个是ECU的工具，它是CU划分上的早停措施，在最外层CU深度的循环上进行。像右边图里展示的这样，原来的HM遍历过程，在某一深度上时，要对各种预测模式进行检查，这个ECU就是当所有预测模式检查完成以后，增加一个判断。如果这一层CU 的最佳模式为SKIP，那么当前CU再向下深度的划分就不再进行了。在划分上引入了一个早停的措施。在HM3.0上，能编码时间降到原来的62%。
下一个工具是ESD。这是对预测模式进行剪枝的工具。它是在检查完常规的inter 2N x2N以后，增加的一个判断。满足触发条件就是如果MVD 等于零，以及CBF这个标志为零的话，就跳过后续的其他预测模式如对称以及非对称的预测模式，以及帧内预测模式的搜索过程，当前cu的预测模式就是SKIP模式。这个工具是可以和上一个ECU工具叠加使用的。然后单独使用的话能将编码时间降低到原来的72%，结合ECU一块使用的话，编码时间降低到原来的56%，然后有1.6%的BD-rate损失。
刚才的ESD是在inter2Nx2N预测模式的代价计算后，进行的剪枝操作。在HM中还有一个叫做CFM的工具，它是在每一个预测模式搜索计算结束时进行的判断。当某一个预测模式结束以后，会进行cbf_YU V 三个标志的判断，当他们为零时，也会将后续预测模式的检查过程跳过。这个CFM与ESD 的作用条件类似，效果的话，提案里的数据是单独开启这个工具时，能使得编码时间降低到原来的67%。
以上是帧间对划分和预测模式的快速算法，最后还有一个对于预测信息的快速算法。对于帧间来说，一些快速IME算法以及FME算法都是属于这个范畴，它帮助编码器从许多待测运动矢量里快速选出一个最优的运动矢量。这一部分之前介绍的比较多，这里就不展开介绍了。那么目前HM里，在遍历各种划分以及模式的过程里，是右图里这几个快速算法存在，这几个小工具，计算并不复杂，但是能提供一个可观的加速效果。
这篇论文对刚才提到的工具进行了一个测试，刚才介绍的编码时间以及BD-rate是提案在HM3.0 4.0 上实验的结果。这篇文章里是在HM14.0上进行的实验，这里的FAST-HM这一列是三个工具全开启的结果。
从结果上看，这三个工具已经能做到49.4%编码时间节省。但是从这个结果里，提出了这三个工具，对于某些序列BD-rate损失较大，而对于某些序列如riverbed这个序列就基本没起到加速作用。对于这个三个工具在编码加速中出现的现象，作者进行了一些工作。
作者对Riverbed这个序列的时间消耗进行统计，统计结果显示，在CTC以及FAST-HM下，花费时间都差不多，这个序列加速效果不明显。问题在于，ESD，ECU，CFM这三个加速的策略都没被触发，所以在深度、预测模式、预测信息上，编码时间改变不明显。
Kimono这个序列加速效果比较明显，对其时间消耗进行统计，统计结果显示，在深度上，FAST-HM中在深度为0上花费的时间明显高于CTC，这是因为ECU被触发后，后续深度的编码被跳过，所花费的时间就会减少。然后在模式上，SKIP的模式时间占比也会增加，因为ESD这个工具被触发后，其余模式的检查就会被跳过，使得MRG或SKIP时间占比增加。
通过这个分析，作者认为，fast_HM 加速效果不明显的问题在于，一方面，有些时候这三个工具没有被触发，加速效果就不明显。另外当这几个工具被触发时，CU划分会很浅，深层次的划分被跳过了，会造成有时候bd-rate损失比较大。
针对这个问题，作者提出了新的CU计算顺序。以划分深度为3为例，这里的图a,是HM中原来的过程。从大块到小块不断进行划分，然后计算出各个CU块的代价，等最小块的代价计算出来以后，再从小到大的比较代价，进而判断划分情况。在这个访问顺序里，之前提到的那三个工具会使得CU在较浅的位置，CU块较大的时候就进行了早停措施，也就是划分上倾向于选用较大CU划分，对于图像纹理比较均匀的块是适合较大的CU，但是对于运动剧烈，纹理复杂的区域，大尺寸CU就不合适了，它更适合用较小尺寸的CU。
对于这个问题，作者提出了一个RCU的访问顺序。他过程是这样的，在划分时，还是按从大到小的顺序，但是计算CST时，先计算较小CU的CST，然后再进行较大CU的代价计算。通过这样一个调整，会使得对于某些运动序列，早停措施会倾向于用更小尺寸的CU。那要想用这个方式，需要做的是要对当前CTU深度进行一个预测。如果当前CTU可能的划分预测深度较浅，就用正常的访问顺序，如果当前CTU可能的划分预测深度较深，就用RCU的计算顺序。那问题就来到了怎么预测当前CTU的最大预测深度。
一般来说，获取当前CTU深度的方法有两种思路，一方面，从已编码的帧中获取深度信息对当前CTU的深度进行预测。另一方面，从同一帧中已经编码CTU中获取深度信息对当前CTU深度进行预测。本文采取的是第二种。具体做法是，将周围已编码CTU分成四分之一块进行深度的最大值统计。根据周围块最大深度，计算出一个参数Dp来预测当前CTU的最大深度。随后，作者通过统计信息，为这个参数定了一个阈值6，当Dp的值小于6时，就认为当前CTU的深度较浅，采用从大到小的CU计算顺序，当Dp的值大于6时，就认为当前CTU的深度较深，采用正常的从小到大的CU计算顺序。通过这样一种调整CU计算顺序的方法，来调整原来HM中ECU那个工具在早停上对于CU划分尺寸的一个倾向性。
在预测模式上面，由于采用了从小到大的cu计算顺序，作者提出可以利用小块CU所计算出的预测模式，对较大CU的可能采取的预测模式进行预测来降低计算量。首先作者做了一个统计。他将所有预测模式分成了三类，Skip、inter和intra，统计了四个子CU选择的预测模式与当前CU选择的预测模式之间的相关性，也就是表四。这个表里展示了，上层CU最优预测模式的选择与下层最优预测模式的选择高度相关，比如，当四个子CU选择SKIP时，上层CU有0.9447的概率选择用SKIP模式进行预测。
这个数据初步验证了作者想法的有效性，后续作者结合朴素贝叶斯的方法，对这个想法做了进一步扩展。具体做法是，首先作者统计了一个先验，就是各个子CU选择各种预测模式以及当前CU选取各种预测模式之间的关系，得到了四张表。在实际编码过程中，将四个子Cu的选取预测模式的情况作为调整因子，进而求出后验概率，也就是上层块选取各个模式的概率，通过这个概率的大小，对当前的预测模式进行剪枝，去掉那些可能性小的预测模式。只对计算概率大的预测模式，从而达到对预测模式进行减枝的目的。
第三步针对预测信息做的快速算法：在采用从小到大的CU计算顺序中，作者有这样一个统计数据：所有子CU中包含的相同的MV构成一个列表，上层CU所选取的MV很大概率上会在这个列表里出现。基于这样一个现象，作者ME过程进行了简化。首先，利用子块MV来指导上层CU的ME过程这个想法，只有在子CUMV相关程度高的时候才奏效，作者从做转码的文章里找到了一个MVVD的参数来衡量子CU MV之间的相关程度。有了这个参数，作者将四个子CU的MV合成一个集合对MVVD进行计算，将四个子CU进行分成垂直，水平方向进行计算MVVD。
根据计算出来的三个MVVD值，加入他们满足，整体的MVVD小于水平方向以及垂直方向，那就可以认为，子CU和上层CUMV之间相关性很高，在对上层CU进行ME时，只测试子CU构成的MV集合里的MV，而不进行复杂的IME以及FME过程。通过这种方式来对ME过程进行简化。
这张图是本文整体算法的一个流程图，其中Stage1 是开始一个CTU的划分过程时，先判断当前CU的最大预测深度，进而决定是否用RCU，也就是从小到大的CU计算顺序。当决定启用后，在Stage2,根据下层子CU的预测情况，根据贝叶斯算法算出来的概率，对当前CU的预测模式进行一个剪枝。然后进入到Stage3, 根据子CUMV之间的相关性判断是否可以对当前CU的ME过程进行简化。这个是他整体的一个算法。右边是它算法的实验结果，其中Encoder1,2,3分别对应只开启Stage1,以及开启Stage1,2和stage1,2,3全启用的效果。然后他的anchor是HM将快速算法都打开的一个结果，也就是左边这个算法是在HM已经启用了快速算法的基础上话的流程图。
从结果上看，当三个阶段全启用时，它在BD-rate损失2.1基础上，能在HM快速算法的基础上进一步减少36.6%的编码时间，同时对于原来HM快速算法里那些比较难加速的序列，就是斜体的这些序列，作者也进行了统计，结果显示，这些序列能在BD-rate损失1.6的基础上实现45.6的编码时间减少。
关 注 我 们
  实验室网站：http://viplab.fudan.edu.cn/
  OpenASIC官方网站：www.openasic.org
  知乎专栏：http://zhuanlan.zhihu.com/viplab
  微信公众号：OpenASIC
继续阅读
阅读原文