可重構結構下合成視點失真變化算法并行設計與實現

蔣 林，施佳琪，李遠成

（西安科技大學計算機科學與技術學院，西安 710600）

（?通信作者電子郵箱s1007236623@163.com）

0 引言

隨著數字視頻技術日趨成熟和圖像圖形技術、計算機視覺技術的快速發展，三維（Three-dimensional，3D）視頻以其真實的視覺體驗受到了人們的廣泛關注，但其龐大的數據量給視頻的傳輸和存儲帶來了極大的壓力。高效視頻編碼（High Efficiency Video Coding，HEVC）框架主要用于視點紋理圖及深度圖編碼［1］，三維高效視頻編碼（3D High Efficiency Video Coding，3D-HEVC）是將深度圖和紋理圖信息用于虛擬合成視點，采用多視點+深度圖（Multi-view Video plus Depth maps，MVD）的編碼格式，根據數據間關系，引入幀間預測技術降低視頻冗余，達到高效視頻壓縮的目的。

在3D-HEVC 中，編碼紋理圖造成的圖像失真會直接導致合成的虛擬視點失真，如果仍選用標準視頻編碼器進行編碼，視頻就會存在失真。這時，該如何描述合成后圖像的失真程度，對選擇合適的虛擬視點合成（Virtual View Synthesis，VVS）方法有極大的幫助。圖像失真程度一般采用失真值描述，合成視點失真變化（Synthesized View Distortion Change，SVDC）算法是通過計算深度圖與紋理圖信息，獲取合成后圖像的失真值［2］，即縮短SVDC 算法的執行時間，從而高效描述合成后圖像失真程度。

SVDC 算法以整幅圖像作為輸入，隨著圖像尺寸的增大，SVDC 算法時間復雜度會大幅增加，失真值將難以計算［3］。文獻［4］進行算法分析時，發現在失真值計算過程中:當視差矢量為0，失真值也等于0。根據此特點，采用自適應分段跳過規則視點合成方法，在SVDC 算法計算過程中，降低了計算圖像失真程度的時間復雜度。

SVDC 算法以矩陣形式參與運算，運算步驟相對獨立，計算過程中數據依賴性低，具有較高的并行性，適合可重構陣列處理器進行并行計算。一種典型的可重構陣列處理器系統結構如圖1 所示，其中，圖1（a）為可重構陣列處理器系統，由主處理器、全局指令存儲器、輸入/輸出存儲器、可重構陣列處理器和接口控制器等部分組成。主處理器通過接口控制器調度可重構陣列處理器，全局指令存儲器用于存儲可重構陣列處理器操作和調用指令，輸入/輸出存儲器用于存儲陣列處理器需要處理的數據，可重構陣列處理器用于完成主處理器分配的任務。

圖1 可重構陣列處理器系統結構Fig.1 Architecture of reconfigurable array processor system

與通用處理器相比，可重構陣列處理器由主控制器和可重構處理單元陣列組成。主控制器控制整個結構執行，可重構處理單元陣列由多個處理單元（Process Element，PE）構成，每個PE 包含算術邏輯單元（Arithmetic Logical Unit，ALU）、寄存器、存儲器，根據配置不同PE 可以執行常見操作（如加法、減法、與、或、非等）。在編譯方式上，與通用編譯為單一目標處理器的匯編指令不同，可重構編譯通過軟硬件劃分，將劃分結果分別生成主控制器的控制碼以及配置陣列處理器上的配置信息。此外，可重構陣列處理的執行方式是通過主處理器將任務下發給可重構陣列處理器執行，采用主控制器選擇片上配置存儲器中的信息，將信息下發給處理簇（Process Element Group，PEG）執行，每個簇再通過片上配置存儲器將存儲的可重構配置信息［5］分配到PE中進行運算。

綜上所述，本文基于可重構陣列結構（基于現場可編程邏輯門陣列（Field Programmable Gate Array，FPGA）實現的BEE4 平臺），設計并實現了一種混合粒度SVDC 算法，以有效縮短SVDC 算法執行時間。通過分析虛擬視點合成過程中深度圖與紋理圖的關系，利用失真值計算過程中圖像失真值等于像素點失真值累加的特點，發揮可重構陣列結構優勢，設計并實現了SVDC算法并行化映射方法。

1 SVDC算法的并行性分析

SVDC算法是計算虛擬視點合成失真值的方法，但是隨著圖像尺寸的增大，將難以在有限時間內計算虛擬視點合成失真值。因此，將SVDC 算法分為三部分:初始化、重渲染和失真值計算，其計算過程如圖2所示。

圖2 SVDC算法流程Fig.2 Flow chart of SVDC algorithm

由圖2 可以看出，SVDC 算法三部分的具體內容如下:1）初始化部分:已編碼的深度圖像D'與已編碼紋理圖像T'。2）重渲染部分:已編碼的深度圖像D"與未編碼紋理圖像T"，分別進行虛擬視點合成，用V'和V"表示，然后將原始紋理圖T與原始深度圖D合成參考視點V。3）失真值計算:V與V'的差值平方和SSD'和V與V"的差值平方和SSD"的差值表示為虛擬視點合成的失真值。

1.1 SVDC算法計算階段確定

由圖2 中SVDC 的計算過程，可得SVDC 算法主要有兩個模塊:虛擬視點合成和失真值計算，其計算階段劃分如圖3 所示。圖3 中:最左側為將原始圖像分割成大小是8×8 的待處理塊，通過虛擬視點合成獲得合成后的圖像；失真值計算獲得合成后的失真值。

圖3 SVDC算法計算階段示意圖Fig.3 Schematic diagram of SVDC algorithm calculation stages

由于SVDC 算法計算模式不同，所以，在可重構陣列結構處理器上，增加配置信息去映射不同的PEG。

1.2 虛擬視點合成并行分析

虛擬視點合成作為SVDC 算法的第一個模塊，包括三個部分:邊界掩模、3D warping 和空洞填充。這三個部分的輸入單位是像素塊，本文使用的像素塊大小是m×m，具體內容如下:

1）邊界掩模:依據像素點的紋理圖和深度圖信息判斷物體邊界是否遮蔽以及遮蔽后的處理方法。

2）3D warping:依據深度圖信息與紋理圖信息的疊加找到合成后視點的映射規則。在執行邊界掩膜和3D warping 時，需要對整塊區域進行處理。

3）空洞填充:空洞是前景參照物遮擋到后景區域產生的，使得合成視頻較原景象出現較大的偏差，一般通過低通濾波器對深度圖進行預處理減小空洞區域，在視點合成過程中需要空洞填充以保證視頻圖像的準確性。

虛擬視點合成的三個部分，雖然在自身內部計算時不能并行化，但在進行虛擬視點合成時都相對獨立，可以采用流水線與重構方式進行加速計算［6］。

1.3 失真值計算并行分析

SVDC算法的第二個模塊是失真值計算，失真值計算主要分為圖像失真值計算和像素點失真值計算，計算已編碼區和未編碼區分別與參考圖平方和的差值，如式（1）所示。

其中:I為圖像處理塊，ΔD為I的失真值；為I的初始化紋理圖為I的重渲染紋理圖為I的參考紋理圖；()x，y為I的像素點坐標。

1.3.1 圖像失真值計算分析——任務級

失真值計算的流程如圖4 所示，其中，Dx1是第一個循環讀取初始化圖像與參考圖像像素值E1、E2后，差值平方的累加值；Dx2是第二個循環讀取重渲染圖像與參考圖像像素值E3、E4后，差值平方的累加值。

圖4 失真值計算流程Fig.4 Flow chart of distortion value calculation

分析這兩個循環可得失真值計算是整個區域塊內部中所有像素點失真值的累加，兩個循環中每次循環都相對獨立且具有相同的計算過程［7］，因此，失真值計算具備并行性。

1.3.2 像素點失真值計算分析——指令級

由1.3.1 節可知，圖像失真值計算是像素點失真值計算的累加。像素點失真值計算如圖5 所示，圖中a1、a2、a3分別是初始化紋理圖、參考紋理圖、重渲染紋理圖的像素點。

圖5 像素點失真值計算Fig.5 Calculation of pixel distortion value

整個計算過程分解為兩個部分:1）A，計算a1與a2差值平方a6的過程；2）B，計算a3與a2差值平方a7的過程。將A、B 兩部分的結果相減得到最終結果，可得像素點的失真值，兩部分計算過程一致，數據依賴性低，具有并行性［8］。

綜上所述，SVDC 算法的優化主要分為兩個部分:1）虛擬視點合成部分采用流水線方式加速；2）失真值計算部分采用兩級（任務級、指令級）劃分加速。

2 混合粒度劃分方法

首先，提出了混合粒度劃分方法的基本思想。然后，根據SVDC 算法的特點，對虛擬視點合成部分，設計流水線劃分策略縮短虛擬視點合成部分時間；對失真值計算部分，比較像素點以及計算過程對其執行時間的加速程度。最后，選擇合適的方法縮短SVDC 算法的執行時間，并給出SVDC 算法的重構配置信息。

2.1 混合粒度劃分的基本思想

混合粒度劃分為兩個部分:虛擬視點合成和失真值計算。虛擬視點合成采用流水線作業的方式加速。失真值計算采用兩級劃分加速:任務級——像素塊與像素點的依賴關系；指令級——像素點內部計算過程中的依賴關系。

混合粒度劃分方法，通過虛擬視點合成得到合成圖像，計算失真值。并行化過程使用addparallel 方法實現。通過判斷singal狀態選擇并行或同步處理，若為false 則表示計算未結束需要同步等待；反之，需要并行計算，其具體計算步驟如下。

其中，通過VVS 方法實現虛擬視點合成，失真值計算過程中，通過imagedivide方法實現任務級劃分策略，即將像素塊均勻分配給指定數目的處理單元運算；通過get_Set_SVDC 方法實現指令級劃分策略，將任務級劃分的結果作為輸入，對每個結果采用指令級方法，獲取失真值，將失真值結果累加，即可獲得圖像的失真情況。

2.2 虛擬視點合成劃分

根據1.2 節分析可知，虛擬視點合成分為邊界掩模、3D warping 和空洞填充三個部分。由于這三個部分各自不能并行，所以使用如圖6所示的流水線方式進行加速。

圖6 虛擬視點合成時空間流水線作業Fig.6 Spatio-temporal pipelining of virtual view synthesis

圖6 中，將深度圖和紋理圖像素塊通過邊界掩模、3D warping 和空洞填充這三個部分進行虛擬視點合成。當第一個像素塊邊界掩膜完成后，第二個像素塊開始邊界掩膜。因此，采用流水線方式能夠縮短虛擬視點合成階段的執行時間。虛擬視點合成采用流水線方式加速的設計方法，以邊界掩膜為例，具體算法如下。

其中addparallel（“boder”，1）詢問處理單元是否處于freedom狀態，對于繁忙狀態則需要等待，進行線程同步；反之，直接運算。3D warping和空洞填充使用相同的判斷方法。

2.3 失真值計算基礎劃分方法性能對比

根據1.3 節對失真值計算的分析可得兩類劃分策略:1）按照任務級劃分，如1.3.1 節所述，將像素塊中像素點單獨計算，累加求和；2）按照指令級劃分，如1.3.2 節所述，使用兩個處理單元計算初始化失真和重渲染失真結果，兩者相減，累加求和。兩種劃分方法的性能對比如表1所示。

表1 SVDC失真值計算方法性能對比Tab.1 Performance comparison of SVDC distortion value calculation methods

一方面，從表1 中的數據中可得，當處理問題規模不同（像素塊大小不同）時，劃分方法的計算性能提升也不同。問題規模較大時，任務級劃分方法的性能提升較好；而指令級劃分方法對單一點有更好的性能提升。

另一方面，分析表1 中的數據可知，任務級劃分方法能合理使用有限的資源，指令級劃分對單一點加速性能更好。但是從1.3 節可知，圖像的失真值是像素點失真值的累加，然而指令級劃分是對像素點失真值計算的優化。所以，在不考慮處理單元數目時，將任務級和指令級劃分方法混合能夠得到更優的性能［9］。而處理單元數目有限時，任務級劃分方法能夠得到更好的性能提升。

2.4 像素塊-像素點劃分（任務級）

在像素塊-像素點劃分中，由失真值計算式（1）分析可得，像素塊內失真值等于像素點失真值的累加。對失真值計算分析可得，圖像失真值等于像素塊失真值之和，即圖像的失真值等于像素點失真值的累加，由此提出任務級方法［10］。

如圖7 所示，以4 個PE 為例，首先PE00 讀取的是初始化紋理圖St、重渲染紋理圖、參考紋理圖Stf中的第0號像素值，而PE01、PE02、PE03 分別讀取的是三幅圖中第1、2、3 號像素值。然后讀取4×當前PE 已讀取像素點數（如:a為PE00 已讀取像素點數），最后將計算結果在PE03處累加得到失真值。

圖7 像素塊-像素點劃分框圖Fig.7 Block diagram of pixel block-pixel point division

像素塊-像素點劃分方法是將像素塊均勻分配到每個處理單元計算失真值，具體算法如下。

通過計算像素點與處理單元的模值，即通過i取process_num模分配像素點到對應的處理單元計算失真值，并將分配后的點寫入process_point_set中進行失真值計算。

2.5 像素點-計算過程劃分（指令級）

像素點-計算過程劃分是將每個像素點失真值計算過程進行劃分。由1.3 節對失真值計算的分析可得每一個像素點都具有相同的計算過程，可以并行化。因此，將失真值計算的式（1）分解為式（2），整個計算式分為三個部分。

式（2）中，前半部分是初始化像素點差值的平方，后半部分是重渲染像素點差值的平方。該方法能保證負載上的均衡，提升整體計算性能［11］，像素點內部計算過程的任務執行如圖8所示。圖8中，S1代表計算初始化像素與參考圖像素點差值的平方，S2代表計算重渲染像素與參考圖差值的平方，將兩者的計算結果通過PE30相減，得到失真值。

圖8 像素點-計算過程劃分框圖Fig.8 Block diagram of pixel-calculation division

像素點-計算過程的劃分中，通過addparallel 方法將計算初始化和重渲染像素點差值平方進行并行化處理。通過addparallel（“ST1”，1）、addparallel（“ST2”，2）判斷計算完成情況，如果完成，則將結果相減得到最終失真值；反之等待，具體步驟如下。

2.6 重構信息配置

重構配置信息執行示意圖如圖9 所示。首先，通過分析SVDC 算法與可重構陣列結構的關系得到SVDC 算法的配置信息:虛擬視點合成和失真值計算。然后，將配置信息載入到片上配置存儲器，在可重構計算陣列執行時，載入PEG［12-13］。最后，PEG00 載入虛擬視點合成配置信息后重復執行Nt次虛擬視點合成，將每次計算結果寫入PEG01，PEG01重復執行Nt次失真值計算，并將每次計算結果累加，求得圖像失真值。

圖9 可重構配置信息執行示意圖Fig.9 Schematic diagram of reconfigurable configuration information execution

3 實驗與結果分析

為了驗證混合粒度劃分方法的計算性能，本文基于Beecube 公司BEE4 型號的FPGA 開發板進行實驗。可重構陣列處理器結構是由1 024個PE鄰接互連成的動態可編程可重構陣列結構。該陣列結構包含64個簇，每個簇包含16個PE，每個PE 包含大小為512×32 的指令存儲單元、大小為512×16 的數據存儲單元、12 個本地寄存器（R1～R7，R12～R15）和4個共享寄存器（RE、RS、RW、RN），各個PE 之間通過4 個共享寄存器進行數據交互。每個PE 采用load/store 模式的精簡指令集計算機（Reduced Instruction Set Computer，RISC）架構，按照取指、譯碼、執行、寫返回4 級流水線結構進行執行整個過程。

3.1 實驗方案

為了驗證混合粒度劃分方法在陣列結構上的適用性，本文將以3D-HEVC 的參考模型HTM 作為參照［14］。依據可重構陣列結構的設計原理，在Questasim 10.1d 仿真平臺上進行實驗，時鐘周期為20 ns，讀取數據仿真時間為200 ns，合并數據仿真時間為134 ns。

針對大小為8×8 的編碼單元進行仿真。測試用例分別為Balloons（1024×768）、GTFly（1920×1088）、PoznanStreet（1920×1088）、UndoDancer（1920×1088），測試用例的視點為雙視點，分別對應兩對深度序列。首先，采用共享存儲并行編程（Open Multi-Processing，OpenMP）工具在SVDC 算法可并行的代碼段中添加標記［15］。然后，使用底層虛擬機（Low Level Virtual Machine，LLVM）并行編譯器執行SVDC 算法的代碼。最后，由于SVDC 算法中失真值計算部分的并行性較高，采用像素點劃分和本文劃分的方法，分別驗證處理單元數目和像素塊大小對失真值計算的加速性能。

3.1.1 SVDC算法性能仿真

四個測試序列分別采用上述四類方法（本文方法、OpenMP、LLVM 和HTM），針對四個處理單元，像素塊大小為8×8 的執行時間對比如圖10 所示。根據阿姆達爾定律可得混合粒度劃分方法的加速比約為2.11。

圖10 不同平臺上SVDC算法執行時間對比Fig.10 Comparison of SVDC algorithm execution time on different platforms

LLVM 與OpenMP 并行編程方法，都是采用顯式并行策略:一方面通過操作系統進行調度會額外增加調度開銷；另一方面采取保守方式挖掘算法并行性。本文方法是在可重構結構的基礎上挖掘多粒度并行性，減少了額外開銷，具有更好的并行性能。

針對不同的視頻圖像，經計算可得，本文方法與LLVM 并行編譯方法相比計算性能提升了18.56%，與OpenMP 編程模型相比計算性能提升了21.93%。這也表明混合粒度劃分方法對于SVDC算法性能提升更優，尤其序列2更為明顯。

3.1.2 失真值計算性能仿真

由第1.3 節分析可得，失真值計算部分更適合并行執行。分析2.3 節可知，當處理單元有限時，任務級劃分方法會獲得更優的加速性能。而當處理單元數目足夠時，本文方法的性能更優。

因此，實驗對序列2 分別通過PE 數目（2、4、8、16、32、64、128）和像素塊大小（1×1、2×2、4×4、8×8）這兩個因素，設計分別使用任務級劃分方法與本文的混合粒度劃分方法，分析這兩種方法對失真值計算部分加速性能的影響，結果如圖11所示。

由圖11 可以看出，在像素塊大小一致、處理單元數目大于像素塊大小時，本文劃分方法相較像素點劃分方法，加速性能有顯著的提升，并且隨著像素塊擴大，本文劃分方法在PE數目足夠時，加速性能的提升依舊顯著。

3.2 混合粒度劃分方法性能分析

混合粒度劃分方法分為兩步:1）將像素塊分解為若干像素點失真值計算的累加；2）將像素點內部失真值計算過程分解為A、B 兩個過程。對混合粒度方法進行理論分析，得到混合粒度劃分方法執行時間，進行實驗驗證。

假設原圖為On1×n2，使用的像素塊為Gm×m，則需要處理塊的數目block_num=

首先，對虛擬視點合成而言，假設T1、T2、T3分別為虛擬視點合成的三個部分邊界掩膜、3D warping 和空洞填充的執行時間。那么，虛擬視點合成串行算法的時間TVVS=T1+T2+T3。而采用流水線方式進行計算，結合2.2 節視點合成流水線時空圖和相應的算法，得出并行算法的執行時間TVVSp=max｛T1，T2，T3｝。

其次，對失真值計算而言，設Cm×m中每個元素為像素塊中每個點失真值計算的時間，則串行時間TSSD=C11+C12+…+Cmm。而對于混合粒度方法中的失真值計算，包括將像素塊劃分為均勻等分的像素點集劃分數量num=m2/S。

根據像素點-計算過程的劃分，設Cc1、Cc2分別為像素點的SSD'與SSD"計算時間，則每個像素點失真值計算的時間Tc=2×max｛Cc1，Cc2｝+t1。

因此，失真值計算并行執行時間TSSDp=num×（Tc）+m2×t2。

其中，S為可使用的核數，t1為處理單元數據合并時間，t2為像素點失真值累加時間。

最后，經理論推算本文方法的加速比為:

由上述分析可得，本文方法對于SVDC 算法的性能提升體現在:1）虛擬視點合成采用流水線方式加速；2）失真值計算采用任務級+指令級進行加速。本文方法進一步提升了算法性能的主要因素是處理器數目與問題規模的關系，只有選擇合適的處理器數目，才能有效縮短算法的執行時間。

4 結語

SVDC算法是虛擬視點合成中的關鍵環節，而算法的執行效率對圖像視點合成質量非常重要。因此，本文提出了一種在可重構結構下基于混合粒度的SVDC 算法并行化方法。該方法將算法原有的三個部分（初始化、重渲染和失真值計算）轉變為兩個部分:虛擬視點合成和失真值計算。其中，第一個部分虛擬視點合成采用流水線方法進行優化；第二個部分將失真值計算分為兩個過程:像素塊-像素點、像素點-計算過程。實驗結果表明，在處理單元數目為4、像素塊大小為8×8時，本文劃分方法與基于LLVM 和OpenMP 的SVDC 算法相比，計算時間分別縮短了18.56%、21.93%。針對SVDC 計算過程中并行度高的失真值計算部分，通過實驗得到當處理單元數目為128時，失真值計算的性能可提升55.23倍。在接下來的研究中，將把硬件結構作為側重點，包括循環迭代過程中免數據驗證、增加數據傳輸帶寬等，都是提升算法性能的可行性方法。