摘 要： 針對(duì)格式轉(zhuǎn)換領(lǐng)域，提出一種全新的運(yùn)動(dòng)估計(jì)算法。該算法通過使用改進(jìn)的三步搜索算法（TSS）進(jìn)行運(yùn)動(dòng)估計(jì)，并引入零檢測(cè)和矢量濾波器對(duì)運(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)換芯片；幀頻提升；塊匹配

?

　　在視頻信號(hào)中，當(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ù)測(cè)得越準(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ì)，并引入零檢測(cè)和矢量濾波器對(duì)運(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)，平均絕對(duì)差MAD(Mean Absolute Difference)和絕對(duì)差之和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。對(duì)視頻系統(tǒng)中的幀頻提升來說，每兩幀之間的時(shí)間間隔非常小(約20ms)，說明兩幀之間匹配塊的運(yùn)動(dòng)矢量相對(duì)較小?；谶@個(gè)假設(shè)，將三步搜索中三步步長調(diào)整為3、2和1，這樣搜索范圍為±6。經(jīng)過調(diào)整，運(yùn)動(dòng)估計(jì)的運(yùn)動(dòng)估計(jì)精度得到了一定提高。
　　當(dāng)用塊匹配算法對(duì)小尺寸塊進(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)零檢測(cè)(Zero Detection)
　　在計(jì)算得到一個(gè)塊的運(yùn)動(dòng)矢量后，用S_ad(v_x，v_y)與S_ad(0，0)做比較。如果兩者之差小于一個(gè)參數(shù)μ，則判定這個(gè)塊是處于靜止區(qū)域，并將所檢測(cè)到的這個(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)矢量來對(duì)計(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ù)。對(duì)于任意比例的幀頻提升(提升前后的頻率比為m/n的情況，n>m)來說，循環(huán)中的n-m個(gè)新幀必須均勻地插在原來的m個(gè)幀中，以此重組成n個(gè)幀，這就需要相應(yīng)的算法來判斷插幀的位置。對(duì)于此問題，采取的方法是直線DDA算法。
　　DDA算法是以輸出頻率為分母，輸入頻率為分子組成DDA因子c，如從50Hz到60Hz的幀頻提升，c為50/60，此系數(shù)由系統(tǒng)在進(jìn)行對(duì)輸入格式的判定之后給出。每次累加c，當(dāng)c>1時(shí)，則不進(jìn)行幀頻變換，直接進(jìn)入尺寸縮放，并對(duì)所得的值減去1；當(dāng)c<1，則需要進(jìn)行幀頻變換。
　　針對(duì)本項(xiàng)目要求,對(duì)上述一般的DDA算法進(jìn)行了改進(jìn)，當(dāng)c<1時(shí)，每次得到的用作下一次累加的和均小于1；當(dāng)c>1(需要幀頻減低)時(shí)，其和可能大于1，此時(shí)，不累加c，并對(duì)和直接減去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。

?