一种VVC帧内编码单元快速划分算法

陶浩然，路锦正，2，李意弦

1(西南科技大学 信息工程学院，四川 绵阳 621010)2(特殊环境机器人技术四川省重点实验室，四川 绵阳 621010)

1 引 言

人们对高质量视频的需求，例如现场视频、视频会议、实时手稿、全景视频和虚拟现实，视频编码标准得以快速发展.由ISO动态影像专家组(MPEG)和ITU-T视频编码专家组(VCEG)的专家组成的联合视频探索小组(JVET)委员会于2015年开始制定下一代视频编码标准VVC，旨在大幅超越高效视频编码(HEVC).但是，编码性能的提高不可避免地增加了计算复杂度.因此在不影响VVC编码性能的基础上，如何降低帧内编码复杂度成为了当前VVC研究的热点.

许多学者[1-6]通过分析图像纹理与CU划分之间的关系，提出HEVC提前终止四叉树(QT)划分的算法.唐[7]等人利用相邻单元的时空域相关性，提出一种提前中止或跳过不必要的深度的HEVC快速算法.岑[8]等人提出了一种基于决策树的编码单元划分.敬[9]等人根据图像相邻块的结构相似度关系，提出一种HEVC帧内预测编码单元快速划分算法.张[10]等人将率失真(RD)代价作为阈值参数，提出一种适合HEVC帧内预测的快速算法.由于这些工作基于HEVC，以及HEVC和VVC之间的树划分结构不同，尽管具有出色的性能，但无法直接适用于VVC中.

对于VVC中的嵌套多类型树(QTMT)，我们不仅需要考虑何时提前终止划分，还要考虑如何划分CU.Fu[11]等人通过探索VVC中当前CU及其水平划分的子CU的相关性，提出了一种新的基于贝叶斯规则的快速二叉树划分算法.Yao[12],Zouidi[13]等人通过统计分析考虑角度预测的模式使用率，提出了简化预测模式数量的快速帧内预测算法.C[14],Park[15]通过利用先前CU编码中的RD代价，提出了基于RD代价的提前终止块划分算法.Chen[16]参考VVC相邻最大编码单元(LCU)的平均深度信息来确定是否提前终止CU划分，该方法可以有效地消除不必要的RDO操作.

以上技术文献均在一定程度上减少了编码复杂度，节省了编码的时间开销，但对于帧内信息都未达到充分利用，编码效率还有提升空间.本文主要针对VVC帧内编码中的CU划分进行优化，利用MGMSD求QT划分的子CU的相似度以跳过QT划分和不划分，以及利用MT(多类型树)划分的子CU像素方差的方差选择最佳MT划分.实验结果表明，在保证图像质量与压缩效率基本不变的条件下，基于本方法可显著降低VVC帧内编码复杂度.本文第2节简述了VVC的帧内编码，第3节介绍了本文提出的算法原理，第4节展示并分析了实验结果.

2 VVC帧内编码

在VVC中，块编码结构作为编码层的核心，得益于灵活的块大小，获得了良好的编码性能.VVC采用QTMT作为块划分结构来适应各种纹理模式的特征，以支持更灵活的CU划分形状.MT划分有四种划分类型如图1所示：垂直二叉树划分(BT_V)、水平二叉树划分(BT_H)、垂直三叉树划分(TT_V)和水平三叉树划分(TT_H).此外，为了简化CTU的划分过程，一旦CU被MT划分，QT在随后的划分过程中就不再使用.QTMT结构的简图如图2所示.实心黑线表示QT划分，虚线表示MT划分.

图1 MT划分Fig.1 MT division

图2 QTMT编码块结构实例Fig.2 QTMT coding block structure example

为了找到CU大小和相应的模式的最佳组合，CTU首先被QT结构划分成四个等大小的正方形子单元，每个子单元可以递归地被QT划分成正方形CU或被MT划分成矩形CU.在每个CU深度依次进行QTMT划分和帧内预测，为了找到每个CTU对应的内部模式的最佳划分结构，VTM遍历所有可能的组合来执行率失真优化(RDO)过程，选择RDO成本最小的模式作为优化模式.由于RDO过于复杂，导致帧内预测非常耗时.虽然与HEVC相比，需要通过RDO过程的模式数减少了，但是复杂的划分结构仍然是导致VVC编码时间显著增加的原因之一.通过减少需要进行RDO的CU数量，可减少花费在RDO上的总时间，达到提升编码效率的目的.

3 基于梯度幅值偏差的快速块划分

在VVC中，正方形CU的尺寸可以从128×128到最小的4×4，而矩形CU的尺寸可以从64×64到最小的4×4.因为CU在尺寸128×128的时候默认QT划分成4个尺寸为64×64的子CU，直接通过算法跳过64×64的CU划分可能会导致编码性能的巨大损失，而对小CU的预测只会影响很小的一部分编码性能.于是，本文决定采用梯度幅值相似度偏差算法来确定32×32大小的CU的划分，在质量和效率之间达到一个很好的平衡.

3.1 梯度幅值相似度偏差

Xue[17]提出了一种基于梯度幅值相似度(GMS)的图像质量评价方法——梯度相似度偏差(GMSD).GMSD算法效率高、准确度高，并且效果良好.因此，将其用来计算QT划分的子块相似度，其模型定义为：

Prewitt滤波算子模板沿水平方向和垂直方向定义如图3所示.

图3 Prewitt算子模板Fig.3 Prewitt operator template

将图3算子模板分别对子块r和对比子块d进行卷积生成r和d的水平方向和垂直方向的梯度值，表达式如式(1)所示:

Rx(i,j)≈([r(i-1,j-1)+r(i,j-1)+r(i+1,j-1)]-
[r(i-1,j+1)+r(i,j+1)+r(i+1,j+1)])/3
Ry(i,j)≈([r(i-1,j-1)+r(i-1,j)+r(i-1,j+1)]-
[r(i+1,j-1)+r(i+1,j)+r(i+1,j+1)])/3
Dx(i,j)≈([d(i-1,j-1)+d(i,j-1)+d(i+1,j-1)]-
[d(i-1,j+1)+d(i,j+1)+d(i+1,j+1)])/3
Dy(i,j)≈([d(i-1,j-1)+d(i-1,j)+d(i-1,j+1)]-
[d(i+1,j-1)+d(i+1,j)+d(i+1,j+1)])/3

(1)

式中，Rx(i,j)和Ry(i,j)分别表示为子块r的水平方向和垂直方向的梯度值.Dx(i,j)和Dy(i,j)分别表示为子块d的水平方向和垂直方向的梯度值.r(i,j)和d(i,j)分别为子块r和d的像素点(i,j)的值.

子块r、d在位置(i,j)处的梯度幅值大小，记为mr(i,j)和md(i,j).mr(i,j)和md(i,j)的计算如下式(2)所示：

(2)

有了梯度幅值图像mr(i,j)和md(i,j)，梯度幅值相似度(GMS(i,j))计算如下(3)所示:

(3)

其中c=1.70，它提供数值稳定性.

将平均池化应用于GMS得到GMSM(梯度相似度均值)，如式(4)所示：

(4)

其中N为图像块像素的总个数.

基于图像局部质量退化的全局变化可以反映整体质量的思想，Xue提出计算GMSM map的标准差并以此作为最终的指标，即梯度幅值相似度偏差(GMSD)，如式(5)所示:

(5)

为将基于梯度幅值相似度偏差应用于CU分块的判断中，本文定义CU的平均梯度幅值相似度偏差——MGMSD，其计算公式如式(6)所示：

(6)

计算QT划分4个子CU的相似度，得到6个相似度值，并将这6个值求均值得到当前CU的MGMSD，计算过程如图4所示.

图4 MGMSD求值流程图Fig.4 MGMSD evaluation flowchart

3.2 基于平均梯度幅值相似度偏差的划分决策

为了降低复杂度，本文提出了有效的基于MGMSD的VVC帧内编码算法.该算法的决策框架如图5所示.该方法通过早期确定QTMT划分策略，跳过不必要的划分方式，降低了计算复杂度.

图5 基于MGMSD的快速划分算法流程图Fig.5 Flow chart of fast partition algorithm based on MGMSD

步骤1.根据公式分别计算当前CU下的4个子块每两个子块之间的相似度，得到6个GMSD值，然后通过求均值得到MGMSD.

步骤2.如果MGMSD小于阈值TH1，则不进行树划分，直接以当前CU进行帧内角度预测模式遍历以及编码，并结束当前CU的递归遍历.

步骤3.当MGMSD大于阈值TH2时，直接进行QT划分，将当前CU划分成4个更小的CU,即跳过当前CU的递归遍历，并且直接进入当前CU的四个子CU中进行子CU的递归遍历.

步骤4.如果MGMSD大于阈值TH1的同时小于阈值TH2，则在MT划分条件下计算不同划分情况下的子块像素方差的方差.例如，水平二叉树划分是将当前CU划分成上下两个子CU，分别对上子CU和下子CU求像素方差，再对它们的方差求方差.

当得出4种MT各自划分的子块像素方差的方差时，选择方差最大值相对应的划分方式作为当前CU的唯一划分方式.这样计算是因为当块被划分成具有相对不同纹理的子块时，往往每个子块像素方差的差异往往很大.

通过分析阈值TH1和TH2的特征，发现它们与量化参数(QP)正相关.于是定义阈值TH1和TH2如式(7)和式(8)所示：

TH1=α×QP

(7)

TH2=β×QP

(8)

通过设定不同的α和β值对各种分辨率视频序列的划分进行统计分析，当α=0.006和β=0.0083时，本文方法命中率最高，命中率统计结果如表1所示.

表1 在α=0.006和β=0.0083的条件下各种视频序列的划分命中率统计Table 1 Hit rate statistics of various video sequences under the conditions of α=0.006 and β=0.0083

QT划分比是指在所有MGMSD≥TH2的CU中，有平均83.8%的CU进行了四叉树划分.MT划分比是指在所有的TH1≤MGMSD≤TH2的CU中，有平均84.5%的CU进行了多叉树划分.不划分比是指在所有的MGMSD≤TH1的CU中，有平均74.9%的CU不进行划分.从以上数据可以看出了，MGMSD在提取图像细节有着较好的性能，也在一定程度上证明了本文方法的有效性.

4 实验结果及分析

为了验证本文方法的有效性，在VTM7.0上加入本算法，对比标准算法与本文方法，以验证编码性能.

所用实验平台硬件配置为Intel Core I5-7400 CPU，主频为3.00GHz，内存为16GB.为了使得结果更为严谨，本文使用多种不同分辨率大小的测试视频进行验证，同时设置不同量化值(QP=22、27、32、37).通过BDBR以及时间缩减量ΔT来评价本文算法的编码性能.

时间缩减量ΔT，如式(9)所示，若ΔT的值越大，代表缩短的编码时间越多.

(9)

其中，TVTM是采用VTM标准算法所花的时间，Tproposed是采用本文算法所花时间.

本文将不同分辨率的视频序列分为多组分别测试算法效果，测试结果如表2所示.如图6-图8中，将本文算法与VVC原始算法的率失真曲线进行对比，可以看出，本文所提算法的率失真曲线和VTM的率失真曲线非常接近.这表明针对不同分辨率大小的测试序列，本算法都不同程度地缩减了编码时间，降低了编码复杂度，而视频质量损失可忽略不计.

图6 BasketballDril序列R-D曲线Fig.6 R-D curve of BasketballDril sequence

图7 Johnny序列R-D曲线Fig.7 Johnny sequence R-D curve

图8 BQTerrace序列R-D曲线Fig.8 R-D curve of BQTerrace sequence

表2 基于MGMSD的划分决策算法性能Table 2 Performance of partition decision algorithm based on MGMSD

表3 本文算法与文献[15]、文献[18]、文献[19]实验结果Table 3 This paper′s algorithm and literature [15],literature [18],literature [19] experimental results

将本算法分别与Park[15]、Tang[18]、Yang[19]的算法进行比较，对比结果如表3所示.本算法与Park、Tang所提算法具有相似的效果，但显著优于Yang所提算法.本算法比特率增长略高于Park、Tang所提算法，略低于Yang所提算法.

通过分析上述结果，本文算法整体效果优于Yang所提算法.相较于Park、Tang所提算法，编码效率提升明显，图像质量损失很少，总体性能更加优异.本文算法在保持比特率与峰值信噪比无明显下降的情况下，有效的缩短了帧内编码时间，提升了编码效率.

5 结束语

本文提出了一种快速QTMT划分决策方法，以减少新的MTT分块概念带来的计算复杂度.通过MGMSD得到子CU的平均相似度值来达到CU快速QT划分以及跳过QT的目的.同时利用不同划分方式的子CU的像素方差的方差差异大，将需要遍历的多叉树划分方式从四减为一.实验结果表明，本文算法在图像效果与码率基本不变的情况下，帧内编码时间显著降低，有效的提升了编码效率.在将来的研究中,可通过帧内编码模式快速选取进一步降低帧内编码复杂度,持续提升VVC算法的实时性.