導(dǎo)語：小議運(yùn)動(dòng)搜索算法的發(fā)展及運(yùn)用一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：隨著視頻壓縮技術(shù)的發(fā)展以及人們對(duì)大尺寸、高質(zhì)量圖像日益增長的需求，視頻壓縮算法已成為當(dāng)前視頻技術(shù)發(fā)展研究的熱點(diǎn)，而搜索策略又是視頻壓縮算法中研究最多的領(lǐng)域。以傳統(tǒng)經(jīng)典快速搜索算法為依托，重點(diǎn)對(duì)當(dāng)前研究的各種快速運(yùn)動(dòng)估計(jì)算法進(jìn)行闡述、分析和比較。

關(guān)鍵詞：運(yùn)動(dòng)；搜索算法；發(fā)展；應(yīng)用

引言

隨著網(wǎng)絡(luò)上圖像傳輸需求的增多，視頻實(shí)時(shí)圖像的處理越來越受到人們的重視，龐大的圖像數(shù)據(jù)使視頻的實(shí)時(shí)處理變得困難，因此，圖像壓縮技術(shù)成為視頻實(shí)時(shí)圖像處理技術(shù)的關(guān)鍵問題。

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

多數(shù)運(yùn)動(dòng)估計(jì)算法都是基于對(duì)搜索算法的改進(jìn)，通過對(duì)搜索算法的改進(jìn)，以消除搜索所帶來的時(shí)間冗余和空間冗余。

最初提出的快速搜索算法是全搜索法（FullSearch，F(xiàn)S）。全搜索算法運(yùn)算準(zhǔn)確度最高，但是運(yùn)算量巨大，在編碼過程中占據(jù)了總運(yùn)算量的60%～80%，所以很少為實(shí)際所使用。為減小運(yùn)動(dòng)估計(jì)過程中的計(jì)算量，保證運(yùn)動(dòng)估計(jì)的準(zhǔn)確性，運(yùn)動(dòng)估計(jì)領(lǐng)域提出了很多新的快速算法。

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

一、基于分層的自適應(yīng)運(yùn)動(dòng)估計(jì)算法

基于分層的自適應(yīng)運(yùn)動(dòng)估計(jì)算法，主要選取菱形作為搜索模型，通過相鄰宏塊間的運(yùn)動(dòng)矢量關(guān)系來判斷運(yùn)動(dòng)狀況，并對(duì)不同運(yùn)動(dòng)塊采用不同的搜索方法，對(duì)于大運(yùn)動(dòng)塊，采用分層結(jié)構(gòu)搜索；其他運(yùn)動(dòng)使用小菱形搜索。同時(shí)結(jié)合多種提前截至準(zhǔn)則，在保證匹配精度的前提下，提高了搜索速度。

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

二、方向延伸的快速運(yùn)動(dòng)搜索算法（DES）

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

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

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

三、基于概率矩陣的快速運(yùn)動(dòng)估計(jì)算法

基于概率矩陣的快速運(yùn)動(dòng)估計(jì)算法，綜合運(yùn)用時(shí)空相關(guān)性來對(duì)各個(gè)幀宏塊的運(yùn)動(dòng)向量的概率分布進(jìn)行估計(jì)。該算法在綜合運(yùn)用時(shí)空相關(guān)性的基礎(chǔ)上，首先根據(jù)當(dāng)前宏塊的運(yùn)動(dòng)向量概率矩陣及之前宏塊的概率統(tǒng)計(jì)矩陣，通過相應(yīng)的預(yù)測(cè)公式來估計(jì)下一宏塊各個(gè)可能的運(yùn)動(dòng)向量對(duì)應(yīng)的概率值，然后根據(jù)概率值組成和搜索窗口大小相同的概率矩陣，選取矩陣中概率較大的運(yùn)動(dòng)向量進(jìn)行塊匹配運(yùn)算，找到最小平均絕對(duì)誤差（MAD）點(diǎn)，再使用小菱形搜索算法進(jìn)行修正來得到最終運(yùn)動(dòng)估計(jì)結(jié)果。

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

小結(jié)

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

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

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

參考文獻(xiàn)：

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

[2]樂培玉，張?zhí)劊?一種基于概率矩陣的快速運(yùn)動(dòng)估計(jì)算法[J].中國圖像圖形學(xué)報(bào)，2007，(1).

[3]閆敬文，余見，等.優(yōu)化預(yù)測(cè)運(yùn)動(dòng)矢量的快速運(yùn)動(dòng)估計(jì)算法[J].光學(xué)精密工程，2007，(10).

[4]俞柏鋒，趙飛，等.基于分層的自適應(yīng)運(yùn)動(dòng)估計(jì)算法[J].電視技術(shù)，2008，(3).

[5]齊美彬，王德寶，等.一種方向延伸的快速運(yùn)動(dòng)搜索算法[J].工程圖學(xué)學(xué)報(bào)，2008，(1).

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

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

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