3D-HEVC深度建模模式的優化及并行設計

謝曉燕，王 昱，石鵬飛，朱 筠

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

1 引 言

伴隨著二維視頻編碼(High Efficiency Video Coding，HEVC)的發展與成熟，三維視頻編碼方案也在不斷推進，對于三維視頻的規范化研究早前就得到了標準化組織、世界產業界和學術界的重視，并取得了一定成果.作為HEVC/H.265視頻壓縮標準的擴展，3D-HEVC采用多視點視圖及對應的深度圖映射的方式，滿足了人們對立體圖像的追求，卻導致了數據量增加.

由于深度圖幀內預測需要處理銳利的邊緣區域，而紋理圖幀內預測適合處理近似恒定的區域.3D-HEVC中的幀內預測包含紋理圖幀內預測和深度圖幀內預測兩部分，用紋理圖幀內預測方法處理深度圖會導致在銳利邊緣處出現顯著失真現象.深度圖幀內預測中對大量的楔形模板進行窮舉式搜索給幀內預測帶來了極高復雜度，因此，深度圖幀內預測成為近年來研究的熱點.文獻[1]提出了一種快速雙分區模式決策算法，將計算的RD代價作為閾值來加速3D-HEVC深度編碼過程.文獻[2]通過計算RD-Cost，終止不必要的候選模式.這兩種方法無形當中在原本復雜度較高的模式選擇基礎上又增加了計算復雜度，基于此，文獻[3]通過分析紋理圖和深度圖邊緣方向，從而降低計算復雜度.文獻[4]基于父編碼單元(Coding Units，CU)與子CU關系提前終止不必要的模式，但該方法在模式選擇初期依舊遍歷整個模式.以上所示的方法中，無論是通過設置閾值，還是通過預測單元之間的關系降低幀內預測復雜度，都不能從本質上簡化楔形模板.筆者通過對楔形搜索表分析和統計，在保證質量的前提下，篩選出8種預測概率較大的尺寸為4×4的楔形模板，經驗證，存儲空間節約了99.2%，編碼時間減少了61.8%.此外，當前多媒體工程師和設計人員已經開始把視頻編碼向靈活的FPGA、GPU上轉移，有效的硬件解決方案對性能的需求是必要的，但這幾乎是對幀間預測，對于幀內預測在這方面的研究較為缺乏，由于幀內預測算法在視頻編碼中具有重要作用，針對前人設計編碼過程是串行執行的不足，基于以上精簡的楔形搜索模板間無數據相關性的特性，對改進的楔形模板進行并行設計，并映射在項目組提供的具有獨特并行特性的陣列處理器上.經驗證，該方案數據加載時間的串/并加速比為1.912，執行編碼時各模板的串/并加速比達到1.637.這種改進對高效視頻編碼具有重要研究意義.

2 3D-HEVC預測編碼

3D-HEVC幀內預測中幾乎恒定的區域可以用紋理圖預測算法處理，陡峭的邊緣部分需要考慮深度數據編碼方式.而深度圖中大量的楔形搜索模板需要排隊等待計算機的處理，這無疑的加大了預測編碼的時間.

如圖1所示，深度數據編碼在3D-HEVC編碼過程中有將近一半的編碼占用率，它包含四種深度建模模式(Depth Modeling Modes，DMMS)：DMM-1、DMM-2、DMM-3、DMM-4，由于DMM-2和DMM-3的效率不高，已被標準舍棄，剩下的DMM-1模式占10.16%，DMM-4模式占3.34%，可見分析DMM-1模式具有重要意義.

圖1 深度圖編碼比例Fig.1 Depth map coding ratio

文獻[5-8]相對于先前視頻編碼標準，在質量降低允許范圍內降低計算復雜度方面是有效的.而這些快速算法對于3D-HEVC新增的深度圖幀內預測不能直接適用或有效改變編碼效率，如何有效地降低編碼時間和計算復雜度是學術界研究的課題.為此，有專家學者提出了一些關于減少3D-HEVC深度編碼時間的快速算法.

文獻[9-12]僅用于優化深度編碼幀內預測模式，而未充分研究深度圖幀內預測算法的并行方法.所以3D-HEVC深度圖幀內預測的計算復雜度和編碼速度仍然存在優化空間.

針對深度數據在編碼時所帶來的復雜度：基于對楔形搜索表分析和統計，精簡了楔形表的劃分方式，利用一些最小編碼單元的塊作為基準楔形區域，然后進行擴展直至成為當前塊的方法進行楔形劃分，大大地縮減了楔形表所消耗的時間.

針對傳統串行算法中數據串行加載導致部分不具相關性的模塊還在排隊等待數據這一問題，提出了共享存儲加載數據、預測模式并行計算的方式進行算法預測.

3 深度圖幀內預測算法的改進

3.1 DMM-1的優化分析

在DMM-1模式中，不同尺寸的編碼塊楔形模板數量不同，尺寸越大，對應的模板數量越多.待每種模板完成CPVs編碼后，DMM-1在上萬種模板中窮舉式搜索最優楔形模板，這帶來了極高的復雜度.

DMM-1的wedgelets分割方式是通過一條直線將塊劃分為兩個非矩形區域，每個區域由一個恒定值表示.分割線由開始點S和結束點E表示.wedgelets分割可分為兩類(包括六個方向).兩類即相鄰邊緣分割和相對邊緣分割.如圖2所示，相鄰邊緣分割wedgeori的范圍包含在0到3之間，而相對邊緣分割wedgeori等于4或5.

圖2 wedgelets分割選擇Fig.2 Wedgelets segmentation selection

以上為編碼塊的wedgelets劃分，此外還要對不同尺寸的PU進行此類的劃分.

3.2 DMM-1模式基于楔形搜索表的優化

為了避免對整個wedgelets模板進行處理，由深度圖中存在大面積均勻區域，且這些區域大多選擇簡單方向，以及楔形分割和傳統幀內預測的35種預測模式在角度選擇上類似的特點.給出8種不同方向(分別是水平模式、垂直模式、模式5、模式14、模式21、模式32、模式16以及模式30)的預測角度.如圖3所示，由深度圖中楔形分割具有相鄰邊緣分割和相對邊緣分割的特點，給出10種楔形模板.

圖3 精簡楔形模板Fig.3 Streamlined wedge template

利用3D-HEVC編碼器下的全部DMM-1模式搜索進行模擬測試，得出選擇6個候選方向(水平模式、垂直模式、Ang-5、Ang-14、Ang-2和Ang-30)的概率為80.19%，剩余27個方向的總概率不超過20%.證明了簡化楔形搜索表具有代表性，符合預測時對6個方向的搜索.

如圖4所示，基于項目組提供的DPR-CODEC結構精簡指令集并行執行程度好、編譯器效率高的特點，設計出的DPR-CODEC IDE(programable reconfuger unit Integrated Develop Environment，IDE)仿真平臺，給出了改進思路：給定的兩個變量是一個4×4的原始wedgelets搜索模板和該塊所在的位置(i，j).根據給定的位置將該楔形模板擴展成一個N×N的預測單元(Predict Units，PU).通過利用HTM16.1對測試序列進行統計分析，該楔形模板塊所在位置大部分在當前塊中央，因此給出楔形模板四個角像素點的位置，分別為(N/2-1，N/2-1)、(N/2-1，N/2+2)、(N/2+2，N/2-1)和(N/2+2，N/2+2).

以預測一個16×16的PU、4×4的楔形模板為例進行具體改進過程的介紹.其中，模板擴展方式如圖5所示.

圖5 (a)原始Wedgelets搜索模式圖案(2，2)(b)用分區邊界線和楔形波位置(2，2)檢查每個位置Fig.5 (a)Original wedge search pattern (2，2)(b)Check each location with partition boundary and wedge wave position (2，2)

圖5(b)中虛線為分割線，分割線函數由原始楔形波中分割線的起始點(X1，Y1)和終點(X2，Y2)決定.則有分割線函數：y=ax+b，其中a，b計算如公式(1)所示.

a=(Y2-Y1)/(X2-X1)，b=(X2Y1-Y2X1)/(X2-X1)

(1)

為了避免不必要的重復分割，則有Pi，j如公式(2)所示.

Pi，j=j(X2-X1)-(Y2-Y1)i<(X2Y1-Y2X1)?1：0

(2)

如圖6所示，對PE陣列進行功能區域的設計.DIM(Data Input Memory)緩存YUV視頻序列數據；PE00對當前塊像素和參考塊像素的讀取以及將該數據分配到各具體功能模塊；PE01到PE13用來處理每種模板的CPV預測過程；PE20到PE33用來處理深度圖中二進制映射的過程.

圖6 優化后楔形搜索模式的PE功能劃分Fig.6 PE function division of optimized wedge search mode

Step1.數據加載，PE00從DIM取數完，通過共享存儲的方式把參考像素的數據傳遞給PE01和PE10，把當前塊的數據傳遞給PE20和PE30.待4個PE數據加載完成，將接收到的數據傳遞給同一簇內右方PE.

Step2.模板位置確定.此時N=16，則四個角點分別為(7，7)、(7，10)、(10，7)和(10，10).

Step3.模板擴展，PE20到PE33根據(i，j)=(6，6)確定4×4模板四個角的坐標是(10，6)、(6，10)和(10，10)，如圖5(a)所示.當前PU的N=16×16，則向兩側擴展時按整像素精度擴展，直至到達PU的塊邊界，如圖5(b)所示.

Step4.CPV編碼，PE01到PE23都對二進制區域進行CPV編碼.選取參考點，只需上參考樣點的行或者左參考樣點的列樣點里的第一個樣點、最后樣點或中間樣點以生成在不同情況下的DC.

3.3 仿真與驗證

將設計方案在DPR-CODEC IDE上進行仿真驗證，如表1所示，對改進前后的編碼時間進行統計.結果表明，改進前后的平均加速比達到2.619.這是由于在編碼時，搜索范圍限制于精簡的楔形模板，節省了大量的編碼時間，既保證了質量，又降低了編碼復雜度，充分驗證了筆者方案的合理性.

表1 分割方式優化后的時間對比(單位：時鐘周期)Table 1 Time comparison after segmentation optimization (unit：clock cycle)

如表2所示，基于優化的楔形模板，分別對不同測試序列：Kendo、Newspaper1、Balloons、Undo_Dancer、Poznsin_Hallz、Poznan_Street進行測試，結果表明，與文獻[1,13,14,15]相比更節省編碼時間和存儲空間，相較于HTM串行編碼，時間減少了61.8%，存儲空間節約了99.2%.此外，為了發揮陣列處理器的優勢，在第四節中將該優化算法進行并行化設計，映射到該陣列處理器中.

表2 時間、存儲減少對比Table 2 Time and storage reduction contrast

4 深度圖幀內預測算法的并行

4.1 并行化介紹

基于第三節對楔形搜索模板的改進，用項目組提供的陣列處理器DPR-CODEC在數據加載和編碼不同尺寸編碼塊兩個方面進行并行化設計.

4.1.1 數據加載的可并行性分析

3D-HEVC預測編碼時，數據加載是串行執行.從同一編碼單元中不同楔形模板的串行數據加載，到不同尺寸編碼單元中不同楔形模板的串行數據加載過程占整個DMM-1編碼時間2/3.對同一編碼單元中不同楔形模板之間所加載的數據相同，則可對同一編碼單元內所有的楔形模板進行并行數據加載，達到合理利用資源和縮減編碼時間的效果.

4.1.2 楔形模板的可并行性分析

深度圖幀內預測中，當前編碼塊的參考點從相鄰塊中選擇.這保證了在進行DMM-1模式編碼時擁有與紋理圖角度預測一樣獨立完成各角度(楔形模板)預測的特性.因此，用并行處理模板的方式預測當前編碼塊具有合理性.

以一個8×8PU、4×4楔形模板為例.利用1個PEG來完成顯示楔形波預測的并行化映射.DIM是數據緩存區，每個PE完成一種楔形模板的預測編碼，PE03用作最優楔形模板的判斷.

Step1.數據加載，PE00從DIM中讀取當前8×8的編碼塊，接著向當前PEG00的其余PE傳遞已獲取的當前塊及其參考像素.

Step2.二進制映射，按不同楔形模板對當前塊進行預測.此時，并不是所有的PE同時進行，而是按照完成數據加載的情況.

Step3.用CPVs編碼模式預測.

Step4.由公式(3)計算SAD，其中SA是原始像素值，SB是預測值，i=0…N-1，j=0…N-1；根據SAD值大小選擇最優的預測模式.

SAD(i，j)=∑i，j|SA(i，j)- SB(i，j)|

(3)

4.2 仿真與驗證

如表3所示，平均串/并行加速比達到1.912，即在數據加載上本方案節約了約50%的加載時間，之所以能縮減一半的加載時間，是巧妙地運用了同一編碼單元內所有的楔形模板并行數據加載的方式.

表3 串/并行數據加載時間對比(單位：時鐘周期)Table 3 String/parallel data loading time comparison (unit：clock cycle)

注：表3中包含當前編碼塊以及相應的參考像素.

數據加載完成后，對每個PE進行預測處理.如表4所示，列出了不同編碼尺寸的編碼塊處理精簡后的各個楔形模板的串并行編碼時間，實驗表明，DMM-1模式并行處理的平均串/并行加速比為1.637，這一數據充分驗證了該并行方案的實用性、有效性.

表4 并行模板處理(單位：時鐘周期)Table 4 Parallel template processing (unit：clock cycles)

注：表4中包含當前編碼塊以及相應的參考像素.

5 結束語

3D-HEVC作為HEVC的擴展標準，盡管能滿足人們對真實場景的追求，但其背后隱藏著復雜的編碼過程和龐大的數據處理問題.針對這些問題，本文在前期項目組工作基礎上，結合當前視頻應用的需求.基于項目組所提供的DPR-CODEC結構天然并行的特點，對深度圖的幀內預測編碼進行改進和并行化設計.具體研究工作如下：

1)3D-HEVC中深度圖幀內預測優化設計.給出了一種簡化的楔形搜索表方案.經過仿真驗證，從存儲角度來講，該方案節約了99.2%的存儲空間.從編碼時間來講，相較于串行編碼方式減少了61.8%.

2)3D-HEVC中深度圖幀內預測的并行化設計.對于DMM-1，首先篩選出8種預測概率較大的尺寸為4×4的楔形模板，通過對其擴展直至當前編碼塊邊界，得到不同編碼尺寸楔形劃分的區域，然后完成CPVs編碼.經仿真驗證，該方案串/并行平均加速比為1.637.

通過上述方案的實驗結果可以看出，本方案在合理利用資源的同時有效地縮短了編碼時間，提高了運算效率.

另外，由于項目組的仿真平臺DPR-CODEC IDE部分功能還不完善，以及個人的能力與時間有限，目前完成了深度圖在楔形搜索表方面的改進和深度圖的并行化設計.對于深度圖幀內預測的發展還有很長一段路要走，基于多核結構DPR-CODEC對幀內預測進行有效合理的并行化仍是今后需要研究的課題.