《數(shù)字視頻處理及應(yīng)用》課件第2章

第2章運動估計2.1二維運動估計的基本概念2.2二維運動場模型2.3光流法運動估計2.4基于塊的運動估計2.5基于網(wǎng)格的運動估計2.6基于區(qū)域的運動估計2.7多分辨率運動估計2.8本章小結(jié)

2.1二維運動估計的基本概念

在隨時間變化的視頻序列中，幀與幀之間存在著很大的空間冗余，通過運動估計可以有效地去除冗余，保留幀間的有效信息，這對于視頻圖像序列數(shù)據(jù)壓縮和傳輸是非常重要的。如果景物和攝像設(shè)備都是靜止的，則當前幀像素點的位置與在下一幀中的位置應(yīng)當是相同的；如果在靜止景物中還有運動的物體，則對當前幀中運動物體上的某一像素點，在未來時刻的最佳運動位置估計，應(yīng)該為該像素點在下一幀中的位置。真實物體的三維運動在圖像平面上的透視或正交投影是二維運動。平面上的每一點在時刻t與t+Δt間的位移矢量組成了該平面的二維位移矢量場，也稱之為對應(yīng)場。而平面上的每一點在時刻t與t+Δt間的位移變化率就是該點的光流矢量，平面上各點的光流矢量組成了該平面的光流場。因此，產(chǎn)生了對于二維運動估計的兩種提法：(1)在時刻t與t+Δt間，對于各像素點的位移矢量的估計，可表達為式(2-1)；(2)在時刻t與t+Δt間，對于各個像素點的光流矢量的估計，可表達為式(2-2)。

d(x，t；Δt)=[d1(x，t；Δt)d2(x，t；Δt)]T

(2-1)

v(x，t)=[v1(x，t)v2(x，t]T

(2-2)

2.2二維運動場模型

2.2.1參數(shù)模型

參數(shù)模型是用來描述曲面的三維運動(位移和速度)在圖像平面上的正交或透視投影的。通常三維曲面的表達式?jīng)Q定了帶參數(shù)的二維運動場的模型。例如，一個由平面的三維剛體運動產(chǎn)生的二維運動場，在正交投影下，可用六個參數(shù)的仿射模型描述；在透視投影下，可用八個參數(shù)的非線性模型描述。

參數(shù)模型的子類是所謂的“準參數(shù)”模型，它們把每個三維點的深度當作獨立的未知量來對待，那么六個三維運動參數(shù)可以限定局部圖像的矢量沿著指定的方向伸展，同時利用局部深度的知識去確定運動矢量的準確值。這些模型可作為約束條件去規(guī)范二維運動矢量，導(dǎo)出聯(lián)合的二維和三維運動估計公式。2.2.2非參數(shù)模型

參數(shù)模型的主要缺點是它只適用于三維剛體運動。那么，在不使用三維剛體運動模型的情況下可以將非參數(shù)均勻性約束條件強加于二維運動場上。常用的非參數(shù)模型有：

1.基于光流方程的方法

基于光流方程(OpticalFlowEquation)的方法依據(jù)時空圖像的亮度梯度得到一個光流場的估算。對于灰度圖像，光流方程要與合適的時空平滑約束條件聯(lián)合使用，要求位移矢量在附近區(qū)域緩慢變化。對于彩色圖像，光流方程可分別施加于每個顏色帶上，約束三個不同方向的位移矢量。

2.塊運動模型

該方法假設(shè)圖像是由運動的塊構(gòu)成，然后逐幀確定出塊位移。通常包括兩種方法：相位相關(guān)法和塊匹配法。在相位相關(guān)法中，兩個相鄰幀之間的傅立葉相位差決定了運動估計的結(jié)果。塊匹配算法是使用“距離準則”搜索出相繼幀間的固定大小的最佳匹配塊的位置，確定出塊位移。

3.像素遞歸法

像素遞歸法是預(yù)測校正型的位移估算器。預(yù)測值可以作為前一個像素位置的運動估算值，或作為當前像素鄰域內(nèi)的運動估算線性組合。依據(jù)該像素上的位移幀差的梯度最小值，對預(yù)測作進一步的修正。

4.貝葉斯法

貝葉斯法利用隨機平滑度約束條件，通常采用Gibbs隨機場方法來估算位移場。貝葉斯法方法的主要不足是需要大量的計算。

2.3光流法運動估計

光流法運動估計是基于像素的運動估計技術(shù)之一，通過光流場對物體的運動進行描述。光流場是一個二維速度場，是對運動場的近似。它蘊含著三維的運動信息，但由于光流是從兩幅差別很小的圖像中求得的，往往含有很大的噪聲，由此不可以精確地求出運動。盡管如此，通過對光流的分析，可以定性地解釋物體在三維空間的運動。

基于光流場的運動估計技術(shù)針對單個像素，求其運動矢量V(u，v)，該矢量包含像素運動的兩個信息：幅值和方向。光流場的模型基于一些假設(shè)前提，比如物體運動無遮擋，物體表面反射系數(shù)均勻變化并且沒有突變等。在這些前提之下，像素的運動有一個自然的約束方程

I(x，y，t)=I(x+Δx，y+Δy，t+Δt)

(2-3)其中，I(x，y，t)代表位置在(x，y)的像素在t時刻的某種屬性，比如亮度。對該約束方程的兩邊進行泰勒展開，同時再做一些變形，可以得到如下的光流約束方程

(2-4)記，，，，則有(2-5)其中，Ix和Iy分別表示在水平和垂直方向上的亮度變化；u和v分別表示在水平和垂直方向上的運動。僅依靠這個約束不能夠得到要求的運動矢量，還需要一些附加的約束，比如運動矢量平滑的約束，也就是求解(2-6)和(2-7)在這些約束條件下，通過估計得到的來計算，也就是所要求的運動矢量V(u，v)。

2.4基于塊的運動估計

2.4.1塊運動的兩種模型

塊運動模型是假設(shè)圖像由運動的塊構(gòu)成的。一般分為兩種類型的塊運動模型：塊平移模型和可變形塊運動模型。

1.塊平移模型

這種模型限制每一個塊作單純的平移運動。設(shè)塊B的大小是Nx×Ny，塊B的中心為(xc，yc)，經(jīng)過一幀運動到新的位置，則塊B中所有點可表示為

s(x，y，k)=B(x+Δx，y+Δy，k+1)

(2-8)

向量(Δx，Δy)為從(xc，yc)指向(xc+Δx，yc+Δy)的運動向量。一般情況下，(Δx，Δy)取為整數(shù)，在高精度下也可以取實數(shù)。塊平移模型如圖2-1所示。圖2-1塊平移模型在圖2-1中，整個塊被認為具有單一的運動向量，可以直接在逐像素對比的基礎(chǔ)上通過匹配來自k+1幀中相應(yīng)塊的灰度級或顏色信息得到運動補償。塊平移模型的運動估計和運動補償?shù)膬?yōu)點是實現(xiàn)簡單，另外，由于每個塊只需要一個運動矢量，不需要很多附加條件表示運動場，且實現(xiàn)時有現(xiàn)成可用的低價超大規(guī)模集成電路支持，因此基于平移的塊模型的運動補償和估算具有較大的通用性。然而，使用平移塊的運動補償不適用于縮放、旋轉(zhuǎn)運動和局部變形，同時由于物體邊界通常與塊邊界不一致，鄰近的塊實際上可能被表示成完全不同的運動矢量，而導(dǎo)致嚴重的人為分割現(xiàn)象，這在甚低比特率的應(yīng)用中尤其如此。

2.可變形塊運動模型

可變形塊運動模型可以對物體的旋轉(zhuǎn)、縮放、變形等建模。塊的運動參數(shù)不再是簡單的一個平移參數(shù)，而是一些空間變換參數(shù)。常用的可變形塊運動模型有投影運動、仿射運動、雙線性運動等。

(1)投影運動：

(2-9)(2)仿射運動：(2-10)

(3)雙線性運動:(2-11)2.4.2相位相關(guān)法

基于塊的運動模型假設(shè)，圖像是由運動的塊組成的。對于作簡單二維平移的塊的運動模型可寫為

f(x，y，t)=f(x+m，y+n，t+Δt)

(2-12)

對運動模型式(2-12)左右兩邊作二維傅立葉變換，當Δt=1時,

Ft(u，v)=Ft+1(u，v)e－j2π(mu+nv)

(2-13)

其中，F(xiàn)t(u，v)表示t幀對于空間變量x、y的二維傅立葉變換。由此可見，在平移運動的情況下，各個塊的二維傅立葉變換的相位差為

arg{F(u，v，t)}－arg{F(u，v，t+1)}=2π(mu+nv)

(2-14)可見，相位差處在一個變量(u，v)定義的平面上。幀t與t+1間的互相關(guān)函數(shù)為

ct，t+1(x，y)=f(x，y，t)。f(x，y，t+1)

(2-15)

其中，。代表二維卷積運算。兩邊作傅立葉變換，就可得到互功率譜:

Ct，t+1(u，v)=Ft(u，v)Ft+1(u，v)

(2-16)

歸一化互功率譜可得到互功率譜的相位:

(2-17)將式(2-17)作逆傅立葉變換，得到相位相關(guān)函數(shù):(2-18)2.4.3塊匹配法

1.塊匹配運動估計原理

塊匹配法的思想是將圖像劃分為許多互不重疊的子圖像塊，并且認為子塊內(nèi)所有像素的位移幅度都相同，這意味著每個子塊都被視為運動對象。對于k幀圖像中的子塊，在k－1幀圖像中尋找與其最相似的子塊，這個過程稱為尋找匹配塊，并認為該匹配塊在第k－1幀中所處的位置就是k幀子塊位移前的位置，這種位置的變化就可以用運動矢量來表示。塊匹配運動估計過程如圖2-2所示。圖2-2塊匹配運動估計過程

2.塊匹配運動估計的匹配準則

運動搜索的目的就是在搜索窗范圍內(nèi)尋找與當前塊最匹配的數(shù)據(jù)塊，這樣就需要定義一個匹配準則來判斷兩個塊是否匹配。一方面匹配準則的精確與否影響著運動估計的準確性，另一方面匹配準則的復(fù)雜度也影響著運動估計的速度。

目前的各種搜索算法中，常見的匹配準則有絕對平均誤差函數(shù)(MAD)、絕對差值和函數(shù)(SAD)、歸一化互相關(guān)函數(shù)(NCFF)、均方誤差函數(shù)(MSE)、最大誤差最小函數(shù)(MME)等。這些函數(shù)的表達式等具體內(nèi)容如下：

MAD的表達式為(2-19)SAD的表達式為(2-20)NCFF的表達式為(2-21)

MSE的表達式為(2-22)MME的表達是為

MME(i，j)=max|fk(m，n)－fk－1(m+i，n+j))|

(2-23)其中，M×N為宏塊的大小，(i，j)為位移量，fk和fk－1分別為當前幀和參考幀的像素值。在上述匹配準則中，取MAD、MSE、SAD和MME的最小值點為最優(yōu)匹配點，取NCFF的最大值點為最優(yōu)匹配點。

3.典型搜索算法

1)全搜索算法

全搜索算法(FullSearch，F(xiàn)S)也叫窮盡搜索法，是一種最簡單的搜索算法。該算法搜索所有可能的候選位置計算SAD值來找出最小SAD，其對應(yīng)的位置偏移值就是要求的運動矢量值。全搜索算法計算量很大，不過它也是最簡單、最可靠的搜索算法，使用全搜索算法可以找到全局最優(yōu)匹配點。全搜索算法有兩種搜索順序：光柵掃描順序和螺旋掃描順序，如圖2-3所示。圖2-3全搜索算法如圖2-3(a)所示，在光柵掃描順序中，將搜索窗口的左上角作為搜索的起始點位，并且按照光柵掃描的順序?qū)λ阉鞔皟?nèi)的每個點的SAD值進行計算；如圖2-3(b)所示，在螺旋掃描順序中，搜索的起始點位于搜索窗的中心(0，0)處，然后按照螺旋順序計算搜索窗內(nèi)每個點的SAD值。螺旋搜索順序是一種較為優(yōu)異的全搜索算法，它利用了運動矢量的中心偏置特性(運動矢量有很大的概率分布在搜索的中心位置及其附近位置)，可以在一定程度上加快運動矢量的搜索。全搜索算法的搜索遍歷所有的搜索范圍來找到最優(yōu)匹配塊，因此它的搜索精度最高、所產(chǎn)生的殘差系數(shù)最小。起初由于全搜索算法的思想非常地簡單，并且非常易于在硬件上實現(xiàn)，因而被大家所采用，但是全搜索算法的計算量非常大。近年來，快速算法的研究得到了廣泛關(guān)注，研究人員提出了很多快速算法。很多運動估計的快速算法從降低匹配函數(shù)復(fù)雜度和降低搜索點數(shù)等方面進行了改進，早期的運動估計改進算法主要有三步搜索法TSS(ThreeStepSearch)、二維對數(shù)搜索法TDLS(Two-DimensionalLogarithmSearch)和變方向搜索法CDS(ConjugateDirectionSearch)，這些快速算法主要建立在誤差曲面呈單峰分布，存在唯一的全局最小點假設(shè)上；后來為了進一步提高計算速度和預(yù)測矢量精度，利用運動矢量的中心偏移分布特性來設(shè)計搜索樣式，相繼又提出了新三步法NTSS(NewThreeStepSearch)、四步法FSS(FourStepSearch)、梯度下降搜索法BBGDS(Block-BasedGradientDescentSearch)、菱形搜索法DS(DiamondSearch)和六邊形搜索法HEXBS(HEXagon-BasedSearch)等算法。

實際上，快速運動估計算法就是在運動矢量的精確度和搜索過程中的計算復(fù)雜度之間進行折中，尋找最優(yōu)平衡點。

2)三步搜索算法

三步搜索算法(ThreeStepSearch，TSS)是由T.Koga等人提出的一種應(yīng)用相當廣泛的運動估計搜索算法。三步法的基本思想是使用一種由粗到精的搜索模式，從零矢量開始，選取一定的步長，取周圍8個點做匹配，直到搜索到最小誤差值點。當三步法的搜索區(qū)間是［-7，7］，搜索精度取1個像素時，則步長為4、2、1，總共需三步即可滿足要求，所以得名三步法。其具體的算法步驟如下：

(1)選取最大搜索長度的—半為步長，在原點周圍距離為步長的8個點處進行塊匹配計算并比較。

(2)將步長減半，中心點移到上一步的MBD(MininumBlockDistortion，最小塊誤差)點，重新在周圍距離為步長的8個點處進行塊匹配計算并比較。

(3)在中心及周圍8個點處找出MBD點，若步長為1，該點所在位置即對應(yīng)最優(yōu)運動矢量，算法結(jié)束；否則重復(fù)第(2)步。

如圖2-4所示，三步法共搜索9+8+8=25點，這相對于全搜索算法計算量有很大的降低。三步法作為一種比較典型的快速算法，在基本上保持與全搜索算法一致性能的基礎(chǔ)上，其計算量約為全搜索的10%。由于三步法的快速、高效和易于硬件實現(xiàn)，所以三步法在很多視頻壓縮系統(tǒng)中得到了應(yīng)用，如H.261。三步法同樣也是基于運動矢量平均分布的運動規(guī)律，雖然比全搜索算法效率高，但是由于它采用固定的搜索模式進行搜索，所以也有明顯的缺陷：它的第一步搜索步長過大，在搜索窗的范圍比較大時，會導(dǎo)致搜索過于粗糙，使得步長和運動矢量相差太大，這樣容易陷入局部最優(yōu)，導(dǎo)致搜索精度的下降。圖2-4TSS算法示意圖

3)新三步搜索算法

新三步搜索算法(NewThreeStepSearch，NTSS)是1994年由Ren-XiangLi等人提出的。作為對TSS的一種改進，NTSS擁有更好的性能。NTSS利用運動矢量的中心偏置特性，在原有的TSS算法的第一步搜索點的基礎(chǔ)上增加了中心點的8個鄰域點作為搜索點，并且采用了提前終止的策略。該算法加強了對中心區(qū)域的搜索，對于運動較小或者靜止的視頻序列具有很好的效果。其具體的算法步驟如下：

(1)在原有的TSS算法第一步的測試點的基礎(chǔ)上再增加中心點的8-鄰域作為測試點。

(2)半途終止策略用于估計靜止及半靜止塊的運動向量。如果最小的MBD在第一步出現(xiàn)在搜索窗口的中心，則停止搜索。如果最小的MBD出現(xiàn)在中心點的8-鄰域中，則以最小MBD為中心計算其8-鄰域，找出最小的MBD。重復(fù)上面的步驟，直到最小MBD出現(xiàn)在中心。如果最小的MBD出現(xiàn)在(±w/2，±w/2)上，則執(zhí)行TSS算法的第二步和第三步。

圖2-5是NTSS算法的原理圖，圖中數(shù)字表示搜索順序，用黑圈圈出的數(shù)字表示搜索到的最小塊誤差點。圖2-5新三步搜索算法原理圖假設(shè)選取的搜索范圍為±7、搜索窗口為15×15，最好的情況下NTSS算法只需要對17個點做匹配(第一步搜索，最小MBD值點在中心)，在最壞的情況下需要對25+8=33個點做匹配，對于運動較小的塊(運動范圍在±2個像素內(nèi))需要對20或22個點做匹配。根據(jù)運動矢量的中心偏置特性可以知道運動矢量通常分布在搜索窗中心附近一個較小的范圍內(nèi)的概率很大，所以NTSS充分利用運動矢量的中心偏置特性進行搜索，不僅提高了匹配的速度，而且也使得運動搜索陷入局部最優(yōu)的可能減少了很多。提前中止策略的采用可以加快搜索的速度，這一技術(shù)也被以后的算法所廣泛使用。

4)四步搜索算法

四步搜索法(FourStepSearch，F(xiàn)SS)是1996年由Lai-ManPo和Wing-ChugMa提出的。該算法類似于三步法，但它基于現(xiàn)實中序列圖像的一個特征，即運動矢量都是中心分布的，從而在5×5大小的搜索窗口上構(gòu)造了有9個檢測點的搜索模板。FSS改TSS的9×9搜索窗為5×5，窗口的中心總是移到最小MBD的位置，步長的大小由最小MBD的位置來決定。FSS的具體的算法步驟如下：

(1)在15×15的搜索區(qū)域的中心放置一個5×5的窗口，如圖2-6(a)所示，如果最小MBD出現(xiàn)在窗口的中心轉(zhuǎn)(4)，否則轉(zhuǎn)(2)。

(2)搜索窗口保持5×5大小，但是搜索模式依賴于最小MBD出現(xiàn)的位置。

①如果最小MBD出現(xiàn)在窗口的四角，要增加五個測試點，如圖2-6(b)所示；

②如果最小MBD出現(xiàn)在窗口四邊的中心，要增加三個測試點，如圖2-6(c)所示；

③如果最小MBD出現(xiàn)在窗口的中心轉(zhuǎn)(4)，否則轉(zhuǎn)(3)。

(3)搜索模式與第二步相同，但要最后轉(zhuǎn)(4)。

(4)搜索窗口縮小為3×3，如圖2-6(d)所示，最后的運動向量由該九個點中擁有最小MBD的點決定。圖2-6四步搜索法的搜索模式

FSS是快速搜索算法的又一次進步，它在搜索速度上不一定快于TSS，搜索范圍為±7，搜索窗口為15×15，F(xiàn)SS最多需要進行27次匹配計算。但是FSS的計算復(fù)雜度比TSS低，它的搜索幅度比較平滑，不致出現(xiàn)方向上的誤導(dǎo)，所以獲得了較好的搜索效果。而且FSS同樣適用于如攝像機鏡頭伸縮、有快速運動物體的圖像序列中。因此，F(xiàn)SS是一種吸引人的運動估計算法。

5)菱形搜索算法

菱形搜索算法(DiamondSearch，DS)又被稱為鉆石搜索算法，1997年由ShanZhu和Kai-KuangMa提出，1999年10月被MPEG-4國際標準采納并收入驗證模型。作為采用固定模板進行搜索的算法中優(yōu)秀的算法之一，DS算法利用了實際視頻序列中運動矢量存在的中心偏置的特點，基于搜索模板形狀和大小的考慮，采用了兩種搜索模板，分別是有9個搜索點的大菱形搜索模板(LargeDiamondSearchPattern，LDSP)和有5個搜索點的小菱形搜索模板(SmallDiamondSearchPattern，SDSP)。DS算法的具體步驟如下：

(1)以搜索窗的中心點為中心，使用LDSP在中心點和周圍8個點處進行搜索，經(jīng)過匹配計算，如果最小MBD值點位于LDSP的中心點，則轉(zhuǎn)(3)；否則，轉(zhuǎn)(2)。

(2)以(1)中得到的最小MBD值對應(yīng)的點為中心，開始一個新的LDSP，如果最小MBD值點位于中心點，則轉(zhuǎn)(3)；否則，重復(fù)執(zhí)行(2)。

(3)以(1)中得到的最小MBD值對應(yīng)的點為中心，使用SDSP在中心點和周圍4個點處進行搜索，找出最小MBD對應(yīng)的點，該點的位置即對應(yīng)最優(yōu)運動矢量。如圖2-7(a)所示，左邊為LDSP，右邊為SDSP，它們分別構(gòu)成一個大菱形和一個小菱形；如圖2-7(b)所示，使用DS算法經(jīng)過5步搜索得到運動矢量(-4，-2)，其中第一次搜索得到最小MBD點(-1，-1)，然后第二次在該點為中心的大菱形上搜索到最小MBD點(-3，-1)，再第三次以該點為中心的大菱形上搜索到最小MBD點(-4，-2)，再第四次以節(jié)點為中心的大菱形上搜索到最小MBD點(-4，-2)，因該最小MBD點是大菱形的中心，所以第五次以小菱形模塊搜索，得到了運動矢量(-4，-2)。其中第一次搜索9個點，第二次增加了3個點(邊點)，第三次增加了5個點(角點)，第四次增加了3個點(邊點)，最后一次為SDSP，增加了5個點，總共搜索點數(shù)為24，前4次使用LDSP，最后一次則使用SDSP。圖2-7菱形搜索算法

DS算法利用了運動矢量的中心偏置特點，并通過大量的視頻統(tǒng)計規(guī)律和實驗論證，選擇了不同大小的LDSP和SDSP搜索模板。它首先用LDSP搜索，這樣可以進行粗定位，因為LDSP模板的搜索步長大，有很廣的搜索范圍，使搜索過程不會陷于局部最小；當LDSP搜索后，可以認為最優(yōu)點就在LDSP周圍3×3范圍內(nèi)，這時再使用SDSP來準確搜索，使搜索有比較好的準確性，所以它擁有比其他算法更優(yōu)越的性能。此外，使用DS進行搜索時，它的兩個步驟之間相關(guān)性很強，只需在模板移動時對幾個新的檢測點處進行匹配計算，因此搜索速度也得到了提高。由于實際所拍攝的視頻都具有使景物運動趨于水平或垂直方向的運動狀態(tài)，因此菱形搜索模式具有相當好的搜索效果。正是由于DS算法的這些優(yōu)良特性，近年來出現(xiàn)了許多基于DS的改進算法，如C.H.Cheung等人在2001年提出的十字形—菱形搜索算法(Cross-DiamondSearch，CDS)，W.G.Zheng和I.Ahmad等人提出的自適應(yīng)可伸縮菱形搜索法(AdaptiveMotionSearchwithElasticDiamond，AMSED)，A.M.Tourapis和G.C.Au等人提出的高級菱形區(qū)域搜索法(AdvancedDiamondZonalSearch，ADZS)等，在性能上都獲得了不同程度的提高。

6)基于塊的梯度下降搜索算法

基于塊的梯度下降搜索算法(Block-BasedGradientDescendSearch，BBGDS)是1996年由Lurng-KuoLiu和EphraimFeig提出的。與其他快速搜索算法一樣，BBGDS算法是基于以下假設(shè)進行的：運動估計的匹配誤差隨著搜索方向沿著全局最小塊誤差MBD的位置移動而單調(diào)減少，并且誤差曲面函數(shù)是單調(diào)的。BBGDS算法充分利用了運動矢量的中心偏置特性，其搜索的模板是由搜索中心鄰近3×3的9個點構(gòu)成的。與TSS和NTSS相比，BBGDS不限定搜索的步數(shù)。BBGDS某一步對匹配點進行計算時，若最小MBD值點位于中心位置或者已經(jīng)達到搜索窗口的邊緣，則停止搜索。BBGDS算法的具體步驟如下：

(1)以當前塊搜索窗中心(0，0)為中心，使用步長為1的3×3搜索窗對周圍的9個點進行搜索。

(2)如果最小MBD值點在搜索窗的中心，則結(jié)束當前搜索，設(shè)置運動矢量為(0，0)；否則以上一步的MBD值點為中心，重復(fù)(1)進行搜索。如圖2-8(a)所示，BBGDS算法的第1步以①點為中心，若最小MBD值點為①點所在位置，則得到運動矢量，搜索結(jié)束；否則第2步的中心點可能是②點(邊點，需要增加三個搜索點)或者③點(角點，需要增加5個搜索點)。圖2-8(b)演示了使用BBGDS搜索到運動矢量(4，-2)的過程，點(1，0)、(2，-1)、(3，-1)、(4，-2)是依次搜索的MBD點。BBGDS算法初始搜索時利用了運動矢量的中心偏置特征來搜索匹配塊，BBGDS算法匹配的每一步中都對塊進行搜索，而不是對單純的點進行搜索，降低了陷入局部最優(yōu)點的可能性；BBGDS算法對搜索模式中的一個小搜索塊(3×3)進行匹配，找出最匹配的點并設(shè)定梯度下降方向，沿著這個方向進行運動矢量的搜索，這樣加快了搜索的速度，從而大大降低了算法的復(fù)雜度。圖2-8基于塊的梯度下降搜索算法此外，還有一些快速搜索算法，如二維對數(shù)搜索法、交叉搜索法、鉆石搜索法、運動矢量場自適應(yīng)搜索算法、遺傳搜索法等。上面介紹的都是基于整數(shù)像素精度的，若需要進行分數(shù)精度搜索，可以在各個算法最后一步的最佳匹配點鄰域內(nèi)實行插值操作，然后進行分數(shù)精度搜索。

2.5基于網(wǎng)格的運動估計

由于塊匹配算法使用規(guī)則的塊模型，各個塊中的運動參數(shù)都是獨立規(guī)定的。除非鄰近的塊的運動參數(shù)被約束得非常平滑，一般所估計的運動場通常是不連續(xù)的，有時還是混亂的(如圖2-9(a)所示)。解決這個問題的一個辦法是采用基于網(wǎng)格的運動估計。如圖2-9(b)所示，當前幀被一個網(wǎng)格所覆蓋，運動估計的問題是尋找每一個節(jié)點(這里的節(jié)點指任意形狀的運動區(qū)域的部分邊界特征點)的運動，使得當前幀中每一個元素內(nèi)(即任意形狀的運動區(qū)域)的圖案與參考幀中相應(yīng)的變形元素很好地匹配。圖2-9兩幀之間的運動估計在基于網(wǎng)格表示的運動估計中，每一個運動區(qū)域內(nèi)各點的運動矢量是由該區(qū)域的節(jié)點的運動矢量內(nèi)插得到的。只要當前幀的節(jié)點仍構(gòu)成一個可行的網(wǎng)格，基于網(wǎng)格的運動表示就保證是連續(xù)的，從而不會有與基于塊的表示相關(guān)聯(lián)的塊失真?；诰W(wǎng)格表示的另一個優(yōu)點是，它能夠連續(xù)地跟蹤相繼幀上相同的節(jié)點集，這在需要物體跟蹤的應(yīng)用中是很好的。如圖2-10所示，可以為初始幀生成一個網(wǎng)格，然后在每兩幀間估計其節(jié)點的運動。每一個新幀都使用前一幀所產(chǎn)生的網(wǎng)格，使得相同的節(jié)點集在所有的幀內(nèi)得到跟蹤。這在基于塊的表示是不可能做到的。圖2-10基于網(wǎng)格的運動、跟蹤基于網(wǎng)格的運動估計的主要步驟有：

(1)建立網(wǎng)格，希望每個多邊形單元內(nèi)的點具有相同的運動特性，這要求節(jié)點盡量多，但是過多的節(jié)點會產(chǎn)生大量的運動信息，這是視頻壓縮所不希望看到的，通常網(wǎng)格可分為規(guī)則網(wǎng)格和自適應(yīng)網(wǎng)格兩種。

(2)網(wǎng)格節(jié)點的運動估計，估計網(wǎng)格節(jié)點的運動需要最小化位移幀差函數(shù)，可以基于一階或二階梯度進行迭代，通?；诙A梯度的迭代收斂速度較快，但很容易得到較差的局部最小值。各個算法估計節(jié)點運動矢量的先后順序也有所不同，有的按光柵掃描順序估計每個節(jié)點的運動，有的根據(jù)節(jié)點處圖像梯度值進行排序估計，也有的將節(jié)點分組進行估計。圖2-11給出了采用網(wǎng)格運動估計與塊匹配運動估計獲得的預(yù)測圖像的對比，可以看出，基于網(wǎng)格運動估計方法得到的預(yù)測圖像明顯優(yōu)于全搜索塊匹配算法的圖像。

使用基于網(wǎng)格運動估計方法時，其模型可以看做橡膠板的變形，它是各處連續(xù)的。在視頻序列中，物體邊界處的運動經(jīng)常是不連續(xù)的，更精確的表示可以對不同的物體使用分離的網(wǎng)格。與基于塊的表示一樣，基于網(wǎng)格的運動估計的精度依賴于節(jié)點數(shù)。只要使用足夠數(shù)量的節(jié)點，就可以重現(xiàn)非常復(fù)雜的運動場。為了使所需要的節(jié)點數(shù)最小，網(wǎng)格的選擇應(yīng)該自適應(yīng)成像場景，使每個元素中的真實運動是平滑的(即可以由節(jié)點的運動精確地內(nèi)插)。如果使用一個常規(guī)的網(wǎng)格，那么為了精確地近似運動場就需要大量的節(jié)點。圖2-11網(wǎng)格運動估計與塊匹配運動估計預(yù)測圖像對比

2.6基于區(qū)域的運動估計

2.6.1概述

在一個三維場景中，通常存在不同類型的運動(可能屬于不同類型的物體或一個物體的不同部分)。基于區(qū)域的運動估計的基本思想是:將視頻圖像分割為多個區(qū)域，每個區(qū)域?qū)?yīng)一個特定的運動，然后為每個區(qū)域估計運動參數(shù)。由于真實的物體運動通常不能用簡單的平移模型表示，因此，區(qū)域運動模型一般可使用仿射模型、雙線性模型和投影運動模型?；趨^(qū)域的運動估計方法有：

(1)區(qū)域優(yōu)先。首先基于當前幀的紋理、邊緣信息進行區(qū)域分割，然后估計每個區(qū)域的運動參數(shù)，此方法被稱為區(qū)域優(yōu)先。

(2)運動優(yōu)先。首先估計整個運動場，可以由前面提到的基于光流、像素、塊和網(wǎng)格等方法得到，然后對運動場進行分割，使得每個區(qū)域都可以用一個參數(shù)模型描述，此方法被稱為運動優(yōu)先。

(3)聯(lián)合區(qū)域分割和運動估計。該方法將區(qū)域分割和運動估計聯(lián)合進行，一般采用迭代法交替進行區(qū)域分割和運動參數(shù)估計。2.6.2區(qū)域分割與運動估計

1.區(qū)域優(yōu)先的方法

對于較簡單的視頻圖像，如視頻電話、視頻會議等，可以基于圖像的邊緣信息進行區(qū)域分割，也可以使用區(qū)域連接增長的方法得到區(qū)域分割。

當前幀區(qū)域分割完畢后，需要為每個區(qū)域估計運動參數(shù)，令ψ1(x)和ψ2(x)表示當前幀和參考幀，ψ1(x)中第n個區(qū)域表示為Rn，Rn中像素x的運動表示為d(x；an)。其中，an表示區(qū)域Rn的運動參數(shù)矢量，它可以是仿射模型、雙線性模型和投影運動模型中的任意一種。定義區(qū)域Rn上的誤差函數(shù)為

(2-24)

2.運動優(yōu)先的方法

1)聚類

對于每個區(qū)域的運動模型是純平移的情況，采用自動聚類分割方法(例如K均值方法)把所有具有類似運動矢量的空間相連的像素分組到一個區(qū)域。該分割過程是一個迭代過程，從一個初始分割開始計算每個區(qū)域的平均運動矢量(稱為質(zhì)心)，然后每個像素被重新劃分到其質(zhì)心最接近這個像素的運動矢量的區(qū)域，從而產(chǎn)生一個新的分割，重復(fù)這兩步，直到分割不再發(fā)生變化為止。在分割過程中，由于沒有考慮空間的連通性，得到的區(qū)域可能包含空間不連通像素，這樣在迭代的末尾可以加一個后處理步驟，以改善所得到區(qū)域的空間連通性。當每個區(qū)域的運動模型不是一個簡單的平移時，因為不能用運動矢量間的相似性作為準則來進行聚類，這樣基于運動的聚類就較復(fù)雜，此時可以給像素鄰域分配一個映射運動模型，計算運動模型的參數(shù)矢量，然后以運動參數(shù)矢量為基本的觀察量進行類似的聚類迭代過程，如果運動場由基于網(wǎng)格或基于可變形塊的方法得到，就可以將運動參數(shù)矢量相近的網(wǎng)格單元或圖像塊合并成區(qū)域。

2)分層

實際中，可以把運動場分解為不同的層，用第一層表示主導(dǎo)的運動，第二層表示次主導(dǎo)的運動，依此類推。這里，運動的主導(dǎo)性是由進行相應(yīng)運動的區(qū)域范圍決定的。主導(dǎo)的運動通常反映攝像機的運動，它影響整個區(qū)域。例如，在網(wǎng)球比賽的視頻剪輯中，背景是第一層，一般進行一致的全局運動；運動員是第二層，它通常包含對應(yīng)于身體不同部位的運動的幾個子物體級的運動；球拍是第三層；球是第四層。為了提取不同層的運動參數(shù)，可以遞歸地使用健壯估計方法。首先，嘗試使用單個參數(shù)集來模型化整個幀的運動場，并且連續(xù)地從剩余的內(nèi)圍層組中去掉外露層像素，直到所有的內(nèi)圍層組中的像素能夠被很好地模型化。這樣便產(chǎn)生了第一個主導(dǎo)區(qū)域(相應(yīng)于內(nèi)圍層區(qū)域)和與之相關(guān)的運動。然后對剩余的像素(外露層區(qū)域)應(yīng)用同樣的方法，確定次主導(dǎo)區(qū)域及其運動。持續(xù)進行這個過程直到?jīng)]有外露層像素為止。同前面一樣，在迭代的末尾可啟用后處理以改善所得區(qū)域的空間連通性。為了使這種方法能很好地工作，在任何一次迭代中，內(nèi)圍層區(qū)域都必須明顯大于外露層區(qū)域。這意味著最大的區(qū)域必須大于所有其他區(qū)域的聯(lián)合，次最大區(qū)域必須大于剩余區(qū)域的聯(lián)合。這個條件在大多數(shù)視頻場景中是滿足的，它通常含有一個靜止的覆蓋大部分圖像的背景和具有變化尺寸的不同的運動物體。

3.聯(lián)合區(qū)域分割和運動估計的方法

從理論上講，可以把區(qū)域分割圖和每個區(qū)域運動參數(shù)的聯(lián)合估計公式轉(zhuǎn)換為一個最優(yōu)化問題，最小化目標函數(shù)可以是運動補償預(yù)測誤差和區(qū)域平滑度量的結(jié)合。然而，因為高維的參數(shù)空間和這些參數(shù)之間復(fù)雜的相互依賴關(guān)系，解決這個最優(yōu)化的問題是困難的。在實際應(yīng)用中，經(jīng)常采用次最優(yōu)化的方法，即輪換地進行分割估計和運動參數(shù)估計?；诔跏嫉姆指睿烙嬅恳粋€區(qū)域的運動，在下一次迭代中，優(yōu)化這個分割。例如，去掉每個預(yù)測誤差大的區(qū)域中的外露層像素，合并共用相似運動模型的像素，然后重新估計每個優(yōu)化區(qū)域的運動參數(shù)，持續(xù)這個過程直到分割圖不再發(fā)生變化為止。圖2-12給出了該方法的區(qū)域分割和運動估計結(jié)果。圖2-12聯(lián)合區(qū)域分割與運動估計結(jié)果另一個方法是以分層的方式估計區(qū)域及其有關(guān)的運動，這類似于前面所述的分層方法。這里假定每一個點的運動矢量都是已知的，使用一個運動參數(shù)集表示各個運動矢量所造成的匹配誤差來確定最主導(dǎo)運動區(qū)域(即內(nèi)圍層)，這實質(zhì)上是前面介紹的間接健壯估計法。在聯(lián)合區(qū)域分割和運動估計方法中，為了從剩余的像素中提取次主導(dǎo)區(qū)域和相關(guān)運動，可以使用直接健壯估計法，即通過最小化這些像素的預(yù)測誤差來直接估計運動參數(shù)。參數(shù)一旦確定，通過檢驗這個像素的預(yù)測誤差，就可以確定這個像素是否屬于內(nèi)圍層