基于塊匹配的圖像運動估計技術(shù)研究

全搜索法（FullSearchMethod,全搜索法（FullSearchMethod,FS）也稱為窮盡搜索法，是對（N＋2dy）搜索范圍內(nèi)所有可能的候選位置計算MAD(i,j)值，從中找出最小MAD，其對應偏移量即為所求運動矢量。此算法雖計算量大，但最簡單、可靠，F(xiàn)S從原點出發(fā)，按順時針螺旋方向由近及遠，在逐個像素處計算MAD值，直到遍歷搜索范圍內(nèi)聽有的點，然后在計算的所有點的MAD中找到最小值，該點FS算法是最簡單、最原始的塊匹配算法，由于可靠，且能夠得到全局最優(yōu)的結(jié)果，通常是其它算法性能比較的標準，但它的計算量的確很大，這就限制了在三步搜索算法（ThreeStep此搜索算法如圖2-2所示，每一步搜索9個位置點，對每一個位置計算（最小均方誤差）來確定最小失真方向（DMD，在最小失真方向上搜索區(qū)域減第一步第二步第三步圖2- 來進行第三步的搜索匹配，由于第二步和第三步的9個搜索點中均有一個點是在上一步中已經(jīng)計算過MSE值，所以第二步與第三步均只要計算8個點而已，所TSS算法的計算次數(shù)是9＋8＋8＝25次，同直接匹配需要169次比較，計算量新三步搜索算法[26]（NewThree–StepSearch,大部分近似的快速BMA算法（TSS、2D-LOG等）BDM隨搜索窗口內(nèi)當前檢查點與最優(yōu)BDM點之間的距離的增大而單調(diào)增加（BDMMSE或MAD時，然而這個假設并非總是正確，原因是：①孔徑問題；②分塊時引起的運動物體和背景的不連續(xù)分割；③周期性紋理形狀的圖像內(nèi)容；④光線改變。以上原因有時會導致搜索過程陷入局部最優(yōu)點而找不到真正的最優(yōu)點。這正是TSS等傳統(tǒng)快速BMA的主要缺點。不過，盡管BDM的單峰假設在全局上并不總是成立，但是它在全局最優(yōu)點的一個小鄰域內(nèi)還是成立的。因此利用運動矢量的中心偏移特性的新三步法（NTSS、四步法（FSS、二步法（2SS）等可以比TSS、2D-LOG等得到更好的結(jié)果。Renxiangi1994年提出了新三步搜索算法。NTSSS的一個改進，對運動量比較小的序列如可視序列有比較好的性能。對于絕大多數(shù)的序列，運動矢量的分布都是在中心位置上的概率最大，隨著與中心位置的劇運動量比較小的序列的這一特性會更加明顯。圖2-3顯示了這種中心偏移特性2-3Saleman為了利用運動矢量的中心偏移特性，NTSS在第一步除了搜索TSS第一步的9個點外，還搜索了中心點周圍的8個點，如圖2-4所示。圖中顯示出了W＝7時的兩個搜索路徑。中間位置的路徑顯示了搜索小運動的情形。在這種情形下，第一步的最小BDM點是中心點周圍的0246第一步第二步第三步0246 2-4新三步法（NTSS）3個點（8個相鄰點中的4個邊點之一，如圖2-4所示）圖中的情形只需2步，共搜索17＋3＝20個點；若為角點，則也是2步，這時的搜索點數(shù)是17＋5＝22個。右上的路徑是大運動的情形，第一步的最小BDM點是外部的8個搜索點之一，第二步以后的方法與TSS完全相同。因此總共也是3步，但總搜索點數(shù)目多了817＋8＋8＝33個。另外，在NTSS中如果第一步的最小BDM點恰好是中心點，則立即停止搜索，搜索得出的運動矢量結(jié)果為（0，0四步搜索算法[27]（Four–StepLarManPo1996年提出了四步搜索算法（FSS。該算法也利用了運動矢量的中心偏移特性，方法是采用比TSS小的初始步長，取為W／4。由于采用了較小的初始步長，W＝7時FSS需要4步才能達到搜索窗口的邊緣。與NTSS一樣，當運動較小時，F(xiàn)SS也會很快結(jié)束搜索過程，只需要2到3步即可。圖2-5顯示了大運動量時FSS的兩個搜索路徑，二者都需要4步。左下方的路徑需要搜索9＋5＋3＋8＝25個點。正好與三步法（TSS）相同；右上方的路徑則需要9＋5＋5＋8＝27個點，比三步法（TSS）略多。不過W＝727個搜索點是FSS的情況。0246第一步第二步第三步第四步0246 2-5四步法（FSS）2-6顯示了運動較小時FSS的兩個搜索路徑，分別只需要23步，而且W為任何值時都是如此。左邊的路徑需要9＋8＝17個搜索點，右邊的需要＋3＋8＝202-6四步搜索算法（FSS）從圖2-5和圖2-6中可以看出，當最小BDM點不在某次搜索的中心位置時，則下一步需要35個搜索點（最后一步除外；如果已達到搜索窗口的邊緣，則進行最后一步。如果最小BDM點在中心位置，則步長減半，增加8個點；如果此時W＝1則進行最后一步。基于塊的梯度下降搜索算法[28]（Block-BasedGradientDescentSearchBBGDS基于塊的梯度下降搜索法是1996年由Lurng-KuoLi和EphraimFeig該算法采用了一個非常偏向于中心位置的搜索模式——步長為1的9點搜索，如圖2-7所示。它不限制搜索的步數(shù)，當某一步的最小BDM點位于中心位置或該步已到達搜索窗口的邊緣時，則停止搜索。與FSS的某些搜索步驟一樣，BBGDS的每個后續(xù)搜索步驟都是增加3個或5個搜索點。這個算法非常適合于小運動量的場合。圖2-7顯示了BBGDS的兩個小運動情況下的搜索路徑。Step13×39Step2BDM點在搜索窗中心，則算法結(jié)束；否則以上一步BDM點為中心，重復Step1。在每一步搜索過程中，BBGDS算法使用了中心匹配塊而不是匹配塊，降低了陷入局部最優(yōu)的可能性。利用梯度下降的方向來指導搜索方向，對該方向進行0246第一步第二步第三步0246 2-7BBGDS二維對數(shù)搜索算法[29]（Two-Dimensional為了減少塊匹配算法的計算，人們提出了許多塊匹配快速算法。J.R.Jain和A.K.Jain早在1981年就提出了二維對數(shù)搜索算法。它開創(chuàng)了快速算法的先例，分多個階段搜索，逐次減小搜索范圍直到不能再小而結(jié)束。其搜索步驟如圖2-8所示。它通過連續(xù)減少搜索區(qū)域來尋找最小失真方向（DMD。每一步搜索由區(qū)域中心位置和與中心相聯(lián)的4個邊緣點組成，形狀就是一個十字形，連續(xù)搜索直到尋找的區(qū)域成為3×3矩形區(qū)域為止。最后一步計算3×3矩形區(qū)域9個位置點，MSE最小值就是要尋找的DMD。在這種算法中，MES27log2w，同直接尋找所需搜索點數(shù)w2相比較，計算量大大減少。1414023462264564665112346226456466511124682-8二維對數(shù)搜索算法（TDL）示意圖Step1：從原點開始，選取一定的步長，在以十字形分布的五個點處進行最小塊誤差MAD值的計算并比較；Step2：若MBD點在邊緣四個點處，則以該點為中心點，保持步長不變，重新搜索十字形分布的五個點；若MBD點位于中心點，則保持中心點位置不變，Step3：在中心及周圍8個點處找出MBD點，若步長為1，該點所在位置即對應最佳匹配點，算法結(jié)束；否則重復Step2。具體的一個搜索例子請參考圖2-8。圖中點（0，-4（+4，-4（+6，-4）是每個搜索階段的最小塊誤差點。最終運動矢量為（+5，-4），每個點上的數(shù)字表TDL算法搜索時，最大搜索點數(shù)為27log2w，若發(fā)現(xiàn)新的十字形點群的中心點位于搜索區(qū)的邊緣，則步長也減半，后來有人提出應該在搜索的每個階段都將步長減半。所有這些改動都是為了使算法搜索范圍很快變小，提高收斂速度。TDL算法的前提是假設搜索區(qū)內(nèi)只有一個谷點，如果搜索區(qū)內(nèi)存在多個谷點時，該方法找到的可能是局部最小點。不能保證找到全局最優(yōu)點也正是大部分快速搜菱形搜索算法[30]（DiamondDS算法即菱形算法，也稱鉆石算法，最早由ShanZhuKai-KuangMa兩人算法同時也被MPEG-4VM標準接受。搜索模板的形狀和大小不但影響整個算法的運行速度，而且也影響它的性能。塊匹配的誤差實際上是在搜索范圍內(nèi)建立了誤差表面函數(shù)，全局最小點即對應著最佳運動矢量。由于這個誤差表面通常并不是單調(diào)的，所以搜索窗口太小，就容易陷入局部最優(yōu)，例如S算法，其搜索窗口僅為×3；而搜索窗口太大，又容易產(chǎn)生錯誤的搜索路徑，象S算法的第一步。另外，統(tǒng)計數(shù)據(jù)表明，圖像進行運動估計時，最優(yōu)點通常在零矢量周圍(以搜索窗口中心為圓心，兩像素為半徑的圓內(nèi))，如圖2-9所示。基于這兩點實事，DS算法采用了兩種搜索模板，分別是只有5個檢測點的小模板SDSM(SmallDiamondSearchMask)和9個檢測點的大模板LDSM(LargeDiamondSearchMask)，如圖2-10和圖2-11所示。搜索時先用大模板計算，當最小塊誤差MBD點出現(xiàn)在中心點處時，將大模板LDSM換為SDSM，再進行匹配計算，這時5個點中的MBD即為最優(yōu)匹配點。圖2-9最優(yōu)點分布規(guī)律圖2-10小模板SDSM 圖2-11大模板LDSMDS算法的具體步驟是：Step1：用LDSM在搜索區(qū)域中心及周圍八個點處進行匹配計算。若Step3Step2Step3Step2Step3：以上一次找到的MBD點作為中心點，將LDSM換為SDSM，在五個點處計算，找出MBD點，該點所在位置即對應最佳運動矢量。2-12所示，就是一個用DS算法搜索到運動矢量(-5，-2)的例子，。搜索5步，MBD點分別為(-2，0),(-3，-1),(-4，-2)，使用了四次LDSM和一次SDSM，總共搜索了24個點。2468 2468

第一步第二步第三步第四步0第五步0 2-12菱形（DiamondSearch）S算法的特點在于它分析了圖像中運動矢量的基本規(guī)律，選用了大小兩種形狀的搜索模板LSMSDMLSM搜索，由于步長大，搜索范圍廣，可以進行粗定位，使搜索過程不會陷于局部最??；當粗定位結(jié)束后，可以認為最優(yōu)點就在LSM8DM來準確定位，使搜索不至于有大的起伏，所以它的性能優(yōu)于其它算法。另外，DS搜索時各步驟之間有很強的相關性，模板移動時只需在幾個新的檢測點處進行匹配計算，所交叉搜索算法[31]（CrossSearch1990年，Ghanbari提出了交叉搜索算法,它也是在TDLTSS基礎上為進一CSA是從原點開始，以“×”字形分布的五個點構(gòu)成每次搜索的點群，以TDL的搜索方法檢測MBD點，僅在最后一步采用“十”字形點群。CSA算法以“×”字形搜索模式、初始步長為W／2開始搜索，每一步搜索5個點，步長也是每一步減半。圖2-13顯示了CSA的兩個搜索路徑。當步長減到1時：如果該步驟的最小BDM點位于中心、左上角或右上角位置，則以該點為中心再進行一次步長為1的搜索，但搜索模式為“十”字形（如圖2-13所示左下方的路徑；否則，以該點為中心再進行一次步長為1的“×”字形搜索（如圖2-13所示右上方的路徑。W＝7時，CSA需要搜索5＋4＋4＋4＝17個點，共4步。對于任意W，CSA需進行1log2W1)步，搜索54log2W1)個點。CSA0246第一步第二步第三步第四步0246 圖2- Step2MBD5點搜索。若步長大于1，則重復Step2；若步長為1，則進行Step3。Step3MBD點的位置，分別做“十”字形和“×”字形搜索：若上一步MBD點處于中心點、左上角或右上角，做“十”字形搜索；若上一步MBD點處于左下角或右下角，做“×”字形搜索。由當前MBD點得到最佳運動CSA的最大搜索點數(shù)為54log2(W1)果不算太好，在搜索區(qū)域的邊界上有四分之一的點CSA沒有考慮，因此它不適用共軛方向搜索算法（AConjugateDirection1985年，R.SrinirasanK.Rao提出了共軛方向搜索算法。搜索示意圖如圖2-14所示。 j-1j 3333 222 2

123圖2- 123共軛方向搜索算法是一種尋找最小失真方向的有效方法。第一步是沿著水平方向的軸上搜索，計算最小均方誤差函數(shù)（MSE，找出最小失真方向（DMD。第二步是以沿著水平方向找到的最小失真方向為起點，朝垂直方向搜索，找到垂直方向上的極小值點。第三步是把水平方向的極小值點和垂直方向的極小值點相連，沿著連線搜索，找到連線上的極小值點。顯然，連線上的極小值點就是矩形區(qū)域內(nèi)的最小值點即為全程搜索DMD。正交搜索算法[32]（OrthogonalSearchAlgorithm,Puri等于1987年提出了OSA算法，也是最早提出利用運動矢量的相關性進行中心搜索點預測的算法。OSA的初始步長是W／2，每一步都包含水平與豎直搜索兩個小步驟，兩個小步驟的步長相同。圖2-15顯示了OSA的兩個不同的搜索路徑。從水平搜索開始，首先搜索水平方向上的三個點，最小BMD點作為下一步豎直搜索的中心點，豎直方向上也是搜索三個點，與TSS相同，第二步以后每一步的步長也是上一步步長的一半。如果步長減少到1時，則該步為最后一步。不過OSA的最后一步仍然與前面的步驟相同，不像TDL最后一步與TSS相同。圖2-15中W＝7，需搜索3＋2＋2＋2＋2＋2＝13個點，總共也是3步。通常情況下，OSA需進行l(wèi)og2(W1)步，搜索〔14log2(W1)〕個點?？梢姟SA搜索的點數(shù)大約是TSS的一半。第一步第二步第三步 2-15正交搜索算法（OSA）OSA算法每一步可以看成是由水平和垂直兩個階段組成，直到步長變?yōu)?時視為算法結(jié)束。由于每次計算的匹配點數(shù)太少，不能顧及各個方向，雖然速度較分層塊匹配算法[33]Bierling1988年提出了HBMA算法。其基本思想是在圖像的多分辨率表示的每一層分別進行運動估計，從最底分辨率層開始，逐層進行，最底層以外的其它層進行運動估計時都要利用上一層的估計結(jié)果，如圖2-16所示。低分辨率層估計出來的運動矢量將被用來作為下一步估計時的初始值，即高分辨率層的運動估計是對上一低分辨率層估計結(jié)果的進一步細化。由于已經(jīng)有了粗精度的初始估計，高分辨率層在進行運動估計時就可以采用更小的搜索窗口。每一層都可以采用各種BMA方法如FS、TSS等。低分辨率層可以通過對高分辨率層進行亞抽樣得到，也可以采用均值塔形算法或其它算法得到。均值塔形算法的低分辨率層的每一像素對應上一高分辨率層的四個像素，且像素值為四個像素值的均值。HBMA可用于分層編碼以提供性能可伸縮性。 圖2- 簡易搜索算法又稱為象限法，它是在S的基礎上進一步減少調(diào)用函數(shù)的次數(shù)。S中，有完整的八個搜索方向，每個方向都有一個相反的方向。據(jù)單律性誤差平面的假定，塊匹配誤差沿遠離全局最小誤差處的方向單調(diào)增加。這意味著：最小值不可能同時在兩個相反的方向上產(chǎn)生。也就是說，實際上每一步最多需要搜索八個方向的一半，因此，計算復雜度可大大減少。但另一方面，為了確定搜索SES在某一個僅含三個搜索方向的象限中；另外，同TSS一樣，SES算法也使用第二步和第三步來確定所需的步驟數(shù)目和步長。SES的創(chuàng)新在于它將每一步分為兩段來完成：第一段用來選擇進行搜索的象限；第二段用來在所選象限中尋找最小誤（0，0，（P0（0-所示）的誤差函數(shù)（選定MAD）MA（A≥MA（CMAD（A）≥MAD（B）MAD（A）＜MAD（CIMAD（A）＜MAD（B）MA（A）＜MA（CIIMA（A≥MA（CIABC2-17SES在第二段中，根據(jù)每個選定的象限，如圖2-18所示，其中a、b、c、d分別對應I、II、III、IV象限，進一步計算相應的某些位置（如黑點所示）的MAD并作比較。其它與TSS相同。SES在TSS的基礎上將處理速度提高了近一倍。ABCAABCABCABCABC第一次 2-18SES綜上所述，通過總結(jié)概括以上經(jīng)典的塊匹配搜索算法，我們不難發(fā)現(xiàn)，基于塊匹配的運動估計算法的性能取決于以下三個因素：①搜索策略；②匹配準則；③搜索