基于CU特征差异的VVC帧内快速划分算法

陈燕辉 李强 董阳 明艳

摘 要：针对通用视频编码（versatile video coding，VVC）在编码单元（coding unit，CU）划分中引入了多类型树划分结构导致编码复杂度增加的问题，提出了一种基于CU子块方向特性与空间复杂度的快速划分算法。首先利用CU整体的纹理复杂度对当前CU进行分类，筛选出不划分CU；然后利用子块不同划分方向的特性差异提前决策CU划分方向；最后利用CU中间区域与边缘区域的复杂度差异特征判断是否跳过三叉树（ternary tree，TT）划分，进一步减少候选列表划分模式数量。实验结果表明，与官方测试平台VTM10.0相比，编码器在平均输出比特率增加1.12％的代价下，编码时间减少了40.25％，说明该算法在通用视频编码中能以较小的质量损失实现更短的编码时间。

关键词：通用视频编码； 编码单元划分； 纹理特征； 快速算法

中图分类号：TN919.81   文献标志码：A

文章编号：1001-3695（2024）03-045-0939-05

doi：10.19734/j.issn.1001-3695.2023.06.0268

Intra-frame FAST division algorithm of VVC based on CU feature difference

Chen Yanhui1，2， Li Qiang1，2， Dong Yang1，2， Ming Yan1

（1.School of Communications & Information Engineering， Chongqing University of Posts & Telecommunications， Chongqing 400065， China; 2.Chongqing Key Laboratory of Signal & Information Processing， Chongqing 400065， China）

Abstract：Aiming at the problem of multi-type tree division structure in coding unit（CU） division in versatile video coding（VVC） ， this paper proposed a fast division algorithm based on the orientation characteristics and spatial complexity of CU subblocks. Firstly， this paper used the overall texture complexity of CU to classify the current CU and filtered out the CU that was not divided. Then， this method used the difference in the characteristics of different division directions of subblocks to decide the CU division direction in advance. Finally， the algorithm used the complexity difference feature between the middle region and the edge region of CU to determine whether to skip the ternary tree（TT） division， which further reduced the number of candidate list division patterns. The experimental results show that compared with the official test platform VTM10.0， the encoder reduces the encoding time by 40.25% at the cost of increasing the average output bit rate by 1.12%， indicating that the algorithm can achieve shorter encoding time with less quality loss in versatile video coding.

Key words：versatile video coding; coding unit partition; texture features; FAST algorithm

0 引言

為满足未来视频编码的应用需求，ITU-T和ISO两大视频编码国际组织组建联合视频专家小组，共同开发出了新一代视频编码标准，并将其命名为通用视频编码［1］。VVC第一版于2020年7月正式定稿。

VVC标准仍采用混合编码框架，但引入了许多新的编码技术，如帧内编码模块中的帧内子块划分、矩阵加权预测、多参考行帧内预测等；帧间编码模块采用了带运动矢量差的merge模式、对称运动矢量差分编码、仿射运动补偿预测等［2，3］。通过使用新的编码技术，相比上一代高效视频编码（high efficiency video coding，HEVC），VVC的编码性能提高了50％［4］，但编码复杂度大幅上升，在全帧内配置下就增加了18倍以上［5］，这使得VVC的实际应用受到限制。因此，在不明显降低视频编码质量和效率的前提下，降低VVC的编码复杂度成为当前视频编码应用领域研究的一个重要方向。

VVC在CU划分过程中引入了多叉树（multi-type tree，MTT）划分结构，以更灵活地适应视频不同纹理特征，提高编码效率，但也极大地增加了编码器的计算复杂度。据统计分析，视频编码器如果禁用MTT划分结构，可节省90%的编码时间［6］。因此，加快CU划分可以作为降低VVC编码计算复杂度的一种有效方法。

近些年来，国内外研究者提出了许多CU快速划分算法。文献［7］提出了基于视频纹理特征的快速决策算法。首先根据相邻参考块的划分深度终止或跳过部分非必要的划分类型，并使用优化后的Canny算子提取边缘特性作为CU划分方向的判决条件，跳过非最优模式。文献［8］提出一种基于自定义梯度结构相似度的快速划分算法，通过计算当前CU下的四个子块的平均梯度结构相似度，并通过设定的两个阈值进行四叉树划分或终止划分的判决；若继续划分，则计算当前CU水平和垂直方向的标准差值，提前决策划分方向。文献［9］提出基于空间特征的快速帧内二叉树划分决策，使用全局和局部特征符号化CU的纹理方向，并使用全局特征梯度方差值表示两个子CU中编码块复杂度的水平和垂直差异，提前作出判决。文献［10］提出，通过计算不同方向上灰度共生矩阵的相关性，提前判断编码块的划分方向。文献［11］提出基于纹理特征和机器学习的帧内快速决策算法，使用平均绝对差定义纹理复杂度，对纹理复杂的编码块需进一步提取全局信息、局部信息、上下文信息，分类器利用这些信息跳过冗余划分模式，从而降低编码复杂度。文献［12］提出一种基于改进的支持向量机分类模型的编码块快速划分方法，将VVC中编码块划分问题视为一个多分类问题，采用改进的F-score方法提取与CU划分高相关性的特征进行训练，从而加速编码。文献［13，14］提出基于CNN的快速决策算法，将传统CU是否划分问题转换为当前编码块划分深度区间问题，直接预测划分深度，从而加快VVC帧内编码速度。文献［15］提出形状自适应CNN的CU决策算法，充分利用池化层保留原始信息，经训练网络决策是否进行划分，从而避免完整的RD计算。文献［16］提出基于ML的轻量级可调QTBT分区方法，使用随机森林分类器为编码块确定划分模式，并通过改变风险区间大小，在编码复杂度降低和编码损失之间实现可调控平衡。

阿里巴巴开发出了能实际应用的实时H.266/VVC软件编码器Ali266。为了提升编码速度，Ali266使用了基于梯度的MTT快速判决方法，利用编码帧的纹理变化特性对CU划分进行快速决策。具体为通过计算CU四个方向的梯度评估纹理变化的剧烈程度，若水平方向梯度大于另外三个方向梯度且大于一定阈值时，说明水平方向纹理变化剧烈，因此跳过水平方向的二叉树与三叉树划分过程。该方法利用纹理方向与划分方向的关联性，并通过统计学方法得到梯度值、阈值与划分决策的关系，实现了MTT的快速决策，使编码器能获得14.8%的加速效果，编码效率损失仅为0.4%。

CU快速划分算法对视频纹理的表征有限，使用机器学习等方法进行编码加速时，性能受选择特征的限制。因此，本文提出基于子块方向特性与复杂度特性的CU快速划分算法，通过使用信息熵对纹理方向特性进行表征，并利用相邻子块间复杂度的比较，筛选不必要的划分模式，从而达到降低编码复杂度的目的。

1 VVC的CU划分结构

VVC编码器把视频的每一帧划分为一个个编码树单元（coding tree unit，CTU），而后基于CTU进行CU划分。HEVC中CTU的大小为64×64，使用四叉树划分结构将CTU划分为四个CU，每一个CU可以划分为一个或多个预测单元（prediction unit，PU）参与预测，CU也可以按四叉树递归的方式划分成多个变换单元（transform unit，TU）参与预测和变换。但在VVC中，CTU大小为128×128，将CTU划分为CU后，在大多数情况下都将CU作为预测、变换和编码的基本单元。VVC摈弃了HEVC中PU、TU的概念。在划分结构上，VVC还引入了多叉树划分结构。该结构包括水平二叉树（horizontal binary tree，HBT）、垂直二叉树（vertical binary tree，VBT）、水平三叉树（horizontal ternary tree，HTT）和垂直三叉树（vertical ternary tree，VTT）四种结构。多叉树划分只应用于四叉树叶子节点，并且在进行多叉树划分后不允许使用四叉树划分。

CTU划分有自上而下和自下而上两个过程。自上而下过程为父CU遍历划分模式列表进行划分，并保存各个划分模式下的率失真代价，直到划分到叶子节点；然后再通过自下而上比较子CU与父CU的率失真代价大小，保留率失真代价最小的划分模式，得到当前CTU的最优划分结构。图1展示了一种CTU划分结构。

图2是图1对应的划分结构树，从图中可以看出，随着划分深度的增加，编码器需要遍歷的分支也急剧增加，计算量增大。因此，在CU划分过程中，如果可以对划分树进行广度和深度，即分支数和根深度两个方面的缩减，则可以明显降低编码复杂度，节省编码时间。

2 CU快速划分算法

本章首先根据CU纹理复杂度对CU进行分类；之后根据子块不同划分方向上的特性判断多类型树的划分方向；最后通过子块间的复杂度差异跳过三叉树划分过程。

2.1 CU划分快速决策

在宏观层面，可以将CU分为简单块和复杂块。简单块具有纹理简单图像平坦的特性；而复杂块为细节丰富图像复杂的编码块。图3为序列basketballDrill中第一帧部分区域CU的划分结果图。从图中可以看出，对于简单块，如块A，内容简单且该区域无明显的纹理变化，编码器趋向于使用不划分模式将该区域划分为大尺寸的编码块；相反地，对于纹理复杂的区域，如块B，细节丰富，包含着黄色条带与浅色地板块，纹理变化明显，编码器趋向于进行划分操作，将该区域划分为小尺寸的编码块。因此，可以利用当前编码块的纹理复杂度作为是否进行划分的判决条件。VVC中多类型树划分结构允许的最大划分尺寸为32×32，四叉树划分允许的最大叶子节点为16×16，CU尺寸在该范围内的CU需要遍历的模式最多，并且对于小尺寸CU，其执行划分过程所需时间较少，加速效果不明显，因此，本文算法作用对象为32×32和16×16的CU。

由上述分析可知，编码单元是否划分与纹理复杂度相关，当前编码块内的像素离散程度可以体现纹理复杂程度。由于像素的方差可以较好地体现出像素的离散程度，所以本文使用图像纹理标准差SD计算当前CU的纹理复杂度，并对当前CU进行分类，其计算公式如下：

本文算法性能测试结果如表2所示。

针对六类22个不同视频序列，本文算法都有着良好的加速效果，平均节省40.25%的编码时间，BDBR仅增加1.12%，综合性能达到35.94。本文算法除个别视频序列外，其加速时间基本相差不大，针对超高清视频，如A1和A2类序列也是有着不错的加速效果，因此本文算法具有较好的普适性。从对比结果可知，本文算法综合性能明显优于文献［17］，并且文献［17］算法在D类别视频中的加速效果較其他差异较大，而本文算法在各类视频中均有着良好的表现。

为了进一步分析本文算法率失真性能，给出如图9所示的blowingBubbles和basketballPass序列的率失真曲线。从图中可以看出，本文算法的率失真曲线也与原始平台VTM10.0的率失真曲线基本重合。这表明本文算法在保持编码性能损失很小的同时，能显著降低编码复杂度。

4 结束语

本文针对VVC编码复杂度过高的问题，提出一种基于编码单元复杂度及其子块方向特征的CU快速划分算法。首先根据当前CU复杂度对其进行是否继续划分的判决，然后根据子块的方向特性对CU进行划分方向的决策，最后利用相邻子块间的复杂度差异对CU进行三叉树划分跳过的判断。本文算法在编码时间与编码效率损失之间取得了良好的平衡。下一步可以使该算法适配到更多不同尺寸的编码块，并拓展到帧间预测CU划分过程中，以进一步提高编码速度。

参考文献：

［1］ITU-T. Versatile video coding： ITU-T Rec. H. 266 version 1［S］. 2020.

［2］Wieckowski A， Hinz T， George V， et al. Next software： an alternative implementation the joint exploration model（JEM）［R/OL］. （2017-12-06）. https：//jvet.experts.org/doc_end_user/current_document.php？id=3366.

［3］Wang Zhao， Meng Xuewei， Jia Chuanmin， et al. Description of SDR video coding technology proposal by DJI and Peking University. JVET-J0011［EB/OL］.（2018-04-11）. https：//jvet.experts.org/doc_end_user/current_document.php？id=3447.

［4］Bross B， Chen Jianle， Ohm J-R， et al. Developments in international video coding standardization after AVC， with an overview of versatile video coding（VVC）［J］.Proceedings of the IEEE， 2021，109（9）：1463-1493.

［5］Pakdaman F， Adelimanesh M A， Gabbouj M， et al. Complexity ana-lysis of next-generation VVC encoding and decoding［C］//Proc of IEEE International Conference on Image Processing. Piscataway， NJ： IEEE Press， 2020： 3134-3138.

［6］Saldanha M， Sanchez G， Marcon C， et al. Complexity analysis of VVC intra coding［C］//Proc of IEEE International Conference on Image Processing. Piscataway， NJ： IEEE Press， 2020： 3119-3123.

［7］崔腾耀. 基于H.266/VVC的高效帧内编码方案研究［D］. 郑州：郑州轻工业大学， 2022. （Cui Tengyao. Research on efficient intra-frame coding scheme based on H.266/VVC［D］. Zhengzhou： Zhengzhou University of Light Industry， 2022.）

［8］Jing Zhiyong， Li Peng， Zhao Jinchao， et al. A fast CU partition algorithm based on gradient structural similarity and texture features［J］. Symmetry， 2022，14（12）： 2644.

［9］Lin Tinglan， Jiang Huiyu， Huang Jingya， et al. Fast binary tree partition decision in H.266/FVC intra coding［C］//Proc of IEEE International Conference on Consumer Electronics. Piscataway， NJ： IEEE Press， 2018： 1-2.

［10］張焕宸. 视频编码标准H.266/VVC帧内快速算法研究［D］. 武汉：华中科技大学， 2021. （Zhang Huanchen. Research on intra-frame fast algorithm of video coding standard H. 266/VVC［D］. Wuhan： Huazhong University of Science and Technology， 2021.）

［11］Zhao Jinchao， Li Peng， Zhang Qiuwen. A fast decision algorithm for VVC intra-coding based on texture feature and machine learning［J/OL］. Computational Intelligence and Neuroscience. （2022-01-01）. https：//doi.org/10.1155/2022/7675749.

［12］Zhang Qiuwen， Wang Yihan， Huang Lixun， et al. Fast CU partition decision for H.266/VVC based on the improved DAG-SVM classifier model［J］. Multimedia Systems， 2021， 27：1-14.

［13］Jin Zhipeng， An Ping， Shen Liquan， et al. CNN oriented fast QTBT partition algorithm for JVET intra coding［C］//Proc of IEEE Visual Communications and Image Processing. Piscataway， NJ： IEEE Press， 2017： 1-4.

［14］Jin Zhipeng， An Ping， Yang Chao， et al. Fast QTBT partition algorithm for intra frame coding through convolutional neural network［J］. IEEE Access， 2018，6： 54660-54673.

［15］Tang Genwei， Jing Minge， Zeng Xiaoyang， et al. Adaptive CU split decision with pooling-variable CNN for VVC intra encoding［C］//Proc of IEEE Visual Communications and Image Processing. Pisca-taway， NJ： IEEE Press， 2019：1-4.

［16］Amestoy T， Mercat A， Hamidouche W， et al. Tunable VVC frame partitioning based on lightweight machine learning［J］. IEEE Trans on Image Processing， 2019，29： 1313-1328.

［17］Feng Aolin， Liu Kang， Liu Dong， et al. Partition map prediction for fast block partitioning in VVC intra-frame coding［J］. IEEE Trans on Image Processing， 2023，32：2237-2251.