Optical Flow

光流（Optical Flow）是一種研究圖像對齊的算法，一般包括兩大類：稀疏光流和稠密光流。顧名思義，稀疏光流就是研究圖像中稀疏點的光流，這些點一般是角點；稠密光流則是研究圖像中所有點的偏移量。

基本介紹

• 中文名：光流
• 外文名：Optical Flow
• 領域：計算機視覺
• 類別：圖像算法
• 套用：圖像配準，目標跟蹤

稀疏光流

稀疏光流是一類專門針對圖像上稀疏的點進行圖像配準的方法，也就是在參考圖上給定若干個點（一般為角點），找到其在當前圖像中的對應點。用數學的語言描述就是，給定參考圖T和當前圖I，計算參考圖T中的一個角點 在當前圖I中對應的點 ，其中 就是角點的偏移量。如果以當P點和Q點為中心的兩個小矩形視窗內的所有點都相同，那么就表示這兩個點是匹配的。

在實際的圖像數據中，由於有噪聲的存在，兩個對應點所在的小矩形視窗內的像素點不可能完全相同，因此可以考慮取其差異最小的一個位置為匹配點，也就求解如下目標函式：

其中 是一個以 為中心， 為半徑的矩形視窗。

上式可以用非線性最小二乘法進行求解，為了加速同時也為了計算大偏移量，一般使用圖像金字塔的方法來求解。其基本思想就是在小圖上先算出一個初始值，然後將這個初始值乘2作為下一層的初始值，這樣每層只需要疊代很少的步驟就可以收斂。具體計算每一層使用的算法是高斯牛頓法，具體做法如下：

將後一項進行一階Taylor展開得到：

將上式帶入目標函式可以得到：

其中：

對 求偏導數可以得到：

為了書寫方便，重新定義以下符號：

， ，

，

由此不難得到二元一次方程組：

解出 即可得到偏移量。

根據柯西不等式， 恆成立，只有當兩向量平行時才會取到等號，此時對應的圖像為純色或者只有單一的直線邊緣，因此一般要求特徵點為角點，這樣可以保證分母恆大於0.

稠密光流

稠密光流是一種針對圖像進行逐點匹配的圖像配準方法，不同於稀疏光流只針對圖像上若干個特徵點，稠密光流計算圖像上所有的點的偏移量，從而形成一個稠密的光流場。通過這個稠密的光流場，可以進行像素級別的圖像配準，所以其配準後的效果也明顯優於稀疏光流配準的效果。但是其副作用也是明顯的，由於要計算每個點的偏移量，其計算量也明顯大於稀疏光流。

稠密光流最早是Horn和Schunck在1981年提出並求解的，因此也被稱為H-S算法。其目標函式如下：

為了方便計算，可以考慮用稀疏光流中近似方法，對數據項進行線性近似，從而得到新的目標函式：

原始論文中的標準解法是採用變分法，得到一個Euler-Lagrange方程，然後通過數值方法求解偏微分方程。考慮到一般人沒學過泛函分析，此處我用初等微積分的知識進行求解。

將上面的定積分形式改寫成離散的形式：

注意上面的 是 的簡寫形式，不是偏導數。由此 可以看成是所有 構成的多元函式，套用多元函式的極值求解不難得到：

平滑項求偏導數含有4項是因為 這三項中均含有 這一項，為了書寫方便，捨去下標得到方程組：

上式中： ， ，

上面的方程組實際是一個大型稀疏線性方程組，一般採用疊代法求解，最容易編程實現的就是SOR（超鬆弛疊代法），解出上面的二元一次方程就可以得到相應的雅克比疊代公式：