劉龍，宋琦軍，趙太飛，元向輝

(1. 西安理工大學(xué) 自動(dòng)化學(xué)院，陜西 西安710048；2. 西安交通大學(xué) 電信學(xué)院，陜西 西安 710049；3. 中國(guó)電子設(shè)備系統(tǒng)工程公司，北京100091)

1 引言

基于塊匹配的運(yùn)動(dòng)估計(jì)是視頻壓縮編碼中的必要環(huán)節(jié)。迄今為止，不同的國(guó)際視頻壓縮編碼標(biāo)準(zhǔn)均采用了塊匹配（BMA）算法進(jìn)行運(yùn)動(dòng)估計(jì)，如H.261、H.263、MPEG-1、MPEG-2、MPEG-4 和H.264等編碼標(biāo)準(zhǔn)。大量的數(shù)據(jù)測(cè)試表明，運(yùn)動(dòng)估計(jì)的運(yùn)算量非常大，以至于影響視頻編碼的實(shí)時(shí)性能，快速有效的運(yùn)動(dòng)估計(jì)算法對(duì)于高質(zhì)量視頻編碼具有重要意義。

目前，基于塊匹配的快速運(yùn)動(dòng)估計(jì)算法涉及了搜索模式、初始搜索點(diǎn)預(yù)測(cè)、自適應(yīng)機(jī)制等方法。搜索模式的設(shè)計(jì)思路是盡可能根據(jù)運(yùn)動(dòng)矢量分布的特點(diǎn)設(shè)計(jì)合理匹配點(diǎn)陣形狀，從而減少搜索收斂前的搜索點(diǎn)數(shù)；初始搜索點(diǎn)的預(yù)測(cè)是使得搜索范圍盡可能接近最終收斂點(diǎn)從而減少運(yùn)算量；自適應(yīng)技術(shù)主要是根據(jù)視頻信息進(jìn)行一定分析并對(duì)運(yùn)動(dòng)估計(jì)進(jìn)行分類(lèi)，根據(jù)不同類(lèi)別采用不同的搜索模式，這樣能夠起到一定的優(yōu)化運(yùn)算，從而提高了運(yùn)算速度。目前，主流的運(yùn)動(dòng)估計(jì)算法是上述3種方法的綜合實(shí)現(xiàn)。

典型的搜索模式算法包括三步法[1]（TSS）、四步法[2](FSS)和鉆石法[3](DS)等，其中，鉆石法最為成功，被MPEG-4標(biāo)準(zhǔn)所采納。Tourapis A M等人在文獻(xiàn)[4]中首次引入了對(duì)初始搜索位置的預(yù)測(cè)；在文獻(xiàn)[5]中，Nisar H等人將時(shí)間信息分別表示為MVTR(n - 1 )、 M VTB(n -1)、 M Vp( n- 1 )，空間信息分別表示為 M VSL(n)、 M VSA(n)，采用了時(shí)間和空間信息的均值或中值進(jìn)行預(yù)測(cè)，Lin Zhaohua[6]等人定義了局部運(yùn)動(dòng)程度(LMA, local motion activity)來(lái)衡量當(dāng)前宏塊與相鄰宏塊的運(yùn)動(dòng)一致性程度，LMA被分為低程度（ L ≤L1）、中等程度(L1＜L≤ L2)和高程度（ L ＞L2），當(dāng)LMA為低程度時(shí)，搜索策略選取空間預(yù)測(cè)器初始化搜索中心起始點(diǎn)的位置，當(dāng)LMA為中等或高程度時(shí)，搜索策略選取空間和時(shí)間預(yù)測(cè)器中 SAD值最小的為搜索中心的起始點(diǎn)。隨著快速運(yùn)動(dòng)估計(jì)算法的發(fā)展，一些新的算法提出了自適應(yīng)選擇搜索模式的機(jī)制，Hosur P I[7]和 Tourapis A M[4]等人首現(xiàn)提出了自適應(yīng)搜索算法MVFAST和PMVFAST，采用空間上鄰近被預(yù)測(cè)運(yùn)動(dòng)矢量的3個(gè)運(yùn)動(dòng)矢量中最大的運(yùn)動(dòng)矢量與某個(gè)閾值比較進(jìn)行矢量分類(lèi)，并根據(jù)不同的運(yùn)動(dòng)矢量分類(lèi)選擇不同的搜索模式；Ahmad I[8]等人根據(jù)運(yùn)動(dòng)矢量大小判斷視頻信號(hào)在時(shí)—空間上運(yùn)動(dòng)劇烈程度；Lin Zhaohua[9]和ChenXiaolin等[10]則通過(guò)統(tǒng)計(jì)分析相鄰運(yùn)動(dòng)矢量預(yù)測(cè)運(yùn)動(dòng)的劇烈程度，并根據(jù)運(yùn)動(dòng)的劇烈程度調(diào)整搜索的范圍，根據(jù)不同的推斷自適應(yīng)地選擇不同的搜索模式的方式提高運(yùn)動(dòng)估計(jì)的速度，方法本質(zhì)與文獻(xiàn)[8]類(lèi)似。Lee Sangkeun[11]首先對(duì)視頻場(chǎng)景的內(nèi)容進(jìn)行了分析，并自適應(yīng)調(diào)整給定的搜索范圍； Paramkusam等[12]根據(jù)相鄰幀像素塊的差值預(yù)測(cè)初始搜搜位置減少計(jì)算時(shí)間；Zaynab Ahmed等[13]根據(jù)空間相鄰的運(yùn)動(dòng)矢量的均值預(yù)測(cè)當(dāng)前與估算運(yùn)動(dòng)矢量的大小，并根據(jù)預(yù)測(cè)結(jié)果采用動(dòng)態(tài)十字搜索模式進(jìn)行運(yùn)動(dòng)估計(jì)。另外，趙志杰等人[14]針對(duì)多視角視頻編碼中的運(yùn)動(dòng)估計(jì)問(wèn)題，利用幀間、視角間相關(guān)性，建立預(yù)測(cè)矢量狀態(tài)集合，通過(guò)馬爾科夫鏈模型的狀態(tài)轉(zhuǎn)移概率，對(duì)預(yù)測(cè)矢量進(jìn)行提前測(cè)試，然后利用提前退出準(zhǔn)則，實(shí)現(xiàn)快速運(yùn)動(dòng)矢量估計(jì)。谷會(huì)濤等人[15]提出了一種基于多搜索中心預(yù)測(cè)和搜索范圍動(dòng)態(tài)調(diào)整的快速算法，對(duì)當(dāng)前宏塊時(shí)間和空間上相鄰塊的運(yùn)動(dòng)向量進(jìn)行分析, 得出多個(gè)預(yù)測(cè)向量作為運(yùn)動(dòng)估計(jì)的搜索中心，降低了運(yùn)動(dòng)估計(jì)的運(yùn)算量。

綜上所述，視頻快速運(yùn)動(dòng)估計(jì)算法設(shè)計(jì)關(guān)鍵在于能否建立合理的預(yù)測(cè)方法，并設(shè)計(jì)相應(yīng)的搜索模式?，F(xiàn)有的算法都不同程度的依賴(lài)了空間或時(shí)間信息對(duì)待估計(jì)運(yùn)動(dòng)矢量進(jìn)行預(yù)測(cè)，同時(shí)采用自適應(yīng)選擇搜索模式已達(dá)到盡可能快速收斂從而提高估計(jì)速度的目的，但值得指出的是實(shí)際上很多的視頻序列會(huì)出現(xiàn)較復(fù)雜運(yùn)動(dòng)場(chǎng)景，這時(shí)空間和時(shí)間上的視頻信號(hào)相關(guān)性較弱，往往運(yùn)動(dòng)特征會(huì)出現(xiàn)突變，使得預(yù)測(cè)產(chǎn)生很大的誤差，僅依據(jù)運(yùn)動(dòng)矢量大小、視頻內(nèi)容以及統(tǒng)計(jì)分析來(lái)對(duì)待估計(jì)運(yùn)動(dòng)矢量進(jìn)行分類(lèi)顯然是不充分的，應(yīng)該看到運(yùn)動(dòng)矢量在時(shí)—空上的可預(yù)測(cè)性與其在時(shí)間和空間上的分布和變化規(guī)律是緊密聯(lián)系的，如不能很好的根據(jù)運(yùn)動(dòng)矢量在時(shí)間和空間上的特點(diǎn)進(jìn)行分類(lèi)處理，那么在運(yùn)動(dòng)復(fù)雜的情況下不僅不能提高估計(jì)速度反而會(huì)使估計(jì)速度下降。本文將重點(diǎn)研究如何根據(jù)運(yùn)動(dòng)矢量時(shí)—空特性建立更加合理有效的預(yù)測(cè)自適應(yīng)機(jī)制，提出了一種新的基于空間運(yùn)動(dòng)相似性的運(yùn)動(dòng)矢量預(yù)測(cè)自適應(yīng)機(jī)制，并將其應(yīng)用到快速運(yùn)動(dòng)估計(jì)算法中提高運(yùn)動(dòng)估計(jì)的速度，克服現(xiàn)有算法的不足。

2 運(yùn)動(dòng)矢量時(shí)—空特性分析

運(yùn)動(dòng)矢量預(yù)測(cè)的準(zhǔn)確性直接受到其時(shí)—空相關(guān)性的影響，相關(guān)性程度高，預(yù)測(cè)的準(zhǔn)確性高；反之，預(yù)測(cè)的準(zhǔn)確性低。本節(jié)將從運(yùn)動(dòng)矢量相關(guān)性程度的角度對(duì)運(yùn)動(dòng)矢量的時(shí)—空特性進(jìn)行分析，并給出運(yùn)動(dòng)矢量在時(shí)間上的變化程度與空間上相似度之間的關(guān)系。

2.1 特性分析

在時(shí)間維度上，運(yùn)動(dòng)矢量的變化程度直接反映了運(yùn)動(dòng)矢量在時(shí)間上的相關(guān)性程度，在相鄰時(shí)間點(diǎn)上變化程度越大，相關(guān)性越弱；反之，相關(guān)性越強(qiáng)。為了分析運(yùn)動(dòng)矢量在時(shí)間上的相關(guān)性特點(diǎn)，首先定義運(yùn)動(dòng)矢量的變化程度如下。

表 1顯示了運(yùn)動(dòng)矢量在時(shí)間上變化的統(tǒng)計(jì)數(shù)據(jù)。統(tǒng)計(jì)數(shù)據(jù)結(jié)果顯示大多數(shù)的運(yùn)動(dòng)矢量在連續(xù) 2個(gè)運(yùn)動(dòng)矢量場(chǎng)之間不變化或變化很小。經(jīng)過(guò)計(jì)算，對(duì)于運(yùn)動(dòng)復(fù)雜度低的視頻序列，超過(guò)70%的運(yùn)動(dòng)矢量沒(méi)有明顯的變化；超過(guò)90%的運(yùn)動(dòng)矢量變化幅度小于3個(gè)單位像素；變化幅度超過(guò)3個(gè)單位的運(yùn)動(dòng)矢量很少；對(duì)于運(yùn)動(dòng)復(fù)雜度高的視頻序列，有30%左右的運(yùn)動(dòng)矢量沒(méi)有明顯的變化；超過(guò)60%的運(yùn)動(dòng)矢量變化幅度大于3個(gè)單位像素，從上述數(shù)據(jù)中可以看出，對(duì)于運(yùn)動(dòng)復(fù)雜程度不同的視頻序列，運(yùn)動(dòng)矢量在時(shí)間軸上有的相關(guān)性弱，這表明在該情況下，時(shí)間上的可預(yù)測(cè)性具有不穩(wěn)定性。綜上所述，可以得到以下結(jié)論：在視頻運(yùn)動(dòng)復(fù)雜程度高時(shí)，運(yùn)動(dòng)矢量在時(shí)間上的變化劇烈，由此導(dǎo)致了在時(shí)間上的可預(yù)測(cè)性的降低；相反地，在視頻運(yùn)動(dòng)復(fù)雜程度低時(shí)，運(yùn)動(dòng)矢量在時(shí)間上的變化平緩，運(yùn)動(dòng)矢量在時(shí)間上的可預(yù)測(cè)性增高。

表1 運(yùn)動(dòng)矢量在時(shí)間上的變化統(tǒng)計(jì)/像素

在空間上，局部區(qū)域的相似性程度直接反映了運(yùn)動(dòng)的復(fù)雜程度與空間相關(guān)性程度，相似度越差，運(yùn)動(dòng)復(fù)雜程度越高，相關(guān)性程度越低；反之，運(yùn)動(dòng)復(fù)雜程度越低，相關(guān)性程度越高。本文采用局部區(qū)域運(yùn)動(dòng)矢量的方差來(lái)描述空間運(yùn)動(dòng)的相似度。假定MBk,i,j是k幀中坐標(biāo)為(i, j)的宏塊，i和 j分別表示宏塊的橫縱坐標(biāo)； Rk,i,j表示包含宏塊 M Bk,i,j及其相鄰宏塊的集合；Sk,i,j表示集合 Rk,i,j中所有宏塊所對(duì)應(yīng)的運(yùn)動(dòng)矢量形成的集合。定義集和 Sk,i,j的均值和方差如下

其中， Rk,i,j包含了 M Bk,i,j及其相鄰的8個(gè)宏塊。

綜上所述，可以得到以下結(jié)論：在視頻復(fù)雜程度高的局部區(qū)域，運(yùn)動(dòng)矢量在空間上的相似度較差，相關(guān)性程度低；相反地，在視頻運(yùn)動(dòng)復(fù)雜程度低的局部區(qū)域，運(yùn)動(dòng)矢量在空間上的相似度較高，相關(guān)性程度高。

2.2 運(yùn)動(dòng)矢量的時(shí)空特性

運(yùn)動(dòng)矢量的空間特性與時(shí)間特性存在一定的關(guān)系，也可以說(shuō)局部區(qū)域運(yùn)動(dòng)矢量的變化程度和相似度之間存在著某種關(guān)系。在運(yùn)動(dòng)復(fù)雜度高的區(qū)域，運(yùn)動(dòng)矢量的局部區(qū)域相似度較低，其時(shí)間上的變化程度也會(huì)較大；而在運(yùn)動(dòng)復(fù)雜度低的區(qū)域，運(yùn)動(dòng)矢量的局部區(qū)域相似程度較高，其時(shí)間上的變化程度也會(huì)較小。本文對(duì) 20視頻序列計(jì)算和Lk,i,j值，繪制其在二維坐標(biāo)系中，局部運(yùn)動(dòng)相關(guān)性程度和運(yùn)動(dòng)矢量的變化程度可以近似的看作線(xiàn)性關(guān)系。圖 1顯示了視頻序列 Foreman、Flower Garden、Stefan和Hall monitor的結(jié)果。本文采用線(xiàn)性模型描述運(yùn)動(dòng)矢量的變化程度和相似度之間的關(guān)系可表示為

圖1 2δ和L的關(guān)系

3 本文提出的快速運(yùn)動(dòng)估計(jì)算法

3.1 運(yùn)動(dòng)矢量的分類(lèi)

根據(jù)2.1節(jié)的分析，可根據(jù)L值與閾值進(jìn)行比較將運(yùn)動(dòng)矢量分為3種類(lèi)型，即不可預(yù)測(cè)運(yùn)動(dòng)矢量（NPMV, no predictable motion vector）、中度可預(yù)測(cè)運(yùn)動(dòng)矢量（MPMV, medial predictable motion vector）和高度可預(yù)測(cè)運(yùn)動(dòng)矢量（HPMV, high predictable motion vector）。設(shè)定運(yùn)動(dòng)矢量的分類(lèi)閾值為L(zhǎng) T= ，運(yùn)動(dòng)矢量可以被分為 3類(lèi)：無(wú)變化的運(yùn)動(dòng)矢量(0L=)；小變化運(yùn)動(dòng)矢量（0LT＜≤）；大變化運(yùn)動(dòng)矢量(LT＞)。分類(lèi)過(guò)程可以定義為

根據(jù)式(4)和式(5)可以被轉(zhuǎn)換成下述等式

3.2 如何計(jì)算系數(shù)a和b

式（6）中的系數(shù)a和b對(duì)于不同的視頻有不同的值。在運(yùn)動(dòng)估計(jì)的初始階段，式（6）中的系數(shù)a和b首先被初始化。采用全搜索法估計(jì)兩幀運(yùn)動(dòng)矢量場(chǎng)。通過(guò)最小二乘法計(jì)算系數(shù)a和b，其過(guò)程描述如下。

假定運(yùn)動(dòng)矢量場(chǎng)中有N個(gè)運(yùn)動(dòng)矢量；通過(guò)式(1)和式(3)計(jì)算

預(yù)測(cè)誤差為

則平方誤差如下

最終的計(jì)算式如下

3.3 搜索模式

根據(jù)3.1節(jié)的運(yùn)動(dòng)矢量分類(lèi)，本文提出了小鉆石模式（SDSP）和方形模式（SSP），如圖2所示。

圖2 搜索模式

1) 小鉆石搜索策略

步驟1 初始化搜索中心位置；

步驟2 對(duì)SDSP的5個(gè)點(diǎn)進(jìn)行像素塊失真計(jì)算。如果最小失真值出現(xiàn)在中心點(diǎn)，那么進(jìn)行步驟4；如果最小失真值沒(méi)有出現(xiàn)在中心點(diǎn)，則進(jìn)行步驟3；

步驟 3 以上一步驟中最小的失真值點(diǎn)為中心進(jìn)行新的SDSP搜索計(jì)算。如果最小失真值出現(xiàn)在中心點(diǎn)，那么進(jìn)行步驟 4；如果最小失真值沒(méi)有出現(xiàn)在中心點(diǎn)，則重復(fù)該步驟；

步驟 4 以上一步驟中最小的失真值點(diǎn)為終止搜索點(diǎn)計(jì)算運(yùn)動(dòng)矢量。

2) 方形搜索策略

步驟1 初始化搜索中心位置；

步驟2 對(duì)SSP的9個(gè)點(diǎn)進(jìn)行像素塊失真計(jì)算；

步驟 3 以上一步驟中最小的失真值點(diǎn)為中心進(jìn)行SDSP搜索計(jì)算。如果最小失真值出現(xiàn)在中心點(diǎn)，那么進(jìn)行步驟 5，如果最小失真值沒(méi)有出現(xiàn)在中心點(diǎn)，則進(jìn)行步驟4；

步驟 4 以上一步驟中最小的失真值點(diǎn)為中心進(jìn)行新的SDSP搜索計(jì)算。如果最小失真值出現(xiàn)在中心點(diǎn)，那么進(jìn)行步驟 5；如果最小失真值沒(méi)有出現(xiàn)在中心點(diǎn)，則重復(fù)該步驟；

步驟 5 以上一步驟中最小的失真值點(diǎn)為終止搜索點(diǎn)計(jì)算運(yùn)動(dòng)矢量。

3.4 快速運(yùn)動(dòng)估計(jì)算法

本文提出的運(yùn)動(dòng)估計(jì)算法分為3個(gè)步驟。假定在運(yùn)動(dòng)估計(jì)的次序是從左到右、從上到下并且k幀的運(yùn)動(dòng)矢量是已知的。對(duì) k + 1幀運(yùn)動(dòng)矢量場(chǎng)進(jìn)行估計(jì)，估計(jì)過(guò)程如下：1→) 系 數(shù)a和b進(jìn)行初始化計(jì)算；2) 通過(guò)式（6）對(duì)進(jìn)行分類(lèi); 3) 根據(jù)不同的分類(lèi)結(jié)果，采用不同的搜索策略對(duì)進(jìn)行估計(jì)。當(dāng) 屬于不可預(yù)測(cè)，用中心位置點(diǎn)作為搜索初始點(diǎn)，采用鉆石搜索法對(duì)進(jìn)行估計(jì)；當(dāng)→ 屬于中度可預(yù)測(cè)，用作為搜索初始點(diǎn)，采用方形搜索策略對(duì) 進(jìn)行估計(jì)；當(dāng) 屬于高度可預(yù)測(cè)，用作為搜索初始點(diǎn)，采用小鉆石搜索策略對(duì) 進(jìn)行估計(jì)。

4 實(shí)驗(yàn)分析

本節(jié)將對(duì)運(yùn)動(dòng)估計(jì)算法性能作測(cè)試，并且與FS、NTSS、DS、MVFAST[4],PMVFAST[7]和文獻(xiàn)[8~10]、文獻(xiàn)[11]、文獻(xiàn)[12]、文獻(xiàn)[13]的算法進(jìn)行比較分析。在實(shí)驗(yàn)中，采用每幀的灰度計(jì)算運(yùn)動(dòng)矢量。宏塊大小為16 16×。采用峰值信噪比（PSNR）衡量運(yùn)動(dòng)估計(jì)的精度，運(yùn)動(dòng)加速（speed up）來(lái)衡量運(yùn)動(dòng)估計(jì)的速度。實(shí)驗(yàn)平臺(tái)選擇MPEG-4校驗(yàn)?zāi)Ｐ途幋a軟件。采用 TM5碼率控制方案，編碼比特率為500kbit/s、每秒15幀。幀間編碼模式為IPPP…。

實(shí)驗(yàn)選取2個(gè)簡(jiǎn)單運(yùn)動(dòng)序列和多個(gè)復(fù)雜運(yùn)動(dòng)序列進(jìn)行測(cè)試。本文采用 Hall Monitor、Mother &Daughter、Coastguard、Foreman、Table Tennis、Flower Garden，Stefan等7個(gè)視頻序列作測(cè)試。其中，簡(jiǎn)單運(yùn)動(dòng)序列為Hall monitor和Mother & Daughter和Coastguard，視頻場(chǎng)景靜止或運(yùn)動(dòng)緩慢，目標(biāo)運(yùn)動(dòng)緩慢；復(fù)雜運(yùn)動(dòng)序列為 Foreman、Table Tennis、Flower Garden和Stefan，其中，Table Tennis和Stefan屬于局部運(yùn)動(dòng)場(chǎng)景，目標(biāo)運(yùn)動(dòng)劇烈，F(xiàn)lower Garden和Foreman屬于全局運(yùn)動(dòng)場(chǎng)景，場(chǎng)景復(fù)雜并伴隨鏡頭快速移動(dòng)，目標(biāo)有較強(qiáng)烈運(yùn)動(dòng)。

表 2顯示了測(cè)試結(jié)果。對(duì)于視頻序列 Hall monitor、Mother&Daughter和 Coastguard，由于運(yùn)動(dòng)緩慢，運(yùn)動(dòng)矢量在時(shí)—空上具有較強(qiáng)的相關(guān)性，預(yù)測(cè)比較準(zhǔn)確，匹配過(guò)程收斂一般較快，但在運(yùn)動(dòng)目標(biāo)邊緣或內(nèi)部部分區(qū)域會(huì)出現(xiàn)運(yùn)動(dòng)的不一致性，會(huì)導(dǎo)致預(yù)測(cè)失敗，損失估計(jì)時(shí)間，因此文獻(xiàn)[8~13]和本文算法都有相當(dāng)?shù)乃俣忍嵘疚乃惴杂袃?yōu)勢(shì),運(yùn)動(dòng)估計(jì)的精度方面基本相當(dāng)。對(duì)于視頻序列Foreman、Table Tennis、Flower Garden、Stefan，其中，Table Tennis和Stefan由于目標(biāo)運(yùn)動(dòng)劇烈，目標(biāo)區(qū)域運(yùn)動(dòng)矢量相關(guān)性弱，無(wú)法準(zhǔn)確預(yù)測(cè)，對(duì)提升運(yùn)算速度有負(fù)面影響；而對(duì) Foreman和Flower Garden，運(yùn)動(dòng)場(chǎng)景較為復(fù)雜，預(yù)測(cè)受到很大影響，因此文獻(xiàn)[8~13]對(duì)于速度提升并不明顯，而本文算法由于對(duì)運(yùn)動(dòng)矢量的預(yù)測(cè)性進(jìn)行了分類(lèi)處理，避免了錯(cuò)誤預(yù)測(cè)，從而在復(fù)雜場(chǎng)景的運(yùn)動(dòng)估算中具有明顯的速度優(yōu)勢(shì)，在估計(jì)精度上略?xún)?yōu)于其他算法。

表2 運(yùn)動(dòng)估計(jì)算法的PSNR測(cè)試值比較

綜上所述，在復(fù)雜運(yùn)動(dòng)場(chǎng)景下本文提出的算法的合理性保證了不必要匹配點(diǎn)的減少和搜索方向的正確性，有效地克服了其他算法在復(fù)雜運(yùn)動(dòng)場(chǎng)景下的不足，在估計(jì)精度上與其他算法相當(dāng)，充分體現(xiàn)本文算法在提升運(yùn)動(dòng)估計(jì)速度方面的優(yōu)勢(shì)。

表 2顯示了測(cè)試結(jié)果。對(duì)于視頻序列 Hall monitor、Mother&Daughter和 Coastguard，由于運(yùn)動(dòng)緩慢，運(yùn)動(dòng)矢量在時(shí)—空上具有較強(qiáng)的相關(guān)性，預(yù)測(cè)比較準(zhǔn)確，匹配過(guò)程收斂一般較快，但在運(yùn)動(dòng)目標(biāo)邊緣或內(nèi)部部分區(qū)域會(huì)出現(xiàn)運(yùn)動(dòng)的不一致性，會(huì)導(dǎo)致預(yù)測(cè)失敗，損失估計(jì)時(shí)間，因此文獻(xiàn)[8~13]和本文算法都有相當(dāng)?shù)乃俣忍嵘?，但本文算法略有?yōu)勢(shì),運(yùn)動(dòng)估計(jì)的精度方面基本相當(dāng)。對(duì)于視頻序列Foreman、Table Tennis、Flower Garden、Stefan，其中，Table Tennis和Stefan由于目標(biāo)運(yùn)動(dòng)劇烈，目標(biāo)區(qū)域運(yùn)動(dòng)矢量相關(guān)性弱，無(wú)法準(zhǔn)確預(yù)測(cè)，對(duì)提升運(yùn)算速度有負(fù)面影響；而對(duì)Foreman和 Flower Garden，運(yùn)動(dòng)場(chǎng)景較為復(fù)雜，預(yù)測(cè)受到很大影響，因此文獻(xiàn)[8~13]對(duì)于速度提升并不明顯，而本文算法由于對(duì)運(yùn)動(dòng)矢量的預(yù)測(cè)性進(jìn)行了分類(lèi)處理，避免了錯(cuò)誤預(yù)測(cè)，從而在復(fù)雜場(chǎng)景的運(yùn)動(dòng)估算中具有明顯的速度優(yōu)勢(shì)，在估計(jì)精度上略?xún)?yōu)于其他算法。

綜上所述，在復(fù)雜運(yùn)動(dòng)場(chǎng)景下本文提出算法的合理性保證了不必要匹配點(diǎn)的減少和搜索方向的正確性，有效地克服了其他算法在復(fù)雜運(yùn)動(dòng)場(chǎng)景下的不足，在估計(jì)精度上與其他算法相當(dāng)，充分體現(xiàn)本文算法在提升運(yùn)動(dòng)估計(jì)速度方面的優(yōu)勢(shì)。

5 結(jié)束語(yǔ)

本文通過(guò)對(duì)運(yùn)動(dòng)矢量時(shí)—空特性的分析，建立了運(yùn)動(dòng)矢量在時(shí)—空變化的關(guān)系，根據(jù)這一關(guān)系，并對(duì)待估計(jì)運(yùn)動(dòng)矢量進(jìn)行分類(lèi)，采用不同的搜索模式進(jìn)行快速運(yùn)動(dòng)估計(jì)。實(shí)驗(yàn)結(jié)果表明：本文提出的算法克服了其他相關(guān)算法的不足，在各種視頻序列測(cè)試下明顯提高了運(yùn)動(dòng)估計(jì)的速度并且具有與其他運(yùn)動(dòng)估計(jì)算法近似或更好的性能，證明了本文算法的有效性。

[1] LI R, ZENG B, LIOU M L. A new three-step search algorithm for block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(4):438-442.

[2] PO L M, MA W C. A novel four-step search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(5):313-317.

[3] THAM J Y, RANGANATH S, RANGANATH M. A novel unrestricted center biased diamond search algorithm for block motion estimation[J].IEEE Transactions on Circuits and Systems for Video Technology,1998, 8(4):369-377.

[4] TOURAPIS A M, AU O C, LIOU M L. Fast Block Matching Motion Estimation Using Predictive Motion Vector Field Adaptive Search Technique (PMVFAST)[S]. ISO/IEC/JTC12 SC29/WG11 MPEG2000/M5866, 2000.

[5] NISAR H, CHOI T S. Fast motion estimation algorithm based on spatio-temporal correlation and direction of motion vector[J]. Electronics Letters, 2006, 42(24):1384-1385.

[6] LIN Z H, ZOU Y B. A novel fast motion estimation algorithm based on starting search point prediction[A]. 2009 Internation Coference on Measuring Technology Mechatronics Automation[C]. Changsha,China, 2009.746-749.

[7] HOSUR P I, MA K K. Motion vector field adaptive fast motion estimation[A]. Second International Conference On Information, Communications and Signal Processing (ICICS’99)[C]. Singapore, 1999. 7-10.

[8] AHMAD I, ZHENG W G, LUO J C. A fast adaptive motion estimation algorithm[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2006, 16(2):420-427.

[9] SOROUSHMEHR S M R, SAMAVI S, SHIRANI S. Fast block motion estimation based on sorting of prediction vectors[J]. Canadian Journal of Electrical and Computer Engineering, 2010, 35(1):25-32.

[10] CHEN X L, CANAGARAJAH N S, JOSE L N Y. Backward adaptive pixel-based fast predictive motion estimation[J]. IEEE Signal Processing Letters, 2009, 16(5):370-373.

[11] LEE S K. Fast motion estimation based on adaptive search range adjustment and matching error prediction[J]. IEEE Transactions on Consumer Electronics, 2009, 55(2):805-811.

[12] PARAMKUSAM A V, REDDY V S K. New fast motion estimation algorithm in video coding[A]. 2011 IEEE Recent Advances in Intelligent Computational Systems (RAICS)[C]. India, 2011. 441-446.

[13] AHMED Z, HUSSAIN A J, AL-JUMEILY D. Mean predictive block matching(MPBM) for fast block matching motion estimation[A]. 2011 3rd European Workshop on Visual Information Processing (EUVIP)[C].Paris, France, 2011. 67-72.

[14] 趙志杰，范智鵬，金雪松等. 針對(duì)多視角視頻編碼的快速運(yùn)動(dòng)估計(jì)方法[J]. 通信學(xué)報(bào), 2011. 32(10):152-157.ZHAO Z J, FAN Z P, JIN X S, et al. Fast motion estimation in multi-view video coding[J]. Journal on Communications, 2011, 32(10):152-157.

[15] 谷會(huì)濤, 陳書(shū)明, 孫書(shū)為等.多搜索中心的運(yùn)動(dòng)估計(jì)快速算法[J].電子學(xué)報(bào). 2011, 39(3):695-699.GU H T, CHEN S M, SUN S W, et al. Fast motion estimation algorithm based on multi-search centers[J]. Acta Electronica Sinica, 2011,39(3): 152-157.