VVC幀間編碼CU快速劃分算法

褚嘉璐，李 強

重慶郵電大學 通信與信息工程學院，重慶 400065

由ISO/IEC的MPEG和ITU-T的VCEG聯合制定的新一代視頻編碼標準——通用視頻編碼（versatile video coding，VVC）已于2020年7月正式發布。該標準技術將應用于4K視頻、8K視頻、直播和沉浸式媒體等多種商用場景。

VVC仍沿用基于塊編碼的技術，在上一代高效視頻編碼（high efficiency video coding，HEVC）框架[1]基礎上通過引入許多新技術提高了編碼效率。如在CU劃分的過程中引入了更加靈活的多類型樹劃分[2]；在幀間預測中引入融合仿射運動預測[3]、幾何塊融合[4]、運動矢量差的融合[5]、幀內幀間聯合預測[6]等新技術。目前VVC的測試模型VTM（VVC test model）已更新至VTM10.0版本。根據文獻[7]，與HEVC的測試模型（HEVC test model，HM）相比，VTM10.0在隨機接入（random access，RA）模式下的編碼性能提升了38.42%，但編碼時間卻增加了977%，這使得VVC難以投入實際應用。因此在保證視頻質量基本不變、編碼性能損失較小的情況下，如何大幅度減少VVC的計算復雜度成了當前視頻編碼研究者的重點研究方向。

近些年來，很多研究者通過分析VVC幀間編碼過程，借鑒HEVC幀間編碼快速算法原理，提出了很多視頻編碼幀間預測加速方案，其中最直接有效的方法就是CU劃分的提前終止。文獻[8]提出了一種基于三幀差分的方法，先計算當前幀與兩個參考幀對應位置像素絕對值之差，通過比較差值大于閾值的數量占CU總像素數量的比重，判斷當前區域是否相對靜止，決定是否跳過CU劃分；文獻[9]提出了限制劃分層次的快速幀間預測算法，通過限制編碼樹單元（coding tree unit，CTU）在劃分過程中的最大深度，提前結束CU劃分過程；文獻[10]使用了機器學習的方法，訓練了多個基于隨機森林的分類器，為每個CU選擇最可能的劃分模式，從而加速了編碼過程。在對HEVC的相關研究中，文獻[11]針對監控和會議視頻的場景，提出了基于虛擬背景幀的快速幀間編碼方法，利用幀間的時域相關性生成虛擬背景幀，進而對CU分類并限制劃分深度，達成加速編碼的目的；文獻[12]利用當前CU與空時域相鄰CU的相關性縮小當前CU需遍歷的深度范圍，從而減小編碼計算量；文獻[13]設計了一種基于卷積神經網絡的快速CU決策算法，減少了待遍歷的CU尺寸的數量，進而達到加速的效果。

幀間預測加速算法通常需要使用參考幀中的信息，利用幀與幀之間的相關性來消除視頻序列的時間冗余，如文獻[8]與文獻[11]使用了已編碼幀的像素信息，文獻[12]則使用了參考幀中CU深度信息。在目前的幀間加速算法中，充分利用參考幀的運動矢量信息進行編碼加速的算法較少。本文對VVC幀間編碼的CU劃分進行了研究，提出了一種基于參考幀運動矢量分布的CU劃分模式提前選擇方法。為了進一步加快編碼速度，本文還提出了一種基于空域相鄰CU預測模式的CU劃分深度提前終止方法。這兩種方法的結合能夠在編碼性能和圖像質量損失較小的前提下，顯著加快編碼速度。

1 VVC的CU塊劃分結構

在視頻編碼過程中，視頻序列首先被分為若干個圖像組（group of pictures，GOP），一個GOP有若干圖片。根據常規環境測試（common test condition，CTC）[14]，在RA模式下，一個GOP有16幀，第1幀為使用幀內預測的I幀，其余為使用幀間預測的B幀。在圖1所示的一個GOP中，POC0作為I幀第一個被編碼，GOP中的最后一幀POC16作為B幀第二個被編碼，后續的編碼順序為8、4、2、1、3、6、5、7、12、10、9、11、14、13、15，先被編碼的幀會作為后續編碼的參考幀。

圖1 GOP編碼順序Fig.1 GOP coding order

幀是塊劃分的基本單位[15]，在對一個B幀進行編碼時，每一幀圖像首先會被分為若干個CTU，再基于CTU進行下一步劃分。HEVC的CTU大小為64×64，通過四叉樹（quad-tree，QT）將CTU劃分為CU，CU再進一步被劃分為預測單元（prediction unit，PU）和變換單元（transform unit，TU）。而VVC的CTU尺寸變為128×128，并取消了CU、PU和TU的劃分，即CTU劃分為CU之后直接進行預測和變換。

VVC使用嵌套多叉樹的四叉樹（quad-tree with nested multi-type-tree，QTMTT）結構對CTU進行劃分。MTT的結構包括垂直二叉樹（vertical binary tree，VBT）、水平二叉樹（horizontal binary tree，HBT）、垂直三叉樹（vertical ternary tree，VTT）以及水平三叉樹（horizontal ternary tree，HTT）。VBT與HBT將塊按照1∶1分成兩部分，而VTT與HTT類似HEVC中PU的非對稱劃分模式，將CU按對應方向進行1∶2∶1劃分。

圖2是一個CTU劃分的例子，編碼器若判決需對CTU進行QT劃分，則對大小為64×64的塊進行QT或MTT劃分，但MTT劃分之后不再允許進行QT劃分，直到塊的長或寬等于4為止。

圖2 CTU劃分實例Fig.2 CTU partitioning example

圖3是圖2對應的QTMTT結構示意圖，是該CTU最終選擇的編碼樹劃分結構。在CTU的劃分過程中，編碼器的率失真優化（rate-distortion optimization，RDO）是一個深度優先遍歷的過程（depth first search，DFS），遍歷每一種劃分的可能性并計算率失真代價[16]（ratedistortion cost，RD-cost），然后選取RD-cost最小的劃分作為最終結果。由于VVC采用了更加靈活的劃分方式，隨著劃分層數的加深，RDO需要遍歷樹的分支急劇增多，因此編碼運算量大幅度增加。在CU劃分過程中，如果能減少劃分模式或者減小遍歷的深度，就可以明顯降低編碼復雜度，加快編碼速度。

圖3 QTMTT結構示意圖Fig.3 QTMTT structure schematic diagram

2 CU快速劃分算法

2.1 VVC的CU劃分過程

VTM10.0的CU劃分流程如圖4所示。第一步是初始化CU。編碼器將所有允許執行的劃分模式放入一個先進后出的棧中，候選棧中的劃分模式越多，當前節點的下一層分支就越多，編碼復雜度就越高；第二步，編碼器計算當前CU執行跳過（skip）、融合（merge）、幀間運動估計（inter ME）等預測模式的RD-cost，并選取RD-cost最小的模式作為當前CU最優模式；第三步按順序逐個調用之前棧中存放的劃分模式，并根據當前CU尺寸以及執行過的劃分順序，確認是否可以執行該模式，如果可以，就將CU劃分為子CU，并以遞歸的形式重復第一步。因此在初始化CU時，如果能減少棧中的劃分模式個數，就可減少下一層的分支數量，降低CU劃分的復雜度。在執行幀間預測模式之后，若能不進入下一層劃分，就能加快CU劃分速度。

圖4 VVC編碼CU流程圖Fig.4 Flowchart of VVC encoding CU process

2.2 CU劃分模式的提前選擇

2.2.1幀間編碼運動矢量特性分析

在幀間編碼過程中，編碼器通過運動估計（motion estimation，ME）為當前編碼塊在參考幀中尋找相似塊。當前塊與相似塊在空間上的相對位置即為運動矢量（motion vector，MV）。圖5是MV分布與CU劃分的例子。通常一個區域內紋理越復雜，MV分布越密集，CU劃分就越細致；相對的，一個區域紋理越簡單，或者MV的分布越稀疏，CU劃分就越簡略。

圖5 GOP中的兩幀Fig.5 Two frames in GOP

圖5中的視頻幀（a）和（b）是同一GOP中的兩個B幀，編碼順序（a）在（b）之前，但時間上（a）在（b）之后，（a）是（b）的參考幀。在圖中，橢圓圈內的區域是紋理較復雜的靜止區域，這些區域在（a）中劃分層數較深，而在（b）中劃分的層數相對淺；對于圖像中移動的行人，在（a）中這部分區域的MV分布密集，說明該區域運動狀態相對復雜，CU也相應地被劃分為更小的塊，對應地，在（b）中相應的運動區域的CU也被劃分為更小的塊，兩幀中的對應區域在CU的劃分特征上呈現了高度的相關性。對于右下角新出現的運動物體，編碼器無法通過ME在參考幀中找到對應的塊，因此采用幀內預測的方式進行編碼，這些塊通常也會被劃分得很小，并且沒有MV信息。

2.2.2CU劃分模式提前選擇算法

因為參考幀的MV分布的疏密程度與當前編碼CU劃分的細致程度存在明顯的相關性，所以為了加速CU的劃分過程，本文提出了一種基于參考幀對應區域MV分布特性的CU劃分提前選擇算法。通過判斷參考幀對應區域的MV分布特性，提前選擇一種或者幾種劃分模式，進而減少需要遍歷的劃分模式個數，從而達到加速編碼的效果

首先確定當前區域的MV是否具有一致性。本文采取的方法如圖6所示第一步是獲取與當前CU相鄰的上CU和左CU的MV。若兩個MV不一致，則說明當前區域和參考幀對應區域的運動情況復雜，MV分布情況無法準確地指導當前CU的劃分。如果二者相等，則說明當前區域的運動有較高的一致性。參考幀對應位置坐標以公式（1）和（2）的方式計算。其中，Xcol和Ycol是參考幀中對應位置的橫坐標和縱坐標，Xcur和Ycur是當前編碼CU的橫坐標和縱坐標，MV x和MV y是當前編碼CU相鄰的MV的橫向分量和縱向分量。

圖6 獲取相鄰CU的MVFig.6 Deriving MVs of adjacent CUs

其次獲取參考幀的MV。本文獲取參考幀MV的模型如圖7所示，當前編碼CU是一個如圖7（a）所示的正方形時，在參考幀對應區域以同樣的長和寬總共取9個點的MV，取樣點位于邊長的1/4，1/2，3/4處；若當前編碼的CU是類似圖7（b）或（c）所示的矩形，則按照與當前CU相同的形狀，在參考幀對應區域取6個點的MV。（b）和（c）中取樣點的距離，較長的邊為1/4，1/2，3/4，較短的邊為1/4，3/4。

圖7 獲取MV的三種模型Fig.7 Three models of deriving MVs

結合VTM10.0中編碼器的特性，本文算法在獲取MV的過程中有如下性質：

（1）取MV的過程與參考幀中對應區域的CU劃分方式無關。以圖7（a）為例，取9個采樣點并不意味著該區域會有對應的9個CU。如果1、2、3點對應的MV屬于同一CU，或者1、2、3點所屬不同CU，但它們的MV相同，那么從1、2、3點所取到的MV將完全相同。

（2）因為CU長和寬的最小值為4，所以對于圖7（b）和（c）的情況，本文算法只考慮矩形最短邊的邊長大于等于8，較長的邊大于等于12的情況，對于圖7（a）只考慮長和寬大于等于12的情況。

（3）參考幀中的取樣點如果超出了圖像范圍，則不使用提前選擇算法。

最后通過分析參考幀中MV的分布特點，將部分劃分模式加入候選棧中，然后編碼器從這些模式中選出最可能的劃分方式。

CU劃分模式提前選擇算法流程如圖8所示。

圖8 CU劃分模式提前選擇算法流程圖Fig.8 Flowchart of early selection algorithm for CU partition modes

（1）判斷相鄰MV是否一致，若不一致，則使用VTM10.0原有的方法進行初始化，否則進入下一步驟。

（2）通過當前CU坐標加MV的偏移得到參考幀對應位置坐標。

（3）判斷當前CU是否為正方形，如是正方形，使用9MV模型，否則進入步驟（4）。

①判斷1，2，3點的MV是否一致。若一致，進入②；如果不一致，則判斷1，4，7的MV，如果一致，則將HTT和HBT模式入棧，如果不一致，則將QT，VTT，HTT模式入棧。

②判斷4，5，6的MV是否一致，若一致，則進入③，否則將VTT和VBT模式加入棧。

③判斷7，8，9的MV是否一致，若一致，則進入④，否則將VTT和VBT模式加入棧。

④若所有MV一致，則不向棧中添加任何模式，否則僅將VTT模式加入棧。

（4）若CU的長大于寬，則在參考幀中使用橫向6MV模型，否則進入步驟（5）。

①若1，2不一致，但1，3，5一致，則將HTT和HBT加入棧；若1，3，5不一致，則加入VTT和HTT模式；若1，2一致，則進入②。

②若3，4不一致，則添加VTT和VBT模式進入棧；若一致，進入③。

③若5，6不一致，則添加VTT和VBT進入棧，否則進入④。

④若所有MV一致，則不加入劃分模式，否則僅將VTT模式加入棧。

（5）CU的長小于寬，使用縱向6MV模型。

①若1，2不一致，且1，3，5不一致，則加VTT，HTT模式；若1，3，5一致則添加VTT，VBT模式；若1，2一致，則進入②。

②若3，4不一致，則將HTT，HBT入棧，若一致，進入③。

③若5，6不一致，則將HTT和HBT入棧。否則進入④。

④若所有MV一致，則不加入劃分模式，否則僅將HTT加入棧。

（6）結束初始化CU。

2.3 CU劃分深度的提前終止

2.3.1相鄰CU空域相關性分析

目前很多視頻編碼快速算法研究利用編碼CU的空域相關性加速其劃分過程，如文獻[12]在HEVC中利用尺寸相近的相鄰CU的深度提前終止CU劃分。在VVC以前的視頻編碼標準中，具有同樣劃分深度的塊意味著具有同樣的尺寸，因此可以直接參考相鄰塊的深度來輔助編碼CU的劃分。但VVC由于引入了更靈活的塊劃分機制，相同深度下塊的尺寸很有可能不相同。在VTM10.0中，當前CU深度值用currDepth來描述，其數值表示經歷過的劃分次數。例如當前CU經歷過2次QT劃分，2次BTT劃分，那么currDepth為4，此時的CU長和寬分別為32和8。但如果經歷了4次QT劃分，currDepth為4，但是此時的CU的長和寬都為8，與前者在尺寸上相差了4倍。因此想要找到與當前CU尺寸相近或相同的塊，應直接比較長和寬的值，而非深度值。

由于圖像相鄰像素空域相關性強，相鄰CU的最優預測模式通常會呈現較高的一致性。例如，序列中如果一個區域紋理簡單，運動緩慢，則該區域的CU很大可能以skip模式作為最優的預測模式；如果一個區域的運動有一致性，則該區域CU可能以Merge模式作為最優預測模式；但某個區域有突然出現的物體，由于參考幀中沒有對應的像素塊，該區域的CU會選擇幀內預測作為最優預測模式。為了統計相鄰CU的空域相關性，本文選取了如表1所示的四個特征不同的序列，對于每個CU以及相鄰尺寸相同CU的最優預測模式進行了統計。

表1 四種測試序列及其特征Table 1 Four test sequences and their features

本文在統計時，考慮了當前CU的左、左下、左上、上、右上五個方向的相鄰CU的預測模式信息。在RA模式下，量化參數（quantity parameter，QP）取22，27，32，37，每個序列測試兩個GOP（32幀）。統計在與當前CU有兩個及以上相同尺寸CU的前提下，這些同尺寸CU的最優預測模式與當前CU最優預測模式相同的概率，I幀的數據不計入結果，統計數據如表2所示。

表2 同尺寸CU預測模式相同的概率Table 2 Probability of same size CUs having same prediction mode %

由表2可知，在四個不同QP值下，相鄰同尺寸CU與當前CU預測模式相同的概率分別為80.45%、76.60%、74.71%和75.30%。可以看出在空間上相鄰CU的預測模式具有較高相關性。但相關性與序列運動特性有關，如運動劇烈的RaceHorses序列，這種相關性相對要小些；而運動復雜程度一般，且紋理簡單的Johnny序列，則相關性相對更大。

根據表2的統計結果，由于圖像中相鄰像素在空域的相關性，同尺寸相鄰CU的預測模式具有較高的參考價值，若它們的最優預測模式與當前CU相同，則當前的劃分深度可能是最優深度，不必繼續向下劃分。在對CTU的率失真優化過程中，編碼器會選擇RD-cost最小的劃分結果作為最優劃分。公式（3）是RD-cost的計算公式：

其中，J即是RD-cost；R是編碼比特率，用來衡量編碼效率；D是失真，衡量重建塊與原始塊的差別。如果將CU劃分得更小，失真這一指標會明顯降低，但另一方面需要表示該CU信息的比特數會增加，因此RD-cost是一個綜合的指標。

2.3.2CU劃分深度提前終止算法

根據以上分析可知，在當前CU選擇了與相鄰同尺寸CU相同的預測模式的前提下，如果RD-cost小于它們的平均值，則可以認為當前塊的劃分比較合理，進一步劃分帶來的性能收益可能比較小。針對這種特性，本文提出了劃分深度提前終止算法，通過參考相鄰CU的尺寸、預測模式以及RD-cost決定是否進入下一深度劃分。算法的流程如圖9所示。

（1）按照相鄰的上、左上、右上、左的順序獲取五個相鄰CU的編碼信息。

（2）判斷是否有兩個及以上可用的相鄰CU，其判斷方式如下：

①如果相鄰CU與當前CU尺寸不同，則該CU不可用。

②如果相鄰CU最優預測方式與當前CU不同，則該CU不可用。

（3）按照公式（4）計算RD-cost的平均值AvgCost，

其中CurCost是當前CU的RD-cost，n為相鄰可用CU的個數。

（4）如果當前CU的RD-cost小于平均RD-cost，則停止劃分，否則進一步劃分。

3 實驗結果及分析

本文算法在VTM10.0上進行了實現，并在配置為Intel?CoreTMi7-9750H CPU的Windows10平臺上進行了測試。按照CTC標準，在RA模式下，GOP為16，CTU為128×128，每32幀中有一幀是I幀，其他為B幀。測試序列分為B，C，D，E，F這5個類型共20個測試序列，量化參數QP分別取22，27，32，37。以BD-BR（Bjntegaard delta bit rate）和BD-PSNR（Bjntegaard delta peak signal to noise ratio）[17]分別表示本文提出的算法與原平臺在編碼效率和圖像質量的變化。BD-BR越高，說明編碼效率損失得越多，BD-PSNR越接近0，說明圖像質量損失越小。ΔT表示本文算法的編碼時間相較于原平臺編碼時間的提升百分比，公式（5）是其計算公式，其中TVTM10.0和Tproposed分別表示VTM10.0和采用本文算法的編碼時長，QPi對應在不同QP值下進行測試的數據。

最終測試結果如表3所示。

表3 本文算法與VTM10.0對比Table 3 Performance comparisons with VTM10.0

對比VTM10.0算法，在RA模式下，本文提出的算法在編碼時間上平均減少了39.28%，而視頻的平均PSNR損失為0.05 dB，平均輸出比特率增加了1.62%。針對高分辨率視頻序列，加速性能較好。對于如RaceHorses，BasketballDrive這類運動劇烈的序列，編碼效率和圖像質量損失相對較大。對于Kimono，BQMall這類運動平緩的序列，在編碼速度上有較大的提升。測試數據表明，在RA模式下，本文算法能夠有效降低編碼復雜度，加速幀間編碼的過程。

文獻[8]使用三幀差分算法實現幀間編碼的加速，同樣利用了GOP中幀與幀之間的時域相關性。由于文獻[8]的測試平臺是較早VTM3.0版本，因此將本文所提算法移植到VTM3.0中進行了性能測試。并且在F序列中，改用了與文獻[8]相同的ChinaSpeed，另外由于文獻[8]沒有給出BD-PSNR指標，因此本文也沒列出該項指標。

比較結果如表4所示。BQTerrace，BQSquare，Basketballpass這類攝像頭運動拍攝的測試序列由于視頻中靜止的區域較少，因此文獻[8]算法的加速效果相對較差，而本文算法加速性能較好；對于運動和紋理簡單，紋理簡單的FourPeople，Johnny，SlideEditing序列，本文算法要略好于文獻[8]算法。而針對運動復雜，紋理復雜的RaceHorses，BasketballDrive，本文算法在BDBR上的損失較小。從平均結果來看，在VTM3.0平臺上采用本文算法，可實現37.23%的編碼速度提升，相較于文獻[8]算法編碼速率提速了5.8%，但編碼輸出比特率增加了0.23%。

表4 本文算法與文獻[8]對比Table 4 Performance comparisons with paper[8]

4 結束語

本文針對VVC編碼復雜度過高的問題，提出了一種基于時空域的CU劃分快速算法。首先利用時域參考幀MV分布特性，篩選掉部分劃分模式，減少需要遍歷的分支。然后，分析當前CU與空域相鄰同尺寸CU預測模式的一致性，決定是否進入下一深度進行遍歷，減小了CU劃分的深度。實驗結果表明，在輸出比特率上升有限，視頻質量損失很小的前提下，本文算法明顯降低了編碼復雜度，加速了編碼過程。