計算機視覺大型攻略 —— 光流（1）基本原理和經典算法

這篇寫光流基本原理，及經典算法Lucas-Kanade，Horn-schunk。大量圖檔和公式出自LearnOpen3和下面幾個PPT。

https://download.csdn.net/download/plateros/11961100

https://download.csdn.net/download/plateros/11961087

相關論文，

[1] An Iterative Image Registration Technique with an Application toStereo Vision

[2] Determining optical flow

[3] Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the algorithm

光流

光流算法尋找一張圖檔上的像素在另一張圖檔的位置。這兩張圖檔一般是時間序列圖檔。算法輸出了像素的速度，也可以說是像素在這兩張圖檔的相對位置變化。計算圖檔中每個像素的光流，稱為稠密光流，而隻對特定像素點計算光流的算法就是稀疏光流。

如上圖，光流問題就是估計連續圖像像素的運動，等價于尋找連續圖像中像素的相關性。

關鍵假設

經典光流算法使用了如下假設

• 顔色/亮度恒定假設(Color Constancy/Brightness Constancy)
• 小運動假設

Brightness Constancy可知，

在小運動的假設下，我們用泰勒公式将函數展開，做線性化近似，

令

， 聯立上面兩個方程，

當u, v趨近于0時，

可以替換成

 。

這個公式的具體含義請見下圖，                         

• Ix, Iy是I(x, y)在空間上的導數，即圖像的梯度。通過Sobel filter等就可以獲得。
• It為時間上的導數，可以通過兩幀圖像做減法獲得。

• u, v代表光流，是未知量。這個方程有兩個未知數，僅由一個像素是無法求解這個方程的。後續出現很多求近似解的算法，最有代表性的就是Lucas-Kanade與Horn-schunck

Lucas-Kanade算法

1981年，論文[1]提出了Lucas-Kanade算法。該算法引入一個新的假設求解上面這個方程 ——空間一緻性假設。假設同一平面上鄰近的點具有相似的運動，具體來說就是選取一個mxn的視窗，在此視窗内假定光流值相同，是以這種算法也被稱為constant flow。舉個例子，假設我們選取5x5的視窗，如果在此視窗内光流相同，我們就可以得到25個公式，

                                                             ......

寫成矩陣的形式，

  采用最小二乘法求解這個方程組的近似解,     

       ,

最小化此方程，等價于求解                  

如果

可逆，可以求出x,

将光流公式代入，

可以看到

秩為2，當其滿秩時，矩陣可逆，也即

有兩個較大的特征向量時。圖像中紋理至少有兩個方向的區域，這個條件不難滿足，聯想到Harris角點檢測算法， 當跟蹤視窗的中心在圖像的角點區域時，

的特性最好。

傳送門:  Harris角點

LK算法最初用于求稠密光流，但是由于其對角點有較多要求，是以通常隻能應用于稀疏光流。

這個算法假設視窗内光流一緻，然而這樣的視窗不易選擇。視窗越小，越容易出現孔徑問題， 視窗越大，越無法保證視窗内光流的一緻性。

舉一個孔徑問題的例子，

這個視窗内所有x軸方向的梯度為0(Ix(i,j)=0)，隻能算出v，而無法算出u。

Horn-Schunck算法

Horn-Schunck算法引入了另一種假設 - 平滑性。與LK的光流一緻性不同，他認為相鄰像素的運動是相近的，平滑的。                                                         

光強一緻性

與LK算法相同，HS算法同樣建立在光強一緻性假設上。事實上，HS算法是最早提出亮度恒定假設和推導出基本亮度恒定方程的方法之一。 與LK不同，HS是一種全局限制算法，也就是說，對每一個像素來說，都需要滿足尋找最優的光流值u,v， 使得

的模最小。

平滑性     

在平滑性假設下，相鄰像素的光流變化越小越好，

完整能量函數

全局限制算法需要引入能量函數E，算法的目的是擷取合适的參數使得E最小 ，

是能量函數的資料項，限制了光強一緻性，

是平滑項，限制了相鄰像素光流的平滑性。這一部分與原始論文有點不一樣，原始論文采用了拉普拉斯模闆計算像素的二階微分。這裡的

定義如下，其實也是像素的二階導數，這裡u, v表示的是光流，光流的導數其實就是像素的二階微分。

優化過程

求解這個能量函數的最小值。

首先對能量函數的u, v求偏導，

   E的極值意味着導數0，可以令這兩個偏導數為0。得到兩個新的公式，仔細看一下，這是一個線性系統。

寫成矩陣的形式，

可以把ukl和vkl解出來，

我後來發現上面推薦的卡内基梅隆大學的講義有一個筆誤，求逆的時候行列式是對的，伴随矩陣寫錯了，但是資源傳上去了貌似 沒法修改了。在這裡更正一下，                               

應該是，

換個形式，

,          

這兩個公式中，

,均是未知數，需要用疊代法求解這個線性方程組，

整個算法流程非常簡單，

1. 計算圖像梯度Ix, Iy
2. 計算前後兩幀圖像差It
3. 初始化光流，比如說u=0, v=0
4. 疊代求解上面兩個方程，直到收斂。

光流金字塔

無論是Lucas-kanade還是Horn-schunck算法，均有小運動的假設。然而在實際場景的下，無法保證這個假設。Jean-Yves Bouguet在論文[3]中提出了光流金字塔算法，以改善小運動假設帶來的弊端。

前後兩幀圖檔(image1, image2)按照一定的比例縮放，最下面一層為原始大小圖檔。算法從最頂端開始計算光流，将上一層估計的結果作為下一層估計的起始輸入進行估計，直到最後一層。是以這個過程也稱為coarse-to-fine。

圖像金字塔

首先看如何生成各層圖像。令

為圖像I的第0層。也即最高分辨率的原始圖像。L定義為層數。

表示第L-1層的圖像。

定義

表示第L-1層初始的光流。

表示第L層估計出來的光流。

論文中指出一般情況下不需要超過4層金字塔，這個說法可能有點随意。層數應該跟圖像分辨率有關。分辨率越大，同樣幅度的運動導緻的像素位移就會越大，層數需要的就越多。

當擷取某一層的光流後，就可以把這個結果作為下一層的初始輸入。原始論文每一層采用LK疊代光流。類似的，HS光流算法同樣可以采用這種方式獲得改善。

代碼

Github上關于LK和HS的代碼，對論文還原的最好的來自Eric yuan。可以通過代碼進一步了解論文。

https://github.com/xingdi-eric-yuan/optical-flow.git