基于視頻陣列處理器的3D-HEVC視差估計算法并行設計與實現

蔣 林 馮 茹

(西安科技大學計算機科學與技術學院 陜西 西安 710121)

0 引 言

由于多視點視頻的數據量呈現爆炸式增長,這對3D-HEVC等三維編碼技術提出了極高的要求。隨著視頻編碼技術的不斷發展,幀間預測技術經歷了不斷提升與改進的過程。視差估計是3D-HEVC中計算復雜度較高的模塊,其編碼時間占到整個編碼時間的60%。視差估計算法本質就是用于尋找當前編碼塊或者當前預測塊在不同視點上對應圖像中的最佳匹配塊。也就是按照某種數學準則在左右圖像上尋找匹配點或塊的過程,就是一個圖像匹配的過程。獲取的視差矢量就是兩個對應點或塊之間的位置差異,它代表了左右圖像在空域上和時域上的冗余信息。直接根據深度圖推導視差矢量(Disparity Vector,DV),提出基于深度圖的視差矢量[1](Depth Map based Disparity Vector,DMDV),計算復雜度高,內存占用量大。Chen等[2]提出相鄰塊視差矢量(Disparity Vector From Neighboring Blocks,NBDV)。NBDV算法的基本思想是利用從另一視點預測得到的、與當前編碼塊位于同一編碼位置的相鄰塊的時空運動信息,導出當前編碼塊的視差矢量。為了提高獲取視差矢量的計算效率,很多學者對此進行研究,提出多種解決方案。

文獻[3]提出基于參考塊與當前編碼塊的空間相關性和時間相關性,來獲取當前編碼塊的視差矢量,并且對基于深度圖的視差矢量獲取提出改進,從而有效節省編碼比特數,提高時效性。文獻[2]計算當前編碼塊的視差矢量,不使用深度圖獲取,而是在紋理圖編碼后,利用當前編碼塊在時域上和空域上的相關性,來預測當前塊的視差矢量,來降低編碼冗余。文獻[4]提出了一種可擴展的大規模并行快速搜索算法,降低運動估計ME和視差估計DE在塊匹配過程中的計算成本,相比于現有的全搜索和快速搜索,在計算復雜度方面分別提高245.8倍和8.4倍。文獻[5]提出運動和視差矢量早期確定算法,以降低3D-HEVC計算復雜度,采用自適應優化算法來選擇有效的視圖間視差矢量(DV)候選。文獻[6]提出了一種基于單向視差搜索算法的三維高效視頻編碼(3D-HEVC)視差估計(Disparity Estimation,DE)的硬件設計。該架構被用于處理四個方形預測單元(PU)尺寸,而不是使用所有24種可能的PU尺寸。文獻[7]提出搜索所有時域和空域相鄰塊的DV,所有有用的DV被構成一個候選列表,刪除列表中的冗余的DV,求出剩余DV的平均值作為最后的NBDV,提高獲取DV的速率。為解決PU無法并行處理問題,文獻[8]提出一種并行的處理方案。在此基礎上,文獻[9]提出一種以編碼單元(CU)為基礎的編碼單元去執行DV的推導,不僅節省相鄰塊,還使多個PU進行并行處理。

綜上所述,針對3D-HEVC視差估計算法計算復雜度高的問題,主要通過三方面來進行優化:一是從搜索算法并行化的角度來優化;二是通過四叉樹結構進行快速的模式決策方法來減少編碼冗余;三是通過邊緣信息加快對編碼塊的搜索。3D-HEVC測試模型中無論是紋理視頻還是深度視頻幀間預測算法都是串行執行的,因此,減少視差估計過程中的計算復雜度,始終是提升3D-HEVC編碼效率的關鍵。研究視差估計算法的并行性對于整體編碼效率的提升起著至關重要的作用。

1 視差估計算法并行性分析

NBDV通過每一個當前CU的空域時域相鄰塊的運動矢量或者運動補償預測(MCP)得到的視差矢量。這種原理與Merge/AMVP很相似,空域和時域相鄰塊按照所給順序進行搜索,第一個可用的DV作為最后的NBDV。最初搜索相鄰塊的順序是空域DCP塊——時域DCP塊。

1.1 空域候選列表的建立

如圖1所示,當前編碼單元有5個相鄰塊,分別記作A0、A1、B0、B1、B2。搜索視差矢量按照A1、B1、B0、A0、B2的順序對每一個塊進行搜索,如果找到第一個可用的視差矢量(DV),就認作為當前編碼單元的NBDV。

圖1 空域相鄰參考塊

1.2 時域候選列表的建立

在時域上進行視差矢量搜索時,由于候選幀數目龐雜,并且空域相鄰塊DV的準確性不如時域相鄰塊DV,因此首先搜索時域DCP塊,其次是空域DCP塊,最后搜索空域DV-MCP,搜索步驟較為煩瑣。根據文獻[10]提到減少搜索塊的方法,從每個候選幀圖像搜索18個塊變為現在只搜索兩個塊,即中間的塊(T1)和右下角的塊(T0),時域塊的搜索順序為T1-T0,如圖2所示。

圖2 時域相鄰參考塊

基于相鄰塊的視差矢量預測算法是將一幀圖像分為互不重疊的許多宏塊,并且認為一個塊內所有的像素點的相對位移是相同的,其目的是為當前視點的一幀圖像的每個塊查找最佳匹配塊,從而在其參考視點的參考幀搜索到最佳匹配塊,圖3為相鄰塊視差矢量的塊匹配示意圖。

圖3 視差估計塊匹配示意圖

通常選擇SAD作為匹配準則,若塊大小為N×N,第n幀中左上角坐標(x,y)的塊與第n-1幀中左上角坐標(x+a,y+b)的塊之間的SAD如式(1)所示。

fn-1(x+a+i,y+b+j)|

(1)

式中:fn(x+i,y+j)表示第n幀中坐標為(x+i,y+j)%處的像素值,fn-1(x+a+i,y+b+j)表示第n-1幀中坐標為(x+a+i,y+b+j)處的像素值。(a,b)表示視差矢量DV,即當前塊到參考塊之間的相對位移。

視差估計中最耗時的模塊是塊匹配操作,在進行塊匹配操作時,在時域上和空域上分別搜索與當前編碼塊相鄰的塊,判斷其相鄰塊與當前編碼塊的SAD值,并選擇最小SAD值,將此SAD值及其對應塊存儲,計算視差矢量。由于搜索的相鄰塊數目煩瑣,且對于視差估計算法中數據計算密集,訪存量較大,全局數據較少,像素之間處理相互獨立,塊與塊之間的處理也相互獨立,因此存在較大的并行性。

塊匹配已經成為視差估計算法中最廣泛使用的方法,其中SAD值計算模塊占據了大量的編碼時間,塊匹配的基本思想就是將每一幀視頻劃分為固定大小的塊,并且基于某種搜索規則和匹配標準,通過在搜索窗口的塊匹配來估計和當前塊最相似的塊,并且通過塊的相對位移來獲得視差矢量。因此,視差估計的準確性以及運算速率直接影響到編碼的質量和性能。考慮到搜索過程中只關注當前編碼塊的結果,不需要參考其他塊匹配的結果,所以可以同時進行幾個塊的匹配操作,并且這幾個塊同時執行相同的處理過程,因此,對于視差估計算法的并行性分析尤為關鍵。從軟件的角度,并行的方式分為任務級并行和數據級并行,任務級并行是指在不同的時間內并行完成不同的任務,因為任務的數量是一定的,所以任務級并行是不可擴展的,本文主要從數據級并行的角度來對算法的宏塊進行并行。在查找最佳塊匹配過程中主要是SAD值計算和加載參考塊兩個模塊。

SAD值計算模塊主要是由當前編碼塊存儲器、參考塊存儲器、預測單元,以及存儲視差矢量和SAD值的寄存器這幾部分組成,將一個預測單元塊分成許多比如8×8的小塊,這些小塊可以并行的進行處理,沒有數據相關性,最后將所有預測單元得出的數據合并并且存儲其視差矢量和SAD值。加載參考塊主要是從搜索窗中加載并下發不同的參考塊,在加載和下發參考塊后進行數據的更新。在加載和下發參考塊數據過程中,可以同時向不同的PE下發數據,這樣每個PE可以并行地處理參考塊數據,減少時間和資源消耗。

2 視差估計算法并行映射方案設計

3D-HEVC編碼過程中,一幀視頻圖像由多個或一個slice組成,而一個slice又可以被分割為多個編碼樹單元(Coding Tree Unit,CTU),CTU的尺寸大小為8×8到64×64。編碼效率取決于CU尺寸的大小以及劃分的深度,尺寸越大,分割的深度越大,編碼效率也就越高。CU攜帶著編碼塊的運動信息,大小范圍從8×8到64×64,其中塊劃分方式分別為:64×64塊深度為0、32×32塊深度為1、16×16塊深度為2、8×8塊深度為3。為了對編碼過程中CU塊的尺寸大小分布情況解釋更加清晰,對3D-HEVC參考軟件(HTM)中幾種測試序列進行了分析統計。圖4是不同深度下幾種測試序列分布情況。這幾種測試序列Depth為0即塊大小為8×8占比最為明顯,均超過總分布的60%,因此,論文中選擇8×8塊進行視差估計并行實現。

圖4 CU不同尺寸的分布情況

本文提出的具體并行設計思想:首先,讀入當前編碼塊和搜索窗數據;其次,同時在空域上和時域上搜索相鄰塊獲取視差矢量,時域相鄰塊順序為T0、T1,在其中選擇與當前編碼塊最匹配的塊,空域相鄰塊順序為A1、B1、B0、A0和B2,在其中選擇與當前編碼塊最匹配的塊;最后通過比較這兩個最優塊候選塊選出一個最匹配塊,計算視差矢量,完成一個塊的視差估計,即當前塊的NBDV過程結束。圖5是視差估計算法流程圖,并行化過程如下:

圖5 視差估計算法流程

1) 從當前幀中按照CTU的執行順序依次處理8×8的塊,從參考塊中取對應搜索窗大小塊,將數據準備好,分配到不同的PE。

2) 同時調度相關PE,在時域相鄰塊T0和T1和空域相鄰塊A1、B1、B0、A0和B2同時進行搜索,計算各自的SAD值,進行塊匹配操作。在這個過程中,考慮到數據之間存在相關性,因此在進行塊匹配之前就已經將當前塊和搜索窗數據分配在不同PE,使得不同PE可以同時操作,并行計算各自的SAD值。

3) 根據上一步計算得到的SAD值,分別計算空域和時域相鄰塊的最優SAD值,并選取各自最小的SAD值,分別得到最優時域和空域相鄰塊。

4) 根據上一步得到的最小空域相鄰塊SAD值和時域相鄰塊SAD值進行比較,從這兩個SAD值中得到最優的SAD,得到最匹配的塊,由此得到視差矢量,完成一個塊的視差估計。

3 基于視頻陣列處理器的視差估計算法并行化實現

3.1 可編程可重構視頻陣列處理器硬件結構

結合3D-HEVC視頻編碼標準的特點,本文采用一種可編程可重構的視頻陣列處理器進行并行化設計。視頻陣列處理器[11]由1 024個輕核處理單元(PE),通過鄰接互連組成32×32的陣列處理器,其中每16個PE組成一個處理器簇(PEG)。采用全局片上網絡局部共享存儲的通信機制,即簇內通過鄰接互連和共享存儲進行數據交互,簇間通過片上網絡進行遠距離通信,圖6所示為視頻陣列處理器的硬件結構,包括數據輸入存儲、數據輸出存儲、全局控制器、陣列處理器和指令存儲器五部分組成。全局控制器是可重構機制的核心,主要是對PE上計算資源的管理與控制,上層接入主機,下層是PE組成的陣列處理器。在主機接口與陣列處理器之間形成一個層次化編程網絡,它可以對陣列資源進行合理的分配與調度,實現多種模式的靈活切換。在每個處理單元中都有一個指令存儲和數據存儲,因為涉及到兩種模式的切換,將指令存儲分為兩部分,0～511號地址配置為0,512～1023號地址配置為1,并通過全局控制器發出的指令讓對應的PE執行相應的操作,從而達到兩種配置間的任意切換。指令下發網絡是動態重構機制的核心模塊,論文主要用到的是指令下發模塊中的指令下發和指令廣播操作。首先將指令存儲在每個PE自帶的指令存儲中,再通過指令廣播的方式啟動需要進行操作的PE。指令下發操作的作用是將全局指令存儲器中的指令下發到指定的PE。

圖6 可重構機制的視差估計算法的硬件結構

3.2 視差估計算法并行映射方案

在視差估計算法中,由于搜索當前編碼塊在空域和時域上相鄰塊數目較多,搜索順序復雜,耗時較長,且算法效率低下,因此本文采用數據并行的思想,在同一時間處理時域上和空域上塊數據,縮短數據讀取時間和計算時間從而提高算法的計算效率。這里以8×8塊為例,給出算法的映射圖如圖7所示。

圖7 視差估計算法并行映射圖

具體的操作步驟如下:

Step1原始數據和參考數據加載。當前幀的數據存儲在數據輸入存儲(Data Input Memory,DIM)中,參考幀數據存儲在外部數據輸出存儲(Data Output Memory,DOM)的。PE00與DIM相連,將外部存儲中原始的一幀圖像分為8×8的塊送給PE00,然后PE00在進行數據分配,分別下發給PE01、PE02、PE11、PE12、PE13、PE21和PE22;PE10與DOM相連,將外部存儲中參考幀圖像分為16×16塊送給PE10,然后PE10再進行數據分配,分別下發給PE01、PE02、PE11、PE12、PE13、PE21和PE22。為了提高數據傳輸速率,不需要等待PE00下發完數據后PE10再下發數據,只要從DOM取到數據,便可下發。

Step2塊匹配操作。各個PE接收到數據之后,PE01、PE02、PE11、PE12、PE13、PE21、PE22開始并行地進行SAD值計算,選取SAD值最優的塊,在這個過程中,計算并不存在數據相關性,所以塊匹配操作可以在7個PE中同時進行。塊匹配計算完成后,時域上最匹配的塊和最優SAD值寄存在PE03,空域 上最匹配的塊和最優SAD值寄存在PE23。

Step3獲取視差矢量。通過比較在PE03寄存的時域上最優SAD值和在PE23寄存的空域上最優SAD值,得出與當前編碼塊最匹配的塊,并計算出視差矢量,完成視差估計。

4 實驗與分析

4.1 實驗平臺環境及測試方案

為了驗證視差估計算法并行實現方案的可行性,論文基于BEECube公司BEE4開發平臺搭建的視頻陣列處理器原型系統進行驗證和測試。首先,根據視頻陣列處理器提出的匯編指令進行算法編譯,接著在指令翻譯器上將匯編代碼指令翻譯成二進制送給硬件結構;然后,通過QuestaSim 10.1d進行功能仿真,可以通過查看信號如目標寄存器號、寄存器的值和內部數據存儲器的值驗證仿真結果是否正確。從而在所搭建的可編程可重構視頻整列處理器DPR-CODEC上進行視差估計算法的全面驗證和測試。在Primeton BPS開發環境下對硬件平臺進行邏輯綜合,基于BEE4開發平臺上的XC6VLX550T FPGA進行硬件測試。表1是在算法驗證時需要的環境及所使用工具。

表1 算法驗證測試環境和所使用工具

4.2 運行時間對比分析

視差估計算法中塊匹配過程采用全搜索算法進行匹配,因此不會降低圖像的編碼質量,算法執行過程中,可以分為四個模塊,即原始數據的加載以及下發、參考數據加載、參考數據下發和SAD值計算模塊。通過串行和并行兩種實現方案,對算法各模塊運行時間作對比分析,串行實現方案是將四個模塊在視頻陣列處理器的一個PE單獨操作,并分別記錄每一個模塊的運行時間。并行實現方案使用視頻陣列處理器中的12個PE來執行程序,模塊運行的時間通過QuestaSim軟件進行功能仿真得到。在算法執行過程中,記錄每一個模塊開始到結束的時間來計算運行時間。視差估計算法各模塊進行串行和并行的運行時間和如表2所示。根據所統計的時間可以看出,本文所設計的方案主要在參考數據下發以及SAD值計算的過程中提升了并行性,減少了編碼時間。兩種塊方式的匹配過程參考數據的下發和SAD值計算模塊加速比超過了4。并行性提升最多的模塊為參考數據的下發和SAD值計算模塊,加速比分別為4.9和4.37。因為本方案在數據下發的過程中,當PE10的參考塊數據存完后,給其握手信號,其他PE便開始塊匹配操作,充分利用空閑PE的資源,減少PE等待時間。而原始數據和參考數據的加載過程中加速比不高,因為數據按照地址順序存儲,并行性提升不大。

表2 視差估計算法各模塊運行時間

文獻[12]選出當前編碼單元的空域、時域相鄰塊所有最優視差矢量重新建立NBDV候選列表,根據列表中DV的數量,結合率失真優化算法推導視差矢量來減少編碼時間,本文是通過并行處理當前編碼單元的相鄰候選塊來提高算法速率。與文獻[12]相比,本文對測試序列Newspaper進行視差估計處理的編碼時間減少最多,減少了29.67%,相比文獻提升了15%,具體結果如圖8所示。

圖8 與文獻[12]編碼時間百分比對比

4.3 運算性能分析

視差估計算法在Primeton BPS開發環境下對硬件平臺進行綜合,再通過BEE4開發平臺XC6VLX550T FPGA對設計進行綜合。表3所示為8×8編碼塊綜合結果,從工作頻率、資源占用率分別進行比較。文獻[13]工作效率比本文低,且資源占用比本文大;文獻[14]提出了稱為MCADSW視差估計算法,并且提出相應的VLSI體系結構,其工作頻率遠低于本文,且資源占用率很大;文獻[15]提出了一種面向硬件的自適應窗口大小視差估計(T-AWDE)算法和第一個實時的三目視差估計(DE)硬件,工作效率高于本文,但是資源占用率也明顯大于本文。

表3 運算性能比較

5 結 語

本文針對軟件實現視差估計算法存在處理數據量大、運算時間長和資源消耗大的缺點,基于視頻陣列處理器提出了視差估計的并行化實現方案,在陣列結構中完成并行映射、功能仿真及FPGA測試。該方案主要包括原始塊數據和參考塊數據加載和下發模塊以及塊匹配模塊,充分挖掘了數據塊之間的并行性,減少了PE等待時間,提高了運算速率。實驗結果表明,所提出的并行實現方案相比于串行單PE時間節省了59%,本文中測試序列Newspaper的編碼時間減少最多,減少了29.67%,相比文獻[12]提升了15%,該結構在具有較高的執行效率的同時也具有較好的靈活性。