可重構(gòu)結(jié)構(gòu)下合成視點失真變化算法并行設(shè)計與實現(xiàn)

蔣 林，施佳琪，李遠成

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

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

0 引言

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

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

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

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

圖1 可重構(gòu)陣列處理器系統(tǒng)結(jié)構(gòu)Fig.1 Architecture of reconfigurable array processor system

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

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

1 SVDC算法的并行性分析

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

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

由圖2 可以看出，SVDC 算法三部分的具體內(nèi)容如下: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 中:最左側(cè)為將原始圖像分割成大小是8×8 的待處理塊，通過虛擬視點合成獲得合成后的圖像；失真值計算獲得合成后的失真值。

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

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

1.2 虛擬視點合成并行分析

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

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

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

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

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

1.3 失真值計算并行分析

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

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

1.3.1 圖像失真值計算分析——任務(wù)級

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

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

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

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

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

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

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

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

2 混合粒度劃分方法

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

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

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

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

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

2.2 虛擬視點合成劃分

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

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

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

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

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

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

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

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

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

2.4 像素塊-像素點劃分（任務(wù)級）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實驗方案

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

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

3.1.1 SVDC算法性能仿真

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

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

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

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

3.1.2 失真值計算性能仿真

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

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

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

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

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

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

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

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

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

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

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

最后，經(jīng)理論推算本文方法的加速比為:

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

4 結(jié)語

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