基于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.