王 欣，蔣 林，曹 非，李遠(yuǎn)成

(1.西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710600；2.西安科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安 710600)

0 引言

高效視頻編碼(High Efficiency Video Coding，HEVC)標(biāo)準(zhǔn)是新一代視頻編碼國際標(biāo)準(zhǔn)。與上一代標(biāo)準(zhǔn)H.264/AVC相比，在編碼結(jié)構(gòu)上放棄了宏塊的概念[1]，采用了對圖像進(jìn)行四叉樹劃分的方式。這種四叉樹遞歸結(jié)構(gòu)在將壓縮效率提升了1倍的同時，也極大地增加了編碼計算復(fù)雜度與編碼時間[2]。因此，降低四叉樹編碼過程中的計算復(fù)雜度與減少編碼時間是研究的問題之一[3]。

針對高效視頻編碼中編碼復(fù)雜度高的問題，一些研究通過算法的簡化，降低四叉樹編碼復(fù)雜度[4]。文獻(xiàn)[5]針對快速編碼單元(Coding Unit，CU)編碼過程中四叉樹遍歷計算出現(xiàn)的冗余信息，提出了一種靈活的復(fù)雜度分配機制，該分配機制將CU深度決策問題轉(zhuǎn)換為分類問題。但是，該方法存在計算量大和存儲成本高的問題。從視頻編碼算法的角度考慮[6]，優(yōu)化后的算法計算量仍然巨大，單從算法層面去進(jìn)行優(yōu)化[7-8]，仍然無法滿足實時視頻編碼的需求。所以，在優(yōu)化編碼算法的同時，采用FPGA進(jìn)行并行加速也是提升編碼效率的一種更有效的方式。文獻(xiàn)[9-11]在優(yōu)化編碼算法的同時進(jìn)行了FPGA加速，縮短了編碼時間，但也占用了較大的硬件資源和專用的DSP。文獻(xiàn)[10]基于多核處理器實現(xiàn)了解碼器，雖然有效利用了多核的并行性，但其使用了多達(dá)64個處理單元，硬件成本較高。

針對高效視頻編碼中編碼復(fù)雜度高的問題，可以通過FPGA加速來提高編碼效率。利用硬件加速器來實現(xiàn)視頻編碼加速，執(zhí)行計算密集型算法，以滿足視頻應(yīng)用的性能要求，是當(dāng)前的研究熱點。四叉樹編碼算法的數(shù)據(jù)以CU的形式參與運算，運算步驟相對獨立，計算過程中數(shù)據(jù)依賴性低，具有較高的并行性，適合可重構(gòu)陣列處理器進(jìn)行并行運算。四叉樹編碼的過程中會將圖像的數(shù)據(jù)最大劃分為樹形結(jié)構(gòu)單元(Coding Tree Unit，CTU)，且編碼過程可以劃分成不同的模塊，不同的CTU間便可以采用流水線作業(yè)思想進(jìn)行加速作業(yè)。

綜上所述，基于可重構(gòu)陣列處理器，提出了一種新的四叉樹CU劃分并行化設(shè)計方案，在不考慮功耗的情況下，重點研究設(shè)計方案在并行加速與硬件資源消耗等方面的性能，實現(xiàn)四叉樹CU在可重構(gòu)陣列上的高效靈活部署。

1 四叉樹CU劃分算法及并行性分析

1.1 四叉樹CU劃分算法

HEVC編碼結(jié)構(gòu)首先是將視頻劃分為圖像組(Group of Picture，GOP)，CTU是HEVC里的基本處理單元。在每個CTU內(nèi)部按照四叉樹的循環(huán)分層結(jié)構(gòu)劃分為不同的CU，CU是HEVC總體框架的基本單元。一幅圖像劃分為CTU以及一個CTU劃分為CU的圖像,劃分結(jié)構(gòu)示意圖如圖1所示。

CU的循環(huán)四叉樹分層結(jié)構(gòu)如圖2所示。CU是否繼續(xù)劃分取決于分割標(biāo)志位(Splitflag)。對于編碼單元CUd，假設(shè)其大小為2N×2N，深度為d。若它對應(yīng)的Splitflag值為0，則CUd不再進(jìn)行劃分；反之，CUd將會作為四叉樹劃分的根源被劃分為4個獨立的編碼單元CUd+1，編碼單元CUd+1的深度和大小變?yōu)閐+1和N×N。HEVC標(biāo)準(zhǔn)中最大的編碼單元(Largest Coding Unit，LCU)為64×64。

圖1 圖像劃分結(jié)構(gòu)示意Fig.1 Schematic diagram of image division structure

圖2 CU的循環(huán)四叉樹分層結(jié)構(gòu)Fig.2 Cyclic quadtree hierarchical structure of coding unit

在HEVC測試模型參考軟件中會有很多種可能的分割方法，通過尋找率失真(Rate Distortion，RD)最小的方法作為最佳分割[12]。率失真的計算公式如下：

J=SATD(S,P)+λmodeRmode，

(1)

式中，SATD(S,P)為經(jīng)過幀內(nèi)預(yù)測后得到的殘差塊的SATD；λmode為拉格朗日因子；Rmode為編碼當(dāng)前模式所需要的比特數(shù)。SATD是指將殘差信號進(jìn)行哈達(dá)瑪變換后再求元素絕對值之和。

算法對每個CU均進(jìn)行率失真的計算，計算方法如下：

JCUi=JCU0+JCU1+JCU2+JCU3，

(2)

式中，JCUi(i=0,1,2,3)表示當(dāng)前CU的率失真；JCU0，JCU1，JCU2，JCU3表示分割后4個更小的CU的率失真。

通過遞歸的方式獲取所有的CU的率失真，對每一深度進(jìn)行分割后CU與分割前CU的率失真比較，選取率失真小的作為最優(yōu)CU分割方法。若J分割前>J分割后，此時Splitflag值為1，CUd將會作為四叉樹劃分的根源被劃分為4個獨立的編碼單元CUd+1。若J分割前

HEVC這種靈活的單元表示方法可以使得在平緩區(qū)域編碼效率大大提高的同時提供數(shù)據(jù)并行處理的結(jié)構(gòu)單元。

1.2 四叉樹編碼劃分的并行性分析

考慮到HEVC標(biāo)準(zhǔn)的特點,在四叉樹編碼劃分的過程中信息劃分為相互獨立的部分，每一部分交給不同的處理單元PE來處理。結(jié)合分布式共享存儲結(jié)構(gòu)，從數(shù)據(jù)級并行的角度進(jìn)行算法加速。數(shù)據(jù)并行實現(xiàn)示意圖如圖3所示。

圖3 并行實現(xiàn)示意Fig.3 Schematic diagram of data parallel implementation

在CTU進(jìn)行四叉樹編碼劃分的內(nèi)部，由于每個CTU的數(shù)據(jù)之間要進(jìn)行比較判別運算，相鄰數(shù)據(jù)之間存在依賴關(guān)系，因此，可將CTU劃分成不同的塊，多塊CTU被分別送到不同的PE處理單元中并行進(jìn)行判別運算處理，當(dāng)每個PE處理結(jié)果出現(xiàn)判別結(jié)束的標(biāo)志時，將這個PE的輸出結(jié)果基于CTU到CU間的循環(huán)嵌套分層結(jié)構(gòu)再進(jìn)行下一層次的判別運算。若所有進(jìn)行多塊CTU的PE劃分到最后，則將多塊CTU的數(shù)據(jù)再整合進(jìn)行判別，最終得到編碼劃分結(jié)果。在整個HEVC編碼過程中，可以分為不同的模塊，主要進(jìn)行數(shù)據(jù)加載、率失真的計算與比較、不同深度的數(shù)據(jù)劃分和編碼劃分結(jié)果的輸出，各個功能的模塊組成串行的四級流水，而分別在各個模塊的內(nèi)部，針對不同的子數(shù)據(jù)進(jìn)行數(shù)據(jù)并行。這樣，在四叉樹CU的劃分過程中基于可重構(gòu)陣列處理器混合功能并行和數(shù)據(jù)并行2種并行方式對編碼過程進(jìn)行加速。

2 基于可重構(gòu)陣列處理器的四叉樹編碼劃分并行實現(xiàn)

2.1 可重構(gòu)陣列處理器硬件結(jié)構(gòu)

可重構(gòu)陣列處理器(基于FPGA實現(xiàn)的BEE4平臺)，能夠滿足四叉樹CU劃分的并行化設(shè)計需求[13]?？芍貥?gòu)陣列處理器由主控器和可重構(gòu)處理單元陣列組成?？芍貥?gòu)陣列處理器的部分硬件結(jié)構(gòu)如圖4所示，主要包括數(shù)據(jù)輸入存儲、陣列處理器、全局控制器、指令存儲器和數(shù)據(jù)輸出存儲器5部分。

圖4 可重構(gòu)陣列處理器部分硬件結(jié)構(gòu)Fig.4 Part of the hardware structure of the reconfigurable array processor

可重構(gòu)陣列處理器結(jié)構(gòu)中每16個處理單元(Process Element，PE)組成一個簇(Processing Element Group，PEG)，采用4×4的矩陣結(jié)構(gòu)。采用分布式共享存儲結(jié)構(gòu)，這種結(jié)構(gòu)是一種最直接且并行度很高的高速交換單元結(jié)構(gòu)。在邏輯上整個片上存儲采用統(tǒng)一的編址方式，在物理上分布于各個PE，實現(xiàn)了存儲的并行訪問。具有“邏輯共享、物理分布”特性的分布式存儲結(jié)構(gòu)，所表現(xiàn)出的并行化設(shè)計優(yōu)勢，適合四叉樹編碼劃分算法這種數(shù)據(jù)密集型算法。

2.2 四叉樹編碼劃分并行實現(xiàn)

基于可重構(gòu)陣列處理器硬件結(jié)構(gòu)以及1.2節(jié)中四叉樹編碼劃分的并行性分析，從功能并行和數(shù)據(jù)并行2種并行方式對編碼過程進(jìn)行加速及映射實現(xiàn)。

2.2.1 基于分布式存儲的并行映射實現(xiàn)——數(shù)據(jù)并行

四叉樹編碼劃分的16個PE并行映射圖如圖5所示。

步驟1：將要劃分的原始圖像幀數(shù)據(jù)存儲在數(shù)據(jù)輸入存儲DIM中。PE00與DIM相連，將外部存儲中原始的一幀圖像分為64 pixel×64 pixel的CTU數(shù)據(jù)通過PE進(jìn)行數(shù)據(jù)下發(fā)，分別下發(fā)給00～33號這16個PE。

步驟2：每個PE并行對其數(shù)據(jù)進(jìn)行判別運算，若PE中的數(shù)據(jù)判別結(jié)果Splitflag值為1，直接將PE的RAM中的16×16的CU塊數(shù)據(jù)分割成8×8的CU，此時輸出depth為3；若每個PE中判別結(jié)果Splitflag值為0，若PE00，PE01，PE10，PE11內(nèi)數(shù)據(jù)判別Splitflag值均為0，則判別這4個PE的Splitflag值；若Splitflag值為1，此時輸出depth為2；與此同時，PE02，PE03，PE12，PE13；PE20，PE21，PE30，PE31；PE02，PE03，PE12，PE13均并行采取相同的操作。

步驟3：若PE00，PE01，PE10，PE11的輸出結(jié)果Splitflag值為0，且PE02，PE03，PE12，PE13的輸出結(jié)果Splitflag值為0；PE20，PE21，PE30，PE31的輸出結(jié)果Splitflag值為0；PE02，PE03，PE12，PE13的輸出結(jié)果Splitflag值為0，則判別這4部分的輸出的Splitflag值，若Splitflag值為1，則輸出depth為1；否則，輸出depth為0。

圖5 基于可重構(gòu)陣列處理器的四叉樹編碼劃分映射Fig.5 Quadtree coding division mapping based on reconfigurable array processor

2.2.2 基于流水線加速并行——功能并行

在采用16個PE進(jìn)行四叉樹編碼的過程中，可以將劃分過程分為數(shù)據(jù)加載、率失真的計算與比較、不同深度的數(shù)據(jù)劃分以及編碼劃分結(jié)果的輸出等不同的模塊。有的PE在算法的執(zhí)行過程中會處于空閑狀態(tài)，為了最大化地減少編碼時間，使用如圖6所示的流水線方式實現(xiàn)CTU間并行加速，其中B1～Bm是指在四叉樹劃分過程中不同深度模塊的操作。

圖6中，將圖像的像素塊通過原始數(shù)據(jù)加載、Splitflag值計算、深度劃分和結(jié)果輸出這4個部分進(jìn)行四叉樹編碼劃分。當(dāng)?shù)谝粋€CTU數(shù)據(jù)加載完成后，第二個CTU開始原始數(shù)據(jù)加載。因此，采用此流水線方式能夠縮短編碼劃分的執(zhí)行時間。采用16個PE進(jìn)行四叉樹編碼劃分的方案采用流水線方式加速的設(shè)計方法，算法如下所示：

if addparallel(“Quadtree”,1)finish∥激活四叉樹編碼劃分操作

The core 1exec

Quadtree(image_orgin,image_code);

endif

addparallel(input,the_core)={

i=get_input_core_ID(input);

if the coreiisfreedom∥確定處理單元是否空閑

return finish;

else

continue to wait;∥同步

endif}

其中，addparallel(“Quadtree”1)詢問處理單元是否處于freedom狀態(tài)，對于繁忙狀態(tài)則需要等待，進(jìn)行線程同步；反之，直接進(jìn)行運算處理。

圖6 四叉樹編碼劃分時空間流水線作業(yè)圖Fig.6 Spatial pipeline operation diagram of quadtree coding division

2.3 重構(gòu)信息配置

在編譯方式上，與通用編譯為單一目標(biāo)處理器的匯編指令不同，可重構(gòu)編譯通過軟硬件劃分，將劃分結(jié)果分別生成主控制器的控制碼以及配置陣列處理器上的配置信息?？芍貥?gòu)陣列處理器的執(zhí)行方式是通過主處理器將任務(wù)下發(fā)給可重構(gòu)陣列處理器執(zhí)行，采用主控制器選擇片上配置存儲器中的信息，將信息下發(fā)給處理簇PEG執(zhí)行，每個簇再通過片上配置存儲器將存儲的可重構(gòu)配置信息分配到PE中進(jìn)行運算。

重構(gòu)配置信息執(zhí)行示意圖如圖7所示。首先，通過分析四叉樹CU的劃分算法與可重構(gòu)陣列結(jié)構(gòu)的關(guān)系得到四叉樹CU算法的配置信息。然后，將配置信息載入到片上配置存儲器，在可重構(gòu)計算陣列執(zhí)行時，載入PEG。最后，在并行執(zhí)行的過程中，PEG00載入四叉樹編碼劃分配置信息后重復(fù)執(zhí)行N次四叉樹編碼劃分，最后得到四叉樹編碼劃分的結(jié)果。

圖7 可重構(gòu)配置信息執(zhí)行示意Fig.7 Schematic diagram of reconfigurable configuration information execution

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

3.1 實驗平臺環(huán)境

為了驗證四叉樹編碼并行化實現(xiàn)方案的可行性，在基于BEECube公司BEE4開發(fā)平臺搭建的可重構(gòu)陣列處理器原型系統(tǒng)上進(jìn)行驗證和測試[14]。首先，將算法代碼編譯為可重構(gòu)陣列處理器匯編指令代碼；接著，用指令翻譯器將匯編代碼指令翻譯成二進(jìn)制代碼；然后，使用Questasim10.1d進(jìn)行功能仿真驗證，通過Xilinx公司的ISE14.7開發(fā)環(huán)境對設(shè)計進(jìn)行綜合，并分析其性能；最后，在參考軟件HM中測試編碼性能，并將本文提出的四叉樹編碼劃分并行化方案在可重構(gòu)陣列處理器測試平臺中進(jìn)行FPGA硬件測試。

3.2 實驗結(jié)果

3.2.1 運行時間分析

實驗通過串行和并行2種實現(xiàn)方案對算法并行模塊運行時間做對比分析。算法的運行時間通過Qusetasim進(jìn)行功能仿真得到。在depth_balloons測試序列中找到4種具有代表性的CTU劃分模型，如圖8所示。測試模型a不進(jìn)行劃分，最大深度為0；測試模型b是一個深度為1的根節(jié)點劃分為最大深度3；測試模型c是一個深度為2的根節(jié)點劃分為最大深度3；測試模型d是全劃分為最大深度3。

在算法執(zhí)行過程中，記錄4種測試模型從開始到結(jié)束的時間來計算運行時間。4種測試序列在不同實現(xiàn)方案下的運行時間對比如表1所示。

(a) 測試模型a

(b) 測試模型b

(c) 測試模型c

(d) 測試模型d

表1 不同測試模型下不同方案運行時間對比

由表1可以看出，用于測試的4種測試模型a～d的數(shù)據(jù)量是逐步增加的，測試模型a～d體現(xiàn)并行性的程度是逐漸提高的。與單個PE串行相比，并行方案在4種測試模型下的平均加速比達(dá)到了9.64，在可重構(gòu)陣列處理器上PE資源的使用比例，即在一個簇內(nèi)的PE資源利用率提高了93.75%。

由統(tǒng)計的運行時間可以看出，并行加速比都隨著測試模型數(shù)據(jù)并行性的增加而增加。本文基于可重構(gòu)陣列處理器所設(shè)計的并行方案在不同的測試模型中均可提高數(shù)據(jù)的并行性，減少編碼時間，特別是在數(shù)據(jù)量越大、數(shù)據(jù)劃分越復(fù)雜的情況下。因而針對四叉樹編碼這種數(shù)據(jù)密集型算法，并行方案能夠有效減少算法的運行時間。

文獻(xiàn)[15]提出了一種基于四叉樹模型的快速幀間編碼算法，同時考慮CU深度級別的邊緣信息，提出了一種快速CU劃分方案。根據(jù)提出的四叉樹模型和CU大小的相關(guān)性盡早確定可能的深度范圍，加快編碼過程。其實驗平臺為Inter? CoreTMi5 CPU，16 GB內(nèi)存。本文基于可重構(gòu)陣列處理器的結(jié)構(gòu)特點進(jìn)行算法的并行實現(xiàn)，減少編碼時間。采用本文所提出的并行化方案對PartScence，Basketballdrive，BQTerrace和Cactus測試序列進(jìn)行編碼劃分，編碼時間對比如圖9所示。與文獻(xiàn)[15]相比，本文對測試序列Cactus進(jìn)行四叉樹劃分的編碼時間減少最多，相比文獻(xiàn)[15]編碼時間總體提升約36倍。

圖9 編碼時間對比Fig.9 Coding time comparison chart

3.2.2 編碼性能對比分析

本文與3D-HEVC參考軟件(HM)中幾種測試序列在編碼過程中CU劃分結(jié)果分析統(tǒng)計并進(jìn)行了對比，結(jié)果如圖10和11所示。

圖10 HM劃分結(jié)果Fig.10 HM division result

圖11 本文劃分結(jié)果Fig.11 Division results of test

從圖10和11中的數(shù)據(jù)對比可以得出，本文與HM測試模型相比編碼劃分結(jié)果的精準(zhǔn)率為86%。

使用本文的方法作為編碼劃分的方法，選取了5組測試序列在BeeCube公司的BEE4搭建的可重構(gòu)陣列處理器測試平臺中進(jìn)行驗證測試。采用的峰值信噪比(Peak Signal to Noise Ratio，PSNR)和結(jié)構(gòu)相似性(Structural Similariy Index Measurement，SSIM)是2種常用的圖像質(zhì)量評價指標(biāo)，對完整Ι幀的測試結(jié)果圖像進(jìn)行分析，如表2所示，相比HM測試一個完整Ι幀的結(jié)果，平均PSNR值增加了2.425 1 dB，平均SSIM值為0.995 7。

表2 測試性能分析

3.2.3 硬件資源對比分析

為了更好地說明本文設(shè)計方案的優(yōu)勢，將算法對應(yīng)的硬件設(shè)計綜合情況與其他同類型文獻(xiàn)進(jìn)行對比。實驗數(shù)據(jù)如表3所示，文獻(xiàn)[16]在Xilinx Virtex 6的開發(fā)平臺上設(shè)計基于HEVC的視頻編碼算法，硬件設(shè)計上采用全流水線方式工作，最大只能支持5條路徑并行，本文中支持最大16個PE并行。與本文相比，文獻(xiàn)[16]的LUT的資源與寄存器的資源消耗增加了很多；在實現(xiàn)了更高的并行度的情況下，本文方案硬件消耗相對較少，ISE硬件綜合資源消耗圖如圖12所示，LUT資源僅使用了31 730個，REG資源僅使用了9 664個。

圖12 硬件資源消耗Fig.12 Hardware resource consumption

文獻(xiàn)[17]在Xilinx Zynq ZC706上實現(xiàn)，編碼器以140 MHz的工作頻率實現(xiàn)編碼，工作頻率略高于本文。本文和文獻(xiàn)[17]在功能上都可以支持任意大小塊劃分。但相比于文獻(xiàn)[16]，本文的硬件消耗(LUT資源+REG資源)減少62%，且沒有使用乘法器進(jìn)行運算，使用加法器和移位操作代替乘法器進(jìn)行運算，計算速度更快，無需使用DSP資源。

文獻(xiàn)[18]基于Virtex 7現(xiàn)場可編程門陣列設(shè)計硬件的混合并行和數(shù)據(jù)流級架構(gòu)的HEVC編碼。在功能上可以支持任意大小塊劃分。相比于文獻(xiàn)[18]，在工作頻率略高的情況下本文的硬件消耗也明顯減少。LUT資源僅占其使用量的28%，REG資源僅占其使用量的80%。

綜上所述，本文基于可重構(gòu)陣列處理器的設(shè)計方案在較低的硬件消耗下實現(xiàn)了四叉樹編碼的并行化設(shè)計，并行加速比達(dá)到9.64，且在結(jié)構(gòu)上具備靈活性。

表3 硬件結(jié)果對比

4 結(jié)束語

針對3D-HEVC標(biāo)準(zhǔn)中四叉樹編碼劃分存在的編碼復(fù)雜度高、數(shù)據(jù)量大、編碼時間長和資源消耗大的問題，基于可重構(gòu)陣列處理器提出了一種新的四叉樹CU并行劃分方案，完成并行映射、功能仿真以及FPGA測試。該方案利用可重構(gòu)陣列結(jié)構(gòu)分布式共享存儲的特點，充分挖掘數(shù)據(jù)之間的并行性，實現(xiàn)計算資源PE的最大化利用，減少編碼劃分的時間。實驗結(jié)果表明，四叉樹CU劃分在更具備靈活性的同時，與單個處理單元PE串行相比，16個PE并行設(shè)計的加速比達(dá)到9.64，很大程度上減少了編碼時間。相比于文獻(xiàn)[12]編碼效率總體提升了約36倍。簇內(nèi)PE的資源利用率提高了93.75%。與文獻(xiàn)[14]相比，在不使用DSP資源的情況下資源消耗降低了62%。與文獻(xiàn)[15]專用硬件對比，LUT資源消耗減少了78%，REG資源消耗減少了20%?？傊?，基于可重構(gòu)陣列處理器的四叉樹編碼并行劃分方案，在不影響編碼質(zhì)量的同時，提升了編碼效率，且硬件資源消耗也相對較少。