加權多視圖聚類方法應用于快速幀間模式決策的HEVC改進算法

劉子龍，羅小龍

(上海理工大學 光電信息與計算機工程學院，上海 200444)

1 引 言

隨著超高清影音享受的消費升級，視頻傳輸的數據量急劇增大.人們對于低延時的視頻傳輸需求也與日俱增，Joint Collaborate Team on Video Coding(JCT-VC)已經提出了新一代的高效率視頻編碼標準(High Efficiency Video Coding，HEVC)[1].在保證視頻質量大致相同的前提下，該標準與其上一代壓縮標準H.264/AVC相比，壓縮率提高了2倍.這主要借助其混合編碼框架來實現，并引入許多更加靈活的新方法.為進一步減少時空冗余，編碼冗余和視覺冗余，HEVC將通過四叉樹劃分得到的編碼樹單元(CTU)作為獨立的編碼單元.目的是一個CTU可以被編碼成不同的塊，以適應不同的視頻內容.對每個不同深度的編碼單元(CU)而言，都可以結合各自不同的最佳預測單元(PU)和變換單元(TU)實現編碼.通過率失真(RD)代價遍歷計算所有可能的CU，PU和TU組合，其中RD代價值最小的組合即為最佳組合.顯而易見，該策略極大地增加了計算復雜度，使其無法在低延時的視頻傳輸中應用.

因此，為解決這個難點，本文引入機器學習方法，用聚類方法去代替耗時的預測編碼模式遍歷選擇.減少幀間預測候選模式數量，從而降低復雜度.本文主要貢獻在于探索多視圖聚類方法，在視頻幀間編碼中的應用.

2 研究現狀

為解決這一難題，許多快速編碼算法已經被提出.有的學者在文獻[2]中提出基于解碼輔助的HEVC幀間預測算法，并結合絕對雙向預測差之和與模板匹配運算，幫助合并模式決策和幀間模式決策.在文獻[3]中作者提出提前選中跳過(SKIP)模式的快速幀間模式決策算法，具體通過使用SKIP模式，合并(Merge)模式，幀間2Nx2N的PU模式的率失真代價值來判斷.在文獻[4]中，作者提出基于分層分類的HEVC幀間編碼算法，用來降低復雜度.

近來，諸多學者還通過引入機器學習的方法來降低HEVC編碼復雜度.在文獻[5]中，降維和分類技術，包括逐步回歸，隨機森林，變量選擇，主成分分析，多項式分類器，被用于快速CU分割.在文獻[6]中提出基于RD代價優化的模糊支持向量機快速CU決策算法，其中多級分類的級聯過程指的是CU劃分.在文獻[7]中提出應用支持向量機(SVM)在減少計算復雜度的同時維持較高的編碼質量.主要通過減少CU尺寸劃分決策和PU模式決策的計算量來達到目的.

同樣，深度學習在提高壓縮效率方面也取得了顯著的成果.在文獻[8]中，考慮到只有時間信息被CNN利用去進行幀間預測，這無疑降低了它的預測精度.所以學者提出基于時空信息的幀間預測神經網絡.該神經網絡結構主要由一個全鏈接網絡和一個CNN組成.在文獻[9]中，基于CNN的快速CU模式決策算法被提出，用于HEVC幀間預測編碼.

已知，HEVC支持4種CU模式：64×64，32×32，16×16，8×8.每種CU模式又對應11種候選PU模式：跳過模式(2N×2N)，2種幀內模式(2N×2N，N×N)以及8種幀間模式(2N×2N，2N×N，N×2N，N×N，nL×2N，nR×2N，2N×nU，2N×nD).每種PU模式都會進行復雜和耗時的運動估計和運動補償.通過實驗可以證明，視頻序列中存在大量時域冗余且對同一物體而言，相鄰幀間的變化很小.尤其對于運動緩慢相對靜止的物體或紋理平滑的背景區域而言，幾乎沒有變化.所以如果我們可以識別出它們的類別信息，那么待編碼塊通過復用鄰近幀的同類已編碼塊的CU和PU模式信息，就可以大大減少最佳CU和PU模式的選擇匹配過程，從而顯著提升編碼效率.

由于HEVC編碼的高分辨率視頻信息是未處理的無標簽信息，且本身數據量較大.使用單一視圖聚類方法，難免陷入“管中窺豹，盲人摸象”的境地，很難達到預期分類效果.因此，本文引入多視圖聚類的方法來解決之一難題.視頻流中包含著某一特定物體在不同時間下的狀態，包括不同的運動姿態，由光線等環境因素引起的不同明暗變化，近遠景切換導致的多角度刻畫等等.以上各幀中反應同一物體的每個不同特征稱為一個視圖.將表達同一實例的不同視圖進行歸類分析，使學到的信息更完整，即為對無標簽數據的無監督多視圖聚類學習.該方法已被廣泛應用于醫學影像輔助診斷，自然語音處理，視頻監控和人臉識別等領域.文獻[10-12]HEVC幀間預測的第一幀只能采用幀內預測，這樣的設定無疑為多視圖聚類提供了便利條件.由于CU劃分模式只有4種，在劃分過程中，不可避免的會包含其他類別的部分信息，對最終的聚類結果造成干擾.為此本文又引入特征選擇以及賦予不同權重值的方法，輔助聚類實現.

在文獻[13]中，提出了基于多視圖聚類的HEVC快速幀內模式決策算法.主要應用無監督的加權多視圖聚類方法，來減少幀內預測候選模式數量.但該方法只利用了空域相關性，并未考慮時域相關性.且特征選擇條件單一，其聚類算法計算量也相對較大.本文針對以上3點，都做出了不同程度的合理優化.

3 本文算法的提出

本文沿襲文獻[13]的基本思路，在文獻[14]的基礎上，通過加權多視圖聚類算法的提出，以特征值的選擇作為輔助，不僅使相關運動實例的視圖獲得更大的權重，還可以輔助聚類算法更好的實現.在文獻[7]的基礎上，新增了合并標簽(Merge Flag)，與原有的運動矢量(Motion Vector)，跳過標簽(SKIP Flag)和率失真優化比率(RDO ratio)共同作為本文的特征值，用于PU模式決策.更進一步的突出與其相關的聚類信息，用以實現快速幀間模式決策選擇.算法的核心思想是探索視頻幀間結構信息和相應模式決策的相關性.

核心算法是基于一種快速和高效的基于核的K均值聚類算法[13]，核函數如公式(1)所示：

(1)

(2)

其中j=1，…，Nk=1，…，K；Nk代表第k個聚類中的數據個數.

因為對于特定核函數，相對應的非線性映射φ是無法明確計算的.為了計算公式(1)中的歐幾里德平方距離，文獻[13]中引入核矩陣的方法來計算距離.為提高計算速度，本文采用文獻[14]的方法，通過條件正定核函數簡化歐幾里德平方距離：

(3)

為了將該算法更好的應用于多視圖聚類中，借鑒參考文獻[13]的研究思路，提出加權多視圖聚類算法.通過為視圖增加權重，剔除完全無信息量的視圖并自動根據視圖信息量的重要性，成正比的為其賦予不同大小的權重值.具體推導過程如下：

(4)

(5)

(6)

限制條件：

結合公式(3)和公式(4)，公式(5)可重寫如下：

(7)

(8)

為更進一步提高該算法在HEVC幀間模式預測中的表現，在進行多視圖學習的同時，還引入了特征選擇算法.本文主要選取合并標簽，運動矢量，跳過標簽和率失真優化比率這4個特征值：

(9)

其次為了在運行編碼決策時最小化率失真性能下降，還需引入以下損失函數：

(10)

在編碼過程中，對于給定的帶有特征向量x的PU，通過下式計算它每個候選模式的得分：

(11)

然后通過上文所提到的多視圖聚類算法目標函數，預測得分最低的模式.

4 實驗驗證

本次試驗中使用的HM參考軟件版本為16.8，因為本文目標是通過多視圖聚類的機器學習方法，來預測編碼模式從而降低延時.所以采用統一配置：低延時編碼—編碼幀只有第一幀是幀內方式編碼，并作為及時解碼刷新(Instantaneous Decoding Refresh，IDR)幀和一系列后續的普通P和B幀(Generalized P and B Picture，GPB)組成，因為編碼幀序列維持不變，所以減少了延時.其他所有的環境設置都遵守官方初始化的HM測試狀態進行.實驗所用CPU是Inter Core I5-4200，2.80GHz×4核，8GB運行內存搭載Windows 10操作系統.

官方測試序列中5類共20條測試序列被用來衡量所提算法的優劣，詳情見表1.編碼復雜度由平均編碼時間節省(TS)參數來衡量，因HM16.8統計的編碼時間精確到了毫秒級，所以每次測試結果都略有不同，所以采用測試3次求平均值的方法，具體參見公式(12).

表1 測試序列屬性

(12)

量化步長(QP)分別選取22，27，32和37.編碼視頻質量通過BDBR參數來衡量.

本文算法對上述視頻序列處理的過程中，對關鍵物體的多視圖信息進行了準確的提取.現將部分提取結果展示在圖1中.

圖1 部分多視圖提取結果

幾個典型相關算法的編碼表現對比，在表2中呈現.為了更進一步對比，每一類的平均表現和所有測試序列的平均表現，本文分別做出統計.對比的算法有文獻[4]—基于分層分類的HEVC幀間編碼算法；文獻[7]—支持向量機算法；文獻[13]—基于多視圖聚類的HEVC快速幀內模式決策算法.

分析表2中每一類的平均表現可得，大部分算法都可以在E類實現最大的時間節約.因為E類序列大部分是簡單紋理內容和緩慢移動的物體.所以各種算法都可以在E類實現更大的CU劃分策略，也就意味著可節省更多的時間.而D類恰恰相反，一是因為該類大部分都是復雜文理內容和快速移動的物體.還有一個不容忽視的原因，是該類本身的分辨率最小，所以HEVC原本的編碼時間與其他類相比就是最短，自然各種算法的節約時間有限.

表2 典型相關算法實驗對比結果

分析表2中總的平均表現，文獻[13]獲得了最快的壓縮速度，分別比文獻[4，7]和本文所提算法提高了8.751%；24.505%和13.841%，但它的碼率損耗比它們分別多出0.048%；1.323%和1.143%．所以綜合來看，文獻[13]并沒有很明顯得優勢.況且文獻[13]是全幀內預測模式，本身相對于幀間預測模式就會節省更多的編碼時間.本文所提算法的壓縮速度雖然排名第3，分別比文獻[4，7，13]提高了-5.09%；10.664%和-13.841%；但碼率損耗分別比它們節省1.095%；-0.18%和1.143%.綜合來看，本文所提算法獲得了較好的效果，達到優于同目標各類算法的目的.當然，實驗結果再一次證實——更多編碼時間的節省是以犧牲視頻壓縮質量為代價的.

5 結 論

本文提出將加權多視圖聚類方法用于HEVC幀間模式預測的想法，主要通過將一種快速和高效基于核的K均值聚類算法擴展到多視圖情況下，并通過不同權重值量化視圖信息的重要性.再結合合并標簽，運動矢量，跳過標簽和率失真優化比率的特征選擇，進一步優化無監督機器學習得到的各類性能指標.從而更全面的學習視頻幀間的時間相關性，達到減少幀間預測候選模式數量的目的，顯著降低視頻編碼的復雜度，大大減少視頻傳輸的延遲.經過理論分析和數學推導，證明本文所提算法可以有效降低編碼計算復雜度；之后經過實驗的進一步驗證，得出可以節省高達36.690%的編碼時間，但只造成0.278%的碼率增加.并且通過與同類型和同目標算法的橫向比較，也證實所提算法的綜合優勢明顯，達到預期目標.