HEVC幀內預測算法加速設計與實現

王飛龍 劉新闖 劉 鵬 辛曉斐 石鵬飛

1(西安郵電大學電子工程學院 陜西 西安 710121)2(西安郵電大學計算機學院 陜西 西安 710121)

0 引 言

近年來，隨著高清和超高清視頻的發展，視頻應用已經轉向了數字視頻廣播、移動無線視頻、遠程監控和便攜式攝影等的應用。文獻[1]中闡明了高分辨率和多樣性逐漸成為了視頻應用的發展趨勢，海量的數據處理對視頻編碼提出了高要求。文獻[2]中指出了隨著超大規模集成電路的發展，半導體工藝的進步為新型的數字媒體作出了巨大的貢獻。在一個芯片內集成多個處理器成為了可能，為處理具有海量的數據像素，計算量繁瑣的HEVC算法提供了新的思路。

在幀內預測并行化的過程中，國內外的眾多研究人員和學者提出了不同的方法。文獻[3]建議將序列劃分為一些GOP。GOP之間的相關性很低，它不僅可以限制錯誤傳播，還可以支持并行編碼處理。但是，它需要在并行之前獲取GOP中所有圖片的數據。當GOP圖片太多時，會導致嚴重的延遲，這對于實時視頻編碼應用來說并不方便。文獻[4]提出在幀級實現并行編碼。這種方法局限于幀之間的相關性，因此加速比不能隨著處理器核的數目增加而線性增加。文獻[5-6]提出將宏塊(MB)的預測、變換和熵編碼組織為流水線并將它們分配給多個核，以進行并行計算。如果工作負載在不同處理核處不平衡，則這類方法可以實現有限的并行性。在文獻[7]中，通用四核計算機上的高清晰度序列提高了兩倍的速度。

盡管在并行化方面現有編碼算法做了很多努力，但由于幀內預測中的塊之間的強依賴性以及頂部/左側重建樣本的濾波過程，小塊的幀內亮度預測過程是一個挑戰。原始進程處理串行塊，效率不高。在文獻[8-9]中已經說明了有效的體系結構，其建議以波前序列對MB進行處理，以便當相鄰的MB可用時，可以同時對每條對角線中的MB進行編碼。由于MB級別的細粒度并行性，這些方法可以實現良好的并行性，目前被廣泛使用。

上述提出的方法均提高了幀內預測算法的執行效率。本文通過分析幀內預測算法在處理像素過程中數據之間的依賴關系，將幀內預測算法進行基于預測模式的細粒度并行性設計，并且塊與塊之間采用流水線處理，在保持失真率較低的前提下，減少了幀內預測算法的執行時間，顯著地加速了幀內預測算法。相比于HM16.0官方測試標準，信噪比提高了10%，算法的執行時間減少了大約70%。

1 幀內預測算法分析

1.1 HEVC中的空域預測

HEVC是由JCT-VC(視頻編碼聯合協作小組)在2013年提出的一種新的視頻壓縮標準，它是H.264的一個擴展。相比于H.264，它可以在保證相同視頻質量的前提下，壓縮效率提高50%，但是算法復雜度也隨之提高。文獻[10]指出了關于高效視頻編碼的部分內容已經被運用到HEVC測試模型(HM)中。幀內編碼的主要改進來自如下兩個工具。

1.1.1幀內預測

文獻[11]指出了對于不同的尺寸大小，幀內預測支持16到34個預測方向，并且可以實現1/8像素精度。通過指示預測角度，允許在任意方向上進行塊預測，從而顯著提高了編碼效率。

1.1.2基于四叉樹的編碼結構

利用尺寸大于16×16像素的宏塊結構可以顯著提高編碼效率，特別是在高分辨率的序列中。為了實現更靈活的編碼方案，HEVC利用基于四叉樹的編碼結構[12]，支持尺寸為64×64、32×32、16×16、8×8和4×4像素的宏塊。

HEVC分別定義了三個塊概念：編碼單元(CU)，預測單元(PU)和變換單元(TU)。在定義了最大編碼單元(LCU)的大小和CU的分層深度之后，編解碼器的整體結構以遞歸方式由CU、PU和TU的各種大小來表征。這允許編解碼器容易地適用于具有不同能力的各種內容、應用或設備。CU分裂過程如圖1所示，使用分裂標志來確保當前CU是否需要分割成更小的尺寸。

1.2 HEVC幀內算法的并行性分析

HEVC幀內預測算法規定一幀圖像可以被劃分為N×N(N=4，8，16，32，64)的塊處理。對每種N×N塊進行處理時，首先對參考像素進行濾波，運用濾波完成后的像素，遍歷35種模式，分別得到每種預測模式下所對應的預測像素。運用下式求取殘差值，并計算SAD值：

Diff(i,j)=BlockA(i,j)-BlockB(i,j)

(1)

(2)

式中：BlockA(i,j)是原始像素塊，BlockB(i,j)是預測像素塊。

判斷比較35個SAD值，選取最小SAD值，將此SAD值對應殘差塊傳遞給下一個模塊DCT變換。對于一個N×N的塊，在預測過程中，plannar模式、DC模式、33種角度模式均是利用參考像素進行計算，得到預測像素，而且plannar模式、DC模式、33種角度模式之間并不存在數據的依賴關系,彼此獨立計算，所以是可以并行計算的。

2 動態可編程可重構視頻陣列處理器

本文所用的驗證平臺是動態可編程可重構視頻陣列處理器，它支持H.264/AVC、H.265/HEVC視頻編碼標準，還有并行度高的算法。它由1 024個PE(processor element)組成，可以完成海量的數據處理，不管是在空間上還是在時間上，都實現了并行。如圖2所示，整個系統平臺由三個部分組成。

圖2 動態可編程可重構視頻陣列處理器結構圖

2.1 輕核處理單元

陣列處理器由1 024個PE(processor element)組成，每16個PE在邏輯上劃分為一個PEG(processor element group)，共有64個PEG。每個PE由16個通用寄存器組成，可以支持算術、邏輯運算，分支跳轉指令，用于視頻像素點的計算。

2.2 互連機制

PE之間進行通信所用的機制是鄰接互連，鄰接互連采用2D-mesh結構，運用四個共享寄存器，完成相鄰PE之間的數據交互。圖3展示了鄰接互連結構，有兩種數據交互方式，分別用實線和虛線表示。在PEG之間，通過路由進行通信。

圖3 鄰接互聯數據交互圖

2.3 存 儲

每個PE內部包含512×32 bit指令存儲器，數據存儲器，將每個PE的數據存儲器統一編址，運用所設計的交叉開關邏輯，可以在一個PEG內，任意的PE可以對其他的PE進行訪問，使得在一個PEG內實現存儲共享。

3 算法的并行映射及塊間處理

3.1 幀內預測算法并行映射

文獻[15]闡述了在HEVC測試模型HM中，uiRd Mode List數組中排名第一的預測模式和MPM(Most Probable Mode)中的預測模式被選擇的概率是非常大的。本文統計了在不同的測試序列下以及不同的CU劃分下uiRd Mode List數組中排名第一的預測模式和MPM(Most Probable Mode)中的預測模式，結果顯示，平面模式0、DC模式1、水平預測模式10、垂直預測模式26、角度模式18、角度模式22為被選中概率最大的6種模式。所以本文選取了這六種模式作為幀內預測算法中的模式。

圖4給出了幀內預測并行算法的流程圖，主要包括三個部分：參考像素以及原始像素的獲??；6種模式的計算；判斷SAD值并進行最優模式的選取。圖5是所設計的幀內預測并行算法在陣列處理器上的映射圖。處理過程包括三個部分：數據加載；預測計算；最優模式的選取。

圖4 幀內預測并行算法的流程圖

圖5 幀內算法映射圖

3.1.1數據加載

本文以8×8塊為例進行說明。如圖6所示，在DIM中存入一幀圖像的像素，運用鄰接互連指令，每次從DIM中取出97個像素，包括64個原始像素，以及原始塊左上方的33個參考像素。存入PE00數據存儲器中，運用共享存儲指令，將PE00中數據存儲器中的97個像素加載到PE01、PE02、PE11、PE12、PE13、PE20的存儲中，加載完成后，在PE01、PE02、PE11、PE12、PE13、PE20數據存儲中的固定地址存入一個確定的值，用來表示數據存儲已完成。

圖6 鄰接互聯數據交互圖

3.1.2計算預測像素

在PE01、PE02、PE11、PE12、PE13、PE20中，讀取各自存儲中已存入的確定值，比較相等后，說明參考像素已經存儲到相應的PE存儲中。分別在各自的PE中處理平面模式、DC模式、角度模式中的26、10、18、22號模式，從而得到不同預測模式下的64個預測像素。運用式(1)、式(2)得到不同的模式下的SAD值、殘差值，并存入PE03的數據存儲中。最后，在PE03的數據存儲中寫入一個確定值，表示數據SAD值已經存入完成。

3.1.3選取最優模式

在PE03中讀取已經存入的確定值，比較相等后，說明SAD值、殘差值已經存入到PE03中。然后比較每種預測模式下的SAD值大小，選出最小值，此模式作為最優預測模塊，將殘差值存入PE33中，通過鄰接互連指令，輸出給下一級的DCT模塊。

3.2 幀內預測算法的塊間流水處理

運用視頻陣列處理器多核并行處理的優勢，通過鄰接互連機制結合比較跳轉指令，可以將任務組織為串行的形式進行處理。在上述處理8×8塊的例子中，計算預測模式運用數據加載模塊的結果，最優模式的選取運用計算預測像素模塊的結果，均存在數據依賴關系。本文通過共享存儲指令結合與比較跳轉指令，使數據加載模塊，計算預測像素，選取三個模塊反復執行，將塊與塊之間組織為流水線處理。

圖7為塊與塊之間進行流水處理的示意圖，橫坐標代表時間，縱坐標代表所用的PE資源。塊的加載時間為T1，計算預測模式T2，最優模式的選取T3，并且T1>T2>T3，從而保證每個塊正確執行。在第一個T1時間段內加載第一個塊；在第二個T1時間段內加載第二個塊，同時計算第一個模塊的預測像素；在第三個T1時間段內加載第三個塊，同時計算第二個模塊的預測像素，并且選取第一個塊的最優模式；在第四個T1時間內可以得出第二個塊的最優預測像素。照此執行直到一幀圖像中的所有塊被處理完。

圖7 塊與塊之間進行流水處理的示意圖

4 實驗分析

文獻[14]規定了幀內、幀間預測的配置以及測試序列類別。為了使得所選的測試序列具有代表性，實驗選取了(class A,class B,class C,class D,class E)不同分辨率下的兩種序列來驗證所提出的幀內預測并行算法。

陣列處理器實驗平臺是運用verilog HDL搭建的，運用Synopsys公司的DC(designcompiler)工具，在SMIC90nm工藝庫下進行綜合。表1給出了一個PEG的綜合結果。

表1 一個PEG的綜合結果

將表2中的10種測試序列分別存入到DIM中，對并行設計的幀內預測算法進行評估。

表2 本文設計的并行算法性能統計

信噪比PSNR的計算公式如下：

(3)

(4)

式中：m、n代表圖像像素為m×n；I、K分別代表原始圖像和處理完成后的圖像；Kmax表示圖像處理完成后，m×n個像素中像素最大的值。統計原圖像與處理圖像像素I和K，計算得到每種測試序列下的PSNR。

在modelsim10.0c軟件下統計所用的時鐘周期數n，除以綜合頻率，得出每種測試序列下的運行時間T。

T=t/f

(5)

式中：n為幀內預測算法所用的時鐘周期數；f表示綜合頻率。

實驗環境為intel(R)Core(TM)i5-8400 CPU@2.80 GHz，內存為16 GB。運用HM16.0軟件，分別測試上述10種序列，得出幀內預測算法的運行時間T，信噪比PSNR，如表3所示。

表3 HM16.0性能統計

THM、Y_PSNRHM分別為HM軟件所得出的時間和信噪比，Tpro、Y_PSNRpro分別為本文所設計的并行算法的時間和信噪比，則：

(6)

(7)

如表4所示，本文所提出的并行算法相比于官方HM16.0測試軟件，平均ΔY_PSNR提高了大約10 dB,平均ΔT減少了74.20%。在相同的HM16.0測試環境下，實驗對比結果如表5所示，用本文算法的平均ΔT減去文獻[13]、文獻[16]、文獻[17]算法的ΔT，分別比文獻[13]、文獻[16]、文獻[17]算法多減少了24.20%、34.28%、41.78%。由此可見，本文所提出的方案對HEVC幀內預測算法實現了顯著的加速效果。

表4 不同測試序列下相比于HM16.0的結果 %

表5 實驗對比結果 %

5 結 語

本文通過對HEVC幀內預測算法的處理流程進行分析，挖掘出數據之間的依賴性，將幀內預測算法進行了基于預測模式的細粒度并行設計，并且塊與塊之間采用流水線進行處理，在視頻陣列處理器上進行映射。運用10種測試序列進行驗證，結果顯示，相比與HM16.0官方測試軟件，在時間上減少了74.20%，信噪比增加了10 dB，有了顯著的加速效果。本文從算法分析的角度對幀內預測算法進行并行性的設計，相比于塊、圖片組的粗粒度并行算法，本文提出了一種細粒度的并行方法，在塊與塊之間進行流水技術，對幀內預測算法實現了顯著的加速。鄰接互連的數據交互時間、共享存儲的訪問時間，都會影響PE之間數據的通信效率。對這兩種機制進行改進，幀內預測算法的執行時間和圖像的失真率將會進一步減少，對視頻的實時性處理有很大的幫助。