隨著數(shù)字電視和多媒體信息技術(shù)的發(fā)展，圖像掃描格式的種類與日俱增，要求現(xiàn)今的圖像顯示系統(tǒng)具備多制式兼容及掃描格式轉(zhuǎn)換能力。為使信號的傳輸頻帶降低，我國現(xiàn)行的電視信號為50Hz隔行PAL制式，有較明顯的視覺缺陷，例如爬行及大面積閃爍。解決上述缺陷的方法就是去隔行，并提高系統(tǒng)的幀頻^[1]。簡單的幀復(fù)制或幀平均頻率提升方法會導(dǎo)致運(yùn)動(dòng)圖像的模糊或抖動(dòng)，降低圖像的動(dòng)態(tài)分辨率，嚴(yán)重影響視頻圖像序列的主觀質(zhì)量。為了提高圖像的顯示質(zhì)量，采用運(yùn)動(dòng)補(bǔ)償?shù)膾呙桀l率轉(zhuǎn)換方法逐漸為人們所青睞，文獻(xiàn)[2～3]給出了兩種實(shí)現(xiàn)方法。運(yùn)動(dòng)補(bǔ)償頻率提升的核心就是準(zhǔn)確、高速的運(yùn)動(dòng)矢量計(jì)算。為此，本文提出了一種用于高速運(yùn)動(dòng)估計(jì)" title="運(yùn)動(dòng)估計(jì)">運(yùn)動(dòng)估計(jì)的改進(jìn)三步搜索并用FPGA實(shí)現(xiàn)了該運(yùn)動(dòng)估計(jì)器的硬件原型。
1 運(yùn)動(dòng)估計(jì)/補(bǔ)償幀頻提升原理
1.1 改進(jìn)的三步搜索
　　三步搜索(Three Step Search)具有計(jì)算簡單、性能良好等特點(diǎn)，因而在視頻系統(tǒng)中得到了廣泛的應(yīng)用^[4]。筆者根據(jù)具體的項(xiàng)目要求，在原有的TSS基礎(chǔ)上做了相應(yīng)的改進(jìn)，提出了改進(jìn)的三步搜索。
　　(1)原有的三步搜索一般都是步長折半搜索，也就是說，如果第一步的步長為4(像素)，那么第二步與第三步的步長分別為2和1。對幀頻提升而言，每兩幀之間的時(shí)間間隔非常小(約20ms), 說明兩幀之間匹配塊的運(yùn)動(dòng)矢量比較小。基于上述假設(shè)，將三步搜索中第一步的步長調(diào)整為3，其它兩步的步長保持不變，可以直接計(jì)算出新三步搜索的搜索范圍是±6。經(jīng)過上述調(diào)整，運(yùn)動(dòng)估計(jì)器明顯提升了中心點(diǎn)L₄(圖1所示)附近小運(yùn)動(dòng)的估計(jì)效果，彌補(bǔ)了原三步法因?yàn)榈谝徊讲介L過大而造成的運(yùn)動(dòng)估計(jì)精度下降。

　　(2)傳統(tǒng)三步搜索的匹配塊大小為16×16，顯然不適合精細(xì)的運(yùn)動(dòng)補(bǔ)償線性插補(bǔ)" title="插補(bǔ)">插補(bǔ)。但是，由于真實(shí)物體運(yùn)動(dòng)的一致性，過小的匹配塊會產(chǎn)生較多不正確的運(yùn)動(dòng)矢量^[5]。于是，將匹配塊的大小調(diào)整為8×8，以適應(yīng)插補(bǔ)要求。
　　新三步搜索的過程如圖1所示。每個(gè)8×8匹配塊的中心點(diǎn)定為該塊左上角的像素，搜索區(qū)(Searching Area)的大小為20×20(20＝8＋6＋6)。
　　第1步 搜索t幀搜索區(qū)內(nèi)以L₀～L₈為中心的匹配塊，用MAD(Mean Absolute Difference)函數(shù)計(jì)算塊匹配誤差BME(Block Matching Error)，得出與t＋1幀內(nèi)當(dāng)前塊最匹配的塊；
　　第2步 以第1步搜索得到的最小誤差點(diǎn)為中心，即圖中空心圓代表的位置，步長為2，搜索其周圍的8個(gè)頂點(diǎn)，計(jì)算以這8個(gè)點(diǎn)為中心的匹配塊的BME，得出與當(dāng)前塊最為匹配的塊；
　　第3步 同第2步，步長變?yōu)?。
　　經(jīng)過三步搜索后，運(yùn)動(dòng)估計(jì)器找到了當(dāng)前塊在前一幀內(nèi)的匹配塊以及用相對坐標(biāo)表示的運(yùn)動(dòng)矢量，為后續(xù)的線性插補(bǔ)做準(zhǔn)備。如圖1所示，當(dāng)前塊的運(yùn)動(dòng)矢量為{5，5}。
1.2 幀頻提升原理簡介
　　運(yùn)動(dòng)估計(jì)器計(jì)算出當(dāng)前塊的運(yùn)動(dòng)矢量后，將運(yùn)動(dòng)矢量除以2，就可得到插值" title="插值">插值幀(t＋0.5)內(nèi)與當(dāng)前塊相對應(yīng)插值塊的位置，或者說相對坐標(biāo)。如果運(yùn)動(dòng)估計(jì)足夠準(zhǔn)確，則插值幀內(nèi)所有的塊都能找到與它對應(yīng)的當(dāng)前塊，這樣，可以將插值幀插補(bǔ)出來。將插值幀連同原始幀按順序送顯，可以實(shí)現(xiàn)50Hz～100Hz的幀頻提升。插補(bǔ)的原理如圖2所示，其中A代表前一幀內(nèi)與當(dāng)前塊相匹配的塊，A’代表A在當(dāng)前幀內(nèi)的映射塊，I代表插補(bǔ)塊，B代表當(dāng)前塊。以上只是簡要說明插補(bǔ)的原理，在實(shí)際應(yīng)用中，幀頻一般不會很高，例如VGA格式的LCD顯示器，其最佳掃描頻率為75Hz。要想將逐行的50Hz數(shù)字電視信號在液晶屏上顯示，只需將幀頻提升到75Hz并調(diào)整分辨率即可。當(dāng)然，使用的插補(bǔ)方法會與前述的略有不同，由于篇幅所限，本文就不再敷述。

2 運(yùn)動(dòng)估計(jì)器的硬件實(shí)現(xiàn)
　　標(biāo)準(zhǔn)數(shù)字PAL制式的分辨率為720×576^[6]，也就是說，每一幀圖像內(nèi)有6480個(gè)8×8的像素塊。要想在一幀的間隔內(nèi)(約20ms)將所有像素塊的運(yùn)動(dòng)矢量(MV)計(jì)算出來，并將插值幀連同原始幀實(shí)時(shí)送顯，就要求運(yùn)動(dòng)估計(jì)進(jìn)行得非?？臁榱藵M足矢量計(jì)算的高速性，本文提出的運(yùn)動(dòng)估計(jì)器采用了高度并行的處理結(jié)構(gòu)。
2.1 系統(tǒng)結(jié)構(gòu)
　　該系統(tǒng)主要分為三部分，即存儲子系統(tǒng)、運(yùn)算子系統(tǒng)以及數(shù)據(jù)組織子系統(tǒng)，如圖3所示。

　　存儲子系統(tǒng)主要由1塊片外雙口RAM和若干塊片內(nèi)RAM組成。片外RAM用于存儲當(dāng)前幀和上一幀的像素?cái)?shù)據(jù)，一個(gè)端口用來接收輸入視頻流，另外一個(gè)端口用來向片內(nèi)RAM緩沖區(qū)發(fā)送數(shù)據(jù)。片內(nèi)RAM主要用于緩沖當(dāng)前塊和搜索區(qū)的數(shù)據(jù)，采用Xilinx VirtexⅡ2V1500的內(nèi)置RAM充當(dāng)，在編寫代碼時(shí)用RAMB4_S16_S16原語調(diào)用。片內(nèi)RAM又分為當(dāng)前塊片內(nèi)RAM以及搜索區(qū)(SA)片內(nèi)RAM兩大部分。地址產(chǎn)生及控制單元應(yīng)該位于存儲子系統(tǒng)內(nèi)部，但是考慮到它的重要性，便將其單獨(dú)表示。
　　運(yùn)算子系統(tǒng)即運(yùn)動(dòng)估計(jì)單元，主要負(fù)責(zé)運(yùn)動(dòng)矢量的計(jì)算。它由三組處理單元(PE)、一組比較單元以及部分控制電路組成。
　　數(shù)據(jù)組織子系統(tǒng)主要包括幀到宏像素塊轉(zhuǎn)換模塊(Frame To Macro Block)以及一些控制電路，它主要負(fù)責(zé)輸入視頻的序列緩沖，然后存入片外RAM以及將片外RAM的數(shù)據(jù)緩沖，寫入片內(nèi)RAM。
2.2 片內(nèi)RAM的組織結(jié)構(gòu)
　　用于存儲當(dāng)前塊(8×8)的片內(nèi)RAM由4塊32位RAM組成，2塊構(gòu)成1頁，共有2頁。這樣做的目的是為了在讀取第n個(gè)當(dāng)前塊送入運(yùn)動(dòng)估計(jì)單元進(jìn)行計(jì)算時(shí)，還能用另一頁RAM載入第n＋1個(gè)當(dāng)前塊的數(shù)據(jù)。這種乒乓存儲結(jié)構(gòu)大大提高了運(yùn)算速度，實(shí)現(xiàn)了時(shí)間的復(fù)用。圖4表示了1頁RAM的結(jié)構(gòu)，其中地址線3根，可以計(jì)算出1頁RAM的容量為：，剛好容納1個(gè)當(dāng)前塊。

　　用于存儲搜索區(qū)像素片內(nèi)RAM的組成結(jié)構(gòu)與當(dāng)前塊片內(nèi)RAM基本相同，不同的是用到的RAM的塊數(shù)為10塊。RAM陣列提供了足夠的數(shù)據(jù)帶寬，使運(yùn)動(dòng)估計(jì)器能自由尋址搜索區(qū)內(nèi)的一行20個(gè)像素?cái)?shù)據(jù)。
2.3 運(yùn)動(dòng)估計(jì)單元
　　運(yùn)動(dòng)估計(jì)單元是整個(gè)運(yùn)動(dòng)估計(jì)器的核心，在文獻(xiàn)[7～8]的基礎(chǔ)上，提出了24個(gè)(三組)處理單元同時(shí)并行工作的高速結(jié)構(gòu)。如圖5所示，基于這種結(jié)構(gòu)，運(yùn)動(dòng)估計(jì)單元每個(gè)時(shí)鐘周期能計(jì)算出24個(gè)差值。

　　當(dāng)數(shù)據(jù)組織子系統(tǒng)將當(dāng)前幀的前8行數(shù)據(jù)存入片外RAM后，運(yùn)動(dòng)估計(jì)單元開始工作。系統(tǒng)與時(shí)鐘的上升沿同步，T表示時(shí)鐘周期。圖6給出了運(yùn)動(dòng)估計(jì)單元的工作時(shí)序圖；圖7給出了處理單元PE的硬件結(jié)構(gòu)。

　　0～7 T 依次讀入匹配塊L₀、L₁、L₂的第0行到第7行，送入并行PE陣列；
　　8～9 T 每一個(gè)PE計(jì)算出有效結(jié)果；
　　10～12 T 樹狀加法器陣列計(jì)算出匹配塊L₀、L₁、L₂的匹配誤差BME，并送入結(jié)果緩存。
　　13～20 T 依次讀入匹配塊L₃、L₄、L₅的第0行到第7行，送入并行PE陣列；
　　21～22 T 每一個(gè)PE計(jì)算出有效結(jié)果；
　　23～25 T 樹狀加法器陣列計(jì)算出匹配塊L₃、L₄、L₅的匹配誤差BME，并送入結(jié)果緩存。
　　26～38 T 運(yùn)動(dòng)估計(jì)單元計(jì)算出匹配塊L₆、L₇、L₈的匹配誤差；
　　39～41 T 比較陣列得出新三步搜索第一步的最佳匹配塊。
　　第二步和第三步的情況與第一步類似：第83個(gè)時(shí)鐘的上升沿比較陣列求得第二步的最佳匹配塊，第125個(gè)時(shí)鐘的上升沿比較陣列求得最終的最佳匹配塊。
　　這樣，每經(jīng)過126個(gè)時(shí)鐘周期，運(yùn)動(dòng)估計(jì)器找到一個(gè)當(dāng)前塊的最佳匹配塊，并以運(yùn)動(dòng)矢量的方式將結(jié)果輸出。取主頻100MHz，處理大小為720×576的一幀圖像所用的時(shí)間是=8.1648≈8.2ms＜幀間隔20ms的一半，為后續(xù)的插幀過程留下足夠的處理時(shí)間。
3 實(shí)驗(yàn)結(jié)果
　　用Verilog硬件描述語言編寫源代碼，綜合采用Xilinx ISE 6.3i；用ModelSim做后仿真，將運(yùn)動(dòng)矢量輸出到記錄文件中；用計(jì)算機(jī)處理輸出的結(jié)果，插補(bǔ)出來的t＋0.5幀圖像效果良好。輸入采用football序列，軟硬件的結(jié)果對比如圖8、9所示。

　　本文提出了一種適用于幀頻提升的三步搜索系統(tǒng)實(shí)現(xiàn)，并用FPGA對其硬件原型驗(yàn)證。實(shí)驗(yàn)結(jié)果表明采用高速并行結(jié)構(gòu)的運(yùn)動(dòng)估計(jì)器具有速度快、精度高等優(yōu)點(diǎn)，滿足幀頻提升系統(tǒng)的要求。
參考文獻(xiàn)
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 吳 勇.數(shù)字視頻的時(shí)-空處理算法及其VLSI實(shí)現(xiàn)[J].西安交通大學(xué)博士學(xué)位論文，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)