基于快速编码单元划分和自适应模式决策的HEVC效率改进算法

罗小龙，刘子龙

(上海理工大学 光电与计算机信息工程学院，上海 200093)

随着人们对于超高清音视频实时沟通娱乐的追求，HE ISO-IEC/MPEG和ITU-T/VCEG组织提出了下一代视频压缩标准——高效率视频压缩(High Efficiency Video Coding，HEVC)[1]。HEVC的设计目的比前一代H.264/AVC标准更出众，拥有更好的效果和更高的效率。在相同视频质量的前提下，HEVC比H.264/AVC节省50%的码率。HEVC还提供了灵活的基于块单元的方案，包括四叉树编码单元、可变块尺寸的预测单元和变换单元。在帧内预测方面，HEVC包括35种模式：DC模式、Planar模式以及对每一预测单元的33种角度模式。这虽然提升了编码的质量，但也增加了编码的复杂度和时间[2-3]。

为了降低HEVC的编码复杂度和时间，许多学者从编码单元的划分来寻找突破口。文献[4]运用编码单元的纹理特征决定了一个编码单元是否需要检查和比较子编码单元的率失真代价。文献[6～7]则提出快速编码单元分离算法，通过空间临近的编码树单元信息确定当前编码单元的深度范围，以此来减少不必要的编码单元划分。文献[6]运行了基于机器学习的方法。研究人员提出了许多快速算法以期减少HEVC帧内预测的计算时间。文献[8]通过计算局部方向方差，提出了一种在离散晶格中沿着一组有理斜率共线的纹理方向检测算法。文献[9]提出快速离散交叉差分算法，通过考虑检测块的主导方向使HEVC实现时间节约。

通过深入研究对比，本文发现率失真代价能够在一定程度上表征编码单元的复杂度，但少有利用编码单元的率失真代价来划分编码单元的研究。本文基于深度信息和率失真代价特点提出了快速编码单元划分算法。该算法利用编码单元的拆分相关性，确定当前编码单元的深度范围从而跳过率失真代价计算，提早分离或提早结束编码单元。利用率失真代价和在线学习得到的阀值使不满足以上分离要求的编码单元可以尽早结束其四叉树分离。当编码单元都不满足以上条件时，本文又提出了自适应模式决策算法。利用最小的率失真代价模式和第二小的率失真代价模式有效减少候选集的数量并且确定候选集CS5。然后，最优化CS5以减少候选率失真优化数量。最后进行率失真优化计算来选择最优模式，并通过实验验证本文算法的优势以及实用性。

1 快速编码单元划分算法

由于计算率失真代价需要量化和熵编码[7]编码单元(Coding Unit, CU)划分和率失真代价检查会显著增加计算的复杂度。因此，如果一些编码单元划分在计算它们的率失真代价之前就可以“提早分离”或“提早结束”，那么自然可以节省编码时间。本文所说的“提早分离”指的是编码单元在没有检查率失真代价之前就拆分成4个子编码单元；“提早结束”指的是当前编码单元不需要进一步拆分。

本文选择HEVC官方测试序列BasketballPass 410×240、BQMall 832×480、Cactus 1920×1080、ChinaSpeed 1024×768、Flowervase 832×480、Mobisode 832×480、PartyScene 832×480、Vidyo 1720p来验证本文算法。通过测试发现帧内相邻CU的最优划分深度极其相似。因为编码顺序基于Z扫描(Z-Scan)，所以只有上边和左边的相邻编码单元深度信息可以被利用。如果当前编码单元位于视频帧的上或左边缘，该方法就不再适用。本文通过式(1)和式(2)来获取当前编码单元的深度值范围

|depthl-depthc|≤1

(1)

|depthu-depthc|≤1

(2)

式中，depthl指的是左边相邻的编码单元深度值，depthu指的是上边相邻的编码单元深度值，depthc指的是当前编码单元深度值。

如果depthc小于式(1)和式(2)求出的当前编码单元深度范围的最小值(depth_min)，那么它可以直接被分为4个子编码单元而不用进行粗模式决策和率失真优化，这就是提早分离方案。相应的，当depthc大于等于式(1)和式(2)求出的当前编码单元深度范围的最大值(depth_max)，那么它可以提早结束且不需要进一步划分。例如，当depthl=depthu=2时，根据式(1)和式(2)可以求得当前编码单元的深度范围是{1,2,3}，即depth_min=1，depth_max=3。所以当depthc=0时，当前编码单元可以直接被分为4个子编码单元。

当depthc>depth_min且depthc< depth _max时，本文提出通过训练帧在线学习获得率失真代价阀值(TRD)，从而明确当前编码单元的四叉树分离是否可以提早结束。因为率失真代价是失真和比特率之间的一个平衡指数，所以它能够表征一个编码单元的复杂度。当一个编码单元有平滑的纹理特征，对于较大的编码单元帧内预测将会足够准确，所以进一步的拆分并不会显著减小率失真代价。相反，如果一个编码单元有复杂的纹理特征，进一步的拆分会降低预测误差和率失真代价。因此，一个编码单元的四叉树拆分可以被简化为二元分类问题。通常，一个视频序列中相邻帧的像素差别很小，因此在相同编码配置的情况下，相邻帧有相似的率失真代价。所以，编码单元提早结束的分离策略可以利用率失真代价的时间统计相关性。需要注意的是，该方法只能用于帧内配置，因为其他配置有至少两种不同的帧种类和量化参数，这无疑会破坏率失真代价的相似特性。

当编码视频时，视频序列将根据一个周期(Tp)来分为训练和测试部分。在每个周期内，第一帧作为训练帧，其余作为测试帧。在测试阶段，当编码单元的率失真代价小于阀值TRD，可以推知当前四叉树编码单元拆分结构足够准确且进一步拆分也不会再有更多的收获。运用数学统计分析率失真代价特点可发现率失真代价提早结束和进一步拆分的情况存在联合概率密度，如图1所示。

错误决策概率αT由式(3)和式(4)得到

(3)

(4)

式中，R代表率失真代价值；P(R, Stop)表示提早结束的率失真代价概率；P(R, Split)表示进一步划分的率失真代价概率；n(t)表示编码单元的整体数量，n(s)表示需要进一步拆分的编码单元数量。

在训练阶段，对于从0～3的编码单元尺寸，计算n(t)和n(s)。并且记录需要进一步划分编码单元已获得更好拆分结果的率失真代价值，然后升序排列。TRD可以通过等式(5)～式(7)计算得到

(5)

(6)

TRD=RD[int(index)]

(7)

通过上式可以得出，αT与编码时间呈正相关，但该参数也不宜过大。否则，该算法会出现许多提前结束拆分的决策错误并造成更大的失真。本文提出的快速编码单元划分算法流程图，如图2所示。

当编码视频时，视频帧被分为训练和测试部分。对于训练帧，CU拆分运用HEVC的原本算法来获得率失真代价阀值。对于测试帧，如果当前CU位于视频帧的上或左边缘，该阀值就可以判定在测试帧中的编码单元是停止划分还是需要进一步划分。反之，可以根据相邻的上或左边缘的编码单元深度信息判定是停止划分还是需要进一步划分。

3 自适应模式决策算法

由于预测模式的数量对帧内预测的编码时间有显著的影响，因此本文提出的自适应模式决策算法主要用于减少预测模式的数量。大量研究分析表明最小的率失真代价模式FMi和第二小的率失真代价模式SMi都被包含在FMi-1区域中的概率是60%。在这种情况下，可以只利用FMi-1去计算候选集CSi而不用管SMi。但单一的利用该方案去选择最优模式的失败概率高达40%。综合考虑，本文提出当FMi-1和SMi-1有不同的率失真代价时，只利用FMi-1去计算候选集CSi；否则，FMi-1和SMi都需要考虑。

设RDcostFMi-1和RDcostSMi-1分别代表FMi-1和SMi-1的率失真代价，αi阀值表明如何计算CSi。首先初始化i=1和CS1={2,10,18,26,34}。然后选择FM1和SM1。下一步将i加1，αi的值由i的值和预测单元(Prediction Unit, PU)的大小决定。本文主要通过预先计算上文提到的8种特殊的视频序列，每种序列均取100帧。重复测试多次后，本文获得了αi的值和每一个预测单元PU的大小，表1列出了通过该种方式获得的αi值。

表1 求出的αi值

用RDcostFMi-1/RDcostSMi-1的比率表示FMi-1和SMi-1的率失真代价。当RDcostFM1/RDcostSM1<α2表示FM1的率失真代价明显小于SM1。因为FM1比SM2的率失真代价更小且相邻模式的率失真代价在角模式中是连续的，FM1±4的率失真代价小于SM1±4的率失真代价。此外，FM2和SM2很可能既在FM1中又在FM1±4中。所以CS2只需要通过FM1计算得到。反之表明FM1和SM1的率失真代价没有明显差异，CS2必须由FM1和SM1共同计算得到。CSi取值的完整自适应策略由式(8)计算得到

(8)

式中，DC代表PU的DC模式；Planar代表PU的Planar模式；MPMs(s={1,2,3})代表CS6时的3种最可能的模式。

本文使用率失真代价代替率失真优化代价。这是因为率失真优化代价与率失真代价趋势相同，且更容易计算。另外，使用率失真代价也可以减少候选集的大小。x是一个任意给定的CS5的帧内模式，CSmod表示率失真优化的一个自适应修改候选集，RDcostx是x的率失真代价，β是模拟在上面提出的8种视频中从0到1的测试项阀值。如果RDcostFM5/RDcostx≥β，x从CS5中移除且加到CSmod中。反之x只从CS5中移除而不加入CSmod中。之后遍历所有模式，如果最后CSmod只留下一个模式，则该模式即为最优模式，跳过率失真优化计算。如果CSmod中有两个或多个模式，通过率失真优化计算从这些候选中选出最优模式。图3为自适应模式决策算法流程图。

本文提出的自适应模式决策算法首先通过有效减少候选集的数量并且确定CS5，之后最优化CS5以减少选率失真优化数量，最后进行率失真优化计算选择最优模式。

3 实验验证

本文主要挑选了16种视频序列来验证提出算法的实用和有效性。本文选用的参考软件为HM16.3，所有测试序列编码配置统一是全帧内配置，分别选取100帧，量化参数为{22,27,32,27}。CPU是Inter Core i5-4200，2.80 GHz × 4核，8 GB内存。

本文还通过平均码流差(Bjontegaard Bit Rate，BD-BR)来量化分析编码质量的损失，量化编码节省时间(TS)，可由式(9)计算得到。

(9)

式中，TH代表HM标准测试的编码时间；TF代表本文提出算法的编码时间。

本文提出的提前结束策略在纹理平滑区域的作用频次远大于在复杂纹理区域的作用频次。设αT=10%，Tp=16。本文挑选了Kimono序列的一些平滑区域编码单元，与HEVC标准的最终拆分结果做了对比，结果如图4所示。

最终实验结果如表2所示，通过表2数据可得：快速编码单元划分算法的BDBR损失比自适应模式决策算法小得多，TS的值有所上升但并不十分理想，尤其在实时视频传输的应用场景下有些局限。运用本文提出的综合算法后，很明显BDBR和TS都得到了不同程度的优化，BDBR比损失最小的快速编码单元划分算法还小2.97%，效果较为明显。

而且，本文提出的综合方案还可以通过调节αT的值来调节TS。在实际应用中，如果编码时间比视频质量和码率更重要，可以将αT设置为更高的值，从而提高TS即节省更多的编码时间。如果没有这种特殊要求，综合考虑来看，本文还是建议将αT值维持在较低水平。

4 结束语

本文提出的基于快速编码单元划分和自适应模式决策的HEVC效率改进算法，与HM标准测试结果相比，可在保证编码质量的同时有效降低45.93%的视频编码时间，仅伴有0.597 8%的BDBR上升。获得该结果的主要原因在于，本文算法利用编码单元的拆分相关性来确定当前编码单元的深度范围，从而跳过率失真代价计算，提早分离或提早结束编码单元。利用率失真代价和在线学习得到的阀值使不满足以上分离要求的编码单元可以尽早结束其四叉树分离。当编码单元都不满足以上条件时，利用最小的率失真代价模式和第二小的率失真代价模式有效减少了候选集的数量并且确定候选集CS5，然后最优化CS5以减少候选率失真优化数量，最后进行率失真优化计算选择最优模式。本文算法还可以通过调节αT的值来调节编码时间的值，大幅增加了实际应用的灵活性。

表2 实验结果