大學(xué)計算機學(xué)院多媒體基礎(chǔ)運動估計

1、陳虎視頻圖像的冗余v空間冗余v時間冗余視頻圖像的冗余 視頻序列圖像在時間上存在很強的相關(guān)性，采用運動估計和運動補償技術(shù)可以消除時間冗余以提高編碼效率，這種技術(shù)廣泛用于視頻壓縮的一些國際標準中，如H.261/263/264、MPEG-1/2/4。視頻編碼框架消除時間冗余v當前圖像塊與參考圖像對應(yīng)塊求差值v相似圖像塊才能有效消除時間冗余v圖像塊越相似，消除時間冗余效果越好v采用運動搜索的方法尋找最相似的塊運動估計與補償運動以及運動搜索v時間上目標的空間位移運動矢量v通過搜索比較，確定相似塊以及運動矢量的過程運動估計的分類全局運動估計基于塊的運動估計基于象素點的運動估計基于區(qū)域的運動估計基于網(wǎng)格的運

2、動估計時域運動估計頻域運動估計（DFT、DCT、DWT）運動估計的分類a 全局運動估計c 基于塊的運動估計b 基于象素點的運動估計d 基于區(qū)域的運動估計運動估計的分類a 基于塊的運動估計b 基于網(wǎng)格的運動估計 塊匹配運動估計因算法簡單、便于硬件實現(xiàn)得到廣泛應(yīng)用，本文將對其進行重點討論，下面簡稱其為“運動估計”?；趬K的運動估計 基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認為宏塊內(nèi)所有象素的位移量都相同，然后對每個宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定的匹配準則找出與當前塊最相似的塊，即匹配塊，匹配塊與當前塊的相對位移即為運動矢量。視頻壓縮的時候，只需保存運動矢量和殘差數(shù)據(jù)就可以

3、完全恢復(fù)出當前塊。基于塊的運動估計基于塊的運動估計基于塊的運動估計基于塊的運動估計塊匹配法基本流程 分成互不重疊NN大小的塊，塊遵循物體剛性平動的假設(shè)模型 根據(jù)一定的匹配準則和搜索算法，在參考幀中給定的搜索范圍內(nèi)，尋找到當前塊的最佳匹配塊 當前塊和最佳匹配塊之間的相對位移就是當前塊的運動矢量 匹配準則21111( ,)( , )(,)MNiikkiimnMSE x yfm nfmx nyMN均方誤差：平均絕對誤差：111( ,)( , )(,)MNiikkiimnSAD x yfm nfmx ny絕對誤差：1111( ,)( , )(,)MNiikkiimnMAD x yfm nfmx nyM

4、N舉例運動估計快速算法分類分層的和多分辨率的快速塊匹配方法固定搜索模式的快速塊匹配方法基于時空相關(guān)性和視覺特性的快速塊匹配方法基于連續(xù)消除的快速塊匹配方法基于象素子抽樣的快速塊匹配方法分層的或多分辨率法 在較粗糙的分辨率下預(yù)測一個接近的大尺寸的運動矢量，然后在較高的分辨率下進一步修正。稱為分層的或多分辨率的運動估計快速算法。 缺點：計算過程復(fù)雜，內(nèi)存需求較大。分層的或多分辨率法象素子抽樣法 通常的匹配準則是把塊里所有的象素點進行計算和比較，事實上一個塊里相鄰象素的差別很小，使得它們之間也存在冗余。子采樣運動估計算法就利用了這一事實，只取其中的一部分象素進行計算，可大大減少計算量，但同時降低了準

5、確性。全搜索法對搜索區(qū)域的所有 位置進行窮盡搜索。精度最高計算復(fù)雜，難以實時 處理必須研究相應(yīng)的運動 估計快速算法三步法搜索模板半徑依次減半對小運動檢測效果不好搜索范圍大于7時，搜索步驟不止三步梯度下降法反復(fù)使用33模板進行搜索。模板中心處SAD值最小時結(jié)束。對大運動檢測效果不好四步法 反復(fù)使用55方形模板進行搜索。模板中心處SAD值最小時再用33模板搜索一次確定最佳匹配位置。菱形法 搜索方式與四步法類似，只是搜索模板換為兩個菱形模板。六邊形法 搜索方式與菱形法類似，只是大搜索模板換為一個六邊形模板。2D 對數(shù)法反復(fù)使用33模板進行搜索。模板中心處邊界時結(jié)束。比較2D對數(shù)法與全搜索法的比較水平

6、、垂直方向最大位移為6固定模式搜索法的缺點 沒有利用圖像本身的相關(guān)信息，不能根據(jù)物體運動的劇烈程度自適應(yīng)的改變搜索起點和搜索半徑。 對于運動劇烈的圖像，從原點開始搜索時，要經(jīng)過多次搜索才能找到匹配點，搜索點過多，且容易陷入局部最優(yōu)點。粒子群優(yōu)化算法粒子群優(yōu)化 (Particle Swarm Optimization, PSO)是由Kennedy和Eberhart在1995年共同提出的，源于對鳥群遷徙和魚群聚集行為的啟發(fā)。粒子群優(yōu)化算法( 1)( )( )( )( )( )1122()()kkkkkkididdididddidvvcrand pbestxcrand gbestx(1)()(1)k

7、kkidididxxv群體中的每個個體視為沒有質(zhì)量和體積的“粒子粒子”，可以理解為是搜索空間中的點或者優(yōu)化問題中的解。每個粒子都有自己的速度速度和空間位置位置，還有一個由目標函數(shù)決定的適應(yīng)度值。在進化迭代過程中，每個粒子根據(jù)自身最優(yōu)解自身最優(yōu)解和群體最優(yōu)解群體最優(yōu)解更新自己的飛行速度大小和前進的方向。最終所有粒子向群體的最優(yōu)解聚集，尋找到搜索空間的全局最優(yōu)解全局最優(yōu)解。速度速度位置位置自身最優(yōu)解自身最優(yōu)解群體最優(yōu)解群體最優(yōu)解粒子群優(yōu)化算法粒子群的搜索空間Nn粒子群優(yōu)化粒子群優(yōu)化 運動估計運動估計 運動估計的搜索空間 D=2“粒子”粒子的位置粒子的速度 “搜索點”搜索點的水平和垂直坐標 搜索點的

8、水平和垂直速度 生物地理分布優(yōu)化算法2008年，Dan Simon提出了一種新型的智能優(yōu)化算法，稱為生物地理分布優(yōu)化算法(Biogeography-based Optimization-BBO)，該算法源于對生物地理分布情況的啟發(fā)。生物地理分布優(yōu)化算法BBO的搜索空間Nn生物地理分布優(yōu)化生物地理分布優(yōu)化 運動估計運動估計 運動估計的搜索空間 D=2“島嶼”島嶼適合指數(shù)變量“搜索點”搜索點的水平和垂直坐標 常用搜索算法總結(jié)v 全搜索法 特點：效果最好、復(fù)雜度很高v 三步法、對數(shù)搜索法 特點：效果一般、復(fù)雜度低、適應(yīng)差v 鉆石搜索法、十字搜索法 特點：效果較好、復(fù)雜度低、適應(yīng)較好v 群智能搜索法（

9、遺傳、粒子群、生物地理分布） 特點：效果很好、復(fù)雜度較高、適應(yīng)較好序列相關(guān)性和視覺特性 人們針對序列圖像的時空相關(guān)性和人眼視覺特性，提出了許多改進算法，主要可分類下面幾類：預(yù)測搜索起點扁平搜索模板背景圖像快速檢測多預(yù)測點搜索預(yù)測搜索起點 利用相鄰塊之間的運動相關(guān)性選擇一個反映當前塊運動趨勢的預(yù)測點作為初始搜索點，這個預(yù)測點一般比原點更靠近全局最小點。從預(yù)測點開始搜索可以在一定程度上提高搜索速度和搜索精度。扁平搜索模板 在序列圖像中，大多數(shù)的運動矢量都位于水平或垂直方向，因此有些論文設(shè)計了扁平搜索模板（非對稱搜索模板）來加快搜索速度?？蓞⒖际至庑嗡阉鞣ǎ–DS）。背景圖像的快速檢測 由于一般序列中背景圖像占有相當?shù)谋壤瑢Ρ尘皥D像的快速檢測對搜索算法的性能提高很大。一般有兩種方法：中止判別條件（門限一般設(shè)置512左右）從中心點開始用小模板檢測多預(yù)測點搜索 這種方法是根據(jù)鄰塊運動矢量預(yù)測多個搜索點，在搜索過程中選擇預(yù)測性能最好的預(yù)測點，通常于小模板搜索方法想結(jié)合