編碼單元

高效率視訊編碼利用編碼單元指出這個單元是利用畫面內預測(IntraPrediction)或是畫面間預測(InterPrediction)。這些編碼單元可以很方便地利用四分樹(Quadtree)的方式呈現，四分樹是一種遞迴結構，四分數上的數字表示這個節點是否繼續做分割，若此節點會繼續分割則為1，若不繼續分割則為0。節點上的數字為0時，此節點為編碼單元。換句話説，在編碼樹內葉子節點(LeafNode)為編碼單元。在編碼單元上採用Z-scan的方式，對編碼樹來説即為深度優先遍歷。編碼單元的大小支援2Nx2N，其中N=4、8、16或32，因此高效率視訊編碼(HEVC)的四分樹最高深度(Depth)為4。

為了降低新一代高效視頻編碼 （High　Efficiency　Video　Coding，HEVC）標準的編碼複雜度，提出了一種基於四叉樹結構類型分析和早期編碼單元（Coding　Unit，CU）裁剪的 HEVC快速編碼新算法。首先，通過分析已編碼的最大編碼單元（Largest　CU，LCU）四叉樹結構類型，確定其深度遍歷區間 （Depth　Range，DR）類 型。然後，利用相鄰已編碼 的LCU以及前向參考幀和後向參考幀中座標位置相同的 LCU的 DR類型來預測當前 LCU的 DR類型，並根據預測得到的 DR類型對當前 LCU設定 CU深度遍歷區間。最後，採用貝葉斯決策原理獲取閾值，並利用該閾值在 CU分割過程進行早期 CU裁剪。 ^[1] 

HEVC採用率失真優化方式決定 LCU最 終四叉樹結構的分割形式，這樣，可以在保證視頻質量的前提下獲得最小的碼率。其率失真代價函數J（CU_d）為：

J（CU_d）=SSE_d+λ×B_d，

其中：d表示當前 CU的深度值，B_d 代表當前 CU經過各種 PU預測和模式選擇後編碼所需的比特數，λ為拉格朗 日算子，SSE_d（Sum　of　Square　Error，SSE）表示原始圖像塊和重建圖像塊之間的誤差平方和。 ^[1] 

在充分考慮到 HEVC的四叉樹編碼結構和視頻的時空域相關性的基礎上，首先通過對四叉樹結構類型進行分析，確定其深度遍歷區間 （Depth　Range，DR）類型，利用參考幀相同位置的 LCU和相鄰LCU的 DR類型來預測當前 LCU的 CU深度遍歷區間；然後，再根據預測的深度區間進行編碼。同時，採用貝葉斯決策訓練原理獲取閾值，並利用該閾值對 CU分割進行早期 CU裁剪。 ^[1] 

1、DR類型的確定：

HEVC採用四叉樹結構進行編碼，一 個LCU最終的分割類型是通過其 CU深度值確定的，大小為64×64的 LCU包 括 256個 4×4塊，每 個 4×4塊都用 一 個深度值 depth（depth∈[0，3]）表示。不同四叉樹結構的 LCU，其 CU深度值的分佈情況也不同，LCU的四叉樹結構類型可以分為 8種（即 A，B，C，D，E，F，G，H）。若能在 LCU四叉樹結構劃分前對其類型進行預測，通過該類型設定 CU深度遍歷範圍，就可以減少不必要的 CU深度遍歷，從而降低其編碼複雜度。但過於精細的預測遍歷區間會很容易造成誤判。因此，將深度值分佈相近的四叉樹結構類型進行合併，並定義 T₁、T₂、T₃ 和 T₄ 種 DR類型。例如，T₂包括 C和 D2種四叉樹結構類型，其中：C的 深度值為1和2，D的深度值則全為 2，故 將這 2種四叉樹結構 的 DR類型定為T₂。算法根據DR類型進行 CU深度遍歷，相比原始 0～3的 全遍歷，明顯減少了編碼複雜度。 ^[1] 

2、利用時空相關性的中值 DR類型預測：

在視頻序列中，當前編碼 LCU與相鄰已編碼的 LCU以及前一幀和後一幀中與當前編碼LCU位置相同的 LCU（以下簡稱為對應 LCU）之間有很大的相關性。 LeftLCU、Top　LCU、Left－top　LCU、Col1LCU和Col2LCU共5個參選預測 LCU的 DR類型來預測當前編碼 LCU的 DR類型。

3、基於貝葉斯決策的早期 CU裁剪預判：

在 LCU的塊劃分過程中，若當前 CU（depth∈[1，2]）為其上一層 CU的第4個分割 CU，則在計算完其率失真代價J後 ，就有可能通過預判斷提前進行早期 CU裁剪過程 。

採用貝葉斯決策原理在幀內模式選擇過程中訓練基於 SATD（Hadamard　trans－formed　SAD）的率失真代價最佳閾值。 ^[1] 

高效率視頻編碼(HEVC)採用基於編碼單元(CU)的四叉樹塊分區結構，能靈活地適應各種圖像的紋理特徵，顯著提高編碼效率，但編碼複雜度大大增加，提出一種縮小深度範圍且提前終止CU 劃分的快速 CU 劃分算法。基於Sobel 邊緣檢測算子計算一幀中各深度邊緣點閾值，縮小後面若干幀中CU 遍歷的深度範圍；同時，統計該幀中各 CU 劃分為各深度的率失真(RD)代價，計算各深度的 RD 代價閾值。然後，在後續視頻幀中，利用RD 代價閾值在縮小的深度範圍內提前終止CU 劃分。為了符合視頻內容的變化特性，統計參數是週期性更新的。經測試，在平均比特率增加僅1。2%時，算法時間平均減少約59%，有效提高了編碼效率。 ^[2] 

HM 的 CU 劃分過程，是在4個深度級範圍內逐級比較 RD 代價，並選擇 RD 代價最小的劃分作為最佳劃分。由 LCU 邊緣點確定的2個或3個深度級範圍內進行 CU 劃分。為進一步加快 CU 劃分速度，採用基於 RD 代價的 CU 劃分提前終止策略。 ^[2] 

一般情況下，若 CU 當前深度的 RD 代價越小，則説明當前劃分方式的效果越好，該 CU 繼續劃分的可能性越小。也就是説，若 CU 當前深度 RD 代價小於某個閾值，就無需繼續劃分，這就是“CU 劃分提前終止策略”。

在學習幀中，除了得到邊緣點數目與深度級範圍的對應關係外，還利用 HM 得到各 LCU 的劃分深度及對應的 RD 代價，並計算每個深度級所對應的 RD 代價的均值及標準差，再計算用於提前終止的 RD 代價閾值。在此後的應用幀中，從最小深度級開始計算當前深度級的 RD 代價，若當前深度級 CU 的 RD 代價小於對應深度級的 RD代價閾值，則該 CU 不繼續劃分，提前終止，否則繼續按深度增加逐級比較。這樣，就大大減小了RD代價的計算量。 ^[2] 

對於整個算法流程，首先是學習幀基於梯度獲得一幀圖像中各深度的邊緣點閾值，在統計邊緣點的同時也統計一幀中各LCU最終劃分時各子CU的RD 代價，並對統計得到的各個深度級 RD 代價求均值和標準差，獲得用於判斷的 RD 代價閾值。然後在應用幀中，先依據邊緣點閾值獲得當前 LCU 需遍歷的深度範圍，再在該深度範圍內，比較當前深度 CU 的 RD 代價和 RD 代價閾值的大小，若小於RD 代價閾值則 CU 提前終止。具體步驟為：

(1)首先是學習幀，對每個 LCU 依據 Sobel 邊緣檢測算子計算各像素點的梯度值，獲得梯度圖後，將梯度圖按 LCU 掃描順序劃分為4塊；

(2)利用 otsu 算法計算每塊的分割閾值Gfour_i，i = 0，1，…，3 (取計算得到值的0。75)，並依據該閾值判斷該塊內各 LCU 的邊緣點數； ^[2] 

(3)依據 HM 中該幀圖像各 LCU 最終劃分深度將 LCU 的邊緣點數分組(深度 0 和1 併為一組)，分別計算各深度邊緣點數的均值和標準差，剔除邊緣點數目落在標準差之外的 CU，重新計算，將再次計算的均值和標準差之和作為對應深度級的閾值Th_Edge_j ， j = 1，2 ；

(4)在統計各 LCU 梯度的同時，統計該幀中各CU 最終劃分時的 RD 代價，並計算各深度級的 RD代價均值和標準差，獲得 RD 代價閾值，閾值計算公式為式(4) ；

(5)學習幀結束後，進入應用幀，根據步驟(3)中得到的閾值判斷當前 LCU 的邊緣點數屬於哪個劃分深度，獲得遍歷的深度範圍，然後將遞歸過程中當前深度 CU 的 RD 代價RD_k 與對應深度的閾值Th_RD_k ，k = 0，1，…，3 進行比較，若小於閾值，則終止當前 CU 劃分，CU 最終劃分深度為k 。否則，深度加1，繼續比較下一深度的 RD 代價和相應閾值，直至最大深度。然後進入下一個 LCU 的比較，再次執行步驟(5)。若執行到學習幀，則返回到步驟(1)。 ^[2]