隨著數(shù)字電視和多媒體信息技術(shù)的發(fā)展,，圖像掃描格式的種類與日俱增,，要求現(xiàn)今的圖像顯示系統(tǒng)具備多制式兼容及掃描格式轉(zhuǎn)換能力,。為使信號(hào)的傳輸頻帶降低，我國(guó)現(xiàn)行的電視信號(hào)為50Hz隔行PAL制式,，有較明顯的視覺(jué)缺陷,，例如爬行及大面積閃爍。解決上述缺陷的方法就是去隔行,，并提高系統(tǒng)的幀頻^[1],。簡(jiǎn)單的幀復(fù)制或幀平均頻率提升方法會(huì)導(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ì)算簡(jiǎn)單、性能良好等特點(diǎn),，因而在視頻系統(tǒng)中得到了廣泛的應(yīng)用^[4],。筆者根據(jù)具體的項(xiàng)目要求，在原有的TSS基礎(chǔ)上做了相應(yīng)的改進(jìn),，提出了改進(jìn)的三步搜索,。
　　(1)原有的三步搜索一般都是步長(zhǎng)折半搜索，也就是說(shuō),，如果第一步的步長(zhǎng)為4(像素),，那么第二步與第三步的步長(zhǎng)分別為2和1。對(duì)幀頻提升而言,，每?jī)蓭g的時(shí)間間隔非常小(約20ms), 說(shuō)明兩幀之間匹配塊的運(yùn)動(dòng)矢量比較小,。基于上述假設(shè),，將三步搜索中第一步的步長(zhǎng)調(diào)整為3,，其它兩步的步長(zhǎng)保持不變，可以直接計(jì)算出新三步搜索的搜索范圍是±6,。經(jīng)過(guò)上述調(diào)整,，運(yùn)動(dòng)估計(jì)器明顯提升了中心點(diǎn)L₄(圖1所示)附近小運(yùn)動(dòng)的估計(jì)效果，彌補(bǔ)了原三步法因?yàn)榈谝徊讲介L(zhǎng)過(guò)大而造成的運(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)的一致性,，過(guò)小的匹配塊會(huì)產(chǎn)生較多不正確的運(yùn)動(dòng)矢量^[5]。于是,，將匹配塊的大小調(diào)整為8×8,，以適應(yīng)插補(bǔ)要求,。
　　新三步搜索的過(guò)程如圖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)為中心,，即圖中空心圓代表的位置,，步長(zhǎng)為2，搜索其周圍的8個(gè)頂點(diǎn),，計(jì)算以這8個(gè)點(diǎn)為中心的匹配塊的BME,，得出與當(dāng)前塊最為匹配的塊；
　　第3步 同第2步,，步長(zhǎng)變?yōu)?,。
　　經(jīng)過(guò)三步搜索后，運(yùn)動(dòng)估計(jì)器找到了當(dāng)前塊在前一幀內(nèi)的匹配塊以及用相對(duì)坐標(biāo)表示的運(yùn)動(dòng)矢量,，為后續(xù)的線性插補(bǔ)做準(zhǔn)備,。如圖1所示，當(dāng)前塊的運(yùn)動(dòng)矢量為{5,，5},。
1.2 幀頻提升原理簡(jiǎn)介
　　運(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)前塊相對(duì)應(yīng)插值塊的位置,，或者說(shuō)相對(duì)坐標(biāo)。如果運(yùn)動(dòng)估計(jì)足夠準(zhǔn)確,，則插值幀內(nèi)所有的塊都能找到與它對(duì)應(yīng)的當(dāng)前塊,，這樣，可以將插值幀插補(bǔ)出來(lái),。將插值幀連同原始幀按順序送顯,，可以實(shí)現(xiàn)50Hz～100Hz的幀頻提升。插補(bǔ)的原理如圖2所示,，其中A代表前一幀內(nèi)與當(dāng)前塊相匹配的塊,，A’代表A在當(dāng)前幀內(nèi)的映射塊，I代表插補(bǔ)塊,，B代表當(dāng)前塊,。以上只是簡(jiǎn)要說(shuō)明插補(bǔ)的原理，在實(shí)際應(yīng)用中,，幀頻一般不會(huì)很高,，例如VGA格式的LCD顯示器，其最佳掃描頻率為75Hz,。要想將逐行的50Hz數(shù)字電視信號(hào)在液晶屏上顯示,，只需將幀頻提升到75Hz并調(diào)整分辨率即可。當(dāng)然,，使用的插補(bǔ)方法會(huì)與前述的略有不同,，由于篇幅所限，本文就不再敷述,。

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

　　存儲(chǔ)子系統(tǒng)主要由1塊片外雙口RAM和若干塊片內(nèi)RAM組成,。片外RAM用于存儲(chǔ)當(dāng)前幀和上一幀的像素?cái)?shù)據(jù)，一個(gè)端口用來(lái)接收輸入視頻流,，另外一個(gè)端口用來(lái)向片內(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原語(yǔ)調(diào)用,。片內(nèi)RAM又分為當(dāng)前塊片內(nèi)RAM以及搜索區(qū)(SA)片內(nèi)RAM兩大部分。地址產(chǎn)生及控制單元應(yīng)該位于存儲(chǔ)子系統(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)
　　用于存儲(chǔ)當(dāng)前塊(8×8)的片內(nèi)RAM由4塊32位RAM組成，2塊構(gòu)成1頁(yè),，共有2頁(yè),。這樣做的目的是為了在讀取第n個(gè)當(dāng)前塊送入運(yùn)動(dòng)估計(jì)單元進(jìn)行計(jì)算時(shí)，還能用另一頁(yè)RAM載入第n＋1個(gè)當(dāng)前塊的數(shù)據(jù),。這種乒乓存儲(chǔ)結(jié)構(gòu)大大提高了運(yùn)算速度,，實(shí)現(xiàn)了時(shí)間的復(fù)用,。圖4表示了1頁(yè)RAM的結(jié)構(gòu),，其中地址線3根,，可以計(jì)算出1頁(yè)RAM的容量為：，剛好容納1個(gè)當(dāng)前塊,。

　　用于存儲(chǔ)搜索區(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ì)單元開(kāi)始工作,。系統(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 樹(shù)狀加法器陣列計(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 樹(shù)狀加法器陣列計(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)過(guò)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ù)的插幀過(guò)程留下足夠的處理時(shí)間,。
3 實(shí)驗(yàn)結(jié)果
　　用Verilog硬件描述語(yǔ)言編寫源代碼，綜合采用Xilinx ISE 6.3i,；用ModelSim做后仿真,，將運(yùn)動(dòng)矢量輸出到記錄文件中；用計(jì)算機(jī)處理輸出的結(jié)果,，插補(bǔ)出來(lái)的t＋0.5幀圖像效果良好,。輸入采用football序列，軟硬件的結(jié)果對(duì)比如圖8,、9所示,。

　　本文提出了一種適用于幀頻提升的三步搜索系統(tǒng)實(shí)現(xiàn)，并用FPGA對(duì)其硬件原型驗(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)