H.266/VVC視頻編碼的快速CU劃分算法

周德登

（西南科技大學(xué)信息工程學(xué)院，綿陽621010）

0 引言

隨著4K（4096×2160）以及8K（7680×4320）視頻的出現(xiàn)，市場對高分辨率和高幀率視頻的傳輸和存儲有了極大的需求。上一代視頻編碼標準H.265/HEVC難以適用于如此龐大的數(shù)字視頻數(shù)據(jù)量，于是H.266/VVC在2015年被提上研究日程的，其研究組織在2016年給出了一個公共參考軟件（VVC Test Model，VTM）。在編碼同一個視頻時，VTM7.0的編碼性能在H.265/HEVC的基礎(chǔ)上多了50%左右的提升，但是同時編碼耗時也增加接近30%，所以降低編碼復(fù)雜度是當前研究人員亟待解決的問題。

1 H.266/VVC塊劃分

視頻編碼標準均采用了基于塊的混合編碼方式，首先將待編碼的圖像進行塊劃分，將其劃分為基本編碼單元（Coding Unit，CU），CU將用于后續(xù)的幀內(nèi)或幀間預(yù)測，然后將預(yù)測中產(chǎn)生的殘差數(shù)據(jù)進行變換量化，最后將分塊模式、預(yù)測信息以及量化后殘差等進行熵編碼，得到編碼的二進制碼流[1]。H.266/VVC中使用了四叉樹（Quadro Tree，QT）和嵌套多類型樹（Multi-Type Tree，MTT）劃分，MTT包括二叉樹（Binary Tree，BT）和三叉樹（Ternary Tree，TT），以支持更靈活的CU劃分形狀。如圖1所示，二叉樹劃分為水平和垂直兩個方向，比例為1:1，三叉樹劃分同樣是水平和垂直兩個方向，比例為1:2:1。CU就是多類型樹的葉子節(jié)點，在CU小于最大變換單元（64×64）時，則預(yù)測單元和變換單元不會進行下一步劃分。因此，在很多時候CU、PU和TU的大小是相同的。

圖1 嵌套多類型樹劃分

如圖2所示，在H.266/VVC中，對編碼樹單元CTU首先進行四叉樹劃分，再根據(jù)劃分標識確認下一步劃分方式。四叉樹的劃分標識為qt_split_cu_flag，嵌套多類型樹的劃分標識為mtt_split_cu_flag，確定使用嵌套多類型樹繼續(xù)往下一層深度劃分時，則用劃分標識mtt_split_cu_vertical_flag判別CU劃分方向，最后使用劃分標識mtt_split_cu_binary_flag選擇二叉樹劃分或者三叉樹劃分，劃分標識如圖3所示。

圖2 四叉樹和嵌套多類型樹劃分示例

圖3 CU劃分標識

為了找到適合每個CTU的CU劃分結(jié)構(gòu)，編碼器需要遞歸執(zhí)行每種劃分結(jié)構(gòu)的率失真優(yōu)化（Rate Distortion Optimization，RDO）的計算，比較率失真代價并選擇其中值最小的那一種劃分結(jié)構(gòu)作為這個CTU的最終劃分結(jié)果，這個遞歸運算需要消耗大量的時間。為了減少CU劃分所消耗的時間，必須尋找一種有效的劃分方法。Amna等人[2]提出了一種基于深度卷積神經(jīng)網(wǎng)絡(luò)（CNN）模型的快速Q(mào)T劃分算法，使用CNN模型代替RDO預(yù)測編碼單元劃分，從而大大提高了幀內(nèi)編碼的QTBT性能。Lin等人[3]對二叉樹劃分進行了優(yōu)化，利用圖像空間特征來判斷二叉樹的使用時機。Tang等人[4]提出了在幀內(nèi)編碼中使用Canny算子進行邊緣檢測并根據(jù)檢測結(jié)果快速幀內(nèi)CU劃分算法，在幀間編碼中使用三幀差分法判斷視頻是否為運動圖像來進行快速幀間CU劃分算法。Sun等人[5]提出了一種基于SVM的快速CU劃分算法，該算法利用Canny算子檢測輪廓并使用SVM分類器快速CU劃分。Yang等人[6]提出了一種由低復(fù)雜度CTU結(jié)構(gòu)劃分決策和快速幀內(nèi)模式?jīng)Q策組成的快速幀內(nèi)編碼算法。Zhang等人[7]基于改進的有向無環(huán)圖支持向量機（DAG-SVM）模型設(shè)計了一種快速CU劃分決策算法，以降低CU劃分的復(fù)雜性。本文主要通過對CU劃分方式的一些修剪來降低H.266/VVC的編碼復(fù)雜度。

2 提出的算法

在視頻編碼中，圖像中不同的內(nèi)容也會對編碼單元CU的劃分結(jié)構(gòu)產(chǎn)生影響。如圖4所示，在視頻圖像中左下側(cè)和中上側(cè)的區(qū)域紋理較少，CU劃分尺寸相對較大，而左上角和右下角的區(qū)域紋理較復(fù)雜，CU劃分則更加細致。除此之外，如圖5所示，可以發(fā)現(xiàn)紋理的分布方向也會影響區(qū)域中CU的劃分方向。比如在擁有紋理分布方向偏垂直的區(qū)域中，CTU在多數(shù)情況下會被BTV或者TTV劃分，在擁有紋理分布方向偏水平的區(qū)域中，CTU在多數(shù)情況下會被BTH或者TTH劃分，而在紋理分布較均勻的區(qū)域中，CTU會被QT劃分。

圖4 幀內(nèi)CU劃分實例

圖5 BasketballDrill幀內(nèi)CU劃分分析

根據(jù)上述視頻圖像CU劃分情況和其紋理之間的關(guān)系，首先在CU劃分結(jié)構(gòu)之前確定大致的視頻圖像紋理特征。視頻圖像紋理特征的提取可以看作是對圖像灰度局部的劇烈變化檢測，并根據(jù)檢測結(jié)果做圖像分割，對灰度值波動的檢測過程被稱為邊緣檢測。一階導(dǎo)數(shù)的幅度可以用于檢測圖像中在某個點處是否存在一個邊緣，而二階導(dǎo)數(shù)的符號可以用于確定一個邊緣像素是位于該邊緣的明處還是暗處[8]。由于只是為了利用圖像的邊緣信息來對CU劃分進行后續(xù)處理，不需要判斷明暗特征，使用一階導(dǎo)數(shù)的邊緣檢測可以滿足本文要求并減少計算量。Robert算子、Prewitt算子和Sobel算子都是常用的一階導(dǎo)數(shù)梯度算子。

我們通過灰度值的波動可以判斷當前像素點是否為邊緣像素點，灰度值的波動則可以根據(jù)對圖像像素值求導(dǎo)數(shù)獲得。而像素灰度值的偏導(dǎo)數(shù)?f/?x和?f/?y可以用來得到梯度圖像。根據(jù)圖6中顯示的3個不同邊緣檢測算子的模板，計算其相應(yīng)的偏導(dǎo)數(shù)的公式如下：

圖6 Roberts、Prewitt和Sobel算子

Roberts算子的2×2模板的優(yōu)勢在于計算量小，可以快速獲得邊緣信息，但是對邊緣方向的判斷不如3×3的模板，3×3的模板能夠記錄更多關(guān)于圖像邊緣方向的信息。Prewitt算子和Sobel算子都采用了3×3的模板。在計算Prewitt算子和Sobel算子時，可以近似地將首行和末行的差值看作是x方向的導(dǎo)數(shù)，將首列和末列的差值看作y方向的導(dǎo)數(shù)。Prewitt算子比Sobel算子更簡單，但是計算量卻差不了多少，但是Sobel算子能更好地抑制平滑噪聲[8]。

使用Sobel算子對圖像進行邊緣檢測更為合理，并將其檢測結(jié)果用于CU的快速決策劃分。

在得到邊緣檢測圖像之后，對邊緣圖像進行逐行掃描，可以得到當前CTU中的各個方向的邊緣長度，記錄下水平方向的邊緣長度和垂直方向上的邊緣長度進行后續(xù)處理。

如圖7所示，如果當前CU的區(qū)域中沒有邊緣信息，則終止當前CU繼續(xù)劃分過程；如果當前CU的區(qū)域中垂直邊緣長度與水平邊緣長度的比值大于閾值，那么當前CU將跳過BTH和TTH劃分；如果當前CU的區(qū)域中水平邊緣長度與垂直邊緣長度的比值大于閾值，那么當前CU將跳過BTV和TTV劃分；否則進行QT劃分。

圖7 邊緣檢測快速CU決策流程

3 實驗和結(jié)果分析

3.1 評價度量及對比方法

本文的算法是在VTM7.0框架上對原有的CU劃分算法進行了改進，添加了判決CU劃分的條件，可以減少一種或兩種CU的劃分方式，以此來減少CU劃分和計算率失真代價的時間。在測試本文算法時，采用的電腦配置為Windows 10 64位操作系統(tǒng)，CPU為的Intel Core i5 9400F，主頻2.9 GHz，GPU為NVID?IA RTX2060 SUPER，16 GB內(nèi)存，測試序列為4組不同分辨率中的8個測試視頻序列，分別為416×240（BlowingBubbles，BasketballPass）、832×480（BQMall，PartyScene）、1280×720（FourPeople，Johnny）、1920×1080（Cactus，BasketballDrive），每個測試視頻序列的量化參數(shù)（Quantization Parameter，QP）為(22,27,32,37)進行試驗。

本文通過對比VTM7.0的標準算法來測試改進算法的有效性。編碼后的視頻圖像質(zhì)量可以使用峰值信噪比（Peak Signal Noise Ratio，PSNR）衡量，PSNR與圖像質(zhì)量成正比關(guān)系。編碼時間的提升則可以通過下式計算：

式中Torg為VTM7.0標準算法編碼所需要的時間，Timpr為改進之后的算法所需要的時間。

在衡量改進算法編碼視頻后的質(zhì)量時，時常不能同時兼顧低碼率和高恢復(fù)質(zhì)量，所以在恢復(fù)相同的視頻圖像質(zhì)量的前提下對比編碼之后的碼率變化情況，這個新指標為BD-rate（Bj?ntegaard-Delta-rate），BDrate又被稱為BDBR。

RD曲線圖可以直觀地看出改進算法和原始算法之間的差距。RD曲線圖以圖像的峰值信噪比作為縱軸，編碼的比特率為橫軸。其擬合了同一個視頻序列在4個不同量化參數(shù)下的峰值信噪比和編碼比特率的一條曲線。

3.2 實驗結(jié)果

如表1所示，和VTM7.0標準算法相比，在AI模式下，使用邊緣檢測跳過一部分CU劃分方式可以有效地減少編碼時間，編碼時間減少了39.95%，BDBR僅增加了0.73%。相較于文獻[9]和文獻[6]的算法，雖然本文算法減少的編碼耗時要少一些，但是壓縮后的BDBR增加量卻要少很多，圖像質(zhì)量PSNR也要比兩個文獻的好很多。文獻[9]算法的BDBR增加量是本文算法的兩倍，文獻[6]算法的BDBR增加量是本文算法的3倍，這在很多情況下是不理想的。

表1 改進算法和標準算法效果對比

圖8分別是8個測試視頻序列改進算法和原始算法的RD曲線圖。與VTM 7.0標準算法相比，改進算法可以實現(xiàn)從低比特率到高比特率的相同編碼節(jié)省，并且具有相似的RD特性。根據(jù)表1和RD曲線圖顯示本文改進算法保證了編碼的質(zhì)量幾乎不變的同時，編碼耗時減少了許多。

圖8 RD曲線

4 結(jié)語

本文根據(jù)H.266/VVC中CU劃分結(jié)構(gòu)和視頻圖像紋理之間的相關(guān)性，提出了基于Sobel邊緣檢測的快速CU劃分算法來降低編碼的復(fù)雜性，并將其應(yīng)用于VTM7.0中。與VTM7.0標準算法的編碼時間對比，本文的改進算法時間降低了39.95%，而BDBR僅增加0.73%，實驗證明本文算法優(yōu)于最新的快速CU劃分算法。