一種VVC幀內(nèi)編碼單元快速劃分算法

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

1(西南科技大學(xué) 信息工程學(xué)院，四川 綿陽 621010)2(特殊環(huán)境機器人技術(shù)四川省重點實驗室，四川 綿陽 621010)

1 引 言

人們對高質(zhì)量視頻的需求，例如現(xiàn)場視頻、視頻會議、實時手稿、全景視頻和虛擬現(xiàn)實，視頻編碼標(biāo)準(zhǔn)得以快速發(fā)展.由ISO動態(tài)影像專家組(MPEG)和ITU-T視頻編碼專家組(VCEG)的專家組成的聯(lián)合視頻探索小組(JVET)委員會于2015年開始制定下一代視頻編碼標(biāo)準(zhǔn)VVC，旨在大幅超越高效視頻編碼(HEVC).但是，編碼性能的提高不可避免地增加了計算復(fù)雜度.因此在不影響VVC編碼性能的基礎(chǔ)上，如何降低幀內(nèi)編碼復(fù)雜度成為了當(dāng)前VVC研究的熱點.

許多學(xué)者[1-6]通過分析圖像紋理與CU劃分之間的關(guān)系，提出HEVC提前終止四叉樹(QT)劃分的算法.唐[7]等人利用相鄰單元的時空域相關(guān)性，提出一種提前中止或跳過不必要的深度的HEVC快速算法.岑[8]等人提出了一種基于決策樹的編碼單元劃分.敬[9]等人根據(jù)圖像相鄰塊的結(jié)構(gòu)相似度關(guān)系，提出一種HEVC幀內(nèi)預(yù)測編碼單元快速劃分算法.張[10]等人將率失真(RD)代價作為閾值參數(shù)，提出一種適合HEVC幀內(nèi)預(yù)測的快速算法.由于這些工作基于HEVC，以及HEVC和VVC之間的樹劃分結(jié)構(gòu)不同，盡管具有出色的性能，但無法直接適用于VVC中.

對于VVC中的嵌套多類型樹(QTMT)，我們不僅需要考慮何時提前終止劃分，還要考慮如何劃分CU.Fu[11]等人通過探索VVC中當(dāng)前CU及其水平劃分的子CU的相關(guān)性，提出了一種新的基于貝葉斯規(guī)則的快速二叉樹劃分算法.Yao[12],Zouidi[13]等人通過統(tǒng)計分析考慮角度預(yù)測的模式使用率，提出了簡化預(yù)測模式數(shù)量的快速幀內(nèi)預(yù)測算法.C[14],Park[15]通過利用先前CU編碼中的RD代價，提出了基于RD代價的提前終止塊劃分算法.Chen[16]參考VVC相鄰最大編碼單元(LCU)的平均深度信息來確定是否提前終止CU劃分，該方法可以有效地消除不必要的RDO操作.

以上技術(shù)文獻均在一定程度上減少了編碼復(fù)雜度，節(jié)省了編碼的時間開銷，但對于幀內(nèi)信息都未達到充分利用，編碼效率還有提升空間.本文主要針對VVC幀內(nèi)編碼中的CU劃分進行優(yōu)化，利用MGMSD求QT劃分的子CU的相似度以跳過QT劃分和不劃分，以及利用MT(多類型樹)劃分的子CU像素方差的方差選擇最佳MT劃分.實驗結(jié)果表明，在保證圖像質(zhì)量與壓縮效率基本不變的條件下，基于本方法可顯著降低VVC幀內(nèi)編碼復(fù)雜度.本文第2節(jié)簡述了VVC的幀內(nèi)編碼，第3節(jié)介紹了本文提出的算法原理，第4節(jié)展示并分析了實驗結(jié)果.

2 VVC幀內(nèi)編碼

在VVC中，塊編碼結(jié)構(gòu)作為編碼層的核心，得益于靈活的塊大小，獲得了良好的編碼性能.VVC采用QTMT作為塊劃分結(jié)構(gòu)來適應(yīng)各種紋理模式的特征，以支持更靈活的CU劃分形狀.MT劃分有四種劃分類型如圖1所示：垂直二叉樹劃分(BT_V)、水平二叉樹劃分(BT_H)、垂直三叉樹劃分(TT_V)和水平三叉樹劃分(TT_H).此外，為了簡化CTU的劃分過程，一旦CU被MT劃分，QT在隨后的劃分過程中就不再使用.QTMT結(jié)構(gòu)的簡圖如圖2所示.實心黑線表示QT劃分，虛線表示MT劃分.

圖1 MT劃分Fig.1 MT division

圖2 QTMT編碼塊結(jié)構(gòu)實例Fig.2 QTMT coding block structure example

為了找到CU大小和相應(yīng)的模式的最佳組合，CTU首先被QT結(jié)構(gòu)劃分成四個等大小的正方形子單元，每個子單元可以遞歸地被QT劃分成正方形CU或被MT劃分成矩形CU.在每個CU深度依次進行QTMT劃分和幀內(nèi)預(yù)測，為了找到每個CTU對應(yīng)的內(nèi)部模式的最佳劃分結(jié)構(gòu)，VTM遍歷所有可能的組合來執(zhí)行率失真優(yōu)化(RDO)過程，選擇RDO成本最小的模式作為優(yōu)化模式.由于RDO過于復(fù)雜，導(dǎo)致幀內(nèi)預(yù)測非常耗時.雖然與HEVC相比，需要通過RDO過程的模式數(shù)減少了，但是復(fù)雜的劃分結(jié)構(gòu)仍然是導(dǎo)致VVC編碼時間顯著增加的原因之一.通過減少需要進行RDO的CU數(shù)量，可減少花費在RDO上的總時間，達到提升編碼效率的目的.

3 基于梯度幅值偏差的快速塊劃分

在VVC中，正方形CU的尺寸可以從128×128到最小的4×4，而矩形CU的尺寸可以從64×64到最小的4×4.因為CU在尺寸128×128的時候默認(rèn)QT劃分成4個尺寸為64×64的子CU，直接通過算法跳過64×64的CU劃分可能會導(dǎo)致編碼性能的巨大損失，而對小CU的預(yù)測只會影響很小的一部分編碼性能.于是，本文決定采用梯度幅值相似度偏差算法來確定32×32大小的CU的劃分，在質(zhì)量和效率之間達到一個很好的平衡.

3.1 梯度幅值相似度偏差

Xue[17]提出了一種基于梯度幅值相似度(GMS)的圖像質(zhì)量評價方法——梯度相似度偏差(GMSD).GMSD算法效率高、準(zhǔn)確度高，并且效果良好.因此，將其用來計算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，它提供數(shù)值穩(wěn)定性.

將平均池化應(yīng)用于GMS得到GMSM(梯度相似度均值)，如式(4)所示：

(4)

其中N為圖像塊像素的總個數(shù).

基于圖像局部質(zhì)量退化的全局變化可以反映整體質(zhì)量的思想，Xue提出計算GMSM map的標(biāo)準(zhǔn)差并以此作為最終的指標(biāo)，即梯度幅值相似度偏差(GMSD)，如式(5)所示:

(5)

為將基于梯度幅值相似度偏差應(yīng)用于CU分塊的判斷中，本文定義CU的平均梯度幅值相似度偏差——MGMSD，其計算公式如式(6)所示：

(6)

計算QT劃分4個子CU的相似度，得到6個相似度值，并將這6個值求均值得到當(dāng)前CU的MGMSD，計算過程如圖4所示.

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

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

為了降低復(fù)雜度，本文提出了有效的基于MGMSD的VVC幀內(nèi)編碼算法.該算法的決策框架如圖5所示.該方法通過早期確定QTMT劃分策略，跳過不必要的劃分方式，降低了計算復(fù)雜度.

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

步驟1.根據(jù)公式分別計算當(dāng)前CU下的4個子塊每兩個子塊之間的相似度，得到6個GMSD值，然后通過求均值得到MGMSD.

步驟2.如果MGMSD小于閾值TH1，則不進行樹劃分，直接以當(dāng)前CU進行幀內(nèi)角度預(yù)測模式遍歷以及編碼，并結(jié)束當(dāng)前CU的遞歸遍歷.

步驟3.當(dāng)MGMSD大于閾值TH2時，直接進行QT劃分，將當(dāng)前CU劃分成4個更小的CU,即跳過當(dāng)前CU的遞歸遍歷，并且直接進入當(dāng)前CU的四個子CU中進行子CU的遞歸遍歷.

步驟4.如果MGMSD大于閾值TH1的同時小于閾值TH2，則在MT劃分條件下計算不同劃分情況下的子塊像素方差的方差.例如，水平二叉樹劃分是將當(dāng)前CU劃分成上下兩個子CU，分別對上子CU和下子CU求像素方差，再對它們的方差求方差.

當(dāng)?shù)贸?種MT各自劃分的子塊像素方差的方差時，選擇方差最大值相對應(yīng)的劃分方式作為當(dāng)前CU的唯一劃分方式.這樣計算是因為當(dāng)塊被劃分成具有相對不同紋理的子塊時，往往每個子塊像素方差的差異往往很大.

通過分析閾值TH1和TH2的特征，發(fā)現(xiàn)它們與量化參數(shù)(QP)正相關(guān).于是定義閾值TH1和TH2如式(7)和式(8)所示：

TH1=α×QP

(7)

TH2=β×QP

(8)

通過設(shè)定不同的α和β值對各種分辨率視頻序列的劃分進行統(tǒng)計分析，當(dāng)α=0.006和β=0.0083時，本文方法命中率最高，命中率統(tǒng)計結(jié)果如表1所示.

表1 在α=0.006和β=0.0083的條件下各種視頻序列的劃分命中率統(tǒng)計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不進行劃分.從以上數(shù)據(jù)可以看出了，MGMSD在提取圖像細節(jié)有著較好的性能，也在一定程度上證明了本文方法的有效性.

4 實驗結(jié)果及分析

為了驗證本文方法的有效性，在VTM7.0上加入本算法，對比標(biāo)準(zhǔn)算法與本文方法，以驗證編碼性能.

所用實驗平臺硬件配置為Intel Core I5-7400 CPU，主頻為3.00GHz，內(nèi)存為16GB.為了使得結(jié)果更為嚴(yán)謹(jǐn)，本文使用多種不同分辨率大小的測試視頻進行驗證，同時設(shè)置不同量化值(QP=22、27、32、37).通過BDBR以及時間縮減量ΔT來評價本文算法的編碼性能.

時間縮減量ΔT，如式(9)所示，若ΔT的值越大，代表縮短的編碼時間越多.

(9)

其中，TVTM是采用VTM標(biāo)準(zhǔn)算法所花的時間，Tproposed是采用本文算法所花時間.

本文將不同分辨率的視頻序列分為多組分別測試算法效果，測試結(jié)果如表2所示.如圖6-圖8中，將本文算法與VVC原始算法的率失真曲線進行對比，可以看出，本文所提算法的率失真曲線和VTM的率失真曲線非常接近.這表明針對不同分辨率大小的測試序列，本算法都不同程度地縮減了編碼時間，降低了編碼復(fù)雜度，而視頻質(zhì)量損失可忽略不計.

圖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]實驗結(jié)果Table 3 This paper′s algorithm and literature [15],literature [18],literature [19] experimental results

將本算法分別與Park[15]、Tang[18]、Yang[19]的算法進行比較，對比結(jié)果如表3所示.本算法與Park、Tang所提算法具有相似的效果，但顯著優(yōu)于Yang所提算法.本算法比特率增長略高于Park、Tang所提算法，略低于Yang所提算法.

通過分析上述結(jié)果，本文算法整體效果優(yōu)于Yang所提算法.相較于Park、Tang所提算法，編碼效率提升明顯，圖像質(zhì)量損失很少，總體性能更加優(yōu)異.本文算法在保持比特率與峰值信噪比無明顯下降的情況下，有效的縮短了幀內(nèi)編碼時間，提升了編碼效率.

5 結(jié)束語

本文提出了一種快速Q(mào)TMT劃分決策方法，以減少新的MTT分塊概念帶來的計算復(fù)雜度.通過MGMSD得到子CU的平均相似度值來達到CU快速Q(mào)T劃分以及跳過QT的目的.同時利用不同劃分方式的子CU的像素方差的方差差異大，將需要遍歷的多叉樹劃分方式從四減為一.實驗結(jié)果表明，本文算法在圖像效果與碼率基本不變的情況下，幀內(nèi)編碼時間顯著降低，有效的提升了編碼效率.在將來的研究中,可通過幀內(nèi)編碼模式快速選取進一步降低幀內(nèi)編碼復(fù)雜度,持續(xù)提升VVC算法的實時性.