用改良的Lucas-Kanade演算法偵測大位移的光流

如何處理位移大的情況向來是計算光流時常會遇到的問題，而就在最近(2023年)發表的一項研究為解決這個問題提供了一種思路。在本文中，首先會介紹為何位移(光流向量的長度)大時會是一個問題，然後介紹該問題可以如何解決。

為何位移大時會是一個問題？
首先我們需要了解計算光流這個問題是如何被分析、給予前提假設而得到基本光流方程式。光流是因為觀察著與景物之間的相對運動而產生的，亦即這一幀的某個特徵(物體或像素)經過一個正確的光流(向量)的變化後會對應到它在下一幀的位置，換句話說，圖像的灰度值在空間上(x、y)的變化和在時間上(t)的變化將會吻合，可以表示如下：
$$\partial th+\bigtriangledown_{xy}(\overrightarrow{v}\cdot h)=0 \cdots \cdots \cdots (1)$$
在實務上，由於時間最小單位為幀，是不連續的，所以應該表示成：
$$I(x,y,t)=I(x+\Delta x,y+\Delta y,t+\Delta t)\cdots \cdots \cdots (2)$$
然後我們可以將其用泰勒級數展開：
$$I(x+\Delta x,y+\Delta y,t+\Delta t)=I(x,y,t)+\frac{\partial I}{\partial x}\Delta x+\frac{\partial I}{\partial y}\Delta y+\frac{\partial I}{\partial t}\Delta t+高次項$$
然後我們對該展開做線性近似，也就是只取第一項、省略高次項。這個近似在光流向量長度小時會比較接近，大時就會差比較多，這就是為何位移大會是一個問題的原因所在。

以下，我們繼續推導，並說明該誤差的影響。
承上式，做完近似之後得到：
$$I(x+\Delta x,y+\Delta y,t+\Delta t)=I(x,y,t)+\frac{\partial I}{\partial x}\Delta x+\frac{\partial I}{\partial y}\Delta y+\frac{\partial I}{\partial t}\Delta t\cdots \cdots \cdots (4)$$
合併(2)、(4)，消掉相同的部分，剩下：
$$\frac{\partial I}{\partial x}\Delta x+\frac{\partial I}{\partial y}\Delta y+\frac{\partial I}{\partial t}\Delta t=0$$
最後再同除以$\Delta t$，即可得到基本光流方程式：
$$\frac{\partial I}{\partial x}V_{x}+\frac{\partial I}{\partial y}V_{y}+\frac{\partial I}{\partial t}=0$$
也可以寫成：$I_{x}V_{x}+I_{y}V_{y}=-I_{t}$

這是一個二元一次方程式，其中的未知數$V_{x}、V_{y}$就是光流向量的x、y分量，參數$I_{x}、I_{y}、I_{t}$是圖像在x、y、t方向的梯度。若將此二元一次方程式畫在$V_{x}、V_{y}$為軸的平面上，就會是一條直線，理想上，這條直線會通過代表正確光流的那個點。到這裡，必須引入另一個假設：在一個小範圍(window)內的光流皆相同，於是只要再從旁邊的像素找來一條線，那麼兩線交點就是正確的光流。然而，這些直線往往不會恰好通過正確答案。即使其他條件(比如光照恆定)都理想，來自於取近似的誤差仍然存在，而且位移越大、誤差越大，誤差越大、直線距離點(正確答案)就越遠。在位移較小的情況下，可以透過納入更多條直線來算出光流。比如經典的Lucas-Kanade演算法就是用最小平方法找出一個離所有直線最近的點。

如何處理位移大的情況？
對於位移大的情況，早先已經有一些辦法可以處理，例如pyramid、warp。但是這些方法本質上是對於既有演算法的強化，會需要進行許多額外的計算，而計算光流往往是對於速度有要求的，如果對於沒必要使用pyramid、warp的地方(位移較小)使用了就顯得很不划算，那有沒有辦法只在需要的時候(位移較大)使用pyramid、warp，其他時候使用原本的較快的演算法呢？答案是可以的，Saleh Al-Qudah 和 Mijia Yang在他們的研究《Large Displacement Detection Using Improved Lucas–Kanade Optical Flow》中實現了這件事情。
在所附的流程圖中，Lucas-Kanade演算法的warp、pyramid、traditional版本屬於是已知的，關鍵在於上面的那個菱形。研究者開發了一種足夠快的方法算出possible displacement magnitude，也就是猜測這個位置的光流大小，並用它來判斷要用warp、pyramid還是traditional的方法去計算。總而言之，經過以上改良的Lucas-Kanade演算法成功兼顧了在位移小時的速度和在位移大時的準確度。


撰稿人：劉徹


參考資料：
1. Al-Qudah, S., & Yang, M. (2023). Large Displacement Detection Using Improved Lucas–Kanade Optical Flow. Sensors, 23(6), 3152. https://doi.org/10.3390/s23063152
2. Baker, S., & Matthews, I. (2004). Lucas-kanade 20 years on: A unifying framework. International journal of computer vision, 56, 221-255. https://doi.org/10.1023/B:VISI.0000011205.11775.fd

留言

張貼留言