摘 要： 針對格式轉(zhuǎn)換領(lǐng)域，提出一種全新的運動估計算法,。該算法通過使用改進的三步搜索算法（TSS）進行運動估計,，并引入零檢測和矢量濾波器對運動矢量進行修正。硬件實現(xiàn)結(jié)構(gòu)基于數(shù)字微分分析DDA算法,，通過FPGA系統(tǒng)驗證證明算法有效,，設(shè)計可行。
關(guān)鍵詞： 視頻格式轉(zhuǎn)換芯片,；幀頻提升,；塊匹配
?
在視頻信號中,，當場景中有快速運動物體存在時，必須事先估計場景中運動物體的位移量,，即進行運動位移估值,。得到運動位移的過程稱為運動估計，通過運動估計可以去除幀間冗余度,，使得視頻傳輸?shù)谋忍財?shù)大為減少,。運動估計是視頻編碼中的核心技術(shù)，運動估計的好壞直接影響到編碼的效率和圖像恢復(fù)的質(zhì)量,。
目前在視頻編碼領(lǐng)域使用的運動估計算法有塊匹配,、像素遞歸法、相位相關(guān)法,，其中塊匹配運動估計算法(BMA)是消除視頻數(shù)據(jù)時間冗余最基本且最重要的方法,。由于其具有簡單高效、額外開銷小,、易于硬件實現(xiàn)等優(yōu)點而被包括H.26X,、MPEG.1，MPEG.2和MPEG-4在內(nèi)的絕大多數(shù)視頻編碼標準所采用[1],。塊匹配的基本思想就是將每一幀圖像分成大小相同,、互不重疊的子塊(宏塊)，然后在參考幀中固定大小的搜索窗口內(nèi)找到最佳匹配塊,。按照一種塊損失度量準則找到的最佳匹配塊到當前塊的位移,，用運動矢量來描述。最佳匹配塊與當前塊之間的差值稱為殘差,。預(yù)測得越準確,，意味著殘差中的數(shù)值越小，編碼后的比特數(shù)也就越小,。
如何快速而準確地在參考幀中搜索到最佳的匹配塊是塊匹配算法的核心,。在本文研究的格式轉(zhuǎn)換領(lǐng)域，運動估計注重物體的真實運動軌跡,，不存在估算誤差的反饋補償,，要求得到的運動矢量足夠準確，能反映物體的真實運動,。另外,，由于格式轉(zhuǎn)換應(yīng)用的實時性,，要求算法盡量簡潔,，以易于硬件實現(xiàn)。因此本文使用改進的三步搜索算法（ITSS）進行運動估計,，并引入零檢測和矢量濾波器對運動矢量進行修正,。硬件實現(xiàn)結(jié)構(gòu)基于數(shù)字微分分析DDA(Digital Differential Analyzer)算法,，并用FPGA實現(xiàn)硬件原型。
1 基于塊匹配的運動估計算法
在參考幀中尋找匹配塊時,，需要定義最佳匹配的搜索判據(jù),。最佳匹配的搜索判據(jù)有以下幾種：相關(guān)函數(shù)CCF(Cross-Correlation Function)，均方誤差MSE（Mean-Square Error),，平均絕對差MAD(Mean Absolute Difference)和絕對差之和SAD(Sum of Absolute Difference),。在實際應(yīng)用中，由于SAD函數(shù)簡單（不含乘除法）,，便于硬件實現(xiàn),，而且具有令人滿意的性能，因此在本設(shè)計中也采用這種算法,。公式為：
其中,，(x，y)是指參考幀中當前塊的中心點(每個8×8匹配塊的中心點定為該塊左上角的像素）,，fn+1(x+i,，y+j)是指參考幀中當前塊的像素值，fn-1(x+i+vx,，y+j+vy)則是指前一幀搜索中候選匹配塊的像素值,。
根據(jù)上面最佳匹配的搜索判據(jù)，可得出參考幀中每一個塊的運動矢量：
其中,，S表示運動估計的搜索范圍,。
有了判斷最優(yōu)匹配點的準則，剩下的問題就是確定尋找最優(yōu)匹配點的收縮方法,。在目前的塊匹配算法中,，全搜索法(FS)具有最高的搜索精度，但其運算量大,、實時性差,。研究者們提出了多種快速搜索算法，較有代表性的有三步搜索法(TSS)[2],、四步搜索法(FSS)[3],、梯度下降法(BBGDS)[4]、菱形搜索法(DS)[5],、自適應(yīng)十字模板搜索算法(ARPS)[6]等,。其中三步搜索具有計算簡單、性能良好等優(yōu)點,，因而在視頻系統(tǒng)中得到了廣泛的應(yīng)用,。本文在研究運動估計的特點以及三步搜索算法的基礎(chǔ)上，提出了一種改進的三步搜索算法（ITSS）,。
(1)傳統(tǒng)三步搜索的匹配塊大小為16×16,，這顯然不適用于精細的運動補償線性插補,。但是，由于真實物體運動的一致性,，過小的匹配塊會產(chǎn)生較多不正確的運動矢量,。于是，將匹配塊的大小調(diào)整為8×8 以適應(yīng)插補要求,。
(2)原有的三步搜索一般都是步長折半搜索,，也就是說，如果第一步的補償為4(像素),，則第二步與第三步的補償分別為2和1,。對視頻系統(tǒng)中的幀頻提升來說，每兩幀之間的時間間隔非常小(約20ms),，說明兩幀之間匹配塊的運動矢量相對較小,。基于這個假設(shè),，將三步搜索中三步步長調(diào)整為3,、2和1，這樣搜索范圍為±6,。經(jīng)過調(diào)整,，運動估計的運動估計精度得到了一定提高。
當用塊匹配算法對小尺寸塊進行運動矢量估計時,，常易產(chǎn)生錯誤的運動矢量,。例如，有時即使塊處于靜止區(qū)域,，而得到的運動矢量卻不為零,。因此，本文引入了兩種運動矢量修正技術(shù)來提高運動矢量的準確性,。運動矢量修正技術(shù)是基于一個假設(shè),，即時-空域是平滑的。
(1)零檢測(Zero Detection)
在計算得到一個塊的運動矢量
后,，用Sad(vx,，vy)與Sad(0，0)做比較,。如果兩者之差小于一個參數(shù)μ,，則判定這個塊是處于靜止區(qū)域，并將所檢測到的這個運動矢量修正為零矢量,。參數(shù)μ的設(shè)定可根據(jù)實際情況進行修改,，以提高算法的適應(yīng)性。
(2)矢量濾波器（Vector Filter）
因為8×8的塊在估算運動矢量時不是很可靠,，所以,，需要使用鄰近塊的運動矢量來對計算出的運動矢量進行一定的修正，以提高運動矢量的準確性,。
以一個塊的運動矢量為中心,，加上鄰近塊的8個運動矢量，可以組成一個3×3的濾波器,。根據(jù)這個濾波器,，可以得到修正后的運動矢量
：
其中，W表示3×3的濾波器窗口,。
通過上述計算,，可以提高運動估計的搜索速度和搜索精度，有效降低出現(xiàn)局部最優(yōu)點的可能,。
2 運動估計器的電路實現(xiàn)
2.1 以改進DDA算法為基礎(chǔ)的控制策略
在幀頻提升算法中,，需要根據(jù)輸入輸出頻率確定插幀的位置以及相應(yīng)的運動補償加權(quán)系數(shù)。對于任意比例的幀頻提升(提升前后的頻率比為m/n的情況,，n>m)來說,，循環(huán)中的n-m個新幀必須均勻地插在原來的m個幀中，以此重組成n個幀,，這就需要相應(yīng)的算法來判斷插幀的位置,。對于此問題，采取的方法是直線DDA算法,。
DDA算法是以輸出頻率為分母,，輸入頻率為分子組成DDA因子c，如從50Hz到60Hz的幀頻提升,，c為50/60,，此系數(shù)由系統(tǒng)在進行對輸入格式的判定之后給出。每次累加c,，當c>1時,，則不進行幀頻變換，直接進入尺寸縮放,，并對所得的值減去1,；當c<1，則需要進行幀頻變換,。
針對本項目要求,對上述一般的DDA算法進行了改進,，當c<1時，每次得到的用作下一次累加的和均小于1,；當c>1(需要幀頻減低)時,，其和可能大于1，此時,，不累加c,，并對和直接減去1,，進行幀頻減低，幀頻減低算法為幀刪除,。由于以上算法系數(shù)為輸入輸出頻率,，因此此算法能夠準確控制任意頻率間的幀頻變換。
2.2 運動估算器的實現(xiàn)
在幀頻提升算法中,，運動估計的實現(xiàn)是整個算法實現(xiàn)的核心,。標準數(shù)字PAL制式的分辨率為720×576，也就是說,，每一幀圖像內(nèi)有6 480個8×8的像素塊,。要想在一幀的時間間隔內(nèi)（約20ms）將所有像素塊的運動矢量（MV）計算出來，并且同時將插值幀連同原始幀實時送顯,，這就要求運動估計的速度必須很快,。
運動估計器主要由三部分組成，即存儲單元,，運算單元和數(shù)據(jù)緩存單元,，如圖1。
?
存儲單元主要由一塊片外SDRAM和若干塊片內(nèi)RAM組成,。片外SDRAM用于存儲當前幀和上一幀的圖像數(shù)據(jù),，片內(nèi)RAM主要用于緩沖當前塊和搜索區(qū)的數(shù)據(jù)，采用Xilinx VirtexII 2V1500的內(nèi)置RAM充當,。
運算單元主要負責運動矢量的計算,，它由幾組處理單元（PE）、一組比較單元以及部分控制電路組成,。
數(shù)據(jù)緩存單元主要包括幀到宏像素塊轉(zhuǎn)換模塊以及一些控制電路,，它負責輸入視頻的序列緩沖，然后存入片外RAM以及將片外RAM的數(shù)據(jù)緩沖后寫入片內(nèi)RAM,。
3 實驗結(jié)果
通過上述電路設(shè)計方案,，采用Verilog硬件描述語言對本文提出的運動估計算法進行了RTL級描述，在以xc2v1500為核心的FPGA實驗平臺上驗證,，采用Xilinx ISE 6.3i中集成的工具XST進行綜合,，硬件開銷見表1。綜合估計的最高工作頻率可以達到110MHz,。假如輸入圖像幀格式為720×576,，則運動估計器處理一幀數(shù)據(jù)需要的時間
，而幀時間間隔為20ms,，為后續(xù)的插幀過程留下了足夠的處理時間,，能夠滿足系統(tǒng)實時性的要求。
為了檢驗新算法的性能，選取全搜索算法（FS）,、三步搜索算法（TSS）和四步搜索法（FSS）與本文新算法(Proposed)進行性能比對,。輸入測試源選用了yuv4:2:0（cif：352×288或sif：352×240）的視頻測試序列，共100幀,，包括了Akiyo序列(cif),、Flower Garden序列(cif)、Foreman序列(cif),、Mobile&Calendar序列(sif)和Hall monitor序列(sif)。采用在實際應(yīng)用廣泛的峰值性噪比(PSNR)作為性能指標,。PSNR的計算如下：
測試結(jié)果如表2,。
從表2可以看出，F(xiàn)S算法性能最優(yōu),。本文所介紹的算法測試序列所得平均峰值信噪比（PSNR）高于TSS和FSS算法,。
圖2顯示了三種不同的算法針對Football圖像序列的PSNR值比較。本文算法是在從硬件實現(xiàn)的基礎(chǔ)上設(shè)計提出的,，算法搜索步驟規(guī)則可重復(fù),，便于后續(xù)實現(xiàn)。
本文設(shè)計研究一種新的運動估計算法,，使用改進的三步搜索算法（ITSS）提高了運動估計的準確性,，并引入零檢測和矢量濾波器對運動矢量進行修正。同時算法也具有廣泛的適用性,適合視頻格式轉(zhuǎn)換芯片芯片級設(shè)計要求,。
參考文獻
[1] 陳航,，陳占計.基于H．264的新型快速搜索算法研究[J].電子技術(shù)應(yīng)用，2007(3).
[2] KOGA T,，IINUMA K,，HIRANO A，et al.Motion compensated interframe coding for video conferencing. In Proc.NTC81,，pp.C9.6.1-9.6.5,，New Orleans，LA,，1981.
[3] PO L M,，MA W C.A novel four-step search algorithm for?fast blockmatching.IEEE Trans. Circuits Syst.Video Technol.，1996,，6(3)：313-317.
[4] LIU L K,，F(xiàn)EIG E.A block-based gradient descent search?algorithm for block-based motion estimation in video coding. IEEE Trans.Circuits Syst.Video Technol.，1996,，6(4)：419-422.
[5] ZHU S,，MA K K.A new diamond search algorithm for fast?block matching.IEEE Trans.Circuits Syst.Video Technol.，2000，9(2)：287-290.
[6] NIE Yao,，MA Kai Kuang.Adaptive rood pattern search for?fast block-matching motion estimation[J].IEEE Trans.on?Image Processing,，2002，12(11)：1442-1449.