大學(xué)計(jì)算機(jī)學(xué)院多媒體基礎(chǔ)運(yùn)動(dòng)估計(jì)

運(yùn)動(dòng)估計(jì)基礎(chǔ)陳虎視頻圖像的冗余空間冗余時(shí)間冗余視頻圖像的冗余

視頻序列圖像在時(shí)間上存在很強(qiáng)的相關(guān)性，采用運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償技術(shù)可以消除時(shí)間冗余以提高編碼效率，這種技術(shù)廣泛用于視頻壓縮的一些國(guó)際標(biāo)準(zhǔn)中，如H.261/263/264、MPEG-1/2/4。視頻編碼框架消除時(shí)間冗余當(dāng)前圖像塊與參考圖像對(duì)應(yīng)塊求差值相似圖像塊才能有效消除時(shí)間冗余圖像塊越相似，消除時(shí)間冗余效果越好采用運(yùn)動(dòng)搜索的方法尋找最相似的塊運(yùn)動(dòng)估計(jì)與補(bǔ)償運(yùn)動(dòng)以及運(yùn)動(dòng)搜索時(shí)間上目標(biāo)的空間位移運(yùn)動(dòng)矢量通過(guò)搜索比較，確定相似塊以及運(yùn)動(dòng)矢量的過(guò)程運(yùn)動(dòng)估計(jì)的分類(lèi)全局運(yùn)動(dòng)估計(jì)基于塊的運(yùn)動(dòng)估計(jì)基于象素點(diǎn)的運(yùn)動(dòng)估計(jì)基于區(qū)域的運(yùn)動(dòng)估計(jì)基于網(wǎng)格的運(yùn)動(dòng)估計(jì)時(shí)域運(yùn)動(dòng)估計(jì)頻域運(yùn)動(dòng)估計(jì)（DFT、DCT、DWT）運(yùn)動(dòng)估計(jì)的分類(lèi)a全局運(yùn)動(dòng)估計(jì)c基于塊的運(yùn)動(dòng)估計(jì)b基于象素點(diǎn)的運(yùn)動(dòng)估計(jì)d基于區(qū)域的運(yùn)動(dòng)估計(jì)運(yùn)動(dòng)估計(jì)的分類(lèi)a基于塊的運(yùn)動(dòng)估計(jì)b基于網(wǎng)格的運(yùn)動(dòng)估計(jì)塊匹配運(yùn)動(dòng)估計(jì)因算法簡(jiǎn)單、便于硬件實(shí)現(xiàn)得到廣泛應(yīng)用，本文將對(duì)其進(jìn)行重點(diǎn)討論，下面簡(jiǎn)稱(chēng)其為“運(yùn)動(dòng)估計(jì)”?；趬K的運(yùn)動(dòng)估計(jì)基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認(rèn)為宏塊內(nèi)所有象素的位移量都相同，然后對(duì)每個(gè)宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最相似的塊，即匹配塊，匹配塊與當(dāng)前塊的相對(duì)位移即為運(yùn)動(dòng)矢量。視頻壓縮的時(shí)候，只需保存運(yùn)動(dòng)矢量和殘差數(shù)據(jù)就可以完全恢復(fù)出當(dāng)前塊?；趬K的運(yùn)動(dòng)估計(jì)基于塊的運(yùn)動(dòng)估計(jì)基于塊的運(yùn)動(dòng)估計(jì)基于塊的運(yùn)動(dòng)估計(jì)塊匹配法基本流程分成互不重疊N×N大小的塊，塊遵循物體剛性平動(dòng)的假設(shè)模型根據(jù)一定的匹配準(zhǔn)則和搜索算法，在參考幀中給定的搜索范圍內(nèi)，尋找到當(dāng)前塊的最佳匹配塊

當(dāng)前塊和最佳匹配塊之間的相對(duì)位移就是當(dāng)前塊的運(yùn)動(dòng)矢量

匹配準(zhǔn)則均方誤差：平均絕對(duì)誤差：絕對(duì)誤差：舉例運(yùn)動(dòng)估計(jì)快速算法分類(lèi)分層的和多分辨率的快速塊匹配方法固定搜索模式的快速塊匹配方法基于時(shí)空相關(guān)性和視覺(jué)特性的快速塊匹配方法基于連續(xù)消除的快速塊匹配方法基于象素子抽樣的快速塊匹配方法分層的或多分辨率法在較粗糙的分辨率下預(yù)測(cè)一個(gè)接近的大尺寸的運(yùn)動(dòng)矢量，然后在較高的分辨率下進(jìn)一步修正。稱(chēng)為分層的或多分辨率的運(yùn)動(dòng)估計(jì)快速算法。缺點(diǎn)：計(jì)算過(guò)程復(fù)雜，內(nèi)存需求較大。分層的或多分辨率法象素子抽樣法

通常的匹配準(zhǔn)則是把塊里所有的象素點(diǎn)進(jìn)行計(jì)算和比較，事實(shí)上一個(gè)塊里相鄰象素的差別很小，使得它們之間也存在冗余。子采樣運(yùn)動(dòng)估計(jì)算法就利用了這一事實(shí)，只取其中的一部分象素進(jìn)行計(jì)算，可大大減少計(jì)算量，但同時(shí)降低了準(zhǔn)確性。全搜索法對(duì)搜索區(qū)域的所有位置進(jìn)行窮盡搜索。精度最高計(jì)算復(fù)雜，難以實(shí)時(shí)處理必須研究相應(yīng)的運(yùn)動(dòng)估計(jì)快速算法三步法搜索模板半徑依次減半對(duì)小運(yùn)動(dòng)檢測(cè)效果不好搜索范圍大于7時(shí)，搜索步驟不止三步梯度下降法反復(fù)使用3×3模板進(jìn)行搜索。模板中心處SAD值最小時(shí)結(jié)束。對(duì)大運(yùn)動(dòng)檢測(cè)效果不好四步法

反復(fù)使用5×5方形模板進(jìn)行搜索。模板中心處SAD值最小時(shí)再用3×3模板搜索一次確定最佳匹配位置。菱形法

搜索方式與四步法類(lèi)似，只是搜索模板換為兩個(gè)菱形模板。六邊形法

搜索方式與菱形法類(lèi)似，只是大搜索模板換為一個(gè)六邊形模板。2D對(duì)數(shù)法反復(fù)使用3×3模板進(jìn)行搜索。模板中心處邊界時(shí)結(jié)束。比較2D對(duì)數(shù)法與全搜索法的比較水平、垂直方向最大位移為6固定模式搜索法的缺點(diǎn)

沒(méi)有利用圖像本身的相關(guān)信息，不能根據(jù)物體運(yùn)動(dòng)的劇烈程度自適應(yīng)的改變搜索起點(diǎn)和搜索半徑。對(duì)于運(yùn)動(dòng)劇烈的圖像，從原點(diǎn)開(kāi)始搜索時(shí)，要經(jīng)過(guò)多次搜索才能找到匹配點(diǎn)，搜索點(diǎn)過(guò)多，且容易陷入局部最優(yōu)點(diǎn)。粒子群優(yōu)化算法粒子群優(yōu)化(ParticleSwarmOptimization,PSO)是由Kennedy和Eberhart在1995年共同提出的，源于對(duì)鳥(niǎo)群遷徙和魚(yú)群聚集行為的啟發(fā)。粒子群優(yōu)化算法群體中的每個(gè)個(gè)體視為沒(méi)有質(zhì)量和體積的“粒子”，可以理解為是搜索空間中的點(diǎn)或者優(yōu)化問(wèn)題中的解。每個(gè)粒子都有自己的速度和空間位置，還有一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)度值。在進(jìn)化迭代過(guò)程中，每個(gè)粒子根據(jù)自身最優(yōu)解和群體最優(yōu)解更新自己的飛行速度大小和前進(jìn)的方向。最終所有粒子向群體的最優(yōu)解聚集，尋找到搜索空間的全局最優(yōu)解。速度位置自身最優(yōu)解群體最優(yōu)解粒子群優(yōu)化算法粒子群的搜索空間N粒子群優(yōu)化運(yùn)動(dòng)估計(jì)運(yùn)動(dòng)估計(jì)的搜索空間D=2“粒子”粒子的位置粒子的速度“搜索點(diǎn)”搜索點(diǎn)的水平和垂直坐標(biāo)搜索點(diǎn)的水平和垂直速度生物地理分布優(yōu)化算法2008年，DanSimon提出了一種新型的智能優(yōu)化算法，稱(chēng)為生物地理分布優(yōu)化算法(Biogeography-basedOptimization-BBO)，該算法源于對(duì)生物地理分布情況的啟發(fā)。生物地理分布優(yōu)化算法BBO的搜索空間N生物地理分布優(yōu)化運(yùn)動(dòng)估計(jì)運(yùn)動(dòng)估計(jì)的搜索空間D=2“島嶼”島嶼適合指數(shù)變量“搜索點(diǎn)”搜索點(diǎn)的水平和垂直坐標(biāo)常用搜索算法總結(jié)全搜索法特點(diǎn)：效果最好、復(fù)雜度很高三步法、對(duì)數(shù)搜索法特點(diǎn)：效果一般、復(fù)雜度低、適應(yīng)差鉆石搜索法、十字搜索法特點(diǎn)：效果較好、復(fù)雜度低、適應(yīng)較好群智能搜索法（遺傳、粒子群、生物地理分布）特點(diǎn)：效果很好、復(fù)雜度較高、適應(yīng)較好序列相關(guān)性和視覺(jué)特性

人們針對(duì)序列圖像的時(shí)空相關(guān)性和人眼視覺(jué)特性，提出了許多改進(jìn)算法，主要可分類(lèi)下面幾類(lèi)：預(yù)測(cè)搜索起點(diǎn)扁平搜索模板背景圖像快速檢測(cè)多預(yù)測(cè)點(diǎn)搜索預(yù)測(cè)搜索起點(diǎn)

利用相鄰塊之間的運(yùn)動(dòng)相關(guān)性選擇一個(gè)反映當(dāng)前塊運(yùn)動(dòng)趨勢(shì)的預(yù)測(cè)點(diǎn)作為初始搜索點(diǎn)，這個(gè)預(yù)測(cè)點(diǎn)一般比原點(diǎn)更靠近全局最小點(diǎn)。從預(yù)測(cè)點(diǎn)開(kāi)始搜索可以在一定程度上提高搜索速度和搜索精度。扁平搜索模板

在序列圖像中，大多數(shù)的運(yùn)動(dòng)矢量都位于水平或垂直方向，因此有些論文設(shè)計(jì)了扁平搜索模板（非對(duì)稱(chēng)搜索模板）來(lái)加快搜索速度?？蓞⒖际至庑嗡阉鞣ǎ–DS）。背景圖像的快速檢測(cè)

由于一般序列中背景圖像占有相當(dāng)?shù)谋壤?，?duì)背景圖像的快速檢測(cè)對(duì)搜索算法的性能提高很大。一般有兩種方法：中止判別條件（門(mén)限一般設(shè)置512左右）從中心點(diǎn)開(kāi)始用小模板檢測(cè)多預(yù)測(cè)點(diǎn)搜索

這種方法是根據(jù)鄰塊運(yùn)動(dòng)矢量預(yù)測(cè)多個(gè)搜索點(diǎn)，在搜索過(guò)程中選擇預(yù)測(cè)性能最好的預(yù)測(cè)點(diǎn)，通常于小模板搜索方法想結(jié)合。預(yù)測(cè)方法至關(guān)重要。圖像1圖像2殘差圖像運(yùn)動(dòng)殘差圖像舉例舉例結(jié)果分析結(jié)果分析結(jié)果分析ThankYou!謝謝2月-2500:07:0800:0700:072月-252月-2500:0700:0700:07:082月-252月-2500:07:082025/2/150:07:089、春去春又回，新桃換舊符。在那桃花盛開(kāi)的地方，在這醉人芬芳的季節(jié)，愿你生活像春天一樣陽(yáng)光，心情像桃花一樣美麗，日子像桃子一樣甜蜜。2月-252月-25Saturday,February15,202510、人的志向通常和他們的能力成正比例。00:07:0800:07:0800:072/15/202512:07:08AM11、夫?qū)W須志也，才須學(xué)也，非學(xué)無(wú)以廣才，非志無(wú)以成學(xué)。2月-2500:07:0800:07Feb-2515-Feb-2512、越是無(wú)能的人，越喜歡挑剔別人的錯(cuò)兒。00:07:0800:07:0800:07Saturday,February15,202513、志不立，天下無(wú)可成之事。2月-252月-2500:07:0800:07:08February15,202514、ThankyouverymuchfortakingmewithyouonthatsplendidoutingtoLondon.ItwasthefirsttimethatIhadseentheToweroranyoftheotherfamoussights.IfI'dgonealone,Icouldn'thaveseennearlyasmuch,becauseIwouldn'thaveknownmywayabout.。15二月202512:07:08上午00:07:082月-2515、會(huì)當(dāng)凌絕頂，一覽眾山小。二月2512:07