基于FPGA的運動估計算法優化和硬件架構設計

秦傳義 于林韜,2* 王曉丹 朱一峰,2 周玉軒

1(長春理工大學電子信息工程學院 吉林 長春 130022)2(長春理工大學空地激光通信技術國防重點學科實驗室 吉林 長春 130022)

0 引 言

隨著4K/8K超高清(UHD)視頻應用發展和第五代移動通信(5G)技術的部分商用，圖像清晰度大幅提高，導致視頻流數據量激增。因此，迫切需要利用HEVC/H.265高效的視頻編解碼標準，用以解決大數據量狀態下視頻圖像傳輸以及儲存不暢問題[1]。與其前身的H.264/AVC相比，HEVC在很多方面有了革命性的變化。更加靈活高效的塊結構樣式、采樣點自適應偏移(Sample Adaptive Offset,SAO)技術和自適應環路濾波(Adaptive Loop Filter,ALF)方法配合并行化設計方案使HEVC獲得更好的編碼性能和并行處理能力[2]。

該方法在帶來系統性能提升的同時使得系統架構更加復雜，很難在實際應用中部署。在實際視頻編碼過程中，運動估計(Motion Estimation,ME)和運動補償(Motion Compensation,MC)在幀間預測中高復雜度、高時間消耗等缺點，幀間預測的計算量占總編碼運算量44.5%～86.3%，其消耗超過幀間預測時間的90%。ME比MC更具挑戰性和耗時，由ME引起的幀間預測時間占75%以上。因此，在保證視頻畫面播放質量的同時，設計一種快速算法結構從而降低運動估計的復雜程度，并通過新的硬件架構設計加速運動估計過程，以解決傳統的嵌入式方案下視頻流不穩定、低速率的傳輸特點，從而提高HEVC編解碼速率[3]并以較高的壓縮效率進行數據壓縮。

HEVC編碼的復雜性研究是一個關鍵主題。由于運動估計占據整個編碼的絕大部分時間，因而研究的工作主要是圍繞如何減少運動估計所消耗的時間，從而降低HEVC的計算復雜度。這段時間的減少是通過軟件和硬件方法完成的。

在基于FPGA的運動估計算法軟件優化研究中，主要有線菱形并行搜索算法(LDPS)、水平菱形搜索(HDS)、鉆石搜索(Diamond Search,DS)、交叉鉆石搜索(CDS)。ME算法有比較高計算復雜度，為降低其復雜度、減少搜索算法所需的時間，許多研究學者在基于傳統六邊形搜索的快速搜索算法[4]和傳統鉆石搜索[5]的基礎上提出了許多改進搜索算法，文獻[6]提出了基于SAD算法的快速幀間CU決策。文獻[7]用TZS算法中的六邊形點代替八菱形點和八方形點。盡管這些研究有效減少了運動估計時間，但運動估計算法大多基于軟件平臺算法架構的設計研究，并不適合于傳統硬件條件下的實現。

在基于FPGA的硬件架構設計中，目前已有的運動估計硬件架構的設計思路大部分主要用于上一代H.264/AVC編碼標準，例如文獻[8]中，在Xilinx SpartanII和Virtex-2 FPGA系列上提出了一種快速SAD算法，其塊大小范圍為4×4到16×16。而在H.265/HEVC上，一些硬件實現通過減少SAD計算時間來減少HEVC編碼的運動估計時間。文獻[9]提出了一種用于灰度圖像的硬件SAD設計，允許并行計算一個4×4維定義塊的所有SAD。文獻[10]提出了兩種新的架構，用于在FPGA Xilinx Virtex 5上計算具有和不具有并行性的SAD，實驗結果表明并行架構比非并行架構快3.9倍。

綜合上述研究與討論，本文在傳統DS算法架構的基礎上，提出基于FPGA的運動估計算法優化方法和新型硬件架構設計，結合HEVC視頻編碼的并行技術，改進DS搜索算法的硬件架構，該算法在實驗仿真中性能損失基本可以忽略。配合改進的硬件架構，減少了系統數據讀取時間，提高了硬件資源利用率，加快運動估計過程中系統的處理速度。

1 TZSearch搜索算法

TZSearch算法是由Tang等[11]2010年提出的一種混合搜索模型快速搜索算法，其具體搜索由以下四個步驟組成：運動矢量的預測；初始網格的搜索；柵格的搜索；柵格/星型精細搜索。文獻[11]中詳細描述了運動搜索環節中編碼端模塊TZSearch搜索算法的實現細節，其流程圖如圖1所示。

圖1 TZSearch算法

初始網格的搜索窗口中的搜索點總數N1為：

N1=P(1+floor(1bS))

(1)

式中：P為模板每次需要搜索的點數；S是TZSearch算法中搜索窗的大??；floor為向下取整函數。

柵格搜索的搜索窗口通常會處于采樣式全搜索狀態。當HM16.2的柵格搜索窗的采樣參數R的最佳步長B_distance≥R時，最佳步長被賦值為采樣參數。如下式所示，每一行/列需要搜索的點是C(S/R)，N2的最大值是需要搜索的點數[12]。

(2)

TZSearch算法對比全搜索算法，編碼性能略有降低，復雜程度大幅下降，搜索時間僅為全搜索算法的20%。對比常用運動估計快速搜索算法，TZSearch算法加入了初始搜索點的預測，同時使用可變步長的搜索模式進一步降低復雜度，并提高了搜索的準確性。然而TZSearch仍然存在不足之處：在搜索模板的設計上，TZSearch沒有根據視頻固有特性進行區別的搜索，增加系統編碼的復雜程度，在運動矢量水平垂直方向分布概率方面的相關實驗數據表現也劣于其他方法，在編碼時間和編碼效率上的表現差距同樣巨大，無法在實際場景中應用。

2 改進的TZSearch搜索算法

2.1 TZSearch復雜分布規律

采用TZSearc搜索算法對Vidyo1和Kimono不同特征序列的時間概率分布進行實驗統計，結果如圖2所示。

(a) Vidyo1序列

(b) Kimono序列圖2 Vidyo1和Kimono不同特征序列的時間概率分布

可見，在TZSearch中執行時間和計算復雜性方面最激烈的階段是初始搜索和精細搜索，初始搜索和精細搜索部分占TZSearch總時間的75%和68%。實際上，大部分ME時間由初始搜索和精細搜索部分獲取。

2.2 運動矢量的十字中心偏置特性

運動矢量在一定程度下具有十字中心偏置特性，文獻[13]提出運動矢量出現在水平和垂直方向的概率明顯高于其他任何方向。傳統狀態下的鉆石搜索算法的架構決定了其不能從根本上改變這一狀況，因此本文需要對鉆石搜索算法進行重新設計研究。

2.3 改進的鉆石搜索算法

改進的鉆石搜索算法(Improved Diamond Search,IDS)是使用菱形搜索算法的搜索路徑方法，如圖3所示。

圖3 菱形搜索模板序列(TZSearch算法)

該模式是軸對稱，并且在水平和垂直方向上具有相同的優先級。在DS算法中測試和計算兩種類型的鉆石圖案：小鉆石圖案和大鉆石圖案。

(1) 小鉆石搜索模式(Small Diamond Search Pattern,SDSP)：由圖3中四個“1”形成小菱形的點構成，有且僅有一種SDSP。

(2) 大鉆石搜索模式(Large Diamond Search Pattern,LDSP)：分別由圖3中“2”、“4”、“8”、“16”、“32”、“64”八個點組成六種大菱形，一共有6種LDSP。

算法在工作過程中會選擇最佳匹配塊，從而計算的運動矢量的具體值。匹配算法基于計算當前幀和參考幀之間的誤差代價函數，其被稱為SAD值，又稱絕對差值和。當RB和CB表示參考像素和當前塊時，SAD計算方法為：

(3)

對于每個點，確定SAD值并進行比較以提取每個特定距離中的最小值。搜索距離(Search Distance,SD)是中心點(0,0)到SDSP/LDSP的每個點(SD={1,2,4,8,16,32,64})的距離。開始時，SDS位于搜索窗口的中心點(0,0)。該第一操作是針對SD等于1執行的，之后，計算SD等于2的大鉆石八個點的SAD。然后，通過在每次迭代中將距離SD乘以2來遞歸地重復下一個LDS的過程。重復這些操作，直到SAD從一次迭代變為另一次迭代。當兩次迭代后最小SAD未改變時，或當距離等于搜索范圍時，該過程停止。

DS算法認為是降低計算復雜度的主要研究目標，鉆石搜索算法基于具有不同坐標的多個鉆石計算，即具有不同距離的鉆石，距離為1,2,4,8,16,32,64。因此，當優化一個鉆石時間時，僅通過修改距離參數，另一個時間將減少，這將導致所有DS時間減少，并且節省ME時間。圖4是IDS算法具體流程圖。

圖4 IDS算法流程圖

在IDS算法中，迭代7次，搜索步長SD為集合{1,2,4,8,16,32,64}，利用SDS與LDS方法計算算法迭代過程中的最佳距離B_distance，利用FPGA并行處理結構加速IDS算法使算法性能進一步優化。

3 基于FPGA的搜索算法硬件架構

3.1 基于FPGA的并行硬件架構

為了降低HEVC計算復雜度，減少ME時間。本文利用FPGA器件加速搜索菱形算法，設計并行架構來計算MV，以獲得更高的頻率，同時盡可能降低面積成本。

圖5所示為提出系統的架構及其分解為子模塊。通過名為“loading_module”的第一個模塊，逐行加載當前CTU和參考塊。通過代表第二個模塊的搜索模塊，計算根據菱形算法的運動矢量及其坐標。

圖5 系統的架構及其分解為子模塊

3.1.1加載模塊

對已有八個源和八個參考搜索區域，而不是參考和源塊。將八個參考塊(從塊ref 0到塊ref 7)被并行提取，與此同時選擇與每個參考塊相關的八個行像素。這種提取只需要一個時鐘周期。然后將這八條線傳遞到下一個模塊(SAD模塊par)以計算它們相應的SAD值。

3.1.2搜索模塊

搜索模塊如圖6所示，該模塊使用圖示中的硬件組件，可以計算鉆石的八個參考塊的SAD值。這樣做是為了選擇具有最佳SAD的最佳估計運動矢量。硬件結構由四個子模塊組成，分別是控制單元、Adaptator模塊、Memory模塊、SAD模塊和比較模塊。另外，控制單元選擇與每個參考塊相關聯的像素，負責所有子模塊之間的尋址、定時和同步。

圖6 搜索模塊

3.1.3SAD模塊

SAD模塊如圖7所示，適用于計算參考像素和源像素之間的絕對差值和總和。其由兩個子電路組成：“差分模塊”和“累加器”，用于計算它們的相加。

圖7 SAD模塊

為了獲得最佳的實時性能，該并行架構使用并行執行的一些并行處理元件(PE)。其設計架構允許并行計算八個SAD值，MV是通過同時提取對應于每個參考塊的八條線來完成的。

3.1.4比較模塊

比較模塊如圖8所示，主要是確定MV及其坐標，它將每個獲得的SAD值與前一個值進行比較，提取它們的最小值，將MV的位置信息提供給控制單元，以選擇另一個距離下一個鉆石信息的下一個搜索，直至輸出，其輸出“結束”信號，則說明鉆石的所有塊計算結束。

圖8 比較模塊

4 實驗結果與分析

本文以HEVC為參考軟件HM16.2作為實驗測試平臺，在acer T5000筆記本電腦(Intel酷睿i7-6700HQ處理器、16 GB DDR4的內存、Windows 64位的操作系統)硬件條件下進行實驗，量化參數選擇17、22、27、32、37和42，視頻編碼100幀，實驗結果如表1所示。

表1 本文算法與HM16.2算法的對比結果

采用同等客觀質量下的碼率BDBR(Bj?ntegaard Delta Bit Rate)、同等碼率下的峰值信噪比BDPSNR(Bj?ntegaard Delta Peak Signal-to-Noise Rate)和編碼時間變化率ΔTime作為快速算法的評價指標。BDBR表示相同PSNR條件下碼率的變化百分比，BDPSNR表示相同碼率條件下PSNR的變化量。ΔTime計算方法如下：

(4)

式中：HM和proposed分別代表HM16.2和本文算法。表1的實驗結果證明：本文算法的復雜度平均下降了26.23%，最大可以達到33.87%。而BDPSNR的損失很小，僅降低了0.05 dB,BDBR的增加也不明顯，僅提高了1.19%。實驗證明本文設計的編碼器性能損失較小，本文算法更適合于實際場景中的應用。

圖9是序列Kinomol和Vidyo1使用HM16.2的搜索策略時每幀需要搜索的平均點數。在圖9(a)的序列Kinomol中HM16.2大致為120～190，而本文的搜索模板搜索IDS算法的平均每幀需要搜索的點數大致為50～65。

(a) Kinomol

在圖9(b)的序列Kinomol中HM16.2大致為150～230，IDS算法的平均每幀需要搜索的點數為40～60。實驗進一步說明了IDS算法相關策略可促使傳輸數據幀中每幀搜索點數進一步減少，從而降低編碼所用時間。

圖10給出了序列Kinomol和Vidyo1的性能曲線，從曲線圖可以看出所提出的IDS算法與原始TZSearch搜索算法相比PSNR值幾乎一致，顯示IDS算法保持了原有的編碼性能。

(a) Kinomol

(b) Vidyo1圖10 Kinomol和Vidyo1序列在不同QP下的PSNR曲線圖

圖11是序列Kinomol和Vidyo在不同QP狀態下的Time變化曲線圖，從曲線圖中可以看出本文所研究設計的IDS算法與原始TZSearch搜索算法相比，運動估計時間降低了15.57%～46.32%。

(a) Kinomol

(b) Vidyo1圖11 Kinomol和Vidyo1序列在不同QP下的Time曲線圖

可以看出，在編碼性能上本文優化算法略微有所下降，但是在允許范圍內人眼無法察覺。因此，本文算法在保證視頻質量的情況下降低系統算法復雜度。影響實驗結果的主要原因是本文的IDS算法隨迭代次數增加，搜索量也在持續上升，基于運動估計算法的優化和新型硬件架構的設計改進了FPGA中最耗時的搜索模塊，當迭代次數較少時鉆石搜索將會找到最佳點，從而提前設置了退出搜索的條件并直接退出整個搜索過程，從而保證了系統整體的編碼性能。

本文所提出硬件架構以Verilog語言來設計和實現。以Mentor Graphics ModelSim工具驗證功能的正確性，運用Virtex-7 FPGA器件在Xilinx ISE 13.1開發平臺中完成綜合。使用測試平臺將像素數據發送到菱形架構并存儲計算結果，之后使用Xilinx ISE 13.1將實現合成，放置并最終路由到Virtex-7 FPGA。

表2所示為本文實驗結果與相關文獻比較情況，文獻[14]提出了一種為FS算法設計的并行SAD架構，搜索區域為104×104像素，通過Virtex-5技術獲得的合成結果給出了大約348 MHz的頻率，與本文架構相比，它的頻率較高，但在LUT邏輯資源方面，文獻[14]占到Virtex-5平臺邏輯資源的36%，需要較大的存儲資源。文獻[15]也是使用Virtex-7技術用于整數運動估計器的合成和實現，但在時鐘周期和延遲時間方面，本文架構遠低于文獻[15]。

表2 與不同文獻硬件結構綜合對比

續表2

5 結 語

本文提出一種先小后大鉆石算法和FPGA硬件實現的優化方法，來適用于HEVC的運動估計IDS算法硬件單元，結合并行架構，以降低HEVC在執行時間方面的復雜性。其架構在Virtex-7 FPGA Xilinx ISE上實現。綜合結果表明，與其他架構相比，并行架構獲得一個SAD的相同時間，其允許增益為其他的8倍。此外，計算一個64×64的塊所需的時鐘周期和所獲得的并行版本的延遲優于以前工作中的所有結果。總之，其并行設計可以更好地在FPGA上實現可用資源，有較高的處理速度和資源利用率，所提出的鉆石模塊可以用于具有一些修改的可變塊大小，并且可以提供出色的結果，對以后研究具有一定的實用價值。