以條件數分析ＬＫ演算法
由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\r...
