Lukas-Kanade光流法
光流是圖像亮度的運動信息描述。光流法計算最初是由Horn和Schunck于1981年提出的，創造性地將二維速度場與灰度相聯系，引入光流約束方程，得到光流計算的基本算法．光流計算基于物體移動的光學特性提出了2個假設：
①運動物體的灰度在很短的間隔時間內保持不變；
②給定鄰域內的速度向量場變化是緩慢的。
算法原理
假設圖像上一個像素點(x,y)，在t時刻的亮度為E(x+Δx,y+Δy,t+Δt)，同時用u(x,y)和v(x,y)來表示該點光流在水平和垂直方向上的移動分量：
u=dx/dt
v=dy/dt
在經過一段時間間隔Δt后該點對應點亮度為E(x+Δx,y+Δy,t+Δt),當Δt很小趨近于0時，我們可以認為該點亮度不變，所以可以有：
E(x,y,t)=E(x+Δx,y+Δy,t+Δt)
當該點的亮度有變化時，將移動后點的亮度由Taylor公式展幵，可得：
忽略其二階無窮小，由于Δt趨近于0時，有：
式中w=(u,v)，所以上式就是基本的光流約束方程。
其中令表示圖像中像素點灰度沿x，y，t方向的梯度，可將上式改寫成：
?
Lucas-Kanade是一種廣泛使用的光流估計的差分方法，這個方法是由Bruce D. Lucas和Takeo Kanade發明的。它假設光流在像素點的鄰域是一個常數，然后使用最小二乘法對鄰域中的所有像素點求解基本的光流方程。
通過結合幾個鄰近像素點的信息，盧卡斯-金出方法(簡稱為L-K方法)通常能夠消除光流方程里的多義性。而且，與逐點計算的方法相比，L-K方法對圖像噪聲不敏感。不過，由于這是一種局部方法，所以在圖像的均勻區域內部，L-K方法無法提供光流信息。
Lucas-Kanade改進算法
Jean-Yves Bouguet提出一種基于金字塔分層，針對仿射變換的改進Lucas-Kanade算法。
?
為什么要用金字塔？因為lk算法的約束條件即：小速度，亮度不變以及區域一致性都是較強的假設，并不很容易得到滿足。如當物體運動速度較快時，假設不成立，那么后續的假設就會有較大的偏差，使得最終求出的光流值有較大的誤差。
考慮物體的運動速度較大時，算法會出現較大的誤差。那么就希望能減少圖像中物體的運動速度。一個直觀的方法就是，縮小圖像的尺寸。假設當圖像為400×400時，物體速度為[16 16],那么圖像縮小為200×200時，速度變為[8,8]。縮小為100*100時，速度減少到[4,4]。所以在源圖像縮放了很多以后，原算法又變得適用了。所以光流可以通過生成 原圖像的金字塔圖像，逐層求解，不斷精確來求得。簡單來說上層金字塔（低分辨率）中的一個像素可以代表下層的兩個。
?
假設I和J是兩幅2D的灰度圖像，對于圖像上每個像素點的灰度值定義為：
I(x)=I(x,y) ??和 ?J(x)=j(x,y)
其中x=(x,y)是圖像上像素點的圖像坐標。
在實際場景中圖像I和圖像J可以代表前后兩幀圖像。對于圖像特征點金字塔跟蹤來說的目的是：對于前一幀的圖像I上一點u(ux,uy)，要在后一幀圖像J上找到一點v(ux+dx,uy+dy)與之相匹配，即灰度值最接近。那么向量d=[dx,dy]就是圖像在點u處的運動速度，也就是所說像素點u的光流。為了進一步說明向量d的含義。我們假設前一幀圖像經歷了仿射變換到后一幀圖像，定義變換矩陣為
其中四個參數dxx，dyy，dxy，dyx表征著圖像中的仿射變形。所以光流計算的目的轉變成找到向量d和變換矩陣A使得圖像上一塊區域內灰度差最小。
定義誤差
其中兩個整數wx和wy設定了圖像上矩形窗口的大小(2*wx+1)和(2*wy+1)。
典型的wx和wy取值為1，2，3，4，5，6，7個像素，相似度的函數被在(2ωx+1, 2ωy+1)的區域內定義。注意在金字塔各層窗口的大小是保持恒定的尺寸
對于Lucas-Kanade改進算法來說，主要的步驟有三步：建立金字塔，基于金字塔跟蹤，迭代過程。
?
?
金字塔的建立
令I0 = I 是第 0 層的圖像，它是金字塔圖像中分辨率最高的圖像，圖像的寬度和高度分別定義為nx0 = nx?和 ny0 = ny?。以一種遞歸的方式建立金字塔：從I0中計算I1，從I1中計算I2 ，···。令L =1, 2,...代表金字塔的層數，L通常取2,3,4。IL?1 是第L?1層的圖像，nxL?1 和 nyL?1分別是圖像IL?1 的寬度和高度。圖像IL可按如下方式由IL?1 求得：
即用一個[0.25 0.5 0.25]的低通濾波器對IL-1進行卷積。
?
金字塔跟蹤
總體來講，金字塔特征跟蹤算法描述如下：首先，光流和仿射變換矩陣在最高一層的圖像上計算出；將上一層的計算結果作為初始值傳遞給下一層圖像，這一層的圖像在這個初始值的基礎上，計算這一層的光流和仿射變化矩陣；再將這一層的光流和仿射矩陣作為初始值傳遞給下一層圖像，直到傳遞給最后一層，即原始圖像層，這一層計算出來的光流和仿射變換矩陣作為最后的光流和仿射變換矩陣的結果。
對于L=0,1,2,…L，定義是圖像中像素點u在第L層對應點的坐標。根據上一步中圖像金字塔的定義，可以計算出
我們用數學的思想重新描述在L層和L+1層迭代運算，假定在第L層有對被跟蹤目標的位置有個大致估計，而從第L+1層傳遞到L層的運動矢量，即光流計算初值為（后面會對gL做一個解釋）并且對于最上層的變換矩陣猜測
為了在L層上計算光流和仿射變換矩陣，需要重新定義在L層上的匹配誤差ξL：
其中圖像和是原始圖像在L層上采樣出來的圖像，基于這層中的光流和仿射矩陣初值gL和GL可以計算出兩個對應圖像和：
這里用L+1層得到的最初估計gL對L層作預平移，L層在gL的基礎上求該層的光流dL，這樣求得的殘余光流向量dL= [dLx, dLy]T就足夠小，因此能夠通過標準的光流法來求出這個運動矢量。然后得到的dL結合gL又可以對L-1層的gL-1做估計。最終的光流和就是在所有層的分段光流d的疊加。使用金字塔圖像計算光流的一個明顯的好處是，對于一個有著較大的像素偏移的矢量d，可以通過計算幾個比較小的殘余光流來得到。這里就是金字塔跟蹤算法的核心。
?
接下來就是計算該層上的光流dL和變換矩陣AL，我們將在下一步中談論。現在，假設在這一層上的光流和變換矩陣己經計算出來。接著將結果傳遞給下一層，計算出下一層的假設初值：
將gL-1和GL-1作為初值，重新循環上面的步驟，直到最上一層，計算出光流d和仿射變換矩陣A。
由于金字塔的縮放減小了光流值，最高層的光流估計值可以設為0，設頂層時的初始為：
這種算法最明顯的優勢在于對于每一層的光流都會保持很小，但是最終計算來的光流可以進行累積，便于有效地跟蹤特征點。
?
迭代過程
這一步是算法的核心步驟。在金字塔的每一層，目標是計算出光流dL和仿射變換矩陣AL從而使誤差ξL最小。由于每一層的迭代過程是相同的，所以我們就描述從一層到下一層的迭代過程。首先將上一層的光流u和A傳給這一層，計算這一幀圖像中像素點的光照，同時計算出圖像在該點x方向和y方向上的偏導
Ix=[I(x+1,y)-I(x-1,y)]/2
Iy=[I(x,y+1)-I(x,y-1)]/2
在此基礎上，計算出空間梯度矩陣：
更新光流v=2*v
迭代過程：計算后一幀圖像中對應像素點的灰度，計算兩
幀圖像間相同位置點的灰度值之差，在計算圖像之間的誤差
向量：
最后計算針對仿射光流
，
更新跟蹤結果
直到某個閾值，結束在這一層的迭代過程。
?
?
特征點選擇
因此，可按照以下的步驟選擇特征點：
1、計算圖像 I 中每一個像素的矩陣G和最小特征值λm。
2、尋找整副圖像中最小特征值 λm?中的最大特征值λmax。
3、保留最小特征值 λm?大于給定閾值的像素點。閾值通常取5% λmax?~10% λmax?。
4、保留 λm?局部最大值的像素：像素特征值 λm?大于其3*3 鄰域中其他像素的特征值?λm?。
5、剔除像素密集區域中的一些像素，確保圖像中相鄰像素的距離都大于給定的閾值（常取5~10 pixels）。
上述操作完成后，圖像 I 中剩下的像素即為選擇的特征點，并作為跟蹤特征點。特征點選擇算法的步驟5 確保了特征點間的最小距離。
沒有必要取一個大的綜合窗口選擇特征點（或計算矩陣G）。大量實驗證明，wx = wy =1的 3*3 大小的綜合窗口能夠取得滿意的效果。
?
?
金字塔高度的選擇
在大多數的情況下，超過4的金字塔圖像層次沒有太大的意義。
?
有時為了簡化可以將仿射變換矩陣G簡化為單位矩陣。
?
算法流程
總結
以上是生活随笔為你收集整理的Lukas-Kanade光流法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 分布式计算互相sayhello
- 下一篇： 服务器性能/压力测试工具http_loa