摘 要： 針對格式轉(zhuǎn)換領(lǐng)域,，提出一種全新的運(yùn)動(dòng)估計(jì)算法,。該算法通過使用改進(jìn)的三步搜索算法（TSS）進(jìn)行運(yùn)動(dòng)估計(jì)，并引入零檢測和矢量濾波器對運(yùn)動(dòng)矢量進(jìn)行修正,。硬件實(shí)現(xiàn)結(jié)構(gòu)基于數(shù)字微分分析DDA算法,，通過FPGA系統(tǒng)驗(yàn)證證明算法有效，設(shè)計(jì)可行,。
　　關(guān)鍵詞： 視頻格式轉(zhuǎn)換芯片,；幀頻提升；塊匹配

?

　　在視頻信號中,，當(dāng)場景中有快速運(yùn)動(dòng)物體存在時(shí),，必須事先估計(jì)場景中運(yùn)動(dòng)物體的位移量，即進(jìn)行運(yùn)動(dòng)位移估值,。得到運(yùn)動(dòng)位移的過程稱為運(yùn)動(dòng)估計(jì),，通過運(yùn)動(dòng)估計(jì)可以去除幀間冗余度，使得視頻傳輸?shù)谋忍財(cái)?shù)大為減少,。運(yùn)動(dòng)估計(jì)是視頻編碼中的核心技術(shù),，運(yùn)動(dòng)估計(jì)的好壞直接影響到編碼的效率和圖像恢復(fù)的質(zhì)量。
　　目前在視頻編碼領(lǐng)域使用的運(yùn)動(dòng)估計(jì)算法有塊匹配,、像素遞歸法,、相位相關(guān)法，其中塊匹配運(yùn)動(dòng)估計(jì)算法(BMA)是消除視頻數(shù)據(jù)時(shí)間冗余最基本且最重要的方法,。由于其具有簡單高效,、額外開銷小、易于硬件實(shí)現(xiàn)等優(yōu)點(diǎn)而被包括H.26X,、MPEG.1,，MPEG.2和MPEG-4在內(nèi)的絕大多數(shù)視頻編碼標(biāo)準(zhǔn)所采用^[1]。塊匹配的基本思想就是將每一幀圖像分成大小相同,、互不重疊的子塊(宏塊),，然后在參考幀中固定大小的搜索窗口內(nèi)找到最佳匹配塊。按照一種塊損失度量準(zhǔn)則找到的最佳匹配塊到當(dāng)前塊的位移,，用運(yùn)動(dòng)矢量來描述,。最佳匹配塊與當(dāng)前塊之間的差值稱為殘差。預(yù)測得越準(zhǔn)確，意味著殘差中的數(shù)值越小,，編碼后的比特?cái)?shù)也就越小,。
　　如何快速而準(zhǔn)確地在參考幀中搜索到最佳的匹配塊是塊匹配算法的核心。在本文研究的格式轉(zhuǎn)換領(lǐng)域,，運(yùn)動(dòng)估計(jì)注重物體的真實(shí)運(yùn)動(dòng)軌跡,，不存在估算誤差的反饋補(bǔ)償，要求得到的運(yùn)動(dòng)矢量足夠準(zhǔn)確,，能反映物體的真實(shí)運(yùn)動(dòng),。另外，由于格式轉(zhuǎn)換應(yīng)用的實(shí)時(shí)性,，要求算法盡量簡潔,，以易于硬件實(shí)現(xiàn)。因此本文使用改進(jìn)的三步搜索算法（ITSS）進(jìn)行運(yùn)動(dòng)估計(jì),，并引入零檢測和矢量濾波器對運(yùn)動(dòng)矢量進(jìn)行修正,。硬件實(shí)現(xiàn)結(jié)構(gòu)基于數(shù)字微分分析DDA(Digital Differential Analyzer)算法，并用FPGA實(shí)現(xiàn)硬件原型,。
1 基于塊匹配的運(yùn)動(dòng)估計(jì)算法
　　在參考幀中尋找匹配塊時(shí)，需要定義最佳匹配的搜索判據(jù),。最佳匹配的搜索判據(jù)有以下幾種：相關(guān)函數(shù)CCF(Cross-Correlation Function),，均方誤差MSE（Mean-Square Error)，平均絕對差MAD(Mean Absolute Difference)和絕對差之和SAD(Sum of Absolute Difference),。在實(shí)際應(yīng)用中,，由于SAD函數(shù)簡單（不含乘除法），便于硬件實(shí)現(xiàn),，而且具有令人滿意的性能,，因此在本設(shè)計(jì)中也采用這種算法。公式為：
　　　

　　其中,，(x,，y)是指參考幀中當(dāng)前塊的中心點(diǎn)(每個(gè)8×8匹配塊的中心點(diǎn)定為該塊左上角的像素），f_n+1(x+i,，y+j)是指參考幀中當(dāng)前塊的像素值,，f_n-1(x+i+vx，y+j+vy)則是指前一幀搜索中候選匹配塊的像素值,。
　　根據(jù)上面最佳匹配的搜索判據(jù),，可得出參考幀中每一個(gè)塊的運(yùn)動(dòng)矢量：
　　　　

　　其中，S表示運(yùn)動(dòng)估計(jì)的搜索范圍,。
　　有了判斷最優(yōu)匹配點(diǎn)的準(zhǔn)則,，剩下的問題就是確定尋找最優(yōu)匹配點(diǎn)的收縮方法。在目前的塊匹配算法中，全搜索法(FS)具有最高的搜索精度,，但其運(yùn)算量大,、實(shí)時(shí)性差。研究者們提出了多種快速搜索算法,，較有代表性的有三步搜索法(TSS)^[2],、四步搜索法(FSS)^[3]、梯度下降法(BBGDS)^[4],、菱形搜索法(DS)^[5],、自適應(yīng)十字模板搜索算法(ARPS)^[6]等。其中三步搜索具有計(jì)算簡單,、性能良好等優(yōu)點(diǎn),，因而在視頻系統(tǒng)中得到了廣泛的應(yīng)用。本文在研究運(yùn)動(dòng)估計(jì)的特點(diǎn)以及三步搜索算法的基礎(chǔ)上,，提出了一種改進(jìn)的三步搜索算法（ITSS）,。
　　(1)傳統(tǒng)三步搜索的匹配塊大小為16×16，這顯然不適用于精細(xì)的運(yùn)動(dòng)補(bǔ)償線性插補(bǔ),。但是,，由于真實(shí)物體運(yùn)動(dòng)的一致性，過小的匹配塊會(huì)產(chǎn)生較多不正確的運(yùn)動(dòng)矢量,。于是,，將匹配塊的大小調(diào)整為8×8 以適應(yīng)插補(bǔ)要求。
　　(2)原有的三步搜索一般都是步長折半搜索,，也就是說,，如果第一步的補(bǔ)償為4(像素)，則第二步與第三步的補(bǔ)償分別為2和1,。對視頻系統(tǒng)中的幀頻提升來說,，每兩幀之間的時(shí)間間隔非常小(約20ms)，說明兩幀之間匹配塊的運(yùn)動(dòng)矢量相對較小,?；谶@個(gè)假設(shè)，將三步搜索中三步步長調(diào)整為3,、2和1,，這樣搜索范圍為±6。經(jīng)過調(diào)整,，運(yùn)動(dòng)估計(jì)的運(yùn)動(dòng)估計(jì)精度得到了一定提高,。
　　當(dāng)用塊匹配算法對小尺寸塊進(jìn)行運(yùn)動(dòng)矢量估計(jì)時(shí)，常易產(chǎn)生錯(cuò)誤的運(yùn)動(dòng)矢量,。例如,，有時(shí)即使塊處于靜止區(qū)域,，而得到的運(yùn)動(dòng)矢量卻不為零。因此,，本文引入了兩種運(yùn)動(dòng)矢量修正技術(shù)來提高運(yùn)動(dòng)矢量的準(zhǔn)確性,。運(yùn)動(dòng)矢量修正技術(shù)是基于一個(gè)假設(shè)，即時(shí)-空域是平滑的,。
　　(1)零檢測(Zero Detection)
　　在計(jì)算得到一個(gè)塊的運(yùn)動(dòng)矢量后,，用S_ad(v_x，v_y)與S_ad(0,，0)做比較,。如果兩者之差小于一個(gè)參數(shù)μ，則判定這個(gè)塊是處于靜止區(qū)域,，并將所檢測到的這個(gè)運(yùn)動(dòng)矢量修正為零矢量,。參數(shù)μ的設(shè)定可根據(jù)實(shí)際情況進(jìn)行修改，以提高算法的適應(yīng)性,。
　　(2)矢量濾波器（Vector Filter）
　　因?yàn)?×8的塊在估算運(yùn)動(dòng)矢量時(shí)不是很可靠,，所以，需要使用鄰近塊的運(yùn)動(dòng)矢量來對計(jì)算出的運(yùn)動(dòng)矢量進(jìn)行一定的修正,，以提高運(yùn)動(dòng)矢量的準(zhǔn)確性,。
　　以一個(gè)塊的運(yùn)動(dòng)矢量為中心，加上鄰近塊的8個(gè)運(yùn)動(dòng)矢量,，可以組成一個(gè)3×3的濾波器,。根據(jù)這個(gè)濾波器，可以得到修正后的運(yùn)動(dòng)矢量：
　　
　　其中,，W表示3×3的濾波器窗口,。
　　通過上述計(jì)算,，可以提高運(yùn)動(dòng)估計(jì)的搜索速度和搜索精度,，有效降低出現(xiàn)局部最優(yōu)點(diǎn)的可能。
2 運(yùn)動(dòng)估計(jì)器的電路實(shí)現(xiàn)
2.1 以改進(jìn)DDA算法為基礎(chǔ)的控制策略
　　在幀頻提升算法中,，需要根據(jù)輸入輸出頻率確定插幀的位置以及相應(yīng)的運(yùn)動(dòng)補(bǔ)償加權(quán)系數(shù),。對于任意比例的幀頻提升(提升前后的頻率比為m/n的情況，n>m)來說,，循環(huán)中的n-m個(gè)新幀必須均勻地插在原來的m個(gè)幀中,，以此重組成n個(gè)幀，這就需要相應(yīng)的算法來判斷插幀的位置,。對于此問題,，采取的方法是直線DDA算法。
　　DDA算法是以輸出頻率為分母,，輸入頻率為分子組成DDA因子c,，如從50Hz到60Hz的幀頻提升,，c為50/60，此系數(shù)由系統(tǒng)在進(jìn)行對輸入格式的判定之后給出,。每次累加c,，當(dāng)c>1時(shí)，則不進(jìn)行幀頻變換,，直接進(jìn)入尺寸縮放,，并對所得的值減去1；當(dāng)c<1,，則需要進(jìn)行幀頻變換,。
　　針對本項(xiàng)目要求,對上述一般的DDA算法進(jìn)行了改進(jìn)，當(dāng)c<1時(shí),，每次得到的用作下一次累加的和均小于1,；當(dāng)c>1(需要幀頻減低)時(shí)，其和可能大于1,，此時(shí),，不累加c，并對和直接減去1,，進(jìn)行幀頻減低,，幀頻減低算法為幀刪除。由于以上算法系數(shù)為輸入輸出頻率,，因此此算法能夠準(zhǔn)確控制任意頻率間的幀頻變換,。
2.2 運(yùn)動(dòng)估算器的實(shí)現(xiàn)
　　在幀頻提升算法中，運(yùn)動(dòng)估計(jì)的實(shí)現(xiàn)是整個(gè)算法實(shí)現(xiàn)的核心,。標(biāo)準(zhǔn)數(shù)字PAL制式的分辨率為720×576,，也就是說，每一幀圖像內(nèi)有6 480個(gè)8×8的像素塊,。要想在一幀的時(shí)間間隔內(nèi)（約20ms）將所有像素塊的運(yùn)動(dòng)矢量（MV）計(jì)算出來,，并且同時(shí)將插值幀連同原始幀實(shí)時(shí)送顯，這就要求運(yùn)動(dòng)估計(jì)的速度必須很快,。
　　運(yùn)動(dòng)估計(jì)器主要由三部分組成,，即存儲(chǔ)單元，運(yùn)算單元和數(shù)據(jù)緩存單元,，如圖1,。

?