【论文解析】Fast prediction mode selection and CU partition for HEVC intra coding

• 级别：IET Image Processing（2020）CCF CSCI 4区
• 时间：2020年
• 机构：苏州大学
• 下载地址：Fast prediction mode selection and CU partition for HEVC intra coding

摘要

HEVC确实是一次重大的技术进步，在编码效率上实现了翻倍提升的同时显著增加了计算复杂度。

为此提出了一种基于模式分组的帧内快速算法与一种基于CU及其子块（即子CU）的空间纹理特征（包括内容复杂度与方向复杂度）的双支持向量机。

这两种算法在功能上各有侧重：前者通过减少进入粗略模式决策阶段的数量来降低计算开销；后者则通过高效选择CU大小来平衡码率与重建质量。

实验结果表明这些改进措施的有效性：在保证图像质量的前提下显著降低了编码时间（减少了42.80%），码率仅上升了约0.98%，而图像亮度均方差（PSNR）损失仅为0.018 dB。

介绍

在HEVC压缩编码中，图像首先被划分为多个独立的编码树单元（CTUs），这些CTUs则以一种分形树结构组织为编码单元（CUs）。其中最大尺寸设定为64×64像素对应0级分割深度；而最小尺寸设定为8×8像素对应3级分割深度。在每一级分割阶段中需要综合考虑35种内帧预测方案以及相应的率失真（RD）成本特性，并通过自顶向下的回溯方法确定最优预测方案与最优块尺寸组合。由于这一系列操作涉及大量复杂计算步骤导致整体计算复杂度极高。图1详细展示了典型一个CTU（即LCU）所具有的分形树结构及其对应的CU层级分配情况：其中层次分布如下：CU0位于第0层；CU1位于第1层；以此类推直至CU3位于第3层。

• 本研究主要基于预测单元（PU）在水平、垂直、45°以及135°方向上的梯度信息，并结合不同尺寸下的编码单元（CU）纹理特征展开分析与研究。本研究主要致力于开发出一套高效的帧内预测模式选择方案与CU尺寸优化方法，在显著降低计算复杂度的同时实现了对视频编码效率的有效提升。本文后续章节安排如下：第二部分将介绍相关领域的最新研究成果；第三部分与第四部分将分别阐述所提出的帧内预测模式选择方法与CU尺寸确定的具体方案；第五部分将展示实验验证结果并进行深入分析；第六部分则对全文进行总结与展望。

相关工作

• 主要讨论了减少帧内预测计算复杂度的两种方法。第一种是优化帧内预测的率失真模式选择算法，即PU优化。2010年Piao等人提出的粗略模式决策（RMD）和2011年Zhao等人提出的最可能模式（MPM）有效减少了进行率失真优化（RDO）过程的模式数量，并成为HEVC标准的一部分。2012年，Jiang等人提出了一种基于梯度的预测模式选择算法，根据梯度向量幅值的直方图，选择幅度最大的模式进行RMD过程。2016年，Zhang等人提出了一种基于模式分组的快速算法，根据预测单元（PU）水平梯度与垂直梯度的比值和MPM的统计特征，减少了RMD过程的模式数量。2017年，Maher等人采用块纹理作为特征，减少了RMD的模式数量。2013年，Chen等人通过分析几个主要方向模式的成本，建立了最优相邻模式列表，减少了RDO候选模式的数量。2014年，Zhang等人提出了一种基于Hadamard（HAD）成本的算法，选择性地检查潜在的预测模式。2015年，Jamali等人提出了一种基于边缘检测和绝对变换差值成本分类的预测模式选择算法，提高了预测精度。2015年，Lai及其同事利用顶部和左侧相邻PU的最佳模式来跳过一些模式。2017年，Reuze等人提出了一种增强帧内模式信号的方法。2018年，Zhu等人提出了一种基于纹理分割和方向的快速模式决策算法，包括CTU深度范围预测和帧内预测模式选择。
• 另一种方法是优化帧内CU（编码单元）大小选择算法。2013年，Shi等人提出了一种CU深度范围确定算法，利用空间和时间相邻CU的深度信息。2015年，Wang等人定义了简单LCU、复杂LCU和其他LCU的三个深度范围，当前LCU的深度由相邻LCU的最大深度决定。2017年，Sun等人利用Haar小波提取的CU纹理复杂度进行早期CU分割终止。2016年，Ozturk等人提出了一种基于图像内容中像素变化强度的早期CU确定算法。2013年，Cho和Kim提出了一种基于贝叶斯分类器的CU快速分割和剪枝算法，使用HAD成本和RD成本。2015年，Lim等人提出了一种基于贝叶斯分类器的CU快速分割算法，根据当前CU与相邻CU或父CU的HAD成本比值来确定CU的早期分裂和早期终止。2017年，Hsu等人采用支持向量机（SVM），使用方差、离散余弦变换的低频AC分量和空间相邻CU的深度作为特征，用于快速CU大小决策。2018年，文献[26, 27]的作者采用卷积神经网络进行快速CU深度决策。Tseng和Lai [16]提出了一种快速CU决策方法和一种快速模式选择方法。Zhang等人 [28]提出了一种快速方法，包括在四个CU决策层的SVM基础快速CU大小决策方案的两个阶段。Jamali和Coulombe [29]提出了一种基于预测帧内模式RDO成本的方法，并采用Prewitt算子来消除不相关的模式。Shen等人 [30] 利用空间相关性来跳过一些深度级别和预测模式。

帧内预测模式选择快速算法

• 在"三步快速选择帧内预测模式"策略中, 通过RMD与MPM结合的方式, 在减少RDO所需模式数量方面取得了显著成效. 参考文献[8]探讨了一种基于梯度信息的空间聚类方法. 本研究进一步扩展了这一方法, 在45°与135°方向上也引入了相应的梯度分析.

最优预测模式分布

为了深入研究帧内预测模式选择机制，并从四个不同系列的高分辨率视频序列中进行了实验验证。

其中所选的四个典型视频序列包括：选自JCT-VC标准测试视频集的ParkScene（1080p）、Johnny（720p）、BQMall（480p）和BasketballPass（240p）。这些视频呈现出多样化的场景特征和纹理细节。

本研究主要关注最佳帧内预测模式的空间分布特性。实验采用编码器×265配置下的全帧内编码方案，并设置了量化参数（QP）为32的编码参数设置。每个样本均包含十个连续帧进行编码处理。

统计结果显示如图2所示。

在HEVC编码标准中, 模式编号范围分为水平系列与垂直系列两种类型. 在本研究工作中, 采用新的分类方法: 模式编号7至13归为水平系列, 模式编号23至29归为垂直系列; 而编号范围14至22则被定义为斜向系列. 此外, 编号范围为2至6以及30至34的区域则被称为大斜向系列. 通过图示化分析发现, 平面形态(即编号为0)与DC形态(即编号为1)所占比例高达约24%, 而DC形态又占到了约14%. 这意味着视频图像中的大部分区域都呈现较为平滑且均匀的状态. 除了平面形态与DC形态之外, 最佳角度预估方向主要集中在水平方向(即编号为PU 10)与垂直方向(即编号为PV 26)及其邻近区域上. 这是因为同一帧图像内往往存在较强的空间变化特征主要分布在这些特定的方向上. 同时, 分析结果还表明, 预测单元(PUs)选择斜向系列及大斜向系列的概率分别为7%到8%. 因此, 根据最佳预估方向分布的特点进行分类处理能够显著提升帧内预估效率.

预测模式分组

• 最佳帧内预测模式与预测单元（PU）的方向信息具有密切关联性。梯度信息能够有效地表征PU的方向特性，在本研究中我们采用简单的梯度算子 来计算PU像素亮度分量的空间变化率（如图3所示）。从左到右依次对应水平方向、垂直方向、135°斜向和平面45°斜向四个方向。

在本研究中, 我们称预测单元（PU）在水平方向上的平均梯度为AGH, 在垂直方向上的平均梯度为AGV, 在45°方向上的平均梯度为AGMD, 在135°方向上的平均梯度为AGDD. 其中, AGH 和 AGV 分别为 PU 的水平梯度 |Gx| 和垂直梯度 |Gy| 的均值; AGMD 和 AGDD 则分别代表其对角线方向上的导数值; 如图所示, 其中 N 代表当前预测单元（PU）包含像素的数量, p(i,j) 代表位于预测单元（PU）坐标位置 (i,j) 处的那个像素点亮度值.

• AGMD和AGDD分别是PU的45°梯度|G45|和135°梯度|G135|的均值，如公式(5)-(8)所示。

• 基于AGH、AGV、AGMD和AGDD，我们做出以下假设：

  • (i)如果AGV、AGH、AGMD和AGDD都足够小，PU可以被认为是平坦且均匀的，DC模式或平面模式很可能是最佳预测模式。
  • (ii) 如果AGV大于AGH，水平类模式更可能是最佳预测模式，反之亦然。
  • (iii) 如果AGDD大于AGMD，45°类模式更可能是最佳预测模式，反之亦然。

• 使用BasketballPass和BQMall序列分别评估选择45°类模式的概率φ(AGDD/AGMD)与AGDD/AGMD的关系，以及选择135°类模式的概率φ(AGMD/AGDD)与AGMD/AGDD的关系，如图4a和b所示。如图4所示，对于AGDD/AGMD值大于 2 的 PU，其被选为45°类模式的概率超过80%。相反，对于AGMD/AGDD值大于 2 的PU，其被选为135°类模式的概率超过90%。因此，AGDD/AGMD（AGMD/AGDD）可以用来大致确定PU的45°（135°）类模式。同样，水平类和垂直类模式的判断也符合这些特征。

本研究基于AGH（自动导引高精度）、AGV（自动导引车辆）以及它们的组合形式（如AGH/AGV和AGV/AGH），同时考虑其混合形式（如AGMD/AGDD及其组合形式），将总共35种帧内预测模式进行了系统性归类为10组（见表1）。每组包含特定的模式组合及其对应的数量统计（RMD_num），用于表示进入实时模式处理的数量。

• 每个PU依据四个方向的梯度值选择单一模式组完成RMD过程。
• 模式组决策过程依赖于五个关键阈值（Thsb-e），这些阈值如图5所示。
  这些阈值是通过实验确定的。其中Thsb-e的确定基于最佳预测模式的命中率。
  命中率定义为：设定条件C即梯度比大于相应的Th；满足条件C且其最佳预测模式属于相应组的PU数量为A；满足C的所有PU总数为B；则命中率等于A/B。
  命題率与Thsb-e的关系如图6所示。
  根据图6中的实验结果可知，QP对命中率的影响较小。
  此外，在不同Th取值下命中率呈现阶梯性增长趋势：
  当Th增大时命中率随之提升，
  但计算复杂度会相应降低，
  因此在选取Th时需权衡RD损失与计算复杂度之间的关系。
  基于上述分析，
  我们将目标命中率设定为95%，
  因此可分别选取以下各组参数：
  ** Ths_b = 6**，
  ** Ths_e = 2**，
  ** Thc = 1.5**，
  以及
  ** Thd = 2**。

本研究中针对被分割的CU计算其AGmax（AGH、AGV、AGMD和AGDD）的最大值，在不同QP值和深度层级下展开分析。研究表明当CU发生分割时其对应的AGmax值显著提升因此可以设定一个阈值Th来判断CU是否属于均匀型 CU。当计算得到的AGmax小于该阈值时则判定该CU为均匀型 CU而Threshold Th的具体取值则由 CU 分割过程中的命中率所决定其中目标设定命中率为 95% 不同QP 值与深度层级下的 Th 值均如图7所示标明出来基于设定好的Threshold Th进行分类判断同时将辅助参数 Tha 设置为其计算出的具体数值乘以系数 a 即 a = 0.3 × Th。

预测模式选择快速算法流程

该种三步帧内预测模式快速选择策略包含三个关键步骤：粗糙模式决策（RMD）、最可能模式（MPM）获取以及率失真优化（RDO）。在原有的策略中，在完成粗糙模式决策的过程中需要计算35种预测模式的HAD成本。为了提高效率并降低复杂度，在现有方法的基础上我们提出了一种基于模式分组的帧内预测模抉选择快速算法。具体而言，在完成粗糙模态决策之前，在每个预测单元（PU）中分别计算其水平方向上的平均梯度AGH、垂直方向上的平均梯度AGV、主对角线方向上的平均梯度AGMD以及反对角线方向上的平均梯度AGDD等四个特征指标，并依据各方向平均梯度比例来筛选相应的模板组集合。在此基础上选取具有最小HAD成本的一组模板组合成候选集合，并将其加入到最可能模态获取流程中作为候选对象集合从而生成新的候选集合最终通过率失真优化流程确定最优内部预判模态。

帧内CU尺寸选择快速算法

HEVC基于64\times 64像素的LCU层次化划分机制来决定CU尺寸。

相较于H.264/AVC标准中的固定16\times 16宏块尺寸设定而言，

这种机制可使比特率下降约12\%，

然而其代价是计算复杂度上升。

本研究对CU纹理分布特性进行了深入分析，

并开发出一种综合多类纹理特性的CU尺寸选择方案。

这种新方案实现了高效的动态优化选择。

CU大小与内容的关系

通过研究帧内预测中编码单元（CU）划分与其所承载视频内容之间的关系后发现，在最优选择下，默认采用64×64及32×32大小的CU划分主要对应于视频呈现较为平滑且均匀分布的纹理区域；而16×16及8×8大小的选择则通常对应于细节更为丰富的区域。基于此观察可知,可以通过分析图像的空间纹理特征来优化遍历式四叉树分割策略,从而进一步提升高效率视频编码技术（HEVC）的空间自适应性

多纹理特征提取

• 内容深度 ：基于上述分析，在编码单元（CU）中是否采用四叉树划分主要由其内容深度决定。
  为此开发了一种称为邻域均方误差（NMSE）的量化指标。
  本研究引入了邻域均方误差（NMSE），如公式（9）和（10），以精确衡量编码单元的空间细节。

其中,N代表单元块(CU)的尺寸,p(i,j)是该CU内部坐标为(i,j)像素点的亮度值,pˉ(i,j)则代表该像素点周围八个邻居像素点亮度值的算术平均值.NMSE数值越小,则表明该单元块的空间分布更为均匀.

随着当前CU的平均梯度增大，则其SAG值也会随之提升。

其中，
NMSE_i 和 SAG_i 分别代表四个子 CU 的 NMSE 和 SAG，
NMSE 和 SAG 则分别代表 NMSE_i 和 SAG_i 的平均值。

• 使用 265×265 的超分辨率编码器对 ParkScene 的前 10 帧进行编码，
  QP 设定为 32，
  并获取每个 64×64 CU 的多重纹理特征。
  在图 9a 中，
  X 轴为 log10(NMSE)，
  Y 轴为 log10(Sub_NMSED)；
  红点表示将 64×64 CU 细分为四个 32×32 子 CU，
  黑点则表示不再细分。
  类似地，
  图 9b 反映了 log10(SAG) 和 log10({Sub_SAGD}) 的分布情况。
  从图中可以看出，
  除了少数离群值外，
  红点和黑点呈现出高度集中的趋势；
  这表明这些多纹理特征（NMSE、SAG、Sub_NMSED 和 Sub_SAGD）是判断 CU 是否需要细分的理想指标。

样本校准与模型训练

将需要分裂的编码单元（CU）标记为类别A（Split CUs），而将不需要分裂的CU标记为类别B（Non-split CUs）。基于统计分析结果表明，在NMSE、SAG、Sub_NMSED和Sub_SAGD这些特征维度上存在一定程度的重叠现象，并不能够通过简单的线性手段实现完全区分。因此本研究提出了一种**双支持向量机（SVM）**组合方案用于CU分类。每个SVM都独立地定义了各自的决策函数：
f_i(x) = \text{sign}(\sum_{j=1}^{n} w_{ij}x_j + b_i)

在其中，
xi = [logNMSE, logSAG, logSub_NMSED, logSub_SAGD]^T，
其中log代表基于10的对数计算结果；
yi ∈ {+1,−1}；
+1代表属于类别A，
-1代表属于类别B；
αi是拉格朗日乘子系数，
b是偏移量参数，
M代表训练样本的数量。

我们使用了四个视频序列来训练SVM模型。
在各个深度层次上分别建立了关于类别A和类别B的支持向量机模型。
能够被两个支持向量机模型同时正确分类确定的CU被归类为A类单元；
能够被其中一个支持向量机模型正确分类确定但另一个未能正确分类确定的CU则被视为AB类单元；
无法被这两个模型中的任何一个正确分类确定的CU则被视为C类单元。
详细信息见表2。

CU尺寸选择快速算法流程

• 利用两个支持向量机（SVM）结合多纹理特征信息来确定编码单元（CU）的划分模式，能够显著提高帧内CU四叉树划分的速度。

• 首先提取当前CU的多纹理特征信息，并基于fDepth A (x)和fDepth B (x)进行分类判定：

  • 若判定为A组，则表明当前CU具有较强的复杂度特征，在这种情况下建议直接将其划分为子CU以避免复杂的帧内预测过程（提前分裂策略）。
  • 若判定为B组，则表明当前CU具有较高的平坦度特性，在这种情况下建议提前终止四叉树划分过程以减少计算开销。
  • 在完成当前CU的帧内预测后更新最优划分模式。
  • 若判定为C组，则表示基于现有纹理特征无法快速做出决策，在这种情况下建议按照x265标准算法进行处理并继续划分为子CU。

• 在平坦内容区域中采用提前终止策略可有效降低后续子CU的预测开销；而在复杂内容区域中优先采用提前分裂策略则能显著减少当前CU级别的预测时间开销；两者的结合不仅有助于提升对那些纹理特征差异不明显的编 Unit 的分类准确性而且能够在平衡压缩时间和保真度性能方面取得良好的优化效果。

实验结果与分析

该研究将开源编码器x265作为基准工具使用,因为其在多平台运行时展现出卓越的压缩效率与性能.实验环境采用Intel Core i7-4790处理器,主频3.6 GHz,配备8 GB内存,操作系统为Windows 7 64位系统.编码过程采用了全帧内模式,未启用汇编优化指令,也未启用多线程技术辅助.所有实验数据均基于JCT-VC官方推荐的标准测试视频集,每个视频序列经过100帧编码.

在CU分裂评估指标中,本研究采用了精确度与召回率两个指标来评估分类器的表现.表3列出了不同量化参数设置及各层深度情况下的结果.观察发现,当模型处于最浅层结构时（即深度为0）,其召回率达到最大值,这表明较大的计算单元（如64×64）在分裂与不分裂场景中表现出更强的纹理区分能力.随着模型逐渐加深（如32×32及16×16大小的计算单元）,精确度虽有所提升但召回率却逐步下降.这一现象反映出较大型计算单元相较于较小规模单元更易区分清晰与模糊状态.

• 为了对所提出的快速算法进行性能评估，在性能分析部分采用了ΔTime、ΔBitrate和ΔPSNRy三个指标来衡量其表现效果。实验结果显示：基于模式分组的方法能够平均节省9.44%的编码时间；然而，在PSNR方面出现了略微下降（降噪量减少了0.006 dB），同时bitrate增加了约0.45%。具体而言，在具有复杂前景但背景相对单一的720P视频序列中这一优势表现得更为明显；但对于更为复杂的视频序列（如PartyScene、BQSquare和Cactus），该算法并未带来显著的时间优势。

• 另一个基于多纹理选择策略的CU大小优化算法能够平均节省36.84%的编码时间；然而在bitrate方面出现了略微增长（增加了约0.52%），同时PSNR也出现了轻微下降（降低了0.012 dB）。值得注意的是该算法在所有类型的视频序列上均表现出良好的加速效果：这是因为该方法通过早期分裂策略对复杂纹理区域进行CU划分，并通过早期终止策略对平坦区域进行CU划分从而有效降低了CU选择过程中的计算复杂度。

• 将两种算法综合比较后发现与x265-1.7版本相比，在编码时间上实现了42.80%以上的缩减；bitrate仅增加了约0.98%，而PSNR值仅降低了微乎其微的-0.018 dB水平。此外，在HEVC测试模型（HM）中进行验证时发现，在全帧内模式下该方法表现出良好的加速效果。

最后对比分析了所提方法与其他三种方法的效果平衡性问题。实验结果表明所提方法在时间效率提升与编码效率损失之间实现了理想平衡；同时，在BDPSNR指标上也表现出色

*总体而言, 该研究基于CU纹理特征的提取方法, 并采用SVM技术对CU大小进行判别, 开发出一种高效的快速算法. 该算法较传统方案大幅降低了编码时间, 同时保证了视频质量的稳定性和观感性.

结论

• 为了减少帧内预测模式选择所需的计算复杂度，在本研究中开发了一种基于模式分组的高效帧内预测模式选择算法。
• 为了减少CU四叉树划分所需的计算资源消耗，在本研究中设计了一种基于多纹理特征分析的CU尺寸优化算法。
• 将上述两种优化方案整合后进行编码性能评估。