查看“︁盧卡斯-卡納德-托馬希特徵追蹤”︁的源代码

在[[電腦視覺]]，'''盧卡斯-卡納德-托馬希特徵追蹤'''（[[英文]]：{{lang|en|Kanade–Lucas–Tomasi (KLT) feature tracker}}）是用來抽取特徵的一種方法，最早被提出是為了解決傳統上的影像配准問題，傳統的影像配准技術通常都需要耗費大量資源，盧卡斯-卡納德-托馬希特徵善用空間上的資訊，也因此在找匹配特徵的時候搜尋的數量較少，結果就會比較快。

== 配準問題 ==
傳統的影像配準可以用下列的方式來描述:

x是一個向量，分別對應到兩張圖，<math>F(x)</math>和<math>G(x)</math>分別代表位置x的值，我們希望能找到視差向量<math>h</math>來最小化<math>F(x+h)</math>和<math>G(x)</math>的差異，<math>x</math>可能是在我們有興趣的一塊區域<math>R</math>

一些常見用來量測<math>F(x+h)</math>和<math>G(x)</math>差異的函式:

* L<sub>1</sub> 范數: <math>\sum_{x\in R}\left\vert F(x+h)-G(x) \right\vert</math>
* L<sub>2</sub> 范數: <math>\sqrt{\sum_{x\in R}\left [F(x+h)-G(x)\right ]^{2}}</math>
* 標準化的負相關:   <math>\dfrac{-\sum_{x\in R}F(x+h)G(x)}{\sqrt{\sum_{x\in R}F(x+h)^{2}}\sqrt{\sum_{x\in R}G(x)^{2}}}</math>

== 配準演算法的基礎描述 ==
盧卡斯-卡納德-托馬希特徵追蹤<ref name="LK2">Bruce D. Lucas and Takeo Kanade. An Iterative Image Registration Technique with an Application to Stereo Vision. ''International Joint Conference on Artificial Intelligence'', pages 674–679, 1981.</ref>是建立在兩篇論文的研究成果，在第一篇，盧卡斯和卡納德提出用影像的二次微分當作權重來對影像作局部搜尋

=== 一維實例 ===
如果<math>h</math>是兩張影像的位移，那麼<math>F(x)</math>和<math>G(x) = F(x+h)</math>就能以下列的式子近似:

: <math>F'(x) \approx \dfrac{F(x+h)-F(x)}{h}=\dfrac{G(x)-F(x)}{h}\,</math>

於是

: <math>h \approx \dfrac{G(x)-F(x)}{F'(x)}\,</math>

然而通常這個近似只有在位移<math>h</math>不是太大的時候準確，因為在這個近似裡，不同的<math>x</math>值會影響<math>h</math>，因此我們通常會對<math>h</math>取平均:

: <math>h \approx \dfrac{\sum_{x}\dfrac{G(x)-F(x)}{F'(x)}}{\sum_{x}1}.</math>

平均也可以更進一步寫成下列的形式<math>\left \vert F''(x) \right \vert </math>成反比，

: <math>F''(x) \approx \dfrac{G'(x)-F'(x)}{h}.</math>

另外我們可以定一個權重函式讓表達更方面:

: <math>w(x) = \dfrac{1}{\left \vert G'(x)-F'(x) \right \vert}.</math>

因此<math>h</math>也可以寫成:

: <math>h = \dfrac{\sum_{x}\dfrac{w(x)\left [ G(x)-F(x) \right ]}{F'(x)}}{\sum_{x}w(x)}.</math>

接著，可以運用牛頓法的寫出下列的遞迴式，這個序列最後會收斂到最佳的<math>h</math>

<math>
\begin{cases}
h_{0} = 0 \\
h_{k+1} = h_{k} + \dfrac{\sum_{x}\dfrac{w(x)\left [ G(x)-F(x+h_{k})\right ]}{F'(x+h_{k})}}{\sum_{x}w(x)}
\end{cases}
</math>

=== 另一種推導 ===
上述的推導無法被一般化因為二維的線性近似不太一樣，因此近似要改成下列的式子:

: <math>F(x+h) \approx F(x)+hF'(x),</math>

l2 泛數形式的誤差可以寫成下列

: <math>E=\sum_{x}\left [F(x+h)-G(x)\right ]^{2}.</math>

為了得到找到慧滿足最小誤差的<math>h</math>，對<math>E</math>作偏微分並令為0:

: <math>
\begin{align}
 0 & = \dfrac{\partial E}{\partial h} \\
   & \approx \dfrac{\partial}{\partial h}\sum_{x}\left [F(x)+hF'(x)-G(x)\right ]^{2} \\
   & = \sum_{x}2F'(x)\left [F(x)+hF'(x)-G(x)\right ]
\end{align}</math>,
: <math>\Rightarrow h \approx \dfrac{\sum_{x} F'(x)[G(x)-F(x)]}{\sum_{x} F'(x)^{2}}\,</math>

這個步驟基本上跟一維的實例是一樣的，只是權重函式必須寫成<math>w(x)=F'(x)^2.</math> 所以遞迴關係可以表達成:

<math>
\begin{cases}
h_0 = 0 \\
h_{k+1}=h_k + \dfrac{\sum_x w(x)F'(x+h_k) \left [G(x)-F(x+h_k)\right ]}{\sum_x w(x)F'(x+h_k)^2}
\end{cases}
</math>

=== 效能 ===
在評估這個演算法的效能時，我們通常會好奇<math>h_k</math>'可以多快收斂到真正的<math>h</math>。

如果我們看看下面這個例子:

: <math>F(x)=\sin x,</math>
: <math>G(x)=F(x+h)=\sin (x+h).</math>

當<math>\left\vert h\right\vert < \pi</math>，兩種版本的配準演算法都會收斂到正確的<math>h</math>。我們利用壓抑影像中的高頻來改進收斂的範圍，也就是對影像作平滑化，當然同時一些細節也會喪失。但要注意的是，如果選用的平滑窗格比匹配的物體的大小大太多，物件可能會被壓縮太多，使得找不到對應的匹配。

由於經過低通濾波器的影像可以用更低的解析度去取樣，我們採用由粗到精的層次化匹配策略。一張平滑化的低解析度影像可以用來近似匹配，而之後再把演算法用在高解析度影像即可以讓前面算出的匹配更準。

權重函式加速了收斂速度也增加了近似的準度，如果沒有加權且<math>F(x)=\sin x</math>，當位移接近0.5個波長，計算出來的<math>h_1</math>便會來第一個遞迴變成0。

=== 實作 ===
實作盧卡斯-卡納德-托馬希特徵追蹤需要計算加權和<math>F'G,</math> <math>F'F,</math> and <math>(F')^2</math> ，雖然<math>F'(x)</math>沒辦法準確地算出，卻可以用下式估計:

: <math>F'(x) \approx \dfrac{F(x+\Delta x)-F(x)}{\Delta x},</math>

=== 多維的一般化推廣 ===
一維和二維的配準演算法可以延伸到多維，同樣地，我們也需要去最小化L<sub>2</sub>泛數

: <math>E=\sum_{\mathbf{x}\in R}\left [F(\mathbf{x}+\mathbf{h})-G(\mathbf{x})\right ]^{2},</math>

<math>\mathbf{x}</math>和 <math>\mathbf{h}</math>代表n維的行向量

線性近似:

: <math>F(\mathbf{x}+\mathbf{h}) \approx F(\mathbf{x})+\mathbf{h}\left(\dfrac{\partial}{\partial \mathbf{x}}F(\mathbf{x})\right)^{T}.</math>

接著將<math>E</math>對<math>\mathbf{h}</math>作偏微分:

: <math>\begin{align}
 0 & = \dfrac{\partial E}{\partial \mathbf{h}} \\
   & \approx \dfrac{\partial}{\partial \mathbf{h}}\sum_{\mathbf{x}}\left [F(\mathbf{x})+\mathbf{h}\left(\dfrac{\partial F}{\partial \mathbf{x}}\right)^{T}-G(\mathbf{x})\right ]^{2} \\
   & = \sum_{\mathbf{x}}2\left [F(\mathbf{x})+\mathbf{h}\left(\dfrac{\partial F}{\partial \mathbf{x}}\right)^{T}-G(\mathbf{x})\right ] \left(\dfrac{\partial F}{\partial \mathbf{x}}\right)
\end{align}</math>,

: <math>\Rightarrow \mathbf{h} \approx \left [\sum_{\mathbf{x}}\left [G(\mathbf{x})-F(\mathbf{x})\right ]\left (\dfrac{\partial F}{\partial\mathbf{x}}\right )\right ] \left [\sum_{\mathbf{x}}\left (\dfrac{\partial F}{\partial\mathbf{x}}\right )^{T}\left (\dfrac{\partial F}{\partial\mathbf{x}}\right )\right ]^{-1},</math>

過程其實跟一維的推導很像。

=== 更進一步的延伸 ===
此方法也可以延伸到更複雜的矩陣變換，例如轉動、放大縮小、剪切

: <math>G(x) = F(Ax+h),</math>

<math>A</math>是一個線性轉換，誤差可以表示成下列的式子:

: <math>E=\sum_{x}\left [F(Ax+h)-G(x)\right ]^2.</math>

接著可以再次利用線性估計來決定<math>\Delta A</math>和<math>\Delta h</math>的值:

: <math>F(x(A+\Delta A)+(h+\Delta h))</math>
: <math>\approx F(Ax+h)+(\Delta Ax+\Delta h)\dfrac{\partial}{\partial x}F(x).</math>

上述類似的近似手法也可以用來找誤差表達式，在這裡是個二次方程式，因此可藉由微分尋找最小值。

當兩張不同視角影像的亮度不同時，需要將線性轉換假設成

: <math>F(x)=\alpha G(x)+\beta,</math>

<math>\alpha</math>代表對比度調整而<math>\beta</math>代表亮度調整

將此式與一般的線性轉換結合後，即可得

: <math>E=\sum_{x}\left [F(Ax+h)-(\alpha G(x)+\beta)\right ]^2</math>

所以我們可以用 <math>\alpha,</math> <math>\beta,</math> <math>A,</math> 和<math>h</math>去最小化''E''

== 點特徵的偵測及追蹤 ==
在另一篇論文裡<ref name="TK">Carlo Tomasi and Takeo Kanade. Detection and Tracking of Point Features. ''Carnegie Mellon University Technical Report CMU-CS-91-132'', April 1991.</ref>，托馬希和卡納德用類似的方法提出了另外一種特徵選取，如果其特徵值和梯度矩陣皆大於某個阈值，則選取這個特徵點，藉由與上述相似的推導，我們可以把問題寫成

: <math>\nabla d = e\,</math>

在這裡<math>\nabla</math>代表梯度。很巧的是，此式與上面的最後一個盧卡斯和卡納德所提出的最後一個式子相同。如果梯度矩陣的兩個特徵值皆大於某閾值，則這個局部小塊就會被認為是良好的特徵點。

== 參考資料 ==
<references />

== 更多 ==

* [[角检测|Kanade–Tomasi features]] in the context of feature detection
* [[卢卡斯-卡纳德方法|Lucas–Kanade method]] An optical flow algorithm derived from reference 1.