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

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

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

1 引 言

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

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

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

以上技術(shù)文獻(xiàn)均在一定程度上減少了編碼復(fù)雜度，節(jié)省了編碼的時(shí)間開銷，但對(duì)于幀內(nèi)信息都未達(dá)到充分利用，編碼效率還有提升空間.本文主要針對(duì)VVC幀內(nèi)編碼中的CU劃分進(jìn)行優(yōu)化，利用MGMSD求QT劃分的子CU的相似度以跳過QT劃分和不劃分，以及利用MT(多類型樹)劃分的子CU像素方差的方差選擇最佳MT劃分.實(shí)驗(yàn)結(jié)果表明，在保證圖像質(zhì)量與壓縮效率基本不變的條件下，基于本方法可顯著降低VVC幀內(nèi)編碼復(fù)雜度.本文第2節(jié)簡(jiǎn)述了VVC的幀內(nèi)編碼，第3節(jié)介紹了本文提出的算法原理，第4節(jié)展示并分析了實(shí)驗(yàn)結(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).此外，為了簡(jiǎn)化CTU的劃分過程，一旦CU被MT劃分，QT在隨后的劃分過程中就不再使用.QTMT結(jié)構(gòu)的簡(jiǎn)圖如圖2所示.實(shí)心黑線表示QT劃分，虛線表示MT劃分.

圖1 MT劃分Fig.1 MT division

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

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

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

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

3.1 梯度幅值相似度偏差

Xue[17]提出了一種基于梯度幅值相似度(GMS)的圖像質(zhì)量評(píng)價(jià)方法——梯度相似度偏差(GMSD).GMSD算法效率高、準(zhǔn)確度高，并且效果良好.因此，將其用來計(jì)算QT劃分的子塊相似度，其模型定義為：

Prewitt濾波算子模板沿水平方向和垂直方向定義如圖3所示.

圖3 Prewitt算子模板Fig.3 Prewitt operator template

將圖3算子模板分別對(duì)子塊r和對(duì)比子塊d進(jìn)行卷積生成r和d的水平方向和垂直方向的梯度值，表達(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的像素點(diǎn)(i,j)的值.

子塊r、d在位置(i,j)處的梯度幅值大小，記為mr(i,j)和md(i,j).mr(i,j)和md(i,j)的計(jì)算如下式(2)所示：

(2)

有了梯度幅值圖像mr(i,j)和md(i,j)，梯度幅值相似度(GMS(i,j))計(jì)算如下(3)所示:

(3)

其中c=1.70，它提供數(shù)值穩(wěn)定性.

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

(4)

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

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

(5)

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

(6)

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

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

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

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

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

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

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

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

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

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

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

TH1=α×QP

(7)

TH2=β×QP

(8)

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

表1 在α=0.006和β=0.0083的條件下各種視頻序列的劃分命中率統(tǒng)計(jì)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進(jìn)行了四叉樹劃分.MT劃分比是指在所有的TH1≤MGMSD≤TH2的CU中，有平均84.5%的CU進(jìn)行了多叉樹劃分.不劃分比是指在所有的MGMSD≤TH1的CU中，有平均74.9%的CU不進(jìn)行劃分.從以上數(shù)據(jù)可以看出了，MGMSD在提取圖像細(xì)節(jié)有著較好的性能，也在一定程度上證明了本文方法的有效性.

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

(9)

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

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

圖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 本文算法與文獻(xiàn)[15]、文獻(xiàn)[18]、文獻(xiàn)[19]實(shí)驗(yàn)結(jié)果Table 3 This paper′s algorithm and literature [15],literature [18],literature [19] experimental results

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

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

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

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