基于CU特征差異的VVC幀內(nèi)快速劃分算法

陳燕輝 李強(qiáng) 董陽(yáng) 明艷

摘 要：針對(duì)通用視頻編碼（versatile video coding，VVC）在編碼單元（coding unit，CU）劃分中引入了多類(lèi)型樹(shù)劃分結(jié)構(gòu)導(dǎo)致編碼復(fù)雜度增加的問(wèn)題，提出了一種基于CU子塊方向特性與空間復(fù)雜度的快速劃分算法。首先利用CU整體的紋理復(fù)雜度對(duì)當(dāng)前CU進(jìn)行分類(lèi)，篩選出不劃分CU；然后利用子塊不同劃分方向的特性差異提前決策CU劃分方向；最后利用CU中間區(qū)域與邊緣區(qū)域的復(fù)雜度差異特征判斷是否跳過(guò)三叉樹(shù)（ternary tree，TT）劃分，進(jìn)一步減少候選列表劃分模式數(shù)量。實(shí)驗(yàn)結(jié)果表明，與官方測(cè)試平臺(tái)VTM10.0相比，編碼器在平均輸出比特率增加1.12％的代價(jià)下，編碼時(shí)間減少了40.25％，說(shuō)明該算法在通用視頻編碼中能以較小的質(zhì)量損失實(shí)現(xiàn)更短的編碼時(shí)間。

關(guān)鍵詞：通用視頻編碼； 編碼單元?jiǎng)澐郑?紋理特征； 快速算法

中圖分類(lèi)號(hào)：TN919.81?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

為滿足未來(lái)視頻編碼的應(yīng)用需求，ITU-T和ISO兩大視頻編碼國(guó)際組織組建聯(lián)合視頻專(zhuān)家小組，共同開(kāi)發(fā)出了新一代視頻編碼標(biāo)準(zhǔn)，并將其命名為通用視頻編碼［1］。VVC第一版于2020年7月正式定稿。

VVC標(biāo)準(zhǔn)仍采用混合編碼框架，但引入了許多新的編碼技術(shù)，如幀內(nèi)編碼模塊中的幀內(nèi)子塊劃分、矩陣加權(quán)預(yù)測(cè)、多參考行幀內(nèi)預(yù)測(cè)等；幀間編碼模塊采用了帶運(yùn)動(dòng)矢量差的merge模式、對(duì)稱(chēng)運(yùn)動(dòng)矢量差分編碼、仿射運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)等［2，3］。通過(guò)使用新的編碼技術(shù)，相比上一代高效視頻編碼（high efficiency video coding，HEVC），VVC的編碼性能提高了50％［4］，但編碼復(fù)雜度大幅上升，在全幀內(nèi)配置下就增加了18倍以上［5］，這使得VVC的實(shí)際應(yīng)用受到限制。因此，在不明顯降低視頻編碼質(zhì)量和效率的前提下，降低VVC的編碼復(fù)雜度成為當(dāng)前視頻編碼應(yīng)用領(lǐng)域研究的一個(gè)重要方向。

VVC在CU劃分過(guò)程中引入了多叉樹(shù)（multi-type tree，MTT）劃分結(jié)構(gòu)，以更靈活地適應(yīng)視頻不同紋理特征，提高編碼效率，但也極大地增加了編碼器的計(jì)算復(fù)雜度。據(jù)統(tǒng)計(jì)分析，視頻編碼器如果禁用MTT劃分結(jié)構(gòu)，可節(jié)省90%的編碼時(shí)間［6］。因此，加快CU劃分可以作為降低VVC編碼計(jì)算復(fù)雜度的一種有效方法。

近些年來(lái)，國(guó)內(nèi)外研究者提出了許多CU快速劃分算法。文獻(xiàn)［7］提出了基于視頻紋理特征的快速?zèng)Q策算法。首先根據(jù)相鄰參考?jí)K的劃分深度終止或跳過(guò)部分非必要的劃分類(lèi)型，并使用優(yōu)化后的Canny算子提取邊緣特性作為CU劃分方向的判決條件，跳過(guò)非最優(yōu)模式。文獻(xiàn)［8］提出一種基于自定義梯度結(jié)構(gòu)相似度的快速劃分算法，通過(guò)計(jì)算當(dāng)前CU下的四個(gè)子塊的平均梯度結(jié)構(gòu)相似度，并通過(guò)設(shè)定的兩個(gè)閾值進(jìn)行四叉樹(shù)劃分或終止劃分的判決；若繼續(xù)劃分，則計(jì)算當(dāng)前CU水平和垂直方向的標(biāo)準(zhǔn)差值，提前決策劃分方向。文獻(xiàn)［9］提出基于空間特征的快速幀內(nèi)二叉樹(shù)劃分決策，使用全局和局部特征符號(hào)化CU的紋理方向，并使用全局特征梯度方差值表示兩個(gè)子CU中編碼塊復(fù)雜度的水平和垂直差異，提前作出判決。文獻(xiàn)［10］提出，通過(guò)計(jì)算不同方向上灰度共生矩陣的相關(guān)性，提前判斷編碼塊的劃分方向。文獻(xiàn)［11］提出基于紋理特征和機(jī)器學(xué)習(xí)的幀內(nèi)快速?zèng)Q策算法，使用平均絕對(duì)差定義紋理復(fù)雜度，對(duì)紋理復(fù)雜的編碼塊需進(jìn)一步提取全局信息、局部信息、上下文信息，分類(lèi)器利用這些信息跳過(guò)冗余劃分模式，從而降低編碼復(fù)雜度。文獻(xiàn)［12］提出一種基于改進(jìn)的支持向量機(jī)分類(lèi)模型的編碼塊快速劃分方法，將VVC中編碼塊劃分問(wèn)題視為一個(gè)多分類(lèi)問(wèn)題，采用改進(jìn)的F-score方法提取與CU劃分高相關(guān)性的特征進(jìn)行訓(xùn)練，從而加速編碼。文獻(xiàn)［13，14］提出基于CNN的快速?zèng)Q策算法，將傳統(tǒng)CU是否劃分問(wèn)題轉(zhuǎn)換為當(dāng)前編碼塊劃分深度區(qū)間問(wèn)題，直接預(yù)測(cè)劃分深度，從而加快VVC幀內(nèi)編碼速度。文獻(xiàn)［15］提出形狀自適應(yīng)CNN的CU決策算法，充分利用池化層保留原始信息，經(jīng)訓(xùn)練網(wǎng)絡(luò)決策是否進(jìn)行劃分，從而避免完整的RD計(jì)算。文獻(xiàn)［16］提出基于ML的輕量級(jí)可調(diào)QTBT分區(qū)方法，使用隨機(jī)森林分類(lèi)器為編碼塊確定劃分模式，并通過(guò)改變風(fēng)險(xiǎn)區(qū)間大小，在編碼復(fù)雜度降低和編碼損失之間實(shí)現(xiàn)可調(diào)控平衡。

阿里巴巴開(kāi)發(fā)出了能實(shí)際應(yīng)用的實(shí)時(shí)H.266/VVC軟件編碼器Ali266。為了提升編碼速度，Ali266使用了基于梯度的MTT快速判決方法，利用編碼幀的紋理變化特性對(duì)CU劃分進(jìn)行快速?zèng)Q策。具體為通過(guò)計(jì)算CU四個(gè)方向的梯度評(píng)估紋理變化的劇烈程度，若水平方向梯度大于另外三個(gè)方向梯度且大于一定閾值時(shí)，說(shuō)明水平方向紋理變化劇烈，因此跳過(guò)水平方向的二叉樹(shù)與三叉樹(shù)劃分過(guò)程。該方法利用紋理方向與劃分方向的關(guān)聯(lián)性，并通過(guò)統(tǒng)計(jì)學(xué)方法得到梯度值、閾值與劃分決策的關(guān)系，實(shí)現(xiàn)了MTT的快速?zèng)Q策，使編碼器能獲得14.8%的加速效果，編碼效率損失僅為0.4%。

CU快速劃分算法對(duì)視頻紋理的表征有限，使用機(jī)器學(xué)習(xí)等方法進(jìn)行編碼加速時(shí)，性能受選擇特征的限制。因此，本文提出基于子塊方向特性與復(fù)雜度特性的CU快速劃分算法，通過(guò)使用信息熵對(duì)紋理方向特性進(jìn)行表征，并利用相鄰子塊間復(fù)雜度的比較，篩選不必要的劃分模式，從而達(dá)到降低編碼復(fù)雜度的目的。

1 VVC的CU劃分結(jié)構(gòu)

VVC編碼器把視頻的每一幀劃分為一個(gè)個(gè)編碼樹(shù)單元（coding tree unit，CTU），而后基于CTU進(jìn)行CU劃分。HEVC中CTU的大小為64×64，使用四叉樹(shù)劃分結(jié)構(gòu)將CTU劃分為四個(gè)CU，每一個(gè)CU可以劃分為一個(gè)或多個(gè)預(yù)測(cè)單元（prediction unit，PU）參與預(yù)測(cè)，CU也可以按四叉樹(shù)遞歸的方式劃分成多個(gè)變換單元（transform unit，TU）參與預(yù)測(cè)和變換。但在VVC中，CTU大小為128×128，將CTU劃分為CU后，在大多數(shù)情況下都將CU作為預(yù)測(cè)、變換和編碼的基本單元。VVC擯棄了HEVC中PU、TU的概念。在劃分結(jié)構(gòu)上，VVC還引入了多叉樹(shù)劃分結(jié)構(gòu)。該結(jié)構(gòu)包括水平二叉樹(shù)（horizontal binary tree，HBT）、垂直二叉樹(shù)（vertical binary tree，VBT）、水平三叉樹(shù)（horizontal ternary tree，HTT）和垂直三叉樹(shù)（vertical ternary tree，VTT）四種結(jié)構(gòu)。多叉樹(shù)劃分只應(yīng)用于四叉樹(shù)葉子節(jié)點(diǎn)，并且在進(jìn)行多叉樹(shù)劃分后不允許使用四叉樹(shù)劃分。

CTU劃分有自上而下和自下而上兩個(gè)過(guò)程。自上而下過(guò)程為父CU遍歷劃分模式列表進(jìn)行劃分，并保存各個(gè)劃分模式下的率失真代價(jià)，直到劃分到葉子節(jié)點(diǎn)；然后再通過(guò)自下而上比較子CU與父CU的率失真代價(jià)大小，保留率失真代價(jià)最小的劃分模式，得到當(dāng)前CTU的最優(yōu)劃分結(jié)構(gòu)。圖1展示了一種CTU劃分結(jié)構(gòu)。

圖2是圖1對(duì)應(yīng)的劃分結(jié)構(gòu)樹(shù)，從圖中可以看出，隨著劃分深度的增加，編碼器需要遍歷的分支也急劇增加，計(jì)算量增大。因此，在CU劃分過(guò)程中，如果可以對(duì)劃分樹(shù)進(jìn)行廣度和深度，即分支數(shù)和根深度兩個(gè)方面的縮減，則可以明顯降低編碼復(fù)雜度，節(jié)省編碼時(shí)間。

2 CU快速劃分算法

本章首先根據(jù)CU紋理復(fù)雜度對(duì)CU進(jìn)行分類(lèi)；之后根據(jù)子塊不同劃分方向上的特性判斷多類(lèi)型樹(shù)的劃分方向；最后通過(guò)子塊間的復(fù)雜度差異跳過(guò)三叉樹(shù)劃分過(guò)程。

2.1 CU劃分快速?zèng)Q策

在宏觀層面，可以將CU分為簡(jiǎn)單塊和復(fù)雜塊。簡(jiǎn)單塊具有紋理簡(jiǎn)單圖像平坦的特性；而復(fù)雜塊為細(xì)節(jié)豐富圖像復(fù)雜的編碼塊。圖3為序列basketballDrill中第一幀部分區(qū)域CU的劃分結(jié)果圖。從圖中可以看出，對(duì)于簡(jiǎn)單塊，如塊A，內(nèi)容簡(jiǎn)單且該區(qū)域無(wú)明顯的紋理變化，編碼器趨向于使用不劃分模式將該區(qū)域劃分為大尺寸的編碼塊；相反地，對(duì)于紋理復(fù)雜的區(qū)域，如塊B，細(xì)節(jié)豐富，包含著黃色條帶與淺色地板塊，紋理變化明顯，編碼器趨向于進(jìn)行劃分操作，將該區(qū)域劃分為小尺寸的編碼塊。因此，可以利用當(dāng)前編碼塊的紋理復(fù)雜度作為是否進(jìn)行劃分的判決條件。VVC中多類(lèi)型樹(shù)劃分結(jié)構(gòu)允許的最大劃分尺寸為32×32，四叉樹(shù)劃分允許的最大葉子節(jié)點(diǎn)為16×16，CU尺寸在該范圍內(nèi)的CU需要遍歷的模式最多，并且對(duì)于小尺寸CU，其執(zhí)行劃分過(guò)程所需時(shí)間較少，加速效果不明顯，因此，本文算法作用對(duì)象為32×32和16×16的CU。

由上述分析可知，編碼單元是否劃分與紋理復(fù)雜度相關(guān)，當(dāng)前編碼塊內(nèi)的像素離散程度可以體現(xiàn)紋理復(fù)雜程度。由于像素的方差可以較好地體現(xiàn)出像素的離散程度，所以本文使用圖像紋理標(biāo)準(zhǔn)差SD計(jì)算當(dāng)前CU的紋理復(fù)雜度，并對(duì)當(dāng)前CU進(jìn)行分類(lèi)，其計(jì)算公式如下：

本文算法性能測(cè)試結(jié)果如表2所示。

針對(duì)六類(lèi)22個(gè)不同視頻序列，本文算法都有著良好的加速效果，平均節(jié)省40.25%的編碼時(shí)間，BDBR僅增加1.12%，綜合性能達(dá)到35.94。本文算法除個(gè)別視頻序列外，其加速時(shí)間基本相差不大，針對(duì)超高清視頻，如A1和A2類(lèi)序列也是有著不錯(cuò)的加速效果，因此本文算法具有較好的普適性。從對(duì)比結(jié)果可知，本文算法綜合性能明顯優(yōu)于文獻(xiàn)［17］，并且文獻(xiàn)［17］算法在D類(lèi)別視頻中的加速效果較其他差異較大，而本文算法在各類(lèi)視頻中均有著良好的表現(xiàn)。

為了進(jìn)一步分析本文算法率失真性能，給出如圖9所示的blowingBubbles和basketballPass序列的率失真曲線。從圖中可以看出，本文算法的率失真曲線也與原始平臺(tái)VTM10.0的率失真曲線基本重合。這表明本文算法在保持編碼性能損失很小的同時(shí)，能顯著降低編碼復(fù)雜度。

4 結(jié)束語(yǔ)

本文針對(duì)VVC編碼復(fù)雜度過(guò)高的問(wèn)題，提出一種基于編碼單元復(fù)雜度及其子塊方向特征的CU快速劃分算法。首先根據(jù)當(dāng)前CU復(fù)雜度對(duì)其進(jìn)行是否繼續(xù)劃分的判決，然后根據(jù)子塊的方向特性對(duì)CU進(jìn)行劃分方向的決策，最后利用相鄰子塊間的復(fù)雜度差異對(duì)CU進(jìn)行三叉樹(shù)劃分跳過(guò)的判斷。本文算法在編碼時(shí)間與編碼效率損失之間取得了良好的平衡。下一步可以使該算法適配到更多不同尺寸的編碼塊，并拓展到幀間預(yù)測(cè)CU劃分過(guò)程中，以進(jìn)一步提高編碼速度。

參考文獻(xiàn)：

［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的高效幀內(nèi)編碼方案研究［D］. 鄭州：鄭州輕工業(yè)大學(xué)， 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］張煥宸. 視頻編碼標(biāo)準(zhǔn)H.266/VVC幀內(nèi)快速算法研究［D］. 武漢：華中科技大學(xué)， 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.