基于塊匹配的運動估計的改進算法

1、基于塊匹配的運動估計的改進算法論文導讀：運動估計是視頻處理系統(tǒng)的一個重要的組成部分。下面是綜合運用多個提升搜索速度的途徑得到兼有各類快速算法優(yōu)點的混合快速算法。關鍵詞：運動估計，快速搜索算法，混合快速算法運動估計是視頻處理系統(tǒng)的一個重要的組成部分，它是降低視頻信號時間冗余的最基本和最重要的方法之一，運動矢量的準確性直接影響整個編碼系統(tǒng)的，并對最終視頻系統(tǒng)的質(zhì)量和實時性有很大關系。因此需要綜合考慮運動估計準確度和計算復雜度的關系，得到它們之間的折中點也成為了視頻壓縮編碼領域的一個研究熱點課題。1 運動估計原理運動估計的基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并假設宏塊內(nèi)所有的像素的位

2、移量都相同，然后對于當前幀中的每一塊在前一幀或后一幀的某一給定搜索范圍內(nèi)根據(jù)一定的匹配準則找出與當前塊最相似的塊，即匹配塊。由匹配塊與當前塊的相對位置計算出運動位移，所得的運動位移即為當前塊的運動矢量（Motion Vector）。利用搜索到的運動矢量在參考幀上進行運動補償，補償殘差經(jīng)過DCT變化、量化、行程編碼后與運動矢量共同經(jīng)熵編碼，然后以比特流形式傳出去?？炱ヅ浞ㄊ乾F(xiàn)在最基本的運動估計法。2 典型估計算法及優(yōu)缺點下面介紹一下常見的典型的快匹配算法。全搜索算法FS(Full Search)1 是按一定的順序計算出搜索窗口(以當前宏塊位置(0,0)為中心的S個像素的搜索范圍)內(nèi)每一個點的求和

3、絕對誤差值SAD（Sum of Absolute Difference），找出SAD最小的點所在的位置的算法。FS 算法簡單、可靠，搜索效果好，且能夠得到全局最優(yōu)的結果，通常是其他算法性能比較的標準，但它計算量相當大，也是最耗時，這就限制了在需要實時壓縮場合的應用，所以有必要進一步研究改進算法。三步搜索法TSS(Three Step Search)2 總共進行三步搜索，它基本上保持了FS的性能，逐步減小搜索步長。每次搜索都是以上一步的搜索結果為中心，搜索步長為上一步步長的一半，搜索精度為1個像素。TSS算法是一種由粗到精的搜索算法，快速而且高效，其計算量只有FS的10%左右，是塊匹配運動估計的

4、一種典型的快速算法，但這種搜索不能保證整體最小點，只能求得局部的SAD 最小點。較適合對小運動的估計性能。二維對數(shù)搜索法TDLS(Two-Dimension Logarithmic Search)是第一個利用象限劃分搜索區(qū)域的快速匹配算法。算法的中心思想是，由每一步搜索的結果，確定下一步的搜索所在的象限范圍，并動態(tài)地變化搜索的步長，最終找到相應的最佳匹配位置。TDLS的性能比TSS略差一點，但速度快了許多。由于該算法的前提是假設搜索區(qū)內(nèi)只有一個谷點，搜索過程中可能進入其中一個非最佳匹配的谷點而誤認為其是最佳匹配點，就停止搜索，陷入局部最小點。共軛方向搜索法CDS (Conjugate Dire

5、ctiona1 Search)3，它是先在一個方向(設為X軸方向)進行搜索，固定Y軸方向對橫向的所有點進行逐一匹配，按SAD最小的原則得到一個點；然后保持X不變，在Y軸方向搜索所有點，得到最佳匹配點。這種算法簡單，實現(xiàn)容易。但由于只對兩個方向進行了搜索得到的匹配點可能與真正的最佳匹配點有差距，其性能略低于TSS，運算時間也略長于TSS。四步搜索法FSS (Four Step Search) 是對新三步搜索法NTSS(New Three Step Search)的改進，算法的中心思想是，每一步的搜索范圍由上一步的最佳匹配位置決定，前三步的搜索是定步長搜索，最后一步改變步長，得到最后的最佳匹配位置

6、。這種算法依賴最佳匹配像素點的唯一性及其周圍的單調(diào)性，計算復雜度低，可以明顯減少匹配的計算量，性能比TSS算法更好，與NTSS算法相似。菱形搜索算法DS(Diamond Search)采用的大菱形搜索模板LDSP和小菱形搜索模板SDSP。在進行搜索時，先用大菱形模板進行搜索，如果最佳匹配點不是大菱形的中心點，則以當前最佳匹配點為中心繼續(xù)進行大菱形模板搜索，直至最佳匹配點為當前大菱形的中心點為止，轉為小菱形搜索。DS是一個優(yōu)秀的算法，是依據(jù)一般物體在水平方向和垂直方向上運動的概率比較大的特性設計模板，能在較大的范圍內(nèi)能維持較快的搜索速度和較高的搜索精度。但對于實際運動矢量較大(全局最小值偏離搜索區(qū)中心)而塊匹配誤差平面在近中心區(qū)域存在局部最小值的塊，該算法不能求出正確的運動矢量，而且偏離正確運動矢量的位移較大。3 改進方法前面介紹了各種典型算法，這些算法都有各自的優(yōu)缺點，但如果我們能取長補短，再結合視頻圖象本身的一些特性，就能有新的，較實用的算法的出現(xiàn)。3.1 圖象特性圖象的基于中心傾向分布特性指一般物體在水平和垂直方向上運動的概率比較大。在各向同性分布搜索法中，可以在搜索開始時，對水平和垂直方向上進行菱形的粗搜索。對于典型的匹配模型根據(jù)中心傾向特性加強在水平和垂直方向的搜索后形成偏水平十字模型，偏垂直十字模型，偏向鉆石模型等