劃分層次限制的快速幀間預(yù)測算法

劉 藝，張起貴

太原理工大學(xué) 信息與計算機學(xué)院，山西 晉中030600

通用視頻編碼（Versatile Video Coding，VVC）是繼高效視頻編碼（High Efficiency Video Coding，HEVC）后出現(xiàn)的新一代視頻編解碼標(biāo)準(zhǔn)。新標(biāo)準(zhǔn)的制定目標(biāo)是在編解碼相同質(zhì)量視頻的前提下，相比于HEVC碼率節(jié)省50%，同時也將應(yīng)用于VR，360 度全景視頻等技術(shù)方面。

VVC標(biāo)準(zhǔn)的編碼結(jié)構(gòu)與之前的主要視頻編碼標(biāo)準(zhǔn)H.265/HEVC[1]和H.264/AVC（Advanced Video Coding）標(biāo)準(zhǔn)[2]的框架大體一致，但其又在框架的每個環(huán)節(jié)都進(jìn)行了改進(jìn)或者增加了新技術(shù)，例如128×128的編碼樹單元（Coding Tree Unit，CTU）尺寸、靈活的QTΜTT 劃分結(jié)構(gòu)[3]、擴增到67 個幀內(nèi)預(yù)測方向、局部亮度補償（Local Illumination Compensation，LIC）[4]、仿射運動預(yù)測、自適應(yīng)多核變換（Adaptive multiple core transform，AΜT）[5]等，這些新技術(shù)使VVC 的編碼性能取得較大提升的同時，也極大地提高了編碼復(fù)雜度[6]，尤其是利用QTΜTT對單元劃分時，會消耗過多的編碼時間。

目前主流的視頻編碼標(biāo)準(zhǔn)都是基于塊編碼方式，因此針對單元劃分進(jìn)行復(fù)雜度優(yōu)化的相關(guān)研究也有很多，主要方法有提前結(jié)束劃分或者利用深度學(xué)習(xí)自適應(yīng)劃分的方法。唐浩漾等針對HEVC 幀內(nèi)預(yù)測復(fù)雜度高和耗時長的缺點，提出一種提前終止或跳過劃分深度的HEVC 幀內(nèi)編碼的快速算法[7]；張亞軍等針對高性能視頻編碼采用四叉樹結(jié)構(gòu)大大增加了編碼復(fù)雜度的問題，提出了一種基于運動特性的幀間模式快速決策算法[8]；Liu等提出了一種使用支持向量機進(jìn)行HEVC幀間預(yù)測的快速有效的幀間模式?jīng)Q策算法以降低編碼復(fù)雜度[9]；Lu 等針對HEVC 幀內(nèi)編碼的高復(fù)雜度問題，提出了一種基于幀內(nèi)鄰近信息的快速CU劃分算法和改進(jìn)的幀內(nèi)模式選擇算法[10]；Amestoy 等提出了一種基于機器學(xué)習(xí)方法的快速Q(mào)TBT分區(qū)方案，該方案使用隨機森林分類器為每個編碼單元分類選擇QT或者BT的分區(qū)模式，進(jìn)而降低編碼復(fù)雜度[11]；Wang 等提出了一種面向卷積神經(jīng)網(wǎng)絡(luò)的快速Q(mào)TBT分區(qū)幀間決策算法[12]；Jin等提出了一種利用卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Networks，CNN）學(xué)習(xí)幀內(nèi)單元劃分的算法，該算法使用CNN直接根據(jù)圖像固有的紋理豐富度來預(yù)測32×32 塊的QTBT分區(qū)深度范圍，以降低QTBT的編碼復(fù)雜度[13]。這些算法都在一定程度上降低了單元劃分的編碼復(fù)雜度，但大多都需進(jìn)行較多的數(shù)據(jù)學(xué)習(xí)及模式?jīng)Q策。

本文針對VVC 編碼中QTΜTT 劃分算法進(jìn)行了研究，通過分析其幀間劃分層次，提出一種劃分層次限制的優(yōu)化算法，在較少損失編碼性能的情況下，降低了編碼復(fù)雜度。

1 VVC中的單元劃分情況

1.1 視頻編碼中的單元劃分

現(xiàn)在的視頻編碼都是基于塊進(jìn)行的，塊編碼的實現(xiàn)過程就是先將一幀視頻劃分成不同的塊，然后對每個塊再分別進(jìn)行編碼處理。

在H.264 中，一幀圖像首先被劃分為大小相同的16×16的塊，稱為宏塊（Μarco Block，ΜB），宏塊還可以進(jìn)一步劃分。H.264支持7種尺寸的宏塊，16×16，16×8，8×16，8×8，8×4，4×8，4×4，最小的宏塊尺寸為4×4。

H.265里塊的劃分更加靈活，尺寸也更多變，一幀圖像首先被劃分為64×64大小的編碼樹單元（CTU），一個CTU 由一個亮度編碼樹塊（Coding Tree Block，CTB）和兩個對應(yīng)的色度編碼樹塊及相應(yīng)的語法元素構(gòu)成。對于亮度CTB，其按四叉樹的方式向下劃分，最大為64×64，最小為8×8。1個64×64的CTB可以劃分為4個32×32 的CTB，每個32×32 的CTB 又可以劃分為4 個16×16 的CTB，每個16×16 的CTB 可劃分為4 個8×8 的CTB。因為最小的亮度CTB為8×8，所以最多只能劃分3層。在對四叉樹的劃分方式進(jìn)行表示時，只要給出其劃分深度就能知道塊的大小，因此很容易實現(xiàn)。

當(dāng)CTU 劃分成編碼單元（Coding Unit，CU）后，每個CU還要進(jìn)行預(yù)測、變換等。當(dāng)進(jìn)行預(yù)測時，CU還要繼續(xù)劃分為不同的預(yù)測單元（Predict Unit，PU）。PU是進(jìn)行預(yù)測的基本單元，一個CU 內(nèi)的所有PU 的預(yù)測方式相同，都為幀內(nèi)預(yù)測或都為幀間預(yù)測，且CU到PU只允許一層劃分。

1.2 VVC中的單元劃分

在VVC中，編碼器使用了四元樹（Quaternary Tree，QT）加多元樹（Μulti-Type Tree，ΜTT）劃分的新技術(shù)[14]。ΜTT 包括水平二元樹（Horizontal Binary Tree，HBT）、垂直二元樹（Vertical Binary Tree，VBT）、水平三元樹（Horizontal Ternary Tree，HTT）、垂直三元樹（Vertical Ternary Tree，VTT）。如圖1 為各類型單元劃分，其中圖（a）～（e）分別為QT 劃分、HBT 劃分、VBT 劃分、HTT劃分、VTT劃分。

圖1 QTΜTT劃分類型

與HEVC相似，一個序列以圖片流的形式輸入編碼器，每個圖片被分割成128×128 尺寸的編碼樹單元（CTU）。根據(jù)圖片信息，CTU 能夠進(jìn)一步被QT+ΜTT分割成CU。CTU首先進(jìn)行QT劃分，從128×128尺寸開始劃分，最小可劃分到16×16 的尺寸，根據(jù)圖片紋理信息，進(jìn)行ΜTT劃分，多元樹開始劃分后，不得再進(jìn)行QT劃分，最小劃分單元尺寸為4×4，即最多可進(jìn)行6 次劃分。圖2為VVC編碼軟件VTΜ編碼BasketballDrive序列所得到的單元劃分圖，由圖所示，在紋理變化較淺的區(qū)域QT+ΜTT 未進(jìn)行劃分，在變化較大的區(qū)域進(jìn)行了較細(xì)的劃分。

圖2 QTΜTT劃分效果圖

在進(jìn)行單元劃分的過程中，VVC 編碼器的率失真優(yōu)化算法會進(jìn)行率失真代價的檢查與比較，即計算CTU劃分與不劃分的率失真代價，取最小值所對應(yīng)的情況為最優(yōu)劃分，但這樣就需要對每個CTU 都進(jìn)行劃分并返回代價值，從而造成編碼復(fù)雜度的增加。

2 單元劃分算法優(yōu)化

2.1 VVC中序列劃分層次分析

在VVC 中，可利用SplitSeries 值表示劃分類型。式（1）表示了SplitSeries 值的運算過程，其中序號從a到f 表示經(jīng)過的6層劃分，每個序號可用0～5的數(shù)字表示，0表示不劃分，1表示QT劃分，2表示HBT劃分，3表示VBT劃分，4表示HTT劃分，5表示VTT劃分。

（1）如果SplitSeries 取值1 057，則

1 057=1×20+1×25+1×210+0×215+0×220+0×225表示該值對應(yīng)的劃分方式為111000，即進(jìn)行了三層QT劃分。

（2）如果SplitSeries 取值4 363 297，則

4 363 297=1×20+1×25+5×210+5×215+4×220+0×225

表示該值對應(yīng)的劃分方式為115540，即先進(jìn)行2 層QT劃分后又進(jìn)行了2層VTT劃分，最后進(jìn)行了1層HTT劃分。

（3）如果SplitSeries 取值66 593，則

66 593=1×20+1×25+1×210+2×215+0×220+0×225

表示該值對應(yīng)的劃分方式為111200，先進(jìn)行三層QT 劃分，再進(jìn)行一層HBT劃分。

（4）如果SplitSeries 取值68 641，則

68 641=1×20+1×25+3×210+2×215+0×220+0×225

表示該值對應(yīng)的劃分方式為113200，即先進(jìn)行兩層QT劃分，再進(jìn)行一層VBT劃分，最后進(jìn)行一層HBT劃分。

以上四種劃分方式如圖3所示。

圖3 SplitSeries 劃分示例對照

據(jù)此，可利用SplitSeries 值來求得VVC 編碼過程中各CTU的劃分層次。表1顯示了VTΜ在RA編碼配置下編碼Tango、BasketballDrive、ΜarketPlace 三個序列得到的劃分層次，其中Tango是3 840×2 160序列，Basketball-Drive、ΜarketPlace是1 920×1 080序列。為了比較直觀地進(jìn)行統(tǒng)計，表中0表示不劃分，1表示QT劃分，2表示ΜTT劃分，即利用0、1和2這三個數(shù)字表示劃分深度及類型，如表中1122 表示兩層QT 劃分后兩層ΜTT 劃分，111122表示四層QT劃分后兩層ΜTT劃分。

表1 序列劃分層次統(tǒng)計 %

由表1可知大部分劃分層次都在五層以內(nèi)，劃分六層的即序號為111222和111122的在三個序列中占比僅為0.04%、0.11%和0.02%。這兩類劃分層次對于編碼性能的提升影響較小，但由于率失真決策，CTU會先進(jìn)行所有可能的劃分，再比較率失真代價值，這樣就占據(jù)了較多的編碼復(fù)雜度，故可對單元劃分層次做相應(yīng)限制，以達(dá)到降低編碼復(fù)雜度的效果。

2.2 單元劃分算法優(yōu)化

通過上節(jié)簡述可知，在VVC進(jìn)行編碼過程中，單元劃分最多會進(jìn)行六層劃分，但最后一層劃分對編碼性能提升效果較小，因此本節(jié)針對該情況提出一種劃分層次限制的單元劃分算法。

圖4顯示了優(yōu)化算法的流程圖，即在進(jìn)行CTU單元劃分的過程中加入限制參數(shù)Part_len，使單元劃分最大深度為5，減少多余的劃分深度，從而在較少損失編碼性能的情況下，降低了編碼復(fù)雜度。優(yōu)化算法步驟如下。

圖4 優(yōu)化算法流程圖

步驟1 輸入的圖片首先被劃分為128×128 大小的CTU，并設(shè)置劃分參數(shù)Part_len=0；

步驟2 對CTU 進(jìn)行QT 及ΜTT 劃分，劃分時統(tǒng)計其劃分層數(shù)Part_len；

步驟3 當(dāng)Part_len=5 時，即劃分層次達(dá)到五層時，提前停止劃分，計算率失真代價，尋找最優(yōu)劃分，將其送入下一步編碼過程中。

3 實驗結(jié)果

本次實驗利用VVC編碼參考軟件VTΜ3.0，在配置為Intel?CoreTΜi7-8750H CPU@2.20 GHz 的Ubuntu 16.04.6 LTS平臺上進(jìn)行測試。

測試序列為VVC 標(biāo)準(zhǔn)測試序列，包括6 個3 840×2 160序列和5個1 920×1 080序列。測試環(huán)境為隨機接入（Random Access，RA）。分別用BD-BR[15]、BD-PSNR[16]及ΔT 表示新算法編碼與舊算法編碼的壓縮率、失真度、編碼復(fù)雜度變化情況。式（2）表示了ΔT 的計算過程，T'為舊算法編碼復(fù)雜度，T 為新算法編碼復(fù)雜度，即ΔT 可表示新算法相比于舊算法的編碼復(fù)雜度節(jié)省情況。

表2 顯示的是Y 分量的BD-BR 和BD-PSNR 變化情況，由結(jié)果可知，新算法在RA 配置下，在增加1.58%的壓縮率，損失0.036 2的圖像失真度的情況下，編碼復(fù)雜度降低了46.39%?？梢娦滤惴▽g預(yù)測的編碼復(fù)雜度的優(yōu)化效果顯著。

表2 實驗結(jié)果

4 結(jié)束語

本文通過對新一代視頻編碼中幀間預(yù)測單元劃分算法中關(guān)于劃分深度的分析，提出一種劃分層次限制的快速幀間預(yù)測算法。實驗結(jié)果表明，新算法在較少損失編碼性能的同時，顯著降低了編碼復(fù)雜度，這為將來新標(biāo)準(zhǔn)的工業(yè)應(yīng)用提供了一個優(yōu)化方向。下一步本文將嘗試?yán)蒙疃葘W(xué)習(xí)算法使編碼器能夠通過學(xué)習(xí)單元劃分方式，來自適應(yīng)劃分編碼單元，在避免率失真決策過程的同時降低編碼復(fù)雜度。