二維運動估計

二維運動估計第一頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第二頁，共九十頁，編輯于2023年，星期五概述運動分析與估計數(shù)字視頻處理的基本內容難點和熱點應用場合計算機視覺機器人導航，無人駕駛飛機目標跟蹤軍事偵察、地面和空中的交通管制工業(yè)監(jiān)視工業(yè)自動化控制視頻壓縮第三頁，共九十頁，編輯于2023年，星期五概述不同場合對運動估計的要求不同真實運動估計計算機視覺、目標跟蹤、工業(yè)監(jiān)視等場合期望估計的物體運動和實際運動盡可能一致失真率最優(yōu)運動估計：視頻壓縮最大限度地減小視頻數(shù)據(jù)量估計的結果不一定是真實的運動參數(shù)可視電話、流媒體、DVD、HDTV、IPTV等第四頁，共九十頁，編輯于2023年，星期五概述運動分類根據(jù)攝像機和目標物體的運動狀態(tài)攝像機不動物體不動（SCSO）攝像機不動物體動（SCMO）攝像機動物體不動（MCSO）攝像機動物體動（MCMO）根據(jù)觀察者單攝像機系統(tǒng)、多攝像機系統(tǒng)根據(jù)對象單目標、多目標簡單默認的運動情況單攝像機固定不動的單一運動目標第五頁，共九十頁，編輯于2023年，星期五概述時間序列圖像（運動圖像）攝像機放置在三維空間的某一位置上，對運動物體進行觀測，所拍攝到的一系列圖像

運動物體特征特征點：尖銳點特征直線：邊緣直線特征曲線：邊緣曲線可用來觀察分析物體的運動第六頁，共九十頁，編輯于2023年，星期五運動估計要研究的基本問題估計運動前后相鄰時刻兩幅圖像上對應點坐標之間的差值，即運動矢量。特征對應：運動物體上的特征與其在二維圖像平面上的投影坐標的對應關系OYXZyxP(X,Y,Z)P’(X,Y,Z)p(x,y)p’(x,y)(Δx,Δy)(ΔX,ΔY,ΔZ)第七頁，共九十頁，編輯于2023年，星期五運動分析方法根據(jù)時間相鄰的兩幅或多幅圖像求解物體的運動參數(shù)和三維結構信息圖像序列的光流分析方法運動信息一階：位移二階：速度三階：加速度運動圖像處理二維運動參數(shù)估計三維運動參數(shù)估計運動目標檢測與分割運動物體的三維結構及各個物體之間的空間關系第八頁，共九十頁，編輯于2023年，星期五剛體運動運動物體分為剛體和非剛體（柔體）。所謂剛體是指物體在運動過程中其幾何特征保持不變第九頁，共九十頁，編輯于2023年，星期五對應于不同剛體運動模型的二維運動平移雙線性透視投影仿射第十頁，共九十頁，編輯于2023年，星期五觀察到的二維運動與真實的投影二維運動的不一致性第十一頁，共九十頁，編輯于2023年，星期五二維運動估計兩幀視頻圖像和之間的運動估計。t1到t2時刻的位移矢量（運動矢量）為，其中所有點的運動矢量形成運動場當前幀：參考幀：第十二頁，共九十頁，編輯于2023年，星期五前向運動估計與后向運動估計后向運動估計前向運動估計xxxd(x,t;t-dt)d(x,t;t+dt)t-dttt+dt在基于運動補償?shù)囊曨l編碼中常用第十三頁，共九十頁，編輯于2023年，星期五二維運動估計存在的幾個問題遮擋問題孔徑問題噪聲問題第十四頁，共九十頁，編輯于2023年，星期五二維運動模型及估計方法參數(shù)模型：物體運動被建模為某種映射形式。全局---攝像機移動、單個運動物體區(qū)域---多個運動物體（運動區(qū)域分割）非參數(shù)模型：對運動場施加平滑約束條件。光流、像素、隨機場---估計每個像素運動矢量塊匹配---分割成小的規(guī)則塊，估計每個塊的運動矢量網(wǎng)格---分割成不重疊的多邊形單元，可克服塊失真

第十五頁，共九十頁，編輯于2023年，星期五四種二維運動估計方法基于像素全局基于區(qū)域基于塊第十六頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第十七頁，共九十頁，編輯于2023年，星期五基于光流的運動估計光流觀察動態(tài)物體時在視網(wǎng)膜上產(chǎn)生連續(xù)的光強變化，如同光的“流動”。在視頻序列運動估計中，觀察到的二維運動。視頻序列空間坐標關于時間的變化率

---像素的瞬時速度矢量。

第十八頁，共九十頁，編輯于2023年，星期五基于光流的運動估計光流方程亮度守恒假設：運動物體點的亮度（或色度）在其運動軌跡上保持不變，變化的是物體的位置?；蚱渲袨榭臻g梯度向量，為光流場。第十九頁，共九十頁，編輯于2023年，星期五其中：為圖像空間梯度方向上的單位矢量基于光流的運動估計光流v的分解將光流v分解為兩個正交的分量：為切線方向上的單位矢量只能確定圖像空間梯度方向上的分量（法向流）即：孔徑問題第二十頁，共九十頁，編輯于2023年，星期五圖像梯度的計算光流方程的要求：亮度函數(shù)可微數(shù)字視頻：有限差分法近似m,nm+1,nm,n+1m+1,n+1第二十一頁，共九十頁，編輯于2023年，星期五基于光流的運動估計光流方程一個方程，兩個未知數(shù)多點鄰域約束假設的鄰域內所有像素具有相同的光流矢量，光流方程在領域上的誤差定義為：其中為分配給

的權重。令可得：第二十二頁，共九十頁，編輯于2023年，星期五基于光流的運動估計多點鄰域約束則光流矢量的估計值為：第二十三頁，共九十頁，編輯于2023年，星期五基于光流的運動估計運動場的平滑性第二十四頁，共九十頁，編輯于2023年，星期五基于光流的運動估計運動平滑約束由Horn和Schunck提出，對整個運動場或局部窗施加全局平滑約束。目標誤差函數(shù)為：其中為運動估計的定義域，可以是整幅圖像或一個局部窗。為光流空間梯度的平方函數(shù)，它反映了光流矢量隨像素變化的快慢程度為光流方程誤差的平方函數(shù)第二十五頁，共九十頁，編輯于2023年，星期五對求關于和的偏微分，并令其為0，可得：基于光流的運動估計運動平滑約束最小化施加光流約束最小化施加運動平滑約束表示對像素鄰域（不包括當前像素）求平均。表示迭代次數(shù)，初始光流矢量可設為零。第二十六頁，共九十頁，編輯于2023年，星期五基于光流的運動估計有向平滑約束Horn-Schunck方法的運動平滑假設并不一定成立“運動邊緣”現(xiàn)象：實際的運動場在物體邊緣處是不連續(xù)的，施加全局平滑約束導致物體邊界的運動估計不精確引入有向平滑，減少圖像空間梯度方向上的平滑約束方法：將平滑約束中引入權值矩陣，即：為常數(shù)第二十七頁，共九十頁，編輯于2023年，星期五基于光流的運動估計有向平滑約束誤差函數(shù)：當F=0，時，Horn-Schunck運動平滑約束方法有向平滑約束方法的一個特列第二十八頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第二十九頁，共九十頁，編輯于2023年，星期五基于像素的運動估計與光流法一樣，估計每個像素的運動矢量位移幀差像素x從t1時刻到t1+dt時刻的位移幀差為：為x處的位移矢量由亮度守恒假設，即：兩邊同時除以dt，可得：（光流方程）第三十頁，共九十頁，編輯于2023年，星期五多點鄰域約束假設的鄰域內所有像素具有相同的運動矢量，領域上的誤差函數(shù)為：基于像素的運動估計其中，w(x)為分配給x的權重。誤差函數(shù)關于運動矢量di的梯度為：使用基于一階梯度下降的方法求解運動矢量di：為更新步長。也可以使用窮盡搜索法尋找di。第三十一頁，共九十頁，編輯于2023年，星期五像素遞歸法沿圖像掃描方向逐個估計像素的運動矢量。新像素的運動矢量由已估計像素的運動矢量進行預測使用基于位移幀差函數(shù)最小化的方法更新運動矢量像素的位移矢量無需編碼解碼器端使用同樣的預測更新機制估計精度較低，預測誤差較大基于像素的運動估計局部平滑約束光流約束第三十二頁，共九十頁，編輯于2023年，星期五基于像素的運動估計基于梯度下降的算法(Netravali-Robbins)最小化位移幀差函數(shù)迭代方程：為更新步長；為關于d的梯度。關于位移矢量的梯度計算關于圖像梯度的計算終止迭代條件：更新項或位移幀差小于某閾值收斂速度取決于的選取同樣存在孔徑問題第三十三頁，共九十頁，編輯于2023年，星期五基于像素的運動估計自適應步長算法如果很小，需要較多的迭代次數(shù)如果較大，運動矢量可能會在真實值附近震蕩。圖像梯度的大小影響更新的速度邊界區(qū)域：梯度大，小的更新平坦區(qū)域：梯度小，大的更新Walker-Rao算法Caffario-Rocca算法可以避免在平坦亮度區(qū)域（空間梯度幾乎全為0）出現(xiàn)除以0的情況第三十四頁，共九十頁，編輯于2023年，星期五基于像素的運動估計使用多點鄰域約束的像素遞歸法目標誤差函數(shù)為：123456x1~6為已經(jīng)估計的像素x為當前像素第三十五頁，共九十頁，編輯于2023年，星期五基于像素的運動估計基于貝葉斯準則的方法基于運動估計問題的概率公式隨機場視頻圖像函數(shù)觀察模型運動場運動場模型運動場估計最大后驗概率(MAP)問題用概率密度函數(shù)建模運動場給定兩幀圖像下運動場的后驗概率密度函數(shù)使用貝葉斯公式:不包含運動矢量，視為常數(shù)似然性測度運動場的先驗概率模型第三十六頁，共九十頁，編輯于2023年，星期五基于像素的運動估計基于貝葉斯準則的方法運動場最大后驗概率估計：似然模型：對運動場施加光流約束噪聲-->沿運動軌跡的亮度改變，如噪聲為高斯分布，均值為0，方差為先驗模型：對運動場施加平滑約束第三十七頁，共九十頁，編輯于2023年，星期五基于像素的運動估計基于貝葉斯準則的方法團（clique）可包含一個或多個像素為一個團上的勢函數(shù)包含兩個像素的團，其勢函數(shù)為：最大化最小化4像素領域8像素領域第三十八頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第三十九頁，共九十頁，編輯于2023年，星期五基于塊的運動估計將圖像分成一個個規(guī)則的圖像塊，對每個塊進行運動估計。廣泛應用于各種視頻壓縮編碼標準中。塊運動模型塊平移模型假定每個塊只做平移運動優(yōu)點：實現(xiàn)簡單缺點：1、不能表征旋轉、縮放和局部變形；2、物體邊界和塊邊界通常不一致，導致塊失真；3、同一塊可能包含多個運動物體。可變形塊模型可以對物體的旋轉、縮放、變形建模三種模型：投影運動、仿射運動、雙線性運動方法：相位相關法、塊匹配法第四十頁，共九十頁，編輯于2023年，星期五基于塊的運動估計塊平移模型a)非重疊塊b)重疊塊第四十一頁，共九十頁，編輯于2023年，星期五塊匹配法（BMA）參考幀當前幀第四十二頁，共九十頁，編輯于2023年，星期五塊匹配法（BMA）匹配函數(shù)歸一化互相關函數(shù)均方誤差絕對值誤差匹配像素數(shù)如果N1，N2固定，即塊的大小一定第四十三頁，共九十頁，編輯于2023年，星期五全搜索塊匹配算法（EBMA）全搜索計算量非常大！如使用MAD匹配準則，全搜索一個塊需計算減法、絕對值、加法各N1N2(2s+1)2次搜索算法N1N2x搜索窗N1+2sN2+2ss：搜索范圍第四十四頁，共九十頁，編輯于2023年，星期五分數(shù)精度真實運動未必是整數(shù)值分數(shù)精度搜索可提高運動估計的精度半像素精度MPEG-1、MPEG-2、H.2631/4和1/8像素精度MPEG-4、H.264第四十五頁，共九十頁，編輯于2023年，星期五分數(shù)精度原始參考圖像線性內插內插后的參考圖像MN2M2N第四十六頁，共九十頁，編輯于2023年，星期五降低計算復雜度的方法不降低估計精度的搜索方法通過減少每個候選塊的運算量部分失真搜索法（提前退出法）三角不等式法犧牲估計精度的搜索方法（快速搜索算法）通過減少候選塊的數(shù)目三步搜索法新三步搜索法二維對數(shù)搜索法交叉搜索法菱形搜索法其他方法：四步搜索法、遺傳搜索法、鉆石搜索法等第四十七頁，共九十頁，編輯于2023年，星期五部分失真搜索法又稱提前退出法在全搜索塊匹配方法（或其他快速搜索方法）基礎上，在每次失真測度計算之后加入一個判斷搜索窗每移動一個位置，都將保留最小的失真測度當搜索窗移動到某個位置時，失真測度進行累加計算，每計算一次（一個像素），比較當前失真累加值與前面保留的最小失真測度，如果當前失真累加值較大，則停止計算，將搜索窗移動到下一個位置，反之，則繼續(xù)進行累加。第四十八頁，共九十頁，編輯于2023年，星期五三角不等式法與部分失真搜索法相同，搜索窗每移動一個位置，保留最小的失真測度，如絕對值誤差和（SAD）min根據(jù)三角不等式先計算圖像塊的灰度值和，包括當前塊（只一次就可以了）和搜索塊如果兩個灰度值和之間的差值已經(jīng)超出了保留的最小失真測度，則停止運算，匹配下一個位置。第四十九頁，共九十頁，編輯于2023年，星期五三步搜索法search9+8+8=25points第五十頁，共九十頁，編輯于2023年，星期五新三步搜索法searchcases：1、9+8=17points2、9+8+8+8=33points3、9+8+3=20points小位移矢量的出現(xiàn)概率較大第五十一頁，共九十頁，編輯于2023年，星期五二維對數(shù)搜索法searchatmost5+4+2+3+2+8=24points菱形排列的四個點以及零位移點第五十二頁，共九十頁，編輯于2023年，星期五交叉搜索法searchatmost5+4+4+4=17points二維對數(shù)法：使用（+）型的4個點交叉搜索法：使用（X）型的4個點第五十三頁，共九十頁，編輯于2023年，星期五菱形搜索法性能最優(yōu)異的算法之一，被MPEG-4標準采納1ststep2ndstep3rdstep4thstep5thstep各步驟之間的相關性較大由移動模版而新增加的檢測點不多9個檢測點的大模版5個檢測點的小模版第五十四頁，共九十頁，編輯于2023年，星期五可變形塊匹配方法塊平移模型的缺陷之一：實際的物體運動不是簡單的平移運動可變形塊可解決此缺陷，可對物體的旋轉、縮放、變形等建模對節(jié)點進行運動估計，塊內像素的運動矢量使用節(jié)點運動矢量內插得到當前幀參考幀第五十五頁，共九十頁，編輯于2023年，星期五可變形塊匹配方法基于節(jié)點的可變形塊模型假設塊的控制節(jié)點（如塊的頂點）可自由運動對每個節(jié)點求取位移矢量塊內像素的位移矢量由節(jié)點位移矢量內插得到優(yōu)點：比多項式表示的可變形運動模型更加直觀估計塊節(jié)點的運動比估計多項式參數(shù)容易第五十六頁，共九十頁，編輯于2023年，星期五可變形塊匹配方法內插公式K=1，退化為平移模型K=3，對應于仿射運動模型K=4，對應于雙線性運動模型第k個節(jié)點對像素x的貢獻，稱內插核第五十七頁，共九十頁，編輯于2023年，星期五可變形塊匹配方法內插核需滿足的條件保證運動的連續(xù)性保證節(jié)點處的運動只與其自身有關第五十八頁，共九十頁，編輯于2023年，星期五可變形塊匹配方法內插核函數(shù)設計使用與節(jié)點結構相關的形狀函數(shù)標準三角形標準四邊形第五十九頁，共九十頁，編輯于2023年，星期五可變形塊匹配方法節(jié)點的運動估計匹配函數(shù)最小化匹配函數(shù)方法全搜索法：需較大的計算量基于梯度的迭代法（Newton-Raphson）其中：第六十頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第六十一頁，共九十頁，編輯于2023年，星期五基于網(wǎng)格的運動估計(a)基于塊匹配的運動估計(b)基于網(wǎng)格的運動估計(c)基于網(wǎng)格的運動跟蹤第六十二頁，共九十頁，編輯于2023年，星期五基于網(wǎng)格的運動估計(a)使用三角形網(wǎng)格(b)使用四邊形網(wǎng)格當前幀被分割為不重疊的多邊形單元（網(wǎng)格），運動估計為網(wǎng)格的每個節(jié)點在參考幀找到對應點（即得到其運動矢量），其余點的位移矢量由節(jié)點的運動矢量插值得到。第六十三頁，共九十頁，編輯于2023年，星期五基于網(wǎng)格的運動估計單元內像素的運動由節(jié)點的運動矢量內插得到每個網(wǎng)格節(jié)點只有一個運動矢量，與其相鄰的所有多邊形單元共享此運動矢量第六十四頁，共九十頁，編輯于2023年，星期五基于網(wǎng)格的運動估計主要步驟建立網(wǎng)格規(guī)則網(wǎng)格自適應網(wǎng)格復雜運動的區(qū)域節(jié)點密集，簡單運動的區(qū)域節(jié)點稀疏節(jié)點運動估計最小化位移幀差函數(shù)二階梯度迭代先后順序光柵掃描根據(jù)節(jié)點處圖像梯度值分組第六十五頁，共九十頁，編輯于2023年，星期五自適應三角形網(wǎng)格的建立圖像梯度較大：區(qū)域運動較復雜預測誤差較大：此區(qū)域的運動模型建模失效SG（x,y）和PPE（x,y）非零時：網(wǎng)格節(jié)點密集圖像梯度預測誤差如果如果重建圖像運動補償圖像第六十六頁，共九十頁，編輯于2023年，星期五節(jié)點運動估計更新第n個節(jié)點的運動矢量時，其余節(jié)點的運動矢量保持不變S(n)表示與第n個節(jié)點相連接的多邊形單元全搜索法基于梯度下降的方法第六十七頁，共九十頁，編輯于2023年，星期五節(jié)點運動估計步驟節(jié)點運動估計初始值：塊匹配法按順序迭代估計每個節(jié)點給定某個節(jié)點，固定其他節(jié)點在不改變拓撲結構的范圍內移動該節(jié)點，計算誤差函數(shù)最小化誤差函數(shù)更新的運動矢量滿足某條件，終止迭代每個節(jié)點的更新過程全搜索梯度下降第六十八頁，共九十頁，編輯于2023年，星期五基于網(wǎng)格的運動估計基于網(wǎng)格全搜索塊匹配(半像素精度)參考幀當前幀預測圖像第六十九頁，共九十頁，編輯于2023年，星期五基于網(wǎng)格的運動估計與塊匹配法的比較網(wǎng)格當前幀可以分成規(guī)則的或不規(guī)則的網(wǎng)格參考幀中的不規(guī)則網(wǎng)格是不重疊的每個節(jié)點只有一個運動矢量可變形塊當前幀分成規(guī)則的網(wǎng)格參考幀中的不規(guī)則網(wǎng)格是重疊的每個節(jié)點有多個運動矢量不可變形塊當前幀分成規(guī)則的網(wǎng)格參考幀中的規(guī)則網(wǎng)格是重疊的第七十頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第七十一頁，共九十頁，編輯于2023年，星期五基于區(qū)域的運動估計將視頻圖像分割為多個區(qū)域，每個區(qū)域對應一個特定的運動，然后為每個區(qū)域估計運動參數(shù)區(qū)域分割：力圖區(qū)域內的所有像素的運動具有一致性，可以由一個運動模型表示運動模型：仿射模型、雙線性模型、投影模型方法分類區(qū)域優(yōu)先運動優(yōu)先聯(lián)合區(qū)域分割和運動估計第七十二頁，共九十頁，編輯于2023年，星期五基于區(qū)域的運動估計區(qū)域優(yōu)先的方法基于當前幀的紋理、邊緣信息進行區(qū)域分割局部區(qū)域的直方圖區(qū)域連接增長為每個區(qū)域估計運動參數(shù)表示當前幀第n個區(qū)域Rn中像素x的運動矢量區(qū)域誤差函數(shù)：表示Rn的運動參數(shù)矢量可以是仿射、雙線性、投影運動模型中的任意一種第七十三頁，共九十頁，編輯于2023年，星期五基于區(qū)域的運動估計運動優(yōu)先的方法首先估計整個運動場光流、像素、塊、網(wǎng)格等方法運動場分割聚類：將具有相似運動矢量的像素進行聚合，形成區(qū)域。分層：分成主導運動和次主導運動，從占主導的區(qū)域開始，剔除誤差較大的區(qū)域，等到第一層；然后進一步剔除區(qū)域，直到?jīng)]有剔除區(qū)域。第七十四頁，共九十頁，編輯于2023年，星期五基于區(qū)域的運動估計聯(lián)合區(qū)域分割和運動估計的方法區(qū)域分割和運動估計相互依賴，相輔相成?？山惶孢M行區(qū)域分割和運動估計第七十五頁，共九十頁，編輯于2023年，星期五提綱概述基于光流的運動估計基于像素的運動估計基于塊的運動估計基于網(wǎng)格的運動估計基于區(qū)域的運動估計全局運動估計多分辨率運動估計第七十六頁，共九十頁，編輯于2023年，星期五全局運動估計整幅圖像的運動可以用單一的運動模型表示通常指攝像機相對于靜止場景運動產(chǎn)生的運動整個場景作為一個整體運動（很少發(fā)生）。方法直接估計法間接估計法第七十七頁，共九十頁，編輯于2023年，星期五全局運動估計直接估計法誤差函數(shù)：表示全局運動參數(shù)矢量可以是仿射、雙線性、投影運動模型中的任意一種為權值系數(shù)，調節(jié)可減小與全局運動不匹配的像素對誤差函數(shù)的影響。第七十八頁，共九十頁，編輯于2023年，星期五是的線性函數(shù)，即全局運動估計間接估計法假設已經(jīng)得到一些特征點的運動矢量匹配誤差函數(shù)：對上式求偏導并令其為零，可得運動參數(shù)：第七十九頁，共九十頁，編輯于2023年，星期五全局運動估計間接估計法若全局運動建模為仿射運動模型（正交投影）仿射運動模型的矩陣為減小矩陣計算量，可分別估計x和y方向上的參數(shù)如估計