運動估計是視頻編碼中的關鍵部分，同時也是較為復雜的部分。在運動估計中，運動搜索算法分為兩大類：全搜索算法和快速搜索算法^[1]。全搜索算法（FSM）是一種搜索策略最簡單的算法，是將搜索范圍中的每個塊都搜索一遍，從而找到最佳匹配塊。此算法簡單可靠，易于硬件實現，但是計算量大，耗費的時間多。快速搜索算法是一種只對少數可能是匹配塊的候選塊進行匹配，從而找到局部的最佳匹配塊。此算法計算量小，時間開銷少，但是算法復雜度高，不易于硬件實現。

    由于視頻信號處理對實時性要求很高，而FSM需要計算所有的宏塊，費時較長，因此，本文采取分層的方式^[2]，即在搜索區域中每隔一個像素選取一個像素點作為候選塊搜索的起點(1、3、5…)，利用多個存儲器并聯，將單個像素的讀入/讀出轉換為一列像素的讀入/讀出，并結合大量的處理單元（PE）構成并行的處理器陣列進行數據處理，設計一種分層的二維陣列全搜索運動估計硬件電路，大大減少了計算量以及編碼時間。

1 基本原理

    對于運動估計分層二維陣列全搜索方式，大致有兩種最基本的實現方法：(1)所有的PE陣列同時進行匹配，計算搜索區域內所有的候選塊，這是一種高度并行的方式，處理速度快，對于16×16的當前塊，只需256個時鐘周期就可完成搜索，但是輸入數據帶寬大，控制較為復雜，不易于硬件的實現；(2)相鄰的PE進行匹配時，無論是行還是列，各自都存在延時，如圖1所示，本設計以當前塊為16×16的宏塊、搜索區域為32×32為例，同一行的PE1是在PE0工作2個時鐘周期后開始工作，同一列PE8是在PE0工作32個周期后開始工作，然后以此類推。這是一種并行的流水線結構，數據流規整，易于操作，共需要494個時鐘周期就可完成搜索，但是延時器過多，硬件資源消耗大^[2-4]。

    本設計提出的分層二維陣列搜索方式對以上兩種方法作出了改進，如圖2所示，列與列之間的PE是存在延時的，而行與行之間的PE是不存在延時的，比如第一列的PE最先同時工作，緊接著延時2個時鐘周期，第二列PE也開始同時工作，然后以此類推，最先工作的PE，也最先結束工作。同時從圖中還可看出，輸入的數據為一個時鐘周期輸入一列的像素，而非單個像素，這樣設計不僅使得延時器的個數減少了一半，節約了硬件資源，而且使得一個塊的匹配只需16個時鐘周期，再加上延時的14個時鐘周期，那么完成搜索總共只需30個時鐘周期，大大節約了編碼的時間。

2 硬件電路設計

    分層二維陣列全搜索運動估計硬件電路是以16×16的宏塊為對象，32×32為搜索區域，采用了64個處理單元（PE），形成并行的流水線結構^[5]，它包括地址發生器、16×16的Ram0、32×32的Ram1、延時器、二維PE陣列、比較器和控制器7個模塊。原理框圖如圖3所示。

    圖3中地址發生器用于產生讀與寫的地址以及一些控制信號。7個延時器采用級聯的方式連接，其作用是將當前塊數據延時輸出，第一個延時器(delay1)的輸入連接Ram0的輸出，延時兩個周期；第二個延時器(delay2)的輸入連接delay1的輸出，又延時兩個周期，然后以此類推。Ram0、delay1、delay2…delay7的輸出分別作用于PE0~PE56(第1列PE)、PE1~PE57、PE2~PE58…PE7~PE63，這樣形成了每延時2個周期，一些PE才開始工作，其余部分以下作詳細的介紹。

2.1 存儲器陣列設計

    以Ram0為例，它是一個16×16×8 bit的存儲器，用來存儲當前塊的數據。Ram0的設計是使用了Quartus II 的宏功能模塊RAM^[6]，它是一個16×8 bit的存儲器。因此，為了設計成一個16×16×8 bit的存儲器，本設計采用16個16×8 bit的RAM并聯。結構圖如圖4所示，16個RAM共用同一個讀/寫地址線，當讀/寫地址線從0000~1111變化，分別讀出/寫入Ram0的第0列～第15列。

    從圖4中可以看出，Ram0的輸入/輸出端口都為16×8 bit寬，一個周期可以輸入/輸出一列16個像素的數據，這樣一個16×16的宏塊只需要17個周期就能完全讀出。與單個像素的輸入/輸出相比，節約了大量的周期，加快了讀入/讀出的速度，能更好地滿足實時性要求。

2.2 二維PE陣列設計

    處理單元陣列是運動估計中的核心模塊，它的運算量最大，占用硬件資源也最多。本設計采用了64個PE進行數據的處理，PE的內部結構如圖5所示^[7]。首先對當前塊數據（C）和參考塊數據（R）進行絕對值差值運算，然后將得到的差值與上一次計算所得的值SAD進行累加（ALU），并將累加的結果放在寄存器（REG）中，計數器作用于累加器，控制累加的次數，當累加次數達到16次時，輸出匹配塊的最終殘差值SAD。

2.3 數據比較器設計 

    數據比較器作用于PE之后，對PE最終輸出的各個數據比較大小，從而得到當前塊與搜索區域參考塊的最小殘差（SAD）。它的硬件結構圖如圖6所示。

    從圖6中可以看出，此模塊是采用8個數據比較器級聯的方式，PE0~PE56（第一列PE陣列）的最終輸出最先比較大小，得到這一列陣列的最小值；緊接著過2個時鐘周期，PE1~PE57的最終輸出與之前得到的最小值進行比較，又得到一個最小值。同理可得，延時14個時鐘周期后，PE7~PE63的最終輸出與上個比較器的輸出進行比較，得到最終的最小值SAD。

2.4 控制器設計

    控制器的工作過程可以分為兩個部分：控制Ram的讀寫、控制PE是否工作。具體工作過程：在復位結束后，在時鐘的觸發下產生寫信號，開始對Ram0、Ram1寫數據；延遲一個周期產生讀信號，開始對Ram0、Ram1讀數據；又延遲一個周期產生enable0使能信號，它作用于第1列的PE，表示第1列PE有效，開始工作；接著，延遲2個周期產生enable1使能信號，它作用于第2列的PE，表示第2列PE有效，開始工作；以此類推，enable2……enable7都是在之前的一步延遲2個周期后產生的。工作狀態轉移圖如圖7所示。

3 整體驗證結果及分析

    本文設定時鐘頻率為100 MHz,即時鐘周期為10 ns，輸入數據寬度為8 bit，16×16當前塊所有數據為2，32×32搜索區域數據除7~22列的1~16行（PE3計算區域）外，其他區域全為3，而PE3計算區域只有一個數為3，其余為2，部分仿真結果如圖8所示。從仿真圖可以看出，最小殘差值（SAD）的輸出用了35個時鐘周期，其中PE陣列的輸出用了30個時鐘周期，其余的用于控制和比較。sum0(PE0的SAD輸出)、sum8…sum56第1列的PE陣列首先輸出結果，每個時鐘周期輸出1列，經過16個時鐘周期，最后累加輸出最終結果；sum1、sum9…sum57第2列的陣列延時2個周期輸出結果，然后以此類推。

    觀察仿真結果可知，最匹配塊為PE3計算的區域（sum3=1）,殘差最小值SAD為1，與設定數據的理論計算相符，從而驗證了設計的正確性。

    此硬件模塊采用Verilog HDL硬件描述語言，使用Quartus II 8.1進行綜合與仿真，實現了分層二維陣列全搜索的硬件設計。結果表明，在工作頻率為100 MHz時，相比于傳統的方法，節約了不少時鐘周期，對于30 f/s的情況，完全可以得到滿足。

    本文采用分層的二維陣列全搜索方法，設計了基于FPGA分層的二維陣列全搜索硬件電路，并對此硬件電路進行了分析，完成了各個子模塊的設計，最后對整個模塊進行了仿真，實現了復雜度和編碼速度的良好折中。由于本設計采用的是分層搜索方法，精度相比傳統全搜索有所降低，如果想進一步提高精度，可以以分層搜索得到的最佳塊為中心，對其相近未搜索的幾個像素點進行細搜索。實際上，得到最終高精度的匹配塊，也減少了近一半的工作量，提高了搜索效率。

參考文獻

[1] 賈克斌，劉鵬宇.基于H.264的視頻編碼處理技術與應用[M].北京：科學出版社，2013.

[2] 何春芬.基于FPGA的H.264幀內預測與幀間預測設計[D].重慶：重慶大學，2009.

[3] 和王峰.AVS運動估計模塊硬件架構設計[D].哈爾濱：哈爾濱工業大學，2008.

[4] 吳燕秀，王法翔.適用于AVS的高性能整像素運動估計硬件設計[J].電子技術應用，2013，39(1)：40-42.

[5] 胡文安.AVS視頻編碼并行算法的研究與實現[D].成都：電子科技大學，2010.

[6] Michael D.Ciletti.Verilog HDL 高級數字設計[M].北京：電子工業出版社，2005.

[7] 李本齋，吳從中，陳家銀.H.264運動估計硬件加速器的設計[J].電視技術，2010，34(S1)：79-81.