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

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

2.1二維運(yùn)動(dòng)估計(jì)的基本概念

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

2.2.1參數(shù)模型

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

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

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

1.基于光流方程的方法

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

2.塊運(yùn)動(dòng)模型

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

3.像素遞歸法

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

4.貝葉斯法

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

2.3光流法運(yùn)動(dòng)估計(jì)

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

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

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

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

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

2.4基于塊的運(yùn)動(dòng)估計(jì)

2.4.1塊運(yùn)動(dòng)的兩種模型

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

1.塊平移模型

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

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

(2-8)

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

2.可變形塊運(yùn)動(dòng)模型

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

(1)投影運(yùn)動(dòng)：

(2-9)(2)仿射運(yùn)動(dòng)：(2-10)

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

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

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

(2-12)

對運(yùn)動(dòng)模型式(2-12)左右兩邊作二維傅立葉變換，當(dāng)Δt=1時(shí),

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

(2-13)

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

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

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

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

(2-15)

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

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.塊匹配運(yùn)動(dòng)估計(jì)原理

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

2.塊匹配運(yùn)動(dòng)估計(jì)的匹配準(zhǔn)則

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

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

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

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

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

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

3.典型搜索算法

1)全搜索算法

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

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

2)三步搜索算法

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

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

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

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

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

3)新三步搜索算法

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

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

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

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

4)四步搜索算法

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

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

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

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

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

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

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

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

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

5)菱形搜索算法

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

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

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

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

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

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

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

(1)以當(dāng)前塊搜索窗中心(0，0)為中心，使用步長為1的3×3搜索窗對周圍的9個(gè)點(diǎn)進(jìn)行搜索。

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

2.5基于網(wǎng)格的運(yùn)動(dòng)估計(jì)

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

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

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

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

2.6基于區(qū)域的運(yùn)動(dòng)估計(jì)

2.6.1概述

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

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

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

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

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

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

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

(2-24)

2.運(yùn)動(dòng)優(yōu)先的方法

1)聚類

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

2)分層

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

3.聯(lián)合區(qū)域分割和運(yùn)動(dòng)估計(jì)的方法

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