基于塊分類的深度圖運動估計及其并行實現(xiàn)

謝曉燕，王安琪+，朱 筠，胡傳瞻，杜卓林

(1.西安郵電大學(xué) 計算機學(xué)院，陜西 西安 710121；2.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710121)

0 引 言

3D-HEVC標準[1]采用了多視點加深度(multi-view plus depth，MVD)的編碼格式。MVD包含紋理圖序列和相對應(yīng)的深度圖序列。紋理圖具有豐富的細節(jié)信息和少部分較為平坦的紋理區(qū)域，而深度圖的平坦區(qū)域占比高達85%[2]，只有在物體的邊界處有著陡峭的邊緣。因此紋理圖編碼需要側(cè)重于每個像素點的細節(jié)信息，而深度圖只需要重點保護圖像中各對象的邊緣信息[3]。

針對如何利用深度圖獨有的內(nèi)容特性，降低在幀間預(yù)測部分的編碼復(fù)雜度，專家提出了一些有效的解決方案。文獻[4]針對深度圖平坦塊在運動估計時采用了復(fù)雜度較高的全搜索(full search，F(xiàn)S)算法或者TZSearch算法進行塊匹配，而導(dǎo)致了不必要計算量的問題，提出使用輕量級的菱形搜索(diamond search，DS)算法進行塊匹配，但是忽略了深度圖的邊緣區(qū)域更難預(yù)測這一問題。文獻[5]在文獻[4]的基礎(chǔ)上提出對深度圖進行分類，對不同區(qū)域采用不同的搜索算法，有效降低了運動估計搜索點數(shù)。以上算法都是利用深度圖的特性，從軟件算法層面減少深度圖的編碼時間，但是無法滿足實時視頻編碼的需求。因此，多媒體工程師嘗試把視頻算法向FPGA、ASIC上移植[6]，文獻[7]、文獻[8]分別基于FS、DS算法設(shè)計了專用硬件架構(gòu)。

綜上，針對深度圖特性的算法優(yōu)化和硬件加速是改善3D-HEVC運動估計模塊計算量和編碼效率的有效手段，但是現(xiàn)有文獻還未提出一種易于在硬件上實現(xiàn)且利用深度圖特性的運動估計算法。本文利用深度圖的特性，在運動估計前增加預(yù)處理模塊對編碼塊進行分類，為邊緣和平坦區(qū)域選擇不同的搜索算法，在保證編碼質(zhì)量的前提下，降低平坦塊的計算量；同時對優(yōu)化后的算法基于陣列處理器并行實現(xiàn)，加快運動估計的計算速度，達到算法效率、編碼質(zhì)量和硬件實現(xiàn)的良好折中。

1 深度圖的幀間運動估計

在3D-HEVC的深度圖幀間編碼過程中，延用了HEVC紋理圖的運動估計技術(shù)。如圖1所示，對需要編碼的當前幀，以塊為單位在參考幀的特定區(qū)域內(nèi)進行搜索，并按照一定的塊匹配準則尋找到最佳匹配塊。當前塊與最佳匹配塊之間的相對位移就是運動矢量。

圖1 深度圖運動估計原理

通常采用絕對差值和(sum of absolute difference，SAD)準則來判斷當前塊與參考塊之間的匹配程度，SAD值越低，則兩個編碼塊的匹配程度越高。SAD的計算方法如式(1)所示

(1)

式中：對于大小為M×N的編碼塊，fi(m,n)表示第i幀中坐標為(m,n)處的像素值，fi-1(m+x,n+y)表示第i-1幀中坐標為(m+x,n+y)處的像素值，(x,y)表示運動矢量。

在3D-HEVC標準測試軟件中，推薦了FS和TZSearch兩種搜索最佳匹配塊的算法。FS算法需要將搜索窗中所有位移的參考塊逐一地與當前塊進行比較，尋找SAD值最小的最佳匹配塊。TZSearch算法結(jié)合了DS算法和光柵搜索，能夠極大減少運動搜索點數(shù)同時保持編碼性能。但是這兩種搜索算法是針對變化復(fù)雜的紋理圖屬性設(shè)計的，當被用于平坦區(qū)域為主要特征的深度圖時，會導(dǎo)致較多的運動搜索點數(shù)，使得計算時間增加。在3D-HEVC深度圖編碼中，運動估計模塊的計算量占深度圖編碼總計算量的19.74%[4]。因此如果引入輕量級的搜索算法將會大大降低運動估計模塊的計算開銷。

2 基于塊分類的深度圖運動估計優(yōu)化方法

2.1 運動矢量的中心偏置特性分析

在運動圖像中，中心偏置特性反映了視頻圖像幀間運動的強烈程度。當幀間運動較小時運動矢量總會高度聚集在搜索窗口的中心位置，通常是兩個像素為半徑的范圍。該特性通常用以減少搜索點數(shù)，提高搜索效率。本文對平坦區(qū)域和邊緣區(qū)域編碼塊運動矢量的分布進行了研究，發(fā)現(xiàn)平坦區(qū)域運動矢量的中心偏置特性非常明顯，如圖2所示。圖2對深度圖測試序列Balloons中編碼塊的SAD值進行了統(tǒng)計。其中，圖2(a)、圖2(b)分別為第45幀和第46幀的部分區(qū)域。圖2(b)所示標號為1，2的部分為第46幀的兩個16×16的編碼塊?？梢钥闯鰳颂枮?的編碼塊位于邊緣區(qū)域，標號為2的編碼塊位于平坦區(qū)域，它們在第45幀中的同位塊和搜索窗位置如圖2(a)所示。圖2(c)、圖2(d)分別給出了對第46幀編碼塊1和編碼塊2在第45幀對應(yīng)搜索窗中應(yīng)用FS算法獲得的SAD值分布。從圖2(c)可以看出，邊緣區(qū)域編碼塊的SAD值變化復(fù)雜，且較低的SAD值距離搜索區(qū)域中心點(40,40)較遠，所以運動矢量沒有表現(xiàn)出較為明顯的中心偏置分布特性；而圖2(d)中平坦區(qū)域編碼塊的SAD值變化平緩，且最佳的SAD值高度集中分布在搜索區(qū)域中心點的附近位置，其運動矢量更具有中心偏置分布特性。

圖2 邊緣、平坦區(qū)域SAD值分布

因此，邊緣區(qū)域的運動矢量過于分散，必須選取精細型的搜索算法，才能在搜索窗中找到最佳的SAD值；而對平坦區(qū)域則可以利用其運動矢量的中心偏置分布特性，使用輕量級的快速搜索算法，減少搜索次數(shù)，提高收斂速度。

若要在硬件上實現(xiàn)深度圖運動估計算法，則選取的搜索算法模板不僅要適合深度圖的SAD值分布還要具有較天然的操作可并行性。TZSearch算法可以達到和FS算法相差不多的編碼質(zhì)量并且降低了運動搜索點數(shù)，但是TZSearch算法在搜索時采用了多個搜索模板，使得搜索路徑不確定且數(shù)據(jù)讀取不規(guī)則，因而不利于算法的并行實現(xiàn)；考慮到FS算法計算結(jié)構(gòu)簡單且易于并行處理，本文對深度圖中的邊緣區(qū)域采用了FS算法。此外，考慮到DS算法能夠充分利用運動矢量的中心偏置分布特性，優(yōu)先計算搜索窗口的中心點，對于小運動的視頻序列有較好的預(yù)測結(jié)果[9]，非常契合深度圖大范圍平坦區(qū)域的特點，本文選擇DS算法處理深度圖的平坦區(qū)域。

2.2 算法切換的閾值判定

如果要對不同類型區(qū)域編碼塊使用不同的搜索算法，就需要增加預(yù)處理模塊，對編碼塊是平坦或者邊緣進行判定。常用的深度圖像邊緣檢測方法有兩大類，一類是利用邊緣檢測算子提取圖像的邊緣，該方法在計算過程中采取了大量的卷積操作，使得計算量增加，且邊緣檢測算子對圖像噪聲敏感。另一類是通過統(tǒng)計分析的方法得到區(qū)分邊緣和平坦區(qū)域的經(jīng)驗閾值，文獻[4]采用編碼塊4個角的最大差值對深度圖進行分類，若最大差值大于閾值則判定為邊緣塊，反之則判定為平坦塊，大大降低了計算開銷，但是會對邊緣位于編碼塊內(nèi)部的情況會產(chǎn)生誤判。因此本文針對該問題在文獻[4]的基礎(chǔ)上引入差異程度Pmax對深度圖進行分類，該方法計算開銷較小同時也可以解決文獻[4]存在的誤判問題。

以測試序列Balloons第一幀的深度圖像為例，如圖3所示。其中編號1-4為平坦區(qū)域編碼塊，其像素值均無變化，編號5-8為邊緣區(qū)域編碼塊，其像素值有明顯的邊界變化。本文選用一個編碼塊4個角的像素值作為基準像素值，對編碼塊內(nèi)部的所有像素值分別與4個基準像素值作差求得絕對差值和，選用其中最大的絕對差值和作為差異程度Pmax。對一個大小為M×N的編碼塊，其差異程度Pmax可以通過式(2)獲得

圖3 Balloons序列深度圖

(2)

式中：f(m,n)表示坐標為(m,n)處的像素值，Pi表示第i個角的基準像素值。

為了挖掘編碼塊像素值分布特征和差異程度Pmax之間的關(guān)系，本文利用3D-HEVC幀內(nèi)預(yù)測的模式選擇結(jié)果來對深度圖編碼塊的差異程度進行分類。由于在3D-HEVC幀內(nèi)預(yù)測中，除了常規(guī)的35種幀內(nèi)預(yù)測模式，還專門針對邊緣區(qū)域新增了深度建模模式(depth model modeling，DMM)。因此若某編碼塊選取常規(guī)幀內(nèi)預(yù)測模式作為最佳預(yù)測模式，即該編碼塊更大概率為平坦區(qū)域，而選取DMM作為最佳預(yù)測模式時，該編碼塊為邊緣區(qū)域的可能性更大。它們所對應(yīng)的Pmax就可以被用來作為編碼塊特征的判定依據(jù)。

為此，本文在3D-HEVC測試平臺HTM16.0上對測試序列進行了預(yù)測模式數(shù)據(jù)統(tǒng)計。在通用測試條件(common test condition，CTC)配置下，使用Kendo和Poznan_Street兩組測試序列，計算了8×8，16×16，32×32等不同大小編碼單元(coding unit，CU)的Pmax以及該CU選取的幀內(nèi)預(yù)測模式，并統(tǒng)計了Pmax在各個區(qū)間的概率密度。圖4(a)～圖4(c)分別給出了8×8、16×16、32×32CU的Pmax概率密度分布曲線。在圖4(a)中可以看出當Pmax小于800時，8×8CU選取常規(guī)的幀內(nèi)預(yù)測模式概率很大；當Pmax大于800時，8×8CU選取DMM的概率很大。因此本文將Pmax等于800作為區(qū)分8×8CU為平坦區(qū)域或者邊緣區(qū)域的閾值TH8×8。同理可以得到16×16CU和32×32CU的閾值。由于尺寸較大的CU包含的像素多，所以16×16CU和32×32CU的閾值會更高一些。

圖4 Pmax概率密度分布曲線

采用2.1節(jié)和2.2節(jié)的優(yōu)化思路，本文提出了一種基于塊分類的深度圖運動估計算法，其流程如圖5所示。

圖5 基于塊分類的深度圖運動估計算法流程

3 優(yōu)化后算法的并行化實現(xiàn)

3.1 視頻陣列處理器結(jié)構(gòu)

本文所使用的視頻陣列處理器[10]是由項目組自主研發(fā)的一種可重構(gòu)視頻陣列處理器，支持H.264/AVC，MVC，H.265/HEVC等多種視頻編解碼標準。該處理器從邏輯上將陣列劃分成處理元簇(process elements group，PEG)，每個PEG由4×4的處理元(process element，PE)陣列構(gòu)成。每個PE不僅可以訪問自身的存儲器和寄存器，還可以通過鄰接互連和共享存儲的通信方式訪問同一PEG內(nèi)其它PE的數(shù)據(jù)。由于視頻算法中的數(shù)據(jù)處理大部分都是以N×N的矩形塊進行的，所以這種專用體系結(jié)構(gòu)相比其它結(jié)構(gòu)能更有效應(yīng)對視頻算法的并行化設(shè)計。

通過對運動估計算法分析發(fā)現(xiàn)，每一個編碼塊依據(jù)其原始像素值、參考像素值及相應(yīng)的搜索算法進行塊匹配，獲得該編碼塊的最佳匹配塊。下一個編碼塊進行塊匹配時所需要的數(shù)據(jù)并不依賴于上一個編碼塊的計算結(jié)果，所以不同編碼塊在塊匹配計算時沒有數(shù)據(jù)相關(guān)性。因此，可以對多個編碼塊的計算使用并行操作以減少編碼時間。

3.2 參考像素的數(shù)據(jù)復(fù)用

本文利用視頻陣列處理器的天然并行結(jié)構(gòu)，以8×8大小的編碼塊為對象，對搜索窗為16×16的深度圖運動估計進行并行化設(shè)計。如果同時對多個不同的編碼塊并行進行塊匹配，可以大幅度減少運動估計算法的周期數(shù)，但是卻增加了電路面積和功耗。因此，合理的選擇并行計算編碼塊的個數(shù)，才能達到充分利用資源和縮減編碼時間的效果。

本文從最大化復(fù)用最先被讀取的編碼塊參考像素的角度，來選取并行計算的編碼塊。根據(jù)運動估計算法，上下左右4個相鄰編碼塊的搜索窗之間存在大量參考像素的重合，編碼塊1搜索窗第9列到第16列的參考像素為編碼塊2搜索窗的第1列到第8列如圖6(a)所示，編碼塊1搜索窗第9行到第16行的參考像素為編碼塊3搜索窗的第1行到第8行如圖6(b)所示，編碼塊1搜索窗的第9行第9列、第9行第16列、第16行第9列、第16行第16列所圍成8×8搜索區(qū)域是編碼塊4搜索窗的第1行第1列、第1行第8列、第8行第1列、第8行第8列所圍成區(qū)域的參考像素如圖6(c)所示，編碼塊2～編碼塊4的參考像素和編碼塊1搜索窗重合的總像素數(shù)為196個。如果為4個編碼塊分別從片外存儲加載搜索窗，將會有大量的參考像素被重復(fù)的讀取，增加了計算的總周期數(shù)。但是如果將編碼塊1本地存儲的參考像素復(fù)用到編碼塊2～編碼塊4的參考像素中，對編碼塊1參考像素的數(shù)據(jù)復(fù)用可以達到75%，從而有效地減少訪問片外存儲器的次數(shù)，縮減運動估計算法的時間。綜上所述，本文選擇同時對4個8×8編碼塊并行計算。

圖6 編碼塊1搜索窗的數(shù)據(jù)復(fù)用

3.3 基于塊分類的深度圖運動估計算法并行映射

本文采用一個PEG結(jié)合3.2節(jié)提出的參考像素的數(shù)據(jù)更新方法，對4個8×8的編碼塊并行地進行第2節(jié)所提優(yōu)化算法的閾值計算和塊匹配。算法的映射圖如圖7所示，數(shù)據(jù)輸入存儲器(data input memory，DIM)、數(shù)據(jù)輸出存儲器(data output memory，DOM)均為片外存儲器，分別緩存原始視頻序列和參考視頻序列，PE00、PE10分別為原始像素和參考像素加載模塊；PE01、PE02、PE03和PE13為Pmax計算模塊；PE11、PE12、PE20和PE21為采用FS算法計算SAD值模塊，PE22、PE23、PE30和PE31為采用DS算法計算SAD值模塊；PE32為數(shù)據(jù)輸出模塊。具體操作步驟如下：

圖7 優(yōu)化后運動估計算法映射

步驟1 原始數(shù)據(jù)的加載。PE00訪問DIM，讀取一個16×16的編碼塊，并將編碼塊1、2、3、4的原始像素值分別下發(fā)給PE01、PE02、PE03和PE13；

步驟2 參考數(shù)據(jù)的加載。PE10訪問DOM，按照上述參考像素復(fù)用的方式，將編碼塊1、2、3、4的參考像素值分別下發(fā)給PE11、PE12、PE20和PE21；

步驟3 4個PE并行為4個編碼塊計算Pmax。根據(jù)4個PE計算Pmax的不同，4個編碼塊根據(jù)不同的搜索算法進行SAD值的計算，如果Pmax>TH8×8則跳轉(zhuǎn)至步驟4；如果Pmax

步驟4 PE11、PE12、PE20和PE21根據(jù)FS算法為當前編碼塊進行塊匹配操作。計算得到最佳SAD值后，將最佳SAD值對應(yīng)參考塊的運動矢量存儲到PE32中。

步驟5 PE22、PE23、PE30和PE31根據(jù)DS算法為當前編碼塊進行塊匹配操作。計算得到最佳SAD值后，將最佳SAD值對應(yīng)的運動矢量存儲到PE32中。

步驟6 PE32收到編碼塊1、2、3、4的運動矢量之后，將其輸出。

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

為了比較基于塊分類的深度圖運動估計算法的效果，本文使用了包含不同分辨率和不同運動情況的8組公共測試序列的1-50幀，在MATLAB平臺上通過統(tǒng)計運動搜索次數(shù)，用于衡量算法的計算量；統(tǒng)計圖像的PSNR用于衡量算法的性能。并基于視頻陣列處理器驗證上述基于塊分類的深度圖運動估計算法并行實現(xiàn)的可行性，通過加速比和硬件架構(gòu)資源分析來衡量在視頻陣列處理器上進行并行化的性能。

4.1 算法的運動搜索次數(shù)分析

在運動估計中，運動搜索的次數(shù)可以反應(yīng)運動估計算法的計算量。圖8給出了本文提出的搜索算法與FS算法、DS算法和TZSearch算法相比較搜索次數(shù)改變的百分比，計算公式如式(3)所示

(3)

式中：Ptprop代表本文搜索算法的搜索點數(shù)，Ptcompare代表FS算法、DS算法或者TZSearch算法的搜索點數(shù)，從圖8中可以看出與FS算法相比，本文提出的搜索算法可以大幅度地減少搜索點數(shù)，所有測試序列的搜索點數(shù)平均減少77.32%；相比于TZSearch算法，所有測試序列的搜索點數(shù)平均減少12.04%，極大降低了運動估計算法的計算量。相比于DS算法，所有測試序列的搜索點數(shù)平均增加10.40%。其中Shark序列相比于FS算法搜索點數(shù)減少的幅度較小，相比于TZSearch算法是唯一一個搜索點數(shù)增加的測試序列，相比于DS算法搜索點數(shù)增加的幅度最大，是因為該序列的前景和背景區(qū)域存在著較多的運動對象且運動幅度較大，導(dǎo)致圖像邊緣區(qū)域增多。Poznan_Hall2序列相比于FS算法和TZSearch算法搜索點數(shù)減少幅度較大，相比于DS算法搜索點數(shù)幅度增加最少，是因為該序列的平坦區(qū)域占比更高，且物體的運動幅度較小。

圖8 本文搜索算法減少的搜索點數(shù)

4.2 算法的性能

PSNR是一種衡量圖像質(zhì)量的指標，表1為本文算法與FS算法、DS算法相比圖像的PSNR損耗。從表1可以看出，與FS算法相比，本文算法的平均PSNR損耗為0.0870 dB，在運動搜索次數(shù)大幅度降低的情況下，可以達到和FS算法相差不多的PSNR。相比于DS算法，在運動搜索次數(shù)小幅度增加的情況下，本文算法的平均PSNR損耗為-2.2771 dB。在折中考慮運動搜索次數(shù)和圖像質(zhì)量的情況下，本文所提出的算法在達到和FS算法相差不多的PSNR的情況下，相比于TZSearch算法可以減少12.04%的運動搜索次數(shù)，所以本文提出的改進方法比TZSearch算法性能略佳。

表1 優(yōu)化后算法的PSNR損耗

4.3 硬件綜合對比結(jié)果

本文在視頻陣列處理器上驗證基于塊分類的深度圖運動估計算法并行實現(xiàn)的可行性。首先將測試序列轉(zhuǎn)換成陣列可以識別的二進制序列，然后將原始幀和參考幀分別存儲在片外存儲DIM和DOM中，其次將并行方案的指令初始化到對應(yīng)PE的指令存儲中，最后在QuestaSim上進行仿真驗證。本文用單PE的串行執(zhí)行時間作為串行處理時間。8組公共視頻測試序列的平均串行執(zhí)行時間為1.308 s，并行執(zhí)行時間為0.452 s，平均加速比可以達到2.894，減少了65%的執(zhí)行時間。采用Xilinx公司的ISE14.7開發(fā)環(huán)境進行綜合，綜合結(jié)果見表2，可看出僅需要11 722個LUTs，33 641個Registers的硬件資源，最高工作頻率可達到122 MHz。文獻[7]是在DS算法的基礎(chǔ)上提出的改進算法和硬件架構(gòu)，可以同時計算一個預(yù)測單元內(nèi)所有的搜索點數(shù)，但是是以消耗了大量的硬件資源為代價的，所使用的硬件資源為本文的8.75倍。文獻[8]是在FS算法的基礎(chǔ)上設(shè)計的硬件架構(gòu)，在頻率和本文相當?shù)那闆r下，硬件資源是本文設(shè)計的1.2倍。

表2 硬件資源結(jié)果對比

5 結(jié)束語

本文針對深度圖的運動估計，提出了一種結(jié)合算法和并行設(shè)計的優(yōu)化方法。首先針對深度圖的特點，優(yōu)化了運動估計搜索算法。實驗結(jié)果表明，與FS算法相比，8組測試序列的平均PSNR值損耗僅為0.0870 dB；與TZSearch算法相比，運動搜索次數(shù)平均減少了12.04%，在折中考慮運動搜索次數(shù)和編碼質(zhì)量的情況下，該方法獲得了略優(yōu)于TZSearch算法的性能。然后，基于視頻陣列處理器對提出的改進方法進行了并行化設(shè)計，又從最大化復(fù)用參考數(shù)據(jù)的角度選取了并行計算編碼塊的個數(shù)，進一步減少了硬件資源的消耗。本文提出的基于塊分類的深度圖運動估計及其并行實現(xiàn)方案，在編碼質(zhì)量、計算效率和資源消耗方面均得到了不同程度的改善。