摘 要： 提出了用于運動補償幀頻提升" title="幀頻提升">幀頻提升的改進三步搜索" title="三步搜索">三步搜索，并描述了算法的系統實現。系統具有高度并行、實時性高等優點，經過FPGA系統驗證，所處理的圖像主觀質量良好，滿足應用需要。
關鍵詞： 運動補償 幀頻提升 三步搜索
隨著數字電視和多媒體信息技術的發展，圖像掃描格式的種類與日俱增，要求現今的圖像顯示系統具備多制式兼容及掃描格式轉換能力。為使信號的傳輸頻帶降低，我國現行的電視信號為50Hz隔行PAL制式，有較明顯的視覺缺陷，例如爬行及大面積閃爍。解決上述缺陷的方法就是去隔行，并提高系統的幀頻[1]。簡單的幀復制或幀平均頻率提升方法會導致運動圖像的模糊或抖動，降低圖像的動態分辨率，嚴重影響視頻圖像序列的主觀質量。為了提高圖像的顯示質量，采用運動補償的掃描頻率轉換方法逐漸為人們所青睞，文獻[2～3]給出了兩種實現方法。運動補償頻率提升的核心就是準確、高速的運動矢量計算。為此，本文提出了一種用于高速運動估計" title="運動估計">運動估計的改進三步搜索并用FPGA實現了該運動估計器的硬件原型。
1 運動估計/補償幀頻提升原理
1.1 改進的三步搜索
三步搜索(Three Step Search)具有計算簡單、性能良好等特點，因而在視頻系統中得到了廣泛的應用[4]。筆者根據具體的項目要求，在原有的TSS基礎上做了相應的改進，提出了改進的三步搜索。
(1)原有的三步搜索一般都是步長折半搜索，也就是說，如果第一步的步長為4(像素)，那么第二步與第三步的步長分別為2和1。對幀頻提升而言，每兩幀之間的時間間隔非常小(約20ms), 說明兩幀之間匹配塊的運動矢量比較小。基于上述假設，將三步搜索中第一步的步長調整為3，其它兩步的步長保持不變，可以直接計算出新三步搜索的搜索范圍是±6。經過上述調整，運動估計器明顯提升了中心點L4(圖1所示)附近小運動的估計效果，彌補了原三步法因為第一步步長過大而造成的運動估計精度下降。
(2)傳統三步搜索的匹配塊大小為16×16，顯然不適合精細的運動補償線性插補" title="插補">插補。但是，由于真實物體運動的一致性，過小的匹配塊會產生較多不正確的運動矢量[5]。于是，將匹配塊的大小調整為8×8，以適應插補要求。
新三步搜索的過程如圖1所示。每個8×8匹配塊的中心點定為該塊左上角的像素，搜索區(Searching Area)的大小為20×20(20＝8＋6＋6)。
第1步 搜索t幀搜索區內以L0～L8為中心的匹配塊，用MAD(Mean Absolute Difference)函數計算塊匹配誤差BME(Block Matching Error)，得出與t＋1幀內當前塊最匹配的塊；
第2步 以第1步搜索得到的最小誤差點為中心，即圖中空心圓代表的位置，步長為2，搜索其周圍的8個頂點，計算以這8個點為中心的匹配塊的BME，得出與當前塊最為匹配的塊；
第3步 同第2步，步長變為1。
經過三步搜索后，運動估計器找到了當前塊在前一幀內的匹配塊以及用相對坐標表示的運動矢量，為后續的線性插補做準備。如圖1所示，當前塊的運動矢量為{5，5}。
1.2 幀頻提升原理簡介
運動估計器計算出當前塊的運動矢量后，將運動矢量除以2，就可得到插值" title="插值">插值幀(t＋0.5)內與當前塊相對應插值塊的位置，或者說相對坐標。如果運動估計足夠準確，則插值幀內所有的塊都能找到與它對應的當前塊，這樣，可以將插值幀插補出來。將插值幀連同原始幀按順序送顯，可以實現50Hz～100Hz的幀頻提升。插補的原理如圖2所示，其中A代表前一幀內與當前塊相匹配的塊，A’代表A在當前幀內的映射塊，I代表插補塊，B代表當前塊。以上只是簡要說明插補的原理，在實際應用中，幀頻一般不會很高，例如VGA格式的LCD顯示器，其最佳掃描頻率為75Hz。要想將逐行的50Hz數字電視信號在液晶屏上顯示，只需將幀頻提升到75Hz并調整分辨率即可。當然，使用的插補方法會與前述的略有不同，由于篇幅所限，本文就不再敷述。
2 運動估計器的硬件實現
標準數字PAL制式的分辨率為720×576[6]，也就是說，每一幀圖像內有6480個8×8的像素塊。要想在一幀的間隔內(約20ms)將所有像素塊的運動矢量(MV)計算出來，并將插值幀連同原始幀實時送顯，就要求運動估計進行得非常快。為了滿足矢量計算的高速性，本文提出的運動估計器采用了高度并行的處理結構。
2.1 系統結構
該系統主要分為三部分，即存儲子系統、運算子系統以及數據組織子系統，如圖3所示。
存儲子系統主要由1塊片外雙口RAM和若干塊片內RAM組成。片外RAM用于存儲當前幀和上一幀的像素數據，一個端口用來接收輸入視頻流，另外一個端口用來向片內RAM緩沖區發送數據。片內RAM主要用于緩沖當前塊和搜索區的數據，采用Xilinx VirtexⅡ2V1500的內置RAM充當，在編寫代碼時用RAMB4_S16_S16原語調用。片內RAM又分為當前塊片內RAM以及搜索區(SA)片內RAM兩大部分。地址產生及控制單元應該位于存儲子系統內部，但是考慮到它的重要性，便將其單獨表示。
運算子系統即運動估計單元，主要負責運動矢量的計算。它由三組處理單元(PE)、一組比較單元以及部分控制電路組成。
數據組織子系統主要包括幀到宏像素塊轉換模塊(Frame To Macro Block)以及一些控制電路，它主要負責輸入視頻的序列緩沖，然后存入片外RAM以及將片外RAM的數據緩沖，寫入片內RAM。
2.2 片內RAM的組織結構
用于存儲當前塊(8×8)的片內RAM由4塊32位RAM組成，2塊構成1頁，共有2頁。這樣做的目的是為了在讀取第n個當前塊送入運動估計單元進行計算時，還能用另一頁RAM載入第n＋1個當前塊的數據。這種乒乓存儲結構大大提高了運算速度，實現了時間的復用。圖4表示了1頁RAM的結構，其中地址線3根，可以計算出1頁RAM的容量為：
，剛好容納1個當前塊。
用于存儲搜索區像素片內RAM的組成結構與當前塊片內RAM基本相同，不同的是用到的RAM的塊數為10塊。RAM陣列提供了足夠的數據帶寬，使運動估計器能自由尋址搜索區內的一行20個像素數據。
2.3 運動估計單元
運動估計單元是整個運動估計器的核心，在文獻[7～8]的基礎上，提出了24個(三組)處理單元同時并行工作的高速結構。如圖5所示，基于這種結構，運動估計單元每個時鐘周期能計算出24個差值。
當數據組織子系統將當前幀的前8行數據存入片外RAM后，運動估計單元開始工作。系統與時鐘的上升沿同步，T表示時鐘周期。圖6給出了運動估計單元的工作時序圖；圖7給出了處理單元PE的硬件結構。
0～7 T 依次讀入匹配塊L0、L1、L2的第0行到第7行，送入并行PE陣列；
8～9 T 每一個PE計算出有效結果；
10～12 T 樹狀加法器陣列計算出匹配塊L0、L1、L2的匹配誤差BME，并送入結果緩存。
13～20 T 依次讀入匹配塊L3、L4、L5的第0行到第7行，送入并行PE陣列；
21～22 T 每一個PE計算出有效結果；
23～25 T 樹狀加法器陣列計算出匹配塊L3、L4、L5的匹配誤差BME，并送入結果緩存。
26～38 T 運動估計單元計算出匹配塊L6、L7、L8的匹配誤差；
39～41 T 比較陣列得出新三步搜索第一步的最佳匹配塊。
第二步和第三步的情況與第一步類似：第83個時鐘的上升沿比較陣列求得第二步的最佳匹配塊，第125個時鐘的上升沿比較陣列求得最終的最佳匹配塊。
這樣，每經過126個時鐘周期，運動估計器找到一個當前塊的最佳匹配塊，并以運動矢量的方式將結果輸出。取主頻100MHz，處理大小為720×576的一幀圖像所用的時間是
=8.1648≈8.2ms＜幀間隔20ms的一半，為后續的插幀過程留下足夠的處理時間。
3 實驗結果
用Verilog硬件描述語言編寫源代碼，綜合采用Xilinx ISE 6.3i；用ModelSim做后仿真，將運動矢量輸出到記錄文件中；用計算機處理輸出的結果，插補出來的t＋0.5幀圖像效果良好。輸入采用football序列，軟硬件的結果對比如圖8、9所示。
本文提出了一種適用于幀頻提升的三步搜索系統實現，并用FPGA對其硬件原型驗證。實驗結果表明采用高速并行結構的運動估計器具有速度快、精度高等優點，滿足幀頻提升系統的要求。
參考文獻
1 C. Hentchel. Linear and nonlinear procedures for flicker reduction. [J]in IEEE Trans. Consumer Electron., 1987;CE-33(8)192～198
2 T. Reuter. Improved TV standards conversion with 3-dimen-sional motion compensating interpolation filter. [J]in Proc.Club de Rennes Young TV Researchers Conf.[C],Cambridge, MA, Oct. 1988
3 D. P. Siohan, B.Choquet.Field-rate conversion by motion estimation/compensation.[J]in Signal Processing of HDTV, L.Chiariglione,Ed.Amsterdam: Elsevier, 1988:319～328
4 H. M. Jong,L. G. Chen,T. D. Chiueh. Performance improvements and cost reductions of the 3-step block-matching algorithm.[J]in IEEE Trans.Circ. and Syst.for Video Technol
5 吳 勇.數字視頻的時-空處理算法及其VLSI實現[J].西安交通大學博士學位論文，2002;0401
6 Roberto Castagno, Petri Haavisto, G. Ramponi.A method for motion adaptive frame rate up-conversion.[J]in IEEE Trans-actions on Circuits and Systems for Video Technology, Oct 1996;6(5)
7 H. M. Jong,L. G. Chen,T. D. Chiueh. Parallel architecture for 3-step hierarchical search block-matching algorithm. [J]in IEEE Trans. Circ. and Syst. for Video Technol.Aug.1994;4(4)
8 G. Gupta and C. Chakrabatri. Architectures for hierarchical and other block matching algorithms.[J]in IEEE Trans.Circ. and Syst. for Video Technol.Dec. 1995;5(6)