卢卡斯-卡纳德-托马希特征追踪

在电脑视觉，卢卡斯-卡纳德-托马希特征追踪（英文：Kanade–Lucas–Tomasi (KLT) feature tracker）是用来抽取特征的一种方法，最早被提出是为了解决传统上的影像配准问题，传统的影像配准技术通常都需要耗费大量资源，卢卡斯-卡纳德-托马希特征善用空间上的资讯，也因此在找匹配特征的时候搜寻的数量较少，结果就会比较快。

## 配准问题

传统的影像配准可以用下列的方式来描述:

x是一个向量，分别对应到两张图，$F(x)$和$G(x)$分别代表位置x的值，我们希望能找到视差向量$h$来最小化$F(x+h)$和$G(x)$的差异，$x$可能是在我们有兴趣的一块区域$R$

一些常见用来量测$F(x+h)$和$G(x)$差异的函式:

- L1 范数: $\sum_{x\in R}\left\vert F(x+h)-G(x) \right\vert$
- L2 范数: $\sqrt{\sum_{x\in R}\left [F(x+h)-G(x)\right ]^{2}}$
- 标准化的负相关: $\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}}}$

## 配准算法的基础描述

卢卡斯-卡纳德-托马希特征追踪是建立在两篇论文的研究成果，在第一篇，卢卡斯和卡纳德提出用影像的二次微分当作权重来对影像作局部搜寻

### 一维实例

如果$h$是两张影像的位移，那么$F(x)$和$G(x) = F(x+h)$就能以下列的式子近似:

$$F'(x) \approx \dfrac{F(x+h)-F(x)}{h}=\dfrac{G(x)-F(x)}{h}\,$$

于是

$$h \approx \dfrac{G(x)-F(x)}{F'(x)}\,$$

然而通常这个近似只有在位移$h$不是太大的时候准确，因为在这个近似里，不同的$x$值会影响$h$，因此我们通常会对$h$取平均:

$$h \approx \dfrac{\sum_{x}\dfrac{G(x)-F(x)}{F'(x)}}{\sum_{x}1}.$$

平均也可以更进一步写成下列的形式$\left \vert F''(x) \right \vert$成反比。

$$F''(x) \approx \dfrac{G'(x)-F'(x)}{h}.$$

另外我们可以定一个权重函式让表达更方面:

$$w(x) = \dfrac{1}{\left \vert G'(x)-F'(x) \right \vert}.$$

因此$h$也可以写成:

$$h = \dfrac{\sum_{x}\dfrac{w(x)\left [ G(x)-F(x) \right ]}{F'(x)}}{\sum_{x}w(x)}.$$

接着，可以运用牛顿法的写出下列的递回式，这个序列最后会收敛到最佳的$h$

$$\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}$$

### 另一种推导

上述的推导无法被一般化因为二维的线性近似不太一样，因此近似要改成下列的式子:

$$F(x+h) \approx F(x)+hF'(x),$$

l2 泛数形式的误差可以写成下列

$$E=\sum_{x}\left [F(x+h)-G(x)\right ]^{2}.$$

为了得到找到慧满足最小误差的$h$，对$E$作偏微分并令为0:

$\begin{align} <pre> 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 ] </pre> \end{align}$,

$$\Rightarrow h \approx \dfrac{\sum_{x} F'(x)[G(x)-F(x)]}{\sum_{x} F'(x)^{2}}\,$$

这个步骤基本上跟一维的实例是一样的，只是权重函式必须写成$w(x)=F'(x)^2.$ 所以递回关系可以表达成:

$$\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}$$

### 效能

在评估这个算法的效能时，我们通常会好奇$h_k$'可以多快收敛到真正的$h$。

如果我们看看下面这个例子:

$$F(x)=\sin x,$$

$$G(x)=F(x+h)=\sin (x+h).$$

当$\left\vert h\right\vert < \pi$，两种版本的配准算法都会收敛到正确的$h$。我们利用压抑影像中的高频来改进收敛的范围，也就是对影像作平滑化，当然同时一些细节也会丧失。但要注意的是，如果选用的平滑窗格比匹配的物体的大小大太多，物件可能会被压缩太多，使得找不到对应的匹配。

由于经过低通滤波器的影像可以用更低的分辨率去取样，我们采用由粗到精的层次化匹配策略。一张平滑化的低分辨率影像可以用来近似匹配，而之后再把算法用在高分辨率影像即可以让前面算出的匹配更准。

权重函式加速了收敛速度也增加了近似的准度，如果没有加权且$F(x)=\sin x$，当位移接近0.5个波长，计算出来的$h_1$便会来第一个递回变成0。

### 实作

实作卢卡斯-卡纳德-托马希特征追踪需要计算加权和$F'G,$ $F'F,$ and $(F')^2$，虽然$F'(x)$没办法准确地算出，却可以用下式估计:

$$F'(x) \approx \dfrac{F(x+\Delta x)-F(x)}{\Delta x},$$

### 多维的一般化推广

一维和二维的配准算法可以延伸到多维，同样地，我们也需要去最小化L2泛数

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

$\mathbf{x}$和 $\mathbf{h}$代表n维的行向量

线性近似:

$$F(\mathbf{x}+\mathbf{h}) \approx F(\mathbf{x})+\mathbf{h}\left(\dfrac{\partial}{\partial \mathbf{x}}F(\mathbf{x})\right)^{T}.$$

接着将$E$对$\mathbf{h}$作偏微分:

$\begin{align} <pre> 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) </pre> \end{align}$,

$$\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},$$

过程其实跟一维的推导很像。

### 更进一步的延伸

此方法也可以延伸到更复杂的矩阵变换，例如转动、放大缩小、剪切

$$G(x) = F(Ax+h),$$

$A$是一个线性转换，误差可以表示成下列的式子:

$$E=\sum_{x}\left [F(Ax+h)-G(x)\right ]^2.$$

接着可以再次利用线性估计来决定$\Delta A$和$\Delta h$的值:

$$F(x(A+\Delta A)+(h+\Delta h))$$

$$\approx F(Ax+h)+(\Delta Ax+\Delta h)\dfrac{\partial}{\partial x}F(x).$$

上述类似的近似手法也可以用来找误差表达式，在这里是个二次方程式，因此可借由微分寻找最小值。

当两张不同视角影像的亮度不同时，需要将线性转换假设成

$$F(x)=\alpha G(x)+\beta,$$

$\alpha$代表对比度调整而$\beta$代表亮度调整

将此式与一般的线性转换结合后，即可得

$$E=\sum_{x}\left [F(Ax+h)-(\alpha G(x)+\beta)\right ]^2$$

所以我们可以用 $\alpha,$ $\beta,$ $A,$ 和$h$去最小化E

## 点特征的侦测及追踪

在另一篇论文里，托马希和卡纳德用类似的方法提出了另外一种特征选取，如果其特征值和梯度矩阵皆大于某个阈值，则选取这个特征点，借由与上述相似的推导，我们可以把问题写成

$$\nabla d = e\,$$

在这里$\nabla$代表梯度。很巧的是，此式与上面的最后一个卢卡斯和卡纳德所提出的最后一个式子相同。如果梯度矩阵的两个特征值皆大于某阈值，则这个局部小块就会被认为是良好的特征点。

## 更多

- Kanade–Tomasi features in the context of feature detection
- Lucas–Kanade method An optical flow algorithm derived from reference 1.