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

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

1 基本原理

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

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

2 硬件電路設計

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

    圖3中地址發(fā)生器用于產(chǎn)生讀與寫的地址以及一些控制信號。7個延時器采用級聯(lián)的方式連接，其作用是將當前塊數(shù)據(jù)延時輸出，第一個延時器(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的存儲器，用來存儲當前塊的數(shù)據(jù)。Ram0的設計是使用了Quartus II 的宏功能模塊RAM^[6]，它是一個16×8 bit的存儲器。因此，為了設計成一個16×16×8 bit的存儲器，本設計采用16個16×8 bit的RAM并聯(lián)。結構圖如圖4所示，16個RAM共用同一個讀/寫地址線，當讀/寫地址線從0000~1111變化，分別讀出/寫入Ram0的第0列～第15列。

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

2.2 二維PE陣列設計

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

2.3 數(shù)據(jù)比較器設計 

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

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

2.4 控制器設計

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

3 整體驗證結果及分析

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

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

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

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

參考文獻

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

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

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

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

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

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

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