以條件數分析ＬＫ演算法
由Joab R. Winkler於2024年發表的文章Error Analysis and Condition Estimation of the Pyramidal Form of the Lucas-Kanade Method in Optical Flow 中，作者以條件數為手段，對金字塔形式的的Lucas-Kanade演算法進行分析，並得出了胎演算法在window大小、金字塔層數、角度等方面與條件數有關的特性。
在開始介紹這篇文章之前，有幾個需要注意的先備知識：Lucas-Kanade演算法、金字塔（coarse to fine）技巧、條件數，分別在之前的科普文章中有介紹過，詳情可以參考該篇科普文章，以下則是對與本期相關的內容的重點提示。
Lucas-Kanade演算法
ＬＫ演算法是基於經典的光流方程式：IxVx + IyVy = -It，並且以參考區域（window）包含進了多條方程式，而在實際計算光流的步驟時就是要解聯立方程組。
條件數
條件數中最常見的就是矩陣條件數，可以用來描述聯立方程組的特性，條件數的大小代表著解受到擾動影響的程度大小，或者反過來說就是該聯立方程組的易解性。
金字塔（coarse to fine）技巧
在傳統光流法的領域中，ＬＫ演算法被認為是一種速度快、準度普通的演算法。後來隨著平性計算技術的成熟和硬體持續增強，ＬＫ演算法也進行了一系列的改進，大幅提高了準確度，其中主要的手段就是金字塔技巧。金字塔技巧能增加準確度的原因在於，在推導經典光流方程式的過程中，使用了泰勒級數展開並捨棄高次項來近似，這個近似在光流大於1 pixel時會變得不準，降低解析度能讓該近似重新變得準確。
聯立方程組的條件數
要使用條件數分析ＬＫ演算法，首先還得有能描述聯立方程組的條件數。原本的條件數是用來描述一個方陣，而聯立方程組不一定是方陣（例如window是5*5時就有25條方程式，為25*2的狹長矩陣）、而且還是一個增廣矩陣（也就是在說矩陣算式Ax=b中，除了矩陣A，還要考慮到右邊的b）。
普通的條件數是A的範數（norm）與A的反矩陣的範數相乘即可得到，而本問題所需的條件數也與反矩陣有關。作者在經過了一系列推導與證明後，得出了包含A、b的條件數：
$$ \eta (A,b)=\frac{\left\| A^{+}\right\|\left\| b\right\|}{\left\| x_{0}\right\|}=\frac{\left\| A^{+}\right\|\left\| b\right\|}{\left\| A^{+}b\right\|}$$
其中，$A^+$指的是A的廣義反矩陣，雙直線是norm。
在上式中，位於分母的$x_0$向量其實就是方程組的解。因為在解Ax=b時，將兩邊同乘以A的廣義反矩陣，就會變成$x= A^{+}b$。
至於廣義反矩陣如何得到，也有多種方式，其中最通用的是：$(A^{T}A)^{-1}A^{T}$（註：由於目的是解Ax=b，這邊說的都是左逆陣）。這樣一來，只要分別再算出$A^+$ 和b的norm，就能得到包含A、b的條件數。
實驗結果
作者對一組測試資料運行了多次金字塔形式的的Lucas-Kanade演算法，測了演算法在不同參數（金字塔層數、window大小）下的條件數會如何變化，並將結果整理成附圖：
從圖中可以看出，金字塔層數大（解析度低），條件數越小；以及window越大，條件數越小。Window的部分比較好理解，越多條方程式自然會讓解更可靠，金字塔的部分則比較需要注意。
在直覺上，金字塔層數小時，解析度高，光流越來越準，為什麼反而條件數變大？這邊需要釐清精細程度和可靠程度的差別：金字塔在層層提升解析度的時候，提升了光流的精細程度，並在整體平均上顯得準確，但由於誤差也層層傳遞，每個點的可靠程度反而降低。這可以比喻成一張有許多道多選題的考卷，完全答對的比例降低但總得分提高。
作者的第三個發現是關於角度。條件數會受到向量b（由It們所組成）與矩陣A的列空間之間的夾角有關。當角度接近90度時，條件數會急劇增大，導致光流估算不穩定。
作者最後總結說，透過條件數的分析，ＬＫ演算法還有幾個能繼續改良的方向：試著在window內納入更多不同方向的梯度、在warping階段使用更好的函數和更適當的參數。
撰稿人：劉徹
參考資料
Winkler, J. R. (2024). Error Analysis and Condition Estimation of the Pyramidal Form of the Lucas-Kanade Method in Optical Flow. Electronics, 13(5), 812.
留言
張貼留言