經典光流算法：Lucas Kanade method
光流是透過偵測影像上光強度的變化，藉此判斷運動速度的方法。光流方程式如下：
$$I_xv_x+I_yv_y=-I_t$$
其中，$I_x$、$I_y$ 和$I_t$分別為x方向、y方向和時間的梯度，為已知的參數；$v_x, v_y$ 分別為x方向和y方向的速度，就是我們希望能解出來的光流。然而，一個方程式無法解出兩個未知數，因此需要添加其他的限制協助計算光流。
Lucas Kanade 是經典的光流算法，他假設鄰近點的光流都相同，因此每個點都得到一光流方程式，多條方程式就可以用最小平方法(least square method)擬合出最佳解$(v_x, v_y)$。
然而，圖像通常不會只有平移那麼簡單，因此若將原本的平移改成 Affine warping 表示，並給定template，比較其和 warping image 的誤差，warping 的參數可以藉由誤差最小化得到：
$$Err(u,v)=\Sigma[I(\textbf{W}(\textbf{x};\textbf{p}))-T(\textbf{x})]^2$$
其中，$W(x;p)$ 是考慮了線性變換和平移的結果：
$$W(x;p) = \begin{bmatrix}p_1 & p_2 & p_3 \\ p_4 & p_5 & p_6\end{bmatrix}\begin{bmatrix}x \\ y \\1\end{bmatrix}$$
假如已經有初始值 p，誤差則可以改寫為：
$$Err(u,v)=\Sigma[I(\textbf{W}(\textbf{x};\textbf{p}+\Delta{\textbf{p}}))-T(\textbf{x})]^2$$
因此目標變為解出p的變化量 $\Delta{p}$，並透過迭代，逐漸逼近最佳的p。$$p \leftarrow p + \Delta{p}$$
那要如何求得 $\Delta p$ 呢？ 首先將誤差以一階泰勒展開式展開：
$$Err(u,v)=\Sigma[I(\textbf{W}(\textbf{x};\textbf{p}))+\nabla{I}\frac{\partial \textbf{W}}{\partial \textbf{p}}\Delta \textbf{p}-T(\textbf{x})]^2\\=\Sigma[\nabla{I}\frac{\partial \textbf{W}}{\partial \textbf{p}}\Delta p-[T(\textbf{x})-I(\textbf{W}(\textbf{x};\textbf{p}))]]^2$$
可將之以最小平方法解 $x=(A^T A)^{-1}A^Tb$：
$$\Delta p=H^{-1}\Sigma[\nabla{I}\frac{\partial \textbf{W}}{\partial \textbf{p}}[T(\textbf{x})-I(\textbf{W}(\textbf{x};\textbf{p}))]]^2$$
其中，H 為 Hessian：
$$H=\Sigma[\nabla{I}\frac{\partial \textbf{W}}{\partial \textbf{p}}]^T[\nabla{I}\frac{\partial \textbf{W}}{\partial \textbf{p}}]$$
由此可得$\Delta p$，就可以更新p，進行下一次迭代，直到 p 收斂。
總結Lucas Kanade的算法：
1. Warp 圖像 $I(\textbf{W}(\textbf{x};\textbf{p}))$
2. 計算誤差 $[T(\textbf{x})-I(\textbf{W}(\textbf{x};\textbf{p}))]^2$
3. 計算梯度$\nabla I(x')$
4. 計算 Jacobian $\frac{\partial \textbf{W}}{\partial \textbf{p}}$
5. 計算 Hessian H
6. 得到 $\Delta p$
7. 更新 $p \leftarrow p + \Delta{p}$
Lucas Kanade 是光流計算中相當經典的算法，主要使用了最小平方法解決光流問題，可以實時運行。此外，本文沒有提及的是，由於此方法較適合用於小位移，因此目前opencv中的lucas kanade method 有使用金字塔迭代，增加能計算的位移量，有興趣的讀者可以參考：Bouguet, Jean-Yves. "Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm." Intel corporation 5.1-10 (2001): 4.
撰文：吳芯瑀
Reference:
Baker, Simon, and Iain Matthews. "Lucas-kanade 20 years on: A unifying framework." International journal of computer vision 56 (2004): 221-255.
留言
張貼留言