基于運動特性的HEVC幀間模式快速決策算法

張亞軍，李 強

重慶郵電大學 通信與信息工程學院，重慶 400065

1 引言

隨著高清、超高清和高幀頻數字視頻消費需求的增長，人們對數字視頻的壓縮效率提出了更高的要求。由于H.264/AVC在編碼效率、并行處理等方面存在著局限性，已經難以滿足高清視頻應用發展的需求。為了滿足海量高清視頻數據的傳輸和存儲要求，ITU-T視頻編碼專家組（Video Coding Experts Group，VCEG）和ISO/IEC運動圖像專家組（Moving Picture Experts Group，MPEG）于2010年1月聯合成立了視頻編碼聯合協作小組（Joint Collaborative Team on Video Coding，JCT-VC），專門制定下一代視頻編碼標準。2013年4月JCT-VC正式發布了新一代高效率視頻編碼標準。雖然HEVC仍采用預測、變換加熵編碼的混合框架結構，但通過采用靈活的圖像四叉樹結構、條和片劃分、多角度幀內預測、運動信息融合、高精度運動補償、自適應環路濾波等技術，大大提高了視頻的編碼效率。與H.264/AVC相比，HEVC在相同視頻質量的情況下可節省50%以上的編碼比特流[1]，但編碼計算量增大了2～3倍。HEVC的高復雜度阻礙了其在視頻領域的快速應用。如何在保證一定的視頻質量的情況下，降低HEVC的計算量，是目前很多專家和學者研究的重點。

據統計，在HEVC框架中，幀間編碼的計算量占整個編碼的69%左右，因此，如果能有效降低幀間編碼算法復雜度，就能加快編碼端的處理速度。目前國內外很多學者對幀間預測模式決策算法展開了研究，提出了很多具有應用價值的幀間編碼快速算法。如文獻[2]利用當前CU與空間相鄰CU深度的相關性及視頻內容的運動一致性，跳過相鄰CU很少使用的深度，提前終止當前CU劃分過程。文獻[3]根據視頻圖像運動的快慢，設置了兩個不同的閾值用于判別運動程度，以提前終止CU劃分過程。文獻[4]根據當前幀與參考幀中對應塊位置CU及其左側CU深度信息預測當前CU深度范圍，以縮小可能的CU深度遍歷數，從而減少CU劃分過程。文獻[5]根據預測當前CU對應最有可能的PU模式個數來減少當前PU模式的選擇。文獻[6]依據當前塊的紋理運動簡單性，跳過一些Inter模式來加速編碼過程；文獻[7]通過設置率失真閾值來提前結束幀間PU模式選擇；文獻[8]通過運動特性來提前終止當前CU深度的選擇，從而降低編碼復雜度；文獻[9]通過CU深度時空相關性來預測當前CU的范圍，減少深度的遍歷次數。文獻[10]依據當前CU及對應PU的空時域相關性，通過減少CU深度和PU模式遍歷個數來加速編碼過程。

上述文獻中的算法大多利用視頻內容在空時域上的相關性減小CU深度遍歷和PU模式決策過程來降低編碼時間，但在視頻的運動平坦區域所遍歷的PU模式中，依然存在一定的PU模式冗余信息。比如文獻[10]，所采用的CU深度快速算法雖然在一定程度上提升了CU的遍歷過程，但沒有充分考慮編碼區域運動及紋理的復雜性與所要遍歷CU深度范圍之間的對應關系，在PU模式快速決策過程中只考慮了幀間PU的相似性，沒有考慮與其幀內相鄰CU及其上一深度CU對應的PU的相關性。因此上述編碼過程依然存在一定的信息冗余，仍有減小編碼時間的可能性。本文利用視頻運動快慢與幀間PU類型劃分之間的相關性，提出了一種基于運動特性的幀間預測模式快速決策算法。首先根據當前CU與其相鄰空時域CU深度的相關性，降低當前CU深度遍歷次數。如果當前CU周圍CU深度相同，利用平滑區域CU深度快速決策算法來縮小當前CU深度遍歷范圍；如果當前CU周圍CU深度不同，則采用復雜區域CU深度快速決策算法來降低當前CU深度遍歷范圍。然后根據當前CU上一深度及其空時域相鄰CU所對應的幀間PU模式特性與運動快慢的關系，對運動平坦區域提前終止一些PU模式的遍歷過程，對運動中等區域及運動復雜區域跳過一些不必要PU模式遍歷，從而減少幀間PU模式選擇的個數以降低編碼復雜度。

2 HEVC幀間模式加速決策算法

2.1 HEVC中CU和PU的特性

HEVC的每幀圖像由多個片（Slice）構成，每個片又劃分為多個深度為0的編碼樹單元（Coding Tree Unit，CTU），即大小為64×64的CU。一個CTU可繼續劃分為深度為1、2和3的CU，其對應的CU尺寸大小分別為32×32、16×16和8×8。與H.264/AVC中16×16固定尺寸編碼塊相比，HEVC中的CTU四叉樹劃分結構具有更靈活的尺寸類型，使得幀內和幀間編碼更具有多樣性，從而提高視頻的壓縮效率。

圖1和圖2分別是CTU的劃分及四叉樹結構，每個CU是否繼續劃分由圖2的四叉樹結構來決定。圖1的每個CU可以繼續劃分為如圖3所示的2個或4個PU。PU模式包括合并模式（Merge Mode）、跳過模式（Skip Mode）、幀間模式（Inter Mode）和幀內模式（Intra Mode）四種類型。幀內預測模式都是對稱模式，有2N×2N和N×N兩種，只有在最小尺寸為8×8大小的CU時，才可以繼續劃分成4個4×4的預測塊，其他情況下，CU和PU的尺寸大小相同。

圖1 CTU的劃分

圖2 編碼四叉樹結構示意圖

圖3 HEVC的幀間PU劃分模式

幀間預測模式有6種對稱模式和4種非對稱模式，包 括 Skip、Merge、Inter 2N×2N、Inter 2N×N、Inter N×2N、Inter N×N、Inter 2N×nU、Inter 2N×nD、Inter nL×2N和Inter nR×2N共10種。后4種是非對稱模式，即非對稱運動劃分（Asymmetric Motion Partitioning，AMP）。非對稱模式在HM中是可選模式，只有當CU的尺寸大于8×8時才可以使用。非對稱模式把CU面積按1∶3進行劃分以提高幀間預測的準確性，進而提高壓縮效率。當CU尺寸為8×8時，禁止使用Inter N×N和4種幀間AMP模式，以降低幀間預測中的編碼運算量。Merge模式是HEVC新引進的幀間預測模式，采用“運動合并”技術處理運動參數，無需傳送MV信息，只傳候選PU塊的索引值，由解碼端采用運動推理方法來獲得運動信息[11]。Skip模式是Merge模式編碼塊標志（Coded Block Flag，CBF）為0的一種特殊情況，即殘差為0。HEVC的測試模型（HEVC Test Model，HM）采用全搜索遍歷方式，首先在CU層遍歷所有的深度，然后在每次遞歸過程計算出相應候選PU的率失真值的大小，選擇最小率失真對應的PU作為最佳PU。這種方法能得到高質量的視頻，節省編碼比特率，但大大增加了編碼的運算量。

由于當前CU與空時域相鄰CU深度之間存在著一定的相關性，這些CU對應的PU模式在空間劃分上也具有一定的相似性。本文將利用當前CU的運動特性來減少不必要的CU深度遍歷，實現CU深度范圍的快速決策，降低HEVC幀間預測的運算量。為了分析CU最終劃分的深度信息與視頻序列的運動、紋理之間的關系，本文在HM16.9平臺上對表1所示的5種具有不同運動特征的標準測試視頻序列進行編碼，統計出了不同類型視頻序列的CU深度特性。在編碼測試中，量化參數（Quantity Parameter，QP）設置為 32，采用隨機接入（Random Access，RA）配置，對每個測試序列編碼60幀。

表1 5種測試序列的不同CU深度比例分布

表2是5種測試序列深度值的分布比例，S4序列有25.4%的CU深度值等于0，S2序列有98.8%的CU深度值大于0，而S2和S3序列均有近一半的CU深度值為3。這表明運動平坦，紋理簡單的序列深度值小的比例較高，相反，運動劇烈，紋理復雜的序列深度值大的比例較高；由序列S0、S1及S4的CU深度分布可知，CU深度值比例分布取決于序列的運動快慢程度與紋理特性。鑒于序列CU深度與序列運動和紋理特征的關系，若在CU深度劃分前能提前預測出CU深度范圍，跳過一些CU深度值所占比例低的遍歷過程，則可加快編碼速度。

表2 5種測試序列的不同CU深度比例分布

2.2 CU深度加速預測

文獻[12]根據當前CU深度值大小與其相鄰時空域CU的關聯性，定義了如式（1）所示的當前CU（下面稱為CUcurrent）的預測候選集合S。

圖4中的 CU0、CU1、CU2和 CU3分別表示 CUcurrent空域相鄰的左側、左上側、上側和右上側的編碼單元，CU4和CU5分別是前后參考幀中與CUcurrent對應位置的編碼單元，CU6和CU7分別是CUcurrent的上一級和上二級對應的編碼單元。

圖4 CU current的空時域相鄰CU及上級深度CU

2.2.1 復雜區域的CU深度范圍快速預測

本文將空時域相鄰候選CU深度值不同的區域稱為復雜區域，利用CUcurrent周圍相鄰CU的深度值，通過式（2）和式（3）預測出CUcurrent的深度值。

其中，Depthpre為CUcurrent的加權預測深度值；i表示候選CU對應下標號；N是候選CU的個數，該算法下N取6；Depthi為第i個候選CU的深度值；αi表示第i個候選CU深度值的權重。通過對大量的測試序列進行編碼，統計出CUcurrent與其時空域相鄰CU和上級深度CU之間的相關性，得到如表3所示的CU之間的相關系數。依據表3中的數據給予空時域和上級CU分配相關的權重系數如表4所示。

為了加快對CUcurrent的深度遍歷過程，本文采用CU深度范圍（Depth Range，DR）來表示CUcurrent需要遍歷的深度區間。當得到CUcurrent的深度預測值Depthpre后，對Depthpre分別加減0.5，然后取整作為CUcurrent深度預測范圍的最大值與最小值。

表3 當前CU與候選CU之間的相關系數

表4 候選CU與其對應權重值大小

2.2.2 平滑區域的CU深度快速決策

本文將空時域相鄰候選CU深度值相同的區域稱為平滑區域。對于平滑區域，從預測候選集S中選取空域相鄰編碼塊CU0和CU2的深度值，以及時域相鄰對應塊CU4和CU5的深度值來預測CUcurrent的深度范圍。具體實現過程如下：

（1）如果4個候選CU的深度值都為0，表明前后兩幀CU附近區域相對靜止，CUcurrent提前終止劃分，CUcurrent深度值為0；

（2）如果4個候選CU的深度值都為1，則CUcurrent深度預測范圍DR為[0，2]；

（3）如果4個候選CU的深度值都為2，則CUcurrent深度預測范圍DR為[1，3]；

（4）如果4個候選CU的深度值都為3，則CUcurrent深度預測范圍DR為[2，3]。

2.2.3 CU深度加速預測算法流程

CU深度加速預測算法流程如圖5所示。首先，從預測候選集S中選取C Ucurrent的時空域相鄰編碼塊CU0、CU2、CU4和 CU5，選出這4個編碼塊深度值的最大值和最小值，分別記為Dmax和Dmin；然后判斷Dmax與Dmin是否相等，如果相等，按平滑區域對CUcurrent深度范圍DR進行快速預測，否則按復雜區域預測CUcurrent深度范圍DR。預測時，式（2）和式（3）中的N取6，即選取CUcurrent的時空域相鄰編碼塊CU0、CU1、CU2、CU3、CU4和CU5的深度值來預測其深度范圍DR；最后，遍歷DR，確定CUcurrent的深度值。

這種采用先確定CUcurrent的深度范圍DR，然后在DR中進行遍歷，最后確定CUcurrent的深度的方法將大大減少幀間編碼的時間。

2.3 幀間PU模式加速預測

圖5 CU深度范圍預測流程

當前CU與空時域相鄰CU所遍歷的PU模式在空間劃分上也具有類似的相關性。由于每個CU對應的PU模式有11種，如果能減小當前CU對應PU模式遍歷的范圍，就能加速幀間模式的選擇過程，從而降低幀間編碼過程的運算量。由于CUcurrent與CU6在空間劃分上有被包含關系，與空域相鄰CU0、CU1、CU2和CU3有紋理相似性關系，與時域相鄰CU4具有運動一致性關系。因此，當CU4與CUcurrent深度相同或者CU6比CUcurrent深度值小1時，就可以利用CU4或CU6對應的PU模式作為當前PU模式的遍歷范圍。為了表述方便，本文對于PU劃分的9個幀間預測模式和2個幀內預測模式，采用表5所示的對應編號來表示。圖6是本文幀間PU模式快速預測算法流程，根據視頻編碼區域運動的劇烈程度，CUcurrent的PU遍歷模式過程如下：

（1）判斷 CUcurrent相鄰的 CU0、CU2及上一級 CU6中的對應PU模式是否存在m0；若存在，可判斷CUcurrent所處的區域是靜止或是處于同向極其緩慢的運動狀態，且視頻紋理極其簡單，此時，CUcurrent所需遍歷的PU模式為m0和m1；否則，按下面步驟執行。

（2）如果CUcurrent和CU4深度值相同，表明此時的前后參考幀對應CU塊具有運動一致性，依次如下處理：

①當CU4對應的PU模式是m1，那么對應CU塊所處的區域是均勻運動，且視頻紋理簡單。此時，CUcurrent所需遍歷的PU模式為m0和m1。

②當CU4對應的PU模式是m2，那么對應CU塊所處的運動區域應是中等運動，且視頻紋理較平緩。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3、m4和 m5。

表5 PU劃分模式及對應編號

圖6 PU預測算法流程圖

③當CU4對應的PU模式是m3，那么對應CU塊所處的運動區域是中等運動，且視頻紋理較平緩。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3、m6和m7。

④當CU4對應的PU模式是m4，那么對應CU塊所處的運動區域是劇烈快速運動，且視頻紋理較復雜。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3和 m4。

⑤當CU4對應的PU模式是m5，那么對應CU塊所處的運動區域是劇烈快速運動，且視頻紋理較復雜。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3和 m5。

⑥當CU4對應的PU模式是m6，那么對應CU塊所處的運動區域是劇烈快速運動，且視頻紋理較復雜。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3和 m6。

⑦當CU4對應的PU模式是m7，那么對應CU塊所處的運動區域是劇烈快速運動，且視頻紋理較復雜。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3和 m7。

⑧當CU4對應的PU模式是m8，那么對應CU塊所處的運動區域是劇烈快速運動，且視頻紋理較復雜。此時，CUcurrent所需遍歷的PU模式為 m1、m2、m3和 m8。

（3）如果CUcurrent和CU4深度值不等且兩者之差ΔD等于1或2，說明CUcurrent與時域相鄰CU對應的PU模式劃分存在差別，通常運動越劇烈紋理越復雜的區域PU劃分得越細小。為了準確地預測CUcurrent對應PU模式類型范圍，本文用模式復雜度（Mode Complexity，MC）來描述PU模式的復雜類型，MC的計算公式如式（4）所示，MC越大表明運動復雜度越高。式（4）中的N是預測候選集合S中候選CU的數量，這里N的取值為8；ki用來判斷候選CU是否可用，ki取1表示候選CU可用，ki取0表示候選CU信息不可用；ωi為不同預測類型對應的權重值大小；αi為表4中第i個候選CU深度值的權重的大小。

依據所選用的PU結構劃分關系，將表5中的11種不同預測模式按復雜程度合并為4種預測類型，然后分別賦予權重值ωi為0.5、1.0、1.5和3.0，每種預測類型及其包含的PU模式如表6所示。本文依據運動劇烈程度將運動區域分為4種復雜度區間，分別用集合S、T、U和V來表示。每種運動類型之間的臨界閥值分別用T0、T1和T2來表示，依據對測試序列進行編碼得到的經驗值，可分別設為0.8、2.0和4.0。復雜度區間所對應的遍歷模式類型如表7所示。

表6 不同模式類型對應的權重值

表7 4種運動類型及其對應的區間

（4）如果CUcurrent深度與CU4的深度值之差為3，說明其對應的PU空間劃分差別也非常大，CUcurrent的PU模式不采用CU4的PU模式，結束CUcurrent的PU模式劃分，轉入下一深度CU對應的PU模式判斷。

2.4 幀間預測模式加速決策算法

本文基于時空域相鄰CU的運動特性，從CU深度劃分和PU模式選擇兩方面來加速幀間的預測過程。

首先，預測出當前CU的深度。依據CUcurrent空時域相鄰候選CU深度值是否相同，將編碼區域分為復雜區域和平滑區域兩種類型，針對不同的區域類型按圖5所示的流程，選擇不同的預測算法來加速CU深度的決策過程。

然后，判斷CUcurrent的PU模式。依據CUcurrent深度與空時域相鄰CU及上一深度CU對應的PU模式在空間劃分上的相似性來減少CUcurrent的對應PU模式的遍歷范圍，加速PU模式的選擇。PU模式的快速選擇流程如圖6所示。

3 實驗結果及分析

本文算法在HM16.9上進行了實現，編碼端的基本參數如下：最大CU尺寸為64；最大劃分深度為3；量化步長QP分別取22、27、32和37；選取測試序列分為A、B、C、D、E共5種類型，共18組標準測試序列作為編碼對象，這5種類型測試序列的分辨率分別為2 560×1 600、1 920×1 080、832×480、416×240和1 280×720，且每個測試序列的輸入比特深度為8；其他配置參數及測試條件參考了HM提案JCTVC-J1100[13]。根據文獻[13]，采用RA接入方式的編碼器測試A、B、C和D類4種測試序列；采用低延時（Low Delay，LD）接入方式的編碼器測試B、C、D和E測試序列；測試所用的硬件平臺為泰克公司的圖像質量分析儀PQA600A，其配置為12核CPU，2.30 GHz主頻，32 GB內存，64位Windows7操作系統。

為了測試編碼率失真性能在4個QP下的變化，采用BDBR（Bjntegaard Detla Bit Rate）和BDPSNR（Bjntegaard Detla Peak Signal to Noise Ratio）[14]作為測試指標。使用式（5）計算得到的PSNR來評價圖像編碼的質量[15]。

式（5）中，PSNRV和PSNRU表示色度峰值信噪比，PSNRY表示亮度峰值信噪比。利用式（6）計算得到的編碼時間變化率來評估算法的加速性能。式（6）中的THM16.9和Tfast分別為HM16.9和采用本文算法的編碼器對測試序列編碼所需的時間。

表8和表9分別為本文提出的CU深度加速預測算法和PU模式加速預測算法在RA、LD兩種接入方式下的性能測試結果。對比HM16.9算法，在RA編碼方式中，平均輸出比特率在分別增加了1.43%和2.16%的情況下，平均編碼時間分別減小了28.58%和48.97%，而視頻的平均PSN R都只降低了0.06 dB；在LD編碼方式中，平均輸出比特率分別增加1.64%和1.68%的情況下，平均編碼時間分別減小了25.53%和46.86%，視頻的平均PSN R損失均不高于0.05 dB。測試數據表明，本文算法在RA和LD兩種不同接入方式下都能有效地降低CU深度劃分的復雜度，減少PU模式的遍歷范圍，加速了幀間編碼過程。

為了評估本文幀間模式快速算法的整體性能，在HM16.9平臺上，對文獻[10]中的算法進行了實現，并分別對本文算法和文獻[10]算法進行了性能測試，測試結果如表10和表11所示。在RA編碼方式下，本文算法和文獻[10]算法相對HM16.9，平均編碼時間分別降低了53.93%和48.48%，采用本文算法的平均編碼輸出比特率增加了2.92%，略高于文獻[10]的2.36%，而編碼后視頻失真度基本一致，平均PSNR均下降了0.09 dB。本文算法針對高分辨率的A類和B類視頻序列，相對于HM16.9，平均編碼時間降低了58.36%，而對于中低分辨率的C類和D類視頻序列，平均編碼時間降低了50.05%，說明本文算法針對高清視頻序列有更好的編碼加速性能。在LD編碼方式下，本文算法和文獻[10]算法相對HM16.9，平均編碼時間分別降低了56.64%和49.96%，采用本文算法的平均編碼輸出比特率增加了2.98%，同樣略高于文獻[10]的2.08%，且編碼后視頻失真程度更小，平均P SNR減小均不超過0.07 dB。

表8 CU深度加速預測算法和PU模式加速預測算法在RA配置下性能比較

表9 CU深度加速預測算法和PU模式加速預測算法在LD配置下性能比較

對運動劇烈的測試序列，如BasketballDrive、BasketballDrill、RaceHoursesC、BasketballPass和RaceHorses，在RA編碼方式下本文算法平均編碼時間降低了52.14%，文獻[10]算法降低了45.89%；而在LD編碼模式下本文算法平均編碼時間降低了56.15%，文獻[10]算法降低了46.03%。說明相對文獻[10]算法，本文算法在兩種編碼方式下均能有效降低運動劇烈視頻序列的編碼運算量，并且本文算法在LD編碼方式下效果更顯著。

4 結束語

為了有效降低HEVC的編碼時間，本文通過對CU深度劃分和PU模式選擇過程的分析，提出了一種基于運動特性的幀間預測模式快速算法。首先，依據視頻運動及紋理特性，采用時空域相鄰CU來預測當前CU深度范圍，加速編碼單元的劃分過程；然后，利用CU的PU在深度上下級和相鄰時空域上的相似性，減少PU類型的遍歷過程。實驗仿真結果表明，本文提出的改進算法在視頻質量基本沒有損失，輸出比特率增加較小的前提下，大幅度降低了平均編碼時間。

表10 本文算法與文獻[10]算法在RA配置下性能比較

表11 本文算法與文獻[10]算法在LD配置下性能比較