導語：小議運動搜索算法的發展及運用一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要：隨著視頻壓縮技術的發展以及人們對大尺寸、高質量圖像日益增長的需求，視頻壓縮算法已成為當前視頻技術發展研究的熱點，而搜索策略又是視頻壓縮算法中研究最多的領域。以傳統經典快速搜索算法為依托，重點對當前研究的各種快速運動估計算法進行闡述、分析和比較。

關鍵詞：運動；搜索算法；發展；應用

引言

隨著網絡上圖像傳輸需求的增多，視頻實時圖像的處理越來越受到人們的重視，龐大的圖像數據使視頻的實時處理變得困難，因此，圖像壓縮技術成為視頻實時圖像處理技術的關鍵問題。

視頻壓縮可以從不同的角度進行優化，幀間預測算法的改進是提高整體視頻壓縮算法效率的關鍵。它改進和優化主要涉及以下三方面：搜索策略、塊匹配準則和塊尺寸的選擇。塊匹配算法主要有最小絕對誤差和（SAD）、最小平均絕對誤差（MAD）或最小均方誤差（MSE）算法，還有改進后的最小絕對差分誤差和（SADD）算法以及基于內容的運動搜索算法等。塊尺寸方面，搜索的塊尺寸從16×16到8×8，再到4×4，精度單位從整像素到1/2像素，再到1/4像素，這些算法的改進減少了不必要的搜索點，細化了塊單位，提高了搜索精度和速度。

多數運動估計算法都是基于對搜索算法的改進，通過對搜索算法的改進，以消除搜索所帶來的時間冗余和空間冗余。

最初提出的快速搜索算法是全搜索法（FullSearch，FS）。全搜索算法運算準確度最高，但是運算量巨大，在編碼過程中占據了總運算量的60%～80%，所以很少為實際所使用。為減小運動估計過程中的計算量，保證運動估計的準確性，運動估計領域提出了很多新的快速算法。

早期的快速估計算法有三步搜索法、二維對數搜索法、正交搜索算法、交叉搜索算法等。這些方法通過限制搜索點的數目有效地減少了運算量，相對全搜索算法有了較大改進，但這些算法為了滿足搜索點的減少，往往將初始步長設的較大，使得搜索容易陷入局部最小，導致估計準確度不高。同時早期的算法在設計搜索策略時，多數會選擇全向性作為搜索的方向，即會選擇上下左右四向八點，或選擇菱形搜索等作為搜索模型。這種搜索策略從搜索的全面性以及匹配的精度來講，是有其優越性，但全向性搜索往往同時帶來搜索計算量增大，產生大量計算冗余。針對這些問題，現階段提出的新的快速搜索算法，從不同方面入手，改善搜索算法中的不足，提高搜索效率。為此本文將以經典算法作為研究前提，重點對當前研究的各種快速運動估計算法的對比分析其各自的利弊，提出對運動估計算法發展的新構思。

一、基于分層的自適應運動估計算法

基于分層的自適應運動估計算法，主要選取菱形作為搜索模型，通過相鄰宏塊間的運動矢量關系來判斷運動狀況，并對不同運動塊采用不同的搜索方法，對于大運動塊，采用分層結構搜索；其他運動使用小菱形搜索。同時結合多種提前截至準則，在保證匹配精度的前提下，提高了搜索速度。

基于分層的自適應運動估計算法是基于一種分層塔形的搜索思路延伸而成，但在算法上又明顯優于分層塔形搜索。基于分層塔形的搜索，它的做法是：對于那些運動比較劇烈的宏塊，先在低分辨力下一層層地搜索，然后再轉到原始分辨力下搜索，從而以較低的計算復雜度獲得較高的搜索精度。但現行的分層算法有時會出現重復搜索的問題，特別是在大運動搜索中，當預測起點已經是最優匹配點時，若判決準則不認為是最優，則還要先轉到低分辨力層搜索，再在原分辨力層精確搜索，雖然最終也能找到原先的最優點，但搜索步數增加，搜索速度變慢。因此，若沒有一個好的判決準則，分層方法有時會降低編碼效率。基于分層的自適應運動估計算法，能充分發揮分層思想在大尺度運動中搜索效率高的優勢，通過對各宏塊運動情況進行準確判斷，確定使用分層搜索的時機。使用自適應的搜索起點調整技術來逼近最優點，使用多種有效的提前閾值截止技術來防止重復搜索，與分層思想相結合，使得原來的分層算法效率有所提高。

二、方向延伸的快速運動搜索算法（DES）

方向延伸的快速運動搜索（DES）算法，利用圖像塊運動的方向特性，減小幀間編碼中運動估計的運算量。該算法在鉆石小模板塊失真匹配運算的基礎上引入搜索方向延伸方案、運動矢量預測和運動搜索的自適應門限等要素，先通過鉆石小模塊失真匹配運算找到最小失真檢測點，確定初始搜索點到最小塊失真檢測點為搜索方向，若該最小塊失真點不是中心檢測點，則在搜索方向上不斷延伸下一個相鄰的檢測點進行塊失真匹配，直至下一個檢測點的塊失真大于當前檢測點的塊失真。接著以當前檢測點作為中心檢測點，重復以上操作，直至中心檢測點為最優檢測點，結束搜索。

DES算法是在DS算法的思想基礎上的一種延伸。但其算法思想又明顯有別于DS算法。DS算法是一種基于全向性的搜索思想，該算法以搜索模板形狀而得名，其基本思想重復使用兩種搜索模板，鉆石搜索大模板及鉆石搜索小模板以適應視頻圖像中運動變化的基本規律。在搜索過程先重復使用大模板，直到最佳匹配塊落在大模板中心。然后再使用小模板來實現最佳匹配塊的準確定位。但由于DS算法在每個搜索點位置都進行全向性搜索，容易產生大量的搜索冗余。

DES算法在秉承了DS的鉆石搜索小模板的同時，針對運動不是特別劇烈的視頻圖像，提出方向延伸的搜索算法，使得搜索總是基于失真匹配最小的像素進行，這就大大減少了搜索的范圍和搜索的冗余。但DES算法也有其不足之處，由于初始搜索點的選取時基于當前塊的左方、正上方和右上方三個方向的候選點選取產生，雖然算法中考慮了相鄰塊運動矢量相關性及運動矢量中心偏移特性，也提到了通過閥值限定初始搜索點的選取，但由于算法中僅考慮了空間因素，而沒有考慮時間相關性，而且也沒有全面考慮空間因素，該算法還是會有最佳匹配點和初始搜索點不在相近的搜索區域的情況。這時放棄鉆石搜索大模板而僅僅基于鉆石搜索小模板搜索，就會在相同的算法復雜度的情況下，增加搜索的次數，從而降低搜索效率。DES算法在某些情況下優于DS算法，但由于其初始搜索點缺乏完善，很容易導致后面最佳匹配點的搜索產生繁復。

三、基于概率矩陣的快速運動估計算法

基于概率矩陣的快速運動估計算法，綜合運用時空相關性來對各個幀宏塊的運動向量的概率分布進行估計。該算法在綜合運用時空相關性的基礎上，首先根據當前宏塊的運動向量概率矩陣及之前宏塊的概率統計矩陣，通過相應的預測公式來估計下一宏塊各個可能的運動向量對應的概率值，然后根據概率值組成和搜索窗口大小相同的概率矩陣，選取矩陣中概率較大的運動向量進行塊匹配運算，找到最小平均絕對誤差（MAD）點，再使用小菱形搜索算法進行修正來得到最終運動估計結果。

傳統的快速搜索算法基于兩種思想：（1）通過限制搜索點的個數來降低塊匹配法（BMA）的復雜度，如三步搜索法、四步搜索法、新三步搜索法等；（2）運用時空相關性，從得到的運動向量選擇塊匹配的初始點的方法，如本文提到的DES算法和優化預測運動矢量的快速運動估計算法。這些算法分別從某一個方面入手進行算法優化，而基于概率矩陣的快速運動估計算法則將限制搜索點的思想與時空相關性聯系起來，使得算法將更加優越，而且精度還略有提高。該算法在算法設計中有兩點可取之處，首先選取與搜索窗口大小相同的概率矩陣，使得搜索窗口中所有的方向向量都得到了考慮。而概率矩陣預測算法P（t）=P（t-1）×0.3+P0×0.7的運用提高了概率矩陣預測值的精確性。通過對高概率的運動矢量的塊匹配運算，減少因對低概率的運動矢量進行塊匹配運算而造成的運算速度和精度的低效性。但算法也有其不足之處，該算法思想通過有效地減少了搜索的次數，簡化了搜索的復雜度，提高了搜索精度。但由此產生的概率矩陣同樣產生了計算的低效性。由于概率矩陣的設計是基于與搜索窗口同樣大小，則在概率計算中，就要將窗口中所有運動矢量都要進行計算和概率統計，概率矩陣預測有別于其他搜索算法，相應產生的多余計算，也是其他算法沒有的。

小結

優化預測運動矢量的快速運動估計算法與DES算法在壓縮思想上都是基于通過優化搜索方向算法，減少大量時間消耗和冗余信息。但在算法上兩者又有明顯不同。DES算法是基于鉆石搜索算法，將中心檢測點到最小塊失真檢測點定為搜索方向；而預測運動矢量的快速估計算法，在確定方向時，同時考慮了中心、中值和時間相關的三個矢量作為基本預測矢量，在考慮了序列空間相關性的同時考慮到序列的時間相關性。在算法的精確上比DES算法有了明顯的改進。

而概率搜索矩陣的搜索思想與上述思想有著明顯的差別，該算法在綜合考慮了運動幀間時空相關性的同時，根據搜索半徑確定與搜索窗口同樣大小的概率矩陣。通過尋找概率矩陣中概率值較大的運動向量來進行塊匹配運算，找到最小平均絕對誤差（MAD）點。該算法通過概率矩陣的計算，有效地減少了搜索的次數，簡化了搜索的復雜度，提高了搜索精度。但由此產生的概率矩陣同樣產生了計算的低效性。由于概率矩陣的設計有別于其他搜索算法，相應產生的多余計算，也是其他算法沒有的。

總的來講，新的快速搜索算法都是在原有經典算法的基礎上的改進和延伸。算法思想也主要是基于對時運動幀間時空相關性的考慮，利用菱形搜索算法，大小鉆石搜索算法以及運動向量概率矩陣等，以更為高效的方式，通過更少的運算尋找到最佳匹配塊，達到提高算法的速度和精度。

參考文獻：

[1]楊志云，郝紅衛，等.一種精確而快速的塊匹配算法[J].計算機工程與設計，2008，(2).

[2]樂培玉，張太鎰，等.一種基于概率矩陣的快速運動估計算法[J].中國圖像圖形學報，2007，(1).

[3]閆敬文，余見，等.優化預測運動矢量的快速運動估計算法[J].光學精密工程，2007，(10).

[4]俞柏鋒，趙飛，等.基于分層的自適應運動估計算法[J].電視技術，2008，(3).

[5]齊美彬，王德寶，等.一種方向延伸的快速運動搜索算法[J].工程圖學學報，2008，(1).

[6]劉偉鋒，汪增福，等.基于內容的視頻壓縮改進算法[J].計算機工程與設計，2009，(1).

[7]AndyBeach.視頻壓縮寶典[M].田尊華，程鋼，譯.北京:清華大學出版社，2009.

[8]全予一，門愛東，等.數字視頻圖像處理[M].北京:電子工業出版社，2005.