摘 要： 針對格式轉換領域，提出一種全新的運動估計算法。該算法通過使用改進的三步搜索算法（TSS）進行運動估計，并引入零檢測和矢量濾波器對運動矢量進行修正。硬件實現結構基于數字微分分析DDA算法，通過FPGA系統驗證證明算法有效，設計可行。
　　關鍵詞： 視頻格式轉換芯片；幀頻提升；塊匹配

?

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

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

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

?