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

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

1 基本原理

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

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

2 硬件電路設(shè)計(jì)

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

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

2.1 存儲(chǔ)器陣列設(shè)計(jì)

    以Ram0為例，它是一個(gè)16×16×8 bit的存儲(chǔ)器，用來(lái)存儲(chǔ)當(dāng)前塊的數(shù)據(jù)。Ram0的設(shè)計(jì)是使用了Quartus II 的宏功能模塊RAM^[6]，它是一個(gè)16×8 bit的存儲(chǔ)器。因此，為了設(shè)計(jì)成一個(gè)16×16×8 bit的存儲(chǔ)器，本設(shè)計(jì)采用16個(gè)16×8 bit的RAM并聯(lián)。結(jié)構(gòu)圖如圖4所示，16個(gè)RAM共用同一個(gè)讀/寫(xiě)地址線(xiàn)，當(dāng)讀/寫(xiě)地址線(xiàn)從0000~1111變化，分別讀出/寫(xiě)入Ram0的第0列～第15列。

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

2.2 二維PE陣列設(shè)計(jì)

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

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

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

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

2.4 控制器設(shè)計(jì)

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

3 整體驗(yàn)證結(jié)果及分析

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

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

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

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

參考文獻(xiàn)

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

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

[3] 和王峰.AVS運(yùn)動(dòng)估計(jì)模塊硬件架構(gòu)設(shè)計(jì)[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2008.

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

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

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

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