稀疏光流
Optical Flow
Optical Flow
Optical Flow稀疏光流是一類專門針對圖像上稀疏的點進行圖像配準的方法 ，也就是在參考圖上給定若干個點（一般為角點），找到其在當前圖像中的對應點。用數學的語言描述就是，給定參考圖T和當前圖I，計算參考圖T中的一個角點 在當前圖I中對應的點 ，其中 就是角點的偏移量。如果以當P點和Q點為中心的兩個小矩形視窗內的所有點都相同，那么就表示這兩個點是匹配的。
在實際的圖像數據中，由於有噪聲的存在，兩個對應點所在的小矩形視窗內的像素點不可能完全相同，因此可以考慮取其差異最小的一個位置為匹配點，也就求解如下目標函式：
Optical Flow
Optical Flow
Optical Flow
Optical Flow其中 是一個以 為中心， 為半徑的矩形視窗。
上式可以用非線性最小二乘法進行求解，為了加速同時也為了計算大偏移量，一般使用圖像金字塔的方法來求解。其基本思想就是在小圖上先算出一個初始值，然後將這個初始值乘2作為下一層的初始值，這樣每層只需要疊代很少的步驟就可以收斂。具體計算每一層使用的算法是高斯牛頓法，具體做法如下：
將後一項進行一階Taylor展開得到：
Optical Flow
Optical Flow
Optical Flow將上式帶入目標函式可以得到：
Optical Flow
Optical Flow
Optical Flow其中：
Optical Flow對 求偏導數可以得到：
Optical Flow
Optical Flow為了書寫方便，重新定義以下符號：
Optical Flow
Optical Flow
Optical Flow， ，
Optical Flow
Optical Flow，
由此不難得到二元一次方程組：
Optical Flow
Optical Flow Optical Flow解出 即可得到偏移量。
Optical Flow
Optical Flow
Optical Flow根據柯西不等式， 恆成立，只有當兩向量平行時才會取到等號，此時對應的圖像為純色或者只有單一的直線邊緣，因此一般要求特徵點為角點，這樣可以保證分母恆大於0.
稠密光流
稠密光流是一種針對圖像進行逐點匹配的圖像配準方法，不同於稀疏光流只針對圖像上若干個特徵點，稠密光流計算圖像上所有的點的偏移量，從而形成一個稠密的光流場。通過這個稠密的光流場，可以進行像素級別的圖像配準，所以其配準後的效果也明顯優於稀疏光流配準的效果。但是其副作用也是明顯的，由於要計算每個點的偏移量，其計算量也明顯大於稀疏光流 。
稠密光流最早是Horn和Schunck在1981年提出並求解的 ，因此也被稱為H-S算法。其目標函式如下：
Optical Flow為了方便計算，可以考慮用稀疏光流中近似方法，對數據項進行線性近似，從而得到新的目標函式：
Optical Flow原始論文中的標準解法是採用變分法，得到一個Euler-Lagrange方程，然後通過數值方法求解偏微分方程。考慮到一般人沒學過泛函分析，此處我用初等微積分的知識進行求解。
將上面的定積分形式改寫成離散的形式：
Optical Flow
Optical Flow
Optical Flow
Optical Flow
Optical Flow
Optical Flow注意上面的 是 的簡寫形式，不是偏導數。由此 可以看成是所有 構成的多元函式，套用多元函式的極值求解不難得到：
Optical Flow
Optical Flow
Optical Flow Optical Flow平滑項求偏導數含有4項是因為 這三項中均含有 這一項，為了書寫方便，捨去下標得到方程組：
Optical Flow
Optical Flow
Optical Flow
Optical Flow
Optical Flow上式中： ， ，
上面的方程組實際是一個大型稀疏線性方程組，一般採用疊代法求解，最容易編程實現的就是SOR（超鬆弛疊代法），解出上面的二元一次方程就可以得到相應的雅克比疊代公式：
Optical Flow
Optical Flow