第三章二維運動估計之一

1、第三章二維運動估計之一第三章二維運動估計之一 第三章第三章 二維運動估計二維運動估計 第三章二維運動估計之一第三章二維運動估計之一 運動估計涉及運動估計涉及: 圖像平面運動圖像平面運動(二維運動二維運動) 和空間物體運動和空間物體運動(三維運動三維運動),運運 動分析與估計是數(shù)字視頻處理的基本問題之一動分析與估計是數(shù)字視頻處理的基本問題之一, 也是數(shù)字視頻處理的難也是數(shù)字視頻處理的難 點和熱點。點和熱點。 運動分析與估計廣泛應用于計算機視覺、目標跟蹤、工業(yè)監(jiān)視和視頻運動分析與估計廣泛應用于計算機視覺、目標跟蹤、工業(yè)監(jiān)視和視頻 壓縮等場合壓縮等場合 不同應用場合對運動估計要求不同，有如下區(qū)分：不

2、同應用場合對運動估計要求不同，有如下區(qū)分： 真實運動估計：要求估計獲得的物體運動和實際運動基本真實運動估計：要求估計獲得的物體運動和實際運動基本 一致。如計算機視覺、目標跟蹤、工業(yè)監(jiān)視。一致。如計算機視覺、目標跟蹤、工業(yè)監(jiān)視。 非真實運動估計：在不被察覺的情況下允許有估計誤差，非真實運動估計：在不被察覺的情況下允許有估計誤差， 從而最大限度降低信息量和傳輸帶寬。如廣播電視中的視從而最大限度降低信息量和傳輸帶寬。如廣播電視中的視 頻壓縮。頻壓縮。 第三章二維運動估計之一第三章二維運動估計之一 幾個基本概念幾個基本概念 1.時間序列圖像：隨時間而變化的一系列圖像稱為時間序列圖像或運動時間序列圖像：

3、隨時間而變化的一系列圖像稱為時間序列圖像或運動 圖像。圖像。 2.運動物體特征：指物體形狀或表面特征，如尖銳點、邊緣線等。運動物體特征：指物體形狀或表面特征，如尖銳點、邊緣線等。 可以通過運動物體的特征來觀察分析物體的運動?？梢酝ㄟ^運動物體的特征來觀察分析物體的運動。 3.運動估計的基本問題運動估計的基本問題 運動估計研究的是視頻序列圖像中投影坐標在像平面上的變化，獲取運動估計研究的是視頻序列圖像中投影坐標在像平面上的變化，獲取 運動參數(shù)，但是投影會造成信息丟失（不可逆），導致估計誤差。運動參數(shù)，但是投影會造成信息丟失（不可逆），導致估計誤差。 第三章二維運動估計之一第三章二維運動估計之一 特

4、征對應：運動物體上的特征與其在二維平面上的投影坐標的對應關特征對應：運動物體上的特征與其在二維平面上的投影坐標的對應關 系。見下圖示：系。見下圖示： 設t1t2時，物體由P運動至P，即： 空空 間間：P(X,Y,Z) P(X,Y,Z) 像平面像平面： p(x,y) p(x,y) 二維位移（x, y ）稱為二維運動矢 量，標記為d(x,t1;t2)。 對于一組點，二維空間位移記為 d(xi,t1;t2),i=1,2,。 第三章二維運動估計之一第三章二維運動估計之一 運動估計的基本問題基本問題 是估計運動前后相鄰 兩幀圖像上對應點的 坐標pi(xi,yi)和pi (xi,yi)， i=1,2,3。

5、即像平面 上對應的二維運動矢 量di(xi,t1;t2)。 第三章二維運動估計之一第三章二維運動估計之一 4.運動分析方法：主要有兩種運動分析方法：主要有兩種 .根據(jù)時間相鄰的兩幅或多幅圖像求解物體的運動參數(shù)和三維結構信息。根據(jù)時間相鄰的兩幅或多幅圖像求解物體的運動參數(shù)和三維結構信息。 圖像序列的光流分析法。圖像序列的光流分析法。 運動信息包括：物體的一階（位移）、二階（速度）、三階（加速度）等。運動信息包括：物體的一階（位移）、二階（速度）、三階（加速度）等。 研究內(nèi)容包括：運動目標檢測與分割、運動參數(shù)估計等。研究內(nèi)容包括：運動目標檢測與分割、運動參數(shù)估計等。 光流：指視覺觀察到的圖像中產(chǎn)生

6、的光強變化。它一般對應物體的運動，但也光流：指視覺觀察到的圖像中產(chǎn)生的光強變化。它一般對應物體的運動，但也 有不一致的情況。有不一致的情況。 換句話說，在視頻圖像序列運動估計中，觀察到的二維運動叫光流。換句話說，在視頻圖像序列運動估計中，觀察到的二維運動叫光流。 或定義：視頻序列空間坐標關于時間的變化率稱為光流，即或定義：視頻序列空間坐標關于時間的變化率稱為光流，即 (vx,vy)T=(dx/dt,dy/dt)T,其對應于像素的瞬時速度矢量。其對應于像素的瞬時速度矢量。 第三章二維運動估計之一第三章二維運動估計之一 綱要 v2-D 運動和光流運動和光流 v光流方程解決運動估計的一般方法光流方程

7、解決運動估計的一般方法 運動表示運動表示 運動場參數(shù)化運動場參數(shù)化 最優(yōu)化準則的公式化最優(yōu)化準則的公式化 尋找最優(yōu)化參數(shù)尋找最優(yōu)化參數(shù) v運動估計算法運動估計算法 基于光流的運動估計基于光流的運動估計 基于像素的運動估計基于像素的運動估計 基于塊的運動估計（基于塊的運動估計（EBMA） 第三章二維運動估計之一第三章二維運動估計之一 3-D運動運動 - 2-D運動運動 3-D MV 2-D MV 第三章二維運動估計之一第三章二維運動估計之一 2.1 2-D 運動運動 vs. 光流光流 v2-D 運動運動: 3-D 運動的投影運動的投影, 取決于取決于3D 物體運動和投影物體運動和投影 操作。操作

8、。 v光流光流: 觀測的或表現(xiàn)的二維運動。觀測的或表現(xiàn)的二維運動。 不僅可以由物體運動引起，還可以由攝像機運動或照明條件不僅可以由物體運動引起，還可以由攝像機運動或照明條件 變化引起。注：不等同于真實的二維運動。變化引起。注：不等同于真實的二維運動。 v左邊是一個具有均勻平坦表面 的球在恒定的環(huán)境光下轉(zhuǎn)動。 每一個點都反射相同的彩色， 人們感覺不到球的任何變化， 認為球是靜止的。 v右邊是一個靜止的球，被一個 繞著球轉(zhuǎn)動的點光源照明。光 源的運動引起球上反射光點的 運動，人眼認為球在運動。 第三章二維運動估計之一第三章二維運動估計之一 光流方程光流方程 v如果照明條件未知，那么所能得到的最精確

9、估如果照明條件未知，那么所能得到的最精確估 計就是光流。計就是光流。 v恒定亮度假設恒定亮度假設 光流方程光流方程 又運用泰勒展開式，當又運用泰勒展開式，當dx,dy,dt很小時，很小時， 比較上面兩個式子，得到光流方程：比較上面兩個式子，得到光流方程： ),(),(tyxdtdydx tyx tyxtyx d t d y d x tyxdtdydx ),(),( 000 tt v y v x d t d y d x T yxtyx v T yx , 其中 空間梯度矢量空間梯度矢量 第三章二維運動估計之一第三章二維運動估計之一 其中： 為圖像空間梯度方向 上的單位矢量 v光流v的分解 將光流v

10、分解為兩個正交的分量： n e 0 t v T tn eev tn vv 為切線方向上的單位矢量 t e 0 t vn n e n v t e t v v 只能確定圖像空間梯度方向上的分量（法向流） 即：孔徑問題 n v 光流方程光流方程 第三章二維運動估計之一第三章二維運動估計之一 圖圖6.3 運動估計中的孔徑（用一個恒定亮度假設的小窗口）運動估計中的孔徑（用一個恒定亮度假設的小窗口） 問題問題: 在在x1 處估計運動使用孔徑處估計運動使用孔徑1，但是不可能確定運動，但是不可能確定運動 是向上的還是垂直于邊緣的，因為在這個孔徑中只有一是向上的還是垂直于邊緣的，因為在這個孔徑中只有一 個空間梯

11、度方向?？梢詼蚀_地估計個空間梯度方向。可以準確地估計x2的運動，因為在孔徑的運動，因為在孔徑 2中，圖像有兩個不同方向的梯度。中，圖像有兩個不同方向的梯度。 第三章二維運動估計之一第三章二維運動估計之一 運動估計中的不確定問題運動估計中的不確定問題 v孔徑問題：光流方程只確孔徑問題：光流方程只確 定了法向的投影定了法向的投影vn， ，在切線 在切線 的投影是不確定的，任何的投影是不確定的，任何 vt 的值都滿足光流方程。的值都滿足光流方程。 v一個方程有兩未知數(shù)一個方程有兩未知數(shù) 要施加附加條件：最通常要施加附加條件：最通常 的約束是流矢量在空間平的約束是流矢量在空間平 滑變化。使我們可以利用

12、滑變化。使我們可以利用 x周圍一個小的鄰域亮度周圍一個小的鄰域亮度 變化去估計變化去估計x處的運動。處的運動。 v運動估計僅在有亮度變化運動估計僅在有亮度變化 區(qū)域可靠。區(qū)域可靠。 0| t v vv n ttnn eev 第三章二維運動估計之一第三章二維運動估計之一 v參考幀：參考幀： 1(x, t1) v當前幀當前幀: 2(x, t2) v前向運動估計前向運動估計 /后向運動估計：后向運動估計： t2 t1 / t2 重點重點 v三個關鍵問題：三個關鍵問題： Q1：怎樣將運動場參數(shù)化：怎樣將運動場參數(shù)化 Q2：用什么樣的準則來估計這些參數(shù)：用什么樣的準則來估計這些參數(shù) Q3：怎樣搜索這些最

13、優(yōu)參數(shù)：怎樣搜索這些最優(yōu)參數(shù) 第三章二維運動估計之一第三章二維運動估計之一 2.2.1 運動表示法（運動表示法（Q1） 整體（全整體（全 局）局）: 整體運動整體運動 由若干整由若干整 體參數(shù)表體參數(shù)表 示。示。 基于塊：基于塊： 把圖像域把圖像域 固定分成固定分成 許多小的許多小的 方塊，每方塊，每 個塊用一個塊用一 個簡單的個簡單的 模型表征。模型表征。 基于像素：基于像素： 每個象素都每個象素都 指定運動矢指定運動矢 量量 基于區(qū)域：基于區(qū)域： 將圖像幀分將圖像幀分 為多個區(qū)域，為多個區(qū)域， 每個區(qū)域用每個區(qū)域用 一個參數(shù)化一個參數(shù)化 模型表征。模型表征。 第三章二維運動估計之一第三章二

14、維運動估計之一 2.2.2 運動估計準則運動估計準則1： （Q2） 基于位移幀差準則基于位移幀差準則 v最常用的運動估計準則是參考幀最常用的運動估計準則是參考幀 1與當前幀與當前幀 2 之間每個對應點對之間亮度值之差的和。之間每個對應點對之間亮度值之差的和。 v回憶回憶 1中的中的x移動到移動到 2 中的中的w(x; a) ，則目標函，則目標函 數(shù)寫為：數(shù)寫為： min| )();(|)( 12 p DFD wExaxa x vp 是一個正數(shù)，當是一個正數(shù)，當 p = 1, 上面的誤差稱為平均上面的誤差稱為平均 絕對差絕對差 (MAD), 當當p = 2,稱為均方差稱為均方差(MSE) v誤差

15、圖像誤差圖像e(x; a) = 2(w(x, a) ) - 1(x) 一般稱為一般稱為 位移幀差位移幀差(DFD) 圖像圖像 v使使 最小的必要條件是它的梯度最小的必要條件是它的梯度=0 )(a DFD E 第三章二維運動估計之一第三章二維運動估計之一 2.2.2 運動估計準則運動估計準則2： 基于光流方程準則基于光流方程準則 min| )()();()( |)( 121 p Ax T OF Exxaxdxa v光流方程光流方程 0 tyx d t d y d x v如果如果 dt 很小，令很小，令 )()( 12 xxd t t 0, 0 12112 11 dord y d x T yx v

16、這個光流方程的離散形式更經(jīng)常用在數(shù)字視頻的運動估這個光流方程的離散形式更經(jīng)常用在數(shù)字視頻的運動估 計中，求解符合方程的計中，求解符合方程的x問題可以轉(zhuǎn)化成用以下目標函數(shù)問題可以轉(zhuǎn)化成用以下目標函數(shù) （EOF）表示的最小化問題：）表示的最小化問題： 第三章二維運動估計之一第三章二維運動估計之一 v運動估計是一個不適定（病態(tài)）問題運動估計是一個不適定（病態(tài)）問題 恒定亮度假定不總是成立恒定亮度假定不總是成立 在平面紋理區(qū)域，不同運動估計可以滿足恒定亮度在平面紋理區(qū)域，不同運動估計可以滿足恒定亮度 假設或光流方程。假設或光流方程。 v在嚴格數(shù)學意義上，我們不可能對不適定問題進行求在嚴格數(shù)學意義上，我

17、們不可能對不適定問題進行求 解并得到答案，只能通過先驗知識找到近似解。解并得到答案，只能通過先驗知識找到近似解。 v正則化過程：即用一組與原不適定問題相近的適定問正則化過程：即用一組與原不適定問題相近的適定問 題去逼近原問題的解。題去逼近原問題的解。 v在基于像素和基于塊運動估計中很重要。在基于像素和基于塊運動估計中很重要。 2.2.2 運動估計準則運動估計準則3 平滑約束正則化平滑約束正則化 第三章二維運動估計之一第三章二維運動估計之一 2.2.2 運動估計準則運動估計準則3 平滑約束正則化平滑約束正則化 v常用的正則化方法是增加一個表示平滑變化的常用的正則化方法是增加一個表示平滑變化的 代

18、價項來測量鄰近像素代價項來測量鄰近像素MV的差：的差： v總的最小化準則寫成：總的最小化準則寫成： AxNy s x aydaxdaE 2 );();()( min)()(aEwaEE ssDFD 。以免模糊系數(shù)應該減小來選擇，物體邊界的權 運動平滑的重要性根據(jù)與預測誤差有關的權系數(shù) )( s w 第三章二維運動估計之一第三章二維運動估計之一 不同準則之間的關系 v基于光流方程準則基于光流方程準則OF 只有當運動比較小的時候效果較好。只有當運動比較小的時候效果較好。 當當p=2時最小值函數(shù)是時最小值函數(shù)是MV的二次函數(shù)。如果運動參的二次函數(shù)。如果運動參 數(shù)關于數(shù)關于MV線性，則函數(shù)具有唯一的最

19、小值，容易線性，則函數(shù)具有唯一的最小值，容易 求解。求解。 v當運動比較大，可以對基于光流方程準則當運動比較大，可以對基于光流方程準則OF 進行迭代求解，以滿足基于位移幀差（進行迭代求解，以滿足基于位移幀差（DFD） 準則。準則。 第三章二維運動估計之一第三章二維運動估計之一 2.2.3 優(yōu)化方法（對誤差函數(shù)進行最小化）優(yōu)化方法（對誤差函數(shù)進行最小化） Q3 v窮盡搜索窮盡搜索 通常用在通常用在DFD準則中當準則中當p=1(MAD)的情況的情況 保證全局最優(yōu)保證全局最優(yōu) 計算量太大計算量太大 快速算法可以得到次優(yōu)解?？焖偎惴梢缘玫酱蝺?yōu)解。 v基于梯度搜索基于梯度搜索 通常用在通常用在 DFD

20、 或或 OF 準則，當準則，當 p=2 (MSE)的情況的情況 可以計算出梯度可以計算出梯度 運用運用OF準則時應該可以獲得一個閉合解析式。準則時應該可以獲得一個閉合解析式。 通過先驗知識獲得一個好的初始解，搜索出局部最優(yōu)的點通過先驗知識獲得一個好的初始解，搜索出局部最優(yōu)的點 v多分辨率搜索多分辨率搜索 從粗分辨率搜索到細分辨率，比窮盡搜索快。從粗分辨率搜索到細分辨率，比窮盡搜索快。 避免陷入局部最優(yōu)避免陷入局部最優(yōu) 第三章二維運動估計之一第三章二維運動估計之一 2.3 基于光流的運動估計基于光流的運動估計 v光流方程 亮度守恒假設：運動物體點的亮度（或色度）在其運 動軌跡上保持不變，變化的是

21、物體的位置。 ),(),( tyx dtdydxtyx tyxtyx d t d y d x tyxdtdydx ),(),( 0 tyx d t d y d x 0 t v y v x yx 或0 t v T 其中 為空間梯度向量， 為光流場。 T yx ,),( yx vvv 第三章二維運動估計之一第三章二維運動估計之一 圖像梯度的計算 v光流方程的要求：亮度函數(shù)可微 v數(shù)字視頻：有限差分法近似 m,nm+1,n m,n+1m+1,n+1 )1, 1,() 1, 1, 1( ) 1,() 1, 1(), 1,( ), 1, 1(),(), 1( 4 1 knmknm knmknmknm k

22、nmknmknm x )1, 1() 1, 1, 1( ) 1,() 1, 1,(), 1( ), 1, 1(),(), 1,( 4 1 knmknm knmknmknm knmknmknm y ), 1, 1() 1, 1, 1( ), 1,() 1, 1,(), 1( ) 1, 1(),() 1,( 4 1 knmknm knmknmknm knmknmknm t 第三章二維運動估計之一第三章二維運動估計之一 2.3.1 多點鄰域約束 v光流方程 一個方程，兩個未 知數(shù) v多點鄰域約束 假設 的鄰域 內(nèi)所有像素具有相同的光流矢量，光流 方程在領域 上的誤差定義為： )( i x 2 )(

23、Bx yx t v y v x wE x i x 其中 為分配給 的權重。令 可得： )( i x )(xwx0 yx v E v E 0)( xt v y v x xw Bx yx 0)( yt v y v x xw Bx yx 0 t v y v x yx 第三章二維運動估計之一第三章二維運動估計之一 v多點鄰域約束 則光流矢量的估計值為： Bx Bx BxBx BxBx y x ty xw tx xw yy xw yx xw yx xw xx xw v v )( )( )()( )()( 1 2.3.1 多點鄰域約束 第三章二維運動估計之一第三章二維運動估計之一 2.3.2 運動平滑約束

24、 運動場的平滑性 第三章二維運動估計之一第三章二維運動估計之一 v運動平滑約束 由Horn和Schunck提出，對整個運動場或局部窗施加全局 平滑約束。 目標誤差函數(shù)為： x ssof dxeweE)()()( 22 vvv 其中 為運動估計的定義域，可以是整幅圖像或一個局部窗。 2 2 )( t v y v x e yxof v 222 2 2 2 2 )( y v x v y v x v vve yy xx yxs v )( 2 v s e為光流空間梯度光流空間梯度的平方函數(shù)，它反映了光流矢量隨像素 變化的快慢程度 為光流方程誤差的平方函數(shù) 2.3.2 運動平滑約束 第三章二維運動估計之一

25、第三章二維運動估計之一 對 求關于 和 的偏微 分，并令其為0，可得： )(vE x v y v v運動平滑約束 最小化 施加光流 約束 最小化 施加運動 平滑約束 )( 2 v of e ty vwv y wv yx tx vwv yx v x w ysysx xsyxs 2 2 )( 2 v s e 2 2 )()( )()1( 2 2 )()( )()1( yx w t v y v x y vv yx w t v y v x x vv s l y l x l y l y s l y l x l x l x 表示對像素鄰域（不包括當 前像素）求平均。 表示迭代次數(shù)，初始光流矢 量 可設為零

26、。 )0( v l v 2.3.2 運動平滑約束 第三章二維運動估計之一第三章二維運動估計之一 2.4 基于像素的運動估計基于像素的運動估計 v最優(yōu)化方法最優(yōu)化方法1：多鄰域方法：多鄰域方法 假設像素假設像素xn 周圍的小范圍內(nèi)各個像素的運動向量（周圍的小范圍內(nèi)各個像素的運動向量（MV）一致。）一致。 最小化鄰域上的預測誤差。最小化鄰域上的預測誤差。 v最優(yōu)化方法最優(yōu)化方法2：像素遞歸方法：像素遞歸方法 當前像素的當前像素的MV是在已經(jīng)編碼的鄰近像素的是在已經(jīng)編碼的鄰近像素的MV上更新的。根上更新的。根 據(jù)同樣的更新規(guī)則，據(jù)同樣的更新規(guī)則，MV不用編碼。不用編碼。 應用在較早幾代的視頻編碼器中

27、。應用在較早幾代的視頻編碼器中。 v準則準則平滑約束正則化：平滑約束正則化：Horn-Schunck 方方 法法 光流方程準則光流方程準則 + 運動平滑準則運動平滑準則 )()()( 2 2 2 yxsyx A vvw t v y v x vE x x 第三章二維運動估計之一第三章二維運動估計之一 2.4 基于像素的運動估計基于像素的運動估計 v與光流法一樣，估計每個像素的運動矢量 v位移幀差 像素x從t1時刻到t1+dt時刻的位移幀差為： ),(),(),( 11 tdte t xdxdx T yx dd,d 為為x處的位移矢量處的位移矢量 tyxt d t d y d x tdt ),()

28、,( 11 xdx tyx d t d y d x e ),(dx 由亮度守恒假設由亮度守恒假設 ，即：，即：0),(dxe 0 tyx d t d y d x 兩邊同時除以兩邊同時除以dt，可得：，可得：0 t v y v x yx （光流方程）（光流方程） 第三章二維運動估計之一第三章二維運動估計之一 多點鄰域約束 l假設 的鄰域 內(nèi)所有像素具有相同的運動矢量， 領域 上的誤差函數(shù)為： 2 )( 12 )()()( 2 1 )( i Bx ii wE x xdxxd )( 2 )(),()()( i Bx ii i i ew E E x xd dxdxx d d )( i x )( i x

29、 i x 其中，w(x)為分配給x的權重。誤差函數(shù)關于運動矢量di的 梯度為： 使用基于一階梯度下降一階梯度下降的方法求解運動矢量di： )( )()1( i l i l i E ddd d 為更新步長。 也可以使用窮盡搜索法尋找di。 2.4.1 多點鄰域約束多點鄰域約束 第三章二維運動估計之一第三章二維運動估計之一 像素遞歸法 l沿圖像掃描方向逐個估計像素的運動矢量。 l新像素的運動矢量由已估計像素的運動矢量進行預測 l使用基于位移幀差函數(shù)最小化的方法更新運動矢量 l像素的位移矢量無需編碼 解碼器端使用同樣的預測更新機制 l估計精度較低，預測誤差較大 );,();,();,( ttpt d

30、tdtdtxuxdxd 局部平滑約束 光流約束 2.4.2 像素遞歸法像素遞歸法 第三章二維運動估計之一第三章二維運動估計之一 基于梯度下降的算法 v基于梯度下降的算法(Netravali-Robbins) 最小化位移幀差函數(shù) 迭代方程： 為更新步長； 為關于d的梯度。 關于位移矢量的梯度計算關于圖像梯度的計算 終止迭代條件：更新項或位移幀差小于某閾值 收斂速度取決于 的選取 同樣存在孔徑問題 2 12 2 )()(),(),(xdxdxdx i eE ),(),( )()()() 1(llll eedxdxdd d ),( )(l edx d )(),( )( 2 )()()1(llll e

31、dxdxdd x 第三章二維運動估計之一第三章二維運動估計之一 多點鄰域約束的像素遞歸法 v使用多點鄰域約束的像素遞歸法 目標誤差函數(shù)為： xx xdxdxdx 2 12 2 )()(),(),(eE 1234 56x 16為已經(jīng)估計的像素 x為當前像素 第三章二維運動估計之一第三章二維運動估計之一 v將圖像分成一個個規(guī)則的圖像塊，對每個塊進行運動估計。 v廣泛應用于各種視頻壓縮編碼標準中。 v塊運動模型 塊平移模型 假定每個塊只做平移運動 優(yōu)點：實現(xiàn)簡單 缺點：1、不能表征旋轉(zhuǎn)、縮放和局部變形；2、物體邊界和塊邊界通常 不一致，導致塊失真；3、同一塊可能包含多個運動物體。 可變形塊模型 可以

32、對物體的旋轉(zhuǎn)、縮放、變形建模 三種模型：投影運動、仿射運動、雙線性運動 v方法：相位相關法、塊匹配法 2.5 基于塊的運動估計基于塊的運動估計 第三章二維運動估計之一第三章二維運動估計之一 塊平移模型 a) 非重疊塊 b) 重疊塊 6.4 基于塊的運動估計基于塊的運動估計 第三章二維運動估計之一第三章二維運動估計之一 2.5 基于塊的運動估計（塊匹配算法）基于塊的運動估計（塊匹配算法） v假設把圖像域分割成互不重疊的小區(qū)域（塊），假設把圖像域分割成互不重疊的小區(qū)域（塊）， 每個塊內(nèi)像素運動一致。每個塊的運動參數(shù)可每個塊內(nèi)像素運動一致。每個塊的運動參數(shù)可 獨立搜索。獨立搜索。 v塊匹配算法塊匹配

33、算法 (BMA): 假設塊進行平移運動，每假設塊進行平移運動，每 個塊規(guī)定一個向量個塊規(guī)定一個向量 窮盡塊匹配算法窮盡塊匹配算法 (EBMA) 快速算法快速算法 v可變形塊匹配算法可變形塊匹配算法(DBMA): 允許更多復雜的運允許更多復雜的運 動（仿射，雙線性）動（仿射，雙線性） 第三章二維運動估計之一第三章二維運動估計之一 2.5 基于塊的運動估計基于塊的運動估計 v基本思路：基本思路： 假設塊內(nèi)各個像素都進行平移運動，用一個假設塊內(nèi)各個像素都進行平移運動，用一個 MV表表 示示 用最小化塊的位移幀差用最小化塊的位移幀差DFD來獨立估計每個塊的運來獨立估計每個塊的運 動向量動向量 v最小化

34、函數(shù)最小化函數(shù) v 最優(yōu)化方法：最優(yōu)化方法： 窮盡搜索法窮盡搜索法 (適用于一次搜索一個運動矢量的情況，適用于一次搜索一個運動矢量的情況， p=1的的MAD準則準則) 快速算法快速算法 整數(shù)整數(shù) vs.分數(shù)精度搜索分數(shù)精度搜索 min| )()(|)( 12 p m B mDFD m Exdxd x 第三章二維運動估計之一第三章二維運動估計之一 窮盡塊匹配算法窮盡塊匹配算法 (EBMA) 第三章二維運動估計之一第三章二維運動估計之一 整數(shù)像素精度整數(shù)像素精度 EBMA的復雜度的復雜度 v假設假設 圖像尺寸圖像尺寸: M M 塊尺寸塊尺寸: N N 每個方向的搜索范圍每個方向的搜索范圍: (-R

35、,R) 搜索步長搜索步長: 1 pixel (假設整數(shù)假設整數(shù)MV) v運算次數(shù)運算次數(shù) (1 次運算次運算=1 “-”, 1 “+”, 1 “| |”): 每個塊的候選匹配塊總數(shù)：每個塊的候選匹配塊總數(shù)： (2R+1)2 每個候選估計的每個候選估計的MAD運算數(shù)：運算數(shù)：N2 估計每個塊的估計每個塊的MV運算數(shù)：運算數(shù)： (2R+1)2 N2 整個幀整個幀 的的MV運算數(shù)：運算數(shù)：(M/N)2(2R+1)2 N2 = M2(2R+1)2 和塊的大小和塊的大小N無關無關 v如：如： M=512, N=16, R=16, 30 fps（幀率）（幀率） 總的運算量：總的運算量： 2.85 108

36、/frame =8.55 109/second v結構規(guī)整，可用模塊化設計，有利于結構規(guī)整，可用模塊化設計，有利于VLSI設計應用設計應用 v純軟件實現(xiàn)有難度純軟件實現(xiàn)有難度 第三章二維運動估計之一第三章二維運動估計之一 6.4.2 分數(shù)精度分數(shù)精度 EBMA v現(xiàn)實的運動矢量不一定是整數(shù)像素倍數(shù)。為了更精確現(xiàn)實的運動矢量不一定是整數(shù)像素倍數(shù)。為了更精確 的運動表示，需要分數(shù)像素精度。的運動表示，需要分數(shù)像素精度。 v半像素精度搜索：步長半像素精度搜索：步長=1/2 像素像素 v難點：難點： 目標幀只有整數(shù)像素目標幀只有整數(shù)像素 v解決方法解決方法: 為了實現(xiàn)為了實現(xiàn)1/2像素步長，目標幀必須

37、先進行像素步長，目標幀必須先進行2倍內(nèi)插。倍內(nèi)插。 通常使用雙線性插值法通常使用雙線性插值法 v復雜度：復雜度： 搜索點總數(shù)等于整數(shù)像素精度搜索的四倍，加上內(nèi)插所需的搜索點總數(shù)等于整數(shù)像素精度搜索的四倍，加上內(nèi)插所需的 額外運算量，復雜性大于額外運算量，復雜性大于4倍倍 v快速算法：快速算法： 先用整像素精度搜索，然后用半像素精度在小范圍內(nèi)細化。先用整像素精度搜索，然后用半像素精度在小范圍內(nèi)細化。 第三章二維運動估計之一第三章二維運動估計之一 v真實運動未必是整 數(shù)值 v分數(shù)精度搜索可提 高運動估計的精度 v半像素精度 MPEG- 1、 MPEG-2、 H.263 v1/4和1/8像素精度 M

38、PEG-4、H.264 分數(shù)精度分數(shù)精度 EBMA 第三章二維運動估計之一第三章二維運動估計之一 分數(shù)精度 原始參考圖像 線性內(nèi)插 內(nèi)插后的參考圖像 M N 2M 2N 第三章二維運動估計之一第三章二維運動估計之一 第三章二維運動估計之一第三章二維運動估計之一 EBMA的優(yōu)缺點的優(yōu)缺點 v塊效應塊效應(塊邊界不連續(xù)塊邊界不連續(xù)) 塊位移模型不精確塊位移模型不精確 解決方法：可變形塊匹配算法解決方法：可變形塊匹配算法 v運動域是隨機的運動域是隨機的 塊和塊之間的運動矢量估計是獨立的塊和塊之間的運動矢量估計是獨立的 解決方法解決方法1: 基于網(wǎng)格的運動估計基于網(wǎng)格的運動估計 解決方法解決方法2：提

39、高正則化的光滑約束：提高正則化的光滑約束 v平滑區(qū)域產(chǎn)生錯誤的平滑區(qū)域產(chǎn)生錯誤的MV 當光梯度接近當光梯度接近0時無法估計出運動。時無法估計出運動。 v基于塊的運動估計廣泛應用在視頻編碼中基于塊的運動估計廣泛應用在視頻編碼中 基于它的簡單性和預測誤差最小化基于它的簡單性和預測誤差最小化 第三章二維運動估計之一第三章二維運動估計之一 BMA快速算法快速算法 v基本想法：基本想法： 減小搜索候選塊的個數(shù)：減小搜索候選塊的個數(shù)： 只搜索那些有可能產(chǎn)生誤差的塊只搜索那些有可能產(chǎn)生誤差的塊 基于前期搜索結果，預測剩下的候選塊。基于前期搜索結果，預測剩下的候選塊。 簡化差錯度量簡化差錯度量(DFD) ，以

40、減小計算量。，以減小計算量。 v經(jīng)典的快速算法經(jīng)典的快速算法 二維對數(shù)搜索法二維對數(shù)搜索法 三步搜索法三步搜索法 新三步搜索法新三步搜索法 菱形搜索法菱形搜索法 v更多的快速搜索算法更多的快速搜索算法 有些是針對軟件應用的，有些針對有些是針對軟件應用的，有些針對VLSI應用。應用。 第三章二維運動估計之一第三章二維運動估計之一 二維對數(shù)搜索法二維對數(shù)搜索法 v從零位移的位置開從零位移的位置開 始搜索始搜索 v每一步搜索每一步搜索5個菱形個菱形 排列的點。排列的點。 v下一步，把中心移下一步，把中心移 到前一步找到的最到前一步找到的最 佳匹配點并重復菱佳匹配點并重復菱 形搜索。形搜索。 v當最佳匹配點是中當最佳匹配點是中 心點或是在最大搜心點或是在最大搜 索區(qū)域的邊界上時，索區(qū)域的邊