图像处理特征不变算子系列之KLT算子 论文, 世纪

yuyang911220

作者：kezunhai 出处：http://blog.csdn.net/kezunhai
正在前面的系列博文中，介绍了多种特征算子，在本文中将介绍由Kanade-Lucas两人在上世纪80年代在其论文：An Iterative Image Registration Technique with an Application to Stereo Vision中提出的一个算子，后来称为KLT算法。该算法最开始是一种图像点定位的方法，即图像的局部匹配，将图像匹配问题，从传统的滑动窗口搜索方法变为一个求解偏移量d的过程。后来，Jianbo Shi和Carlo Tomasi两人在1994的CVPR上发表了篇论文：Good Features To Track，进一步对KLT算法进行了完善，并在该文中分析了在求解d的过程中，哪些情况下可以保证一定能够得到d的解，这些情况的点有什么特点（其实就是一些角点）。下面的内容将对论文中介绍的KLT算法进行详细地介绍与分析。           最初，KLT算法是为了解决图像配准问题（Registration Problem）而提出的，可以表述如下：对于给定的图像F(x)和G(x)，需要找到一个视差向量（Disparity Vector）h使得F(x+h)与G(x)的差异最小，如下图：

F(x+h)与G(x)差异的典型度量方式有：

在上式中，为了求解视差向量h，需要计算各种可能的解空间下的F(x+h)与G(x)差异值，该种方式是一种非常耗时的计算。如果G(x)的大小是N×N，h的大小M×M，那么该种情况下的时间复杂度是O(M^2*N^2)。
          首先，我们来看看一维情况下的图像配准问题，如下图，我们希望找到F(x)和G(x)=F(x+h)的水平视差h：

此种情况，我们一般是采用通过对x的邻域进行线性逼近的方式来实现，对于一个很小的h，有：

接着，通过对不同的x进行逼近得到的h进行平均，就可以得到h的估计：

然而，以上的逼近方式对于F(x)是平滑的区域有比较理想的效果，但是对于F(x)''比较大的区域，比较效果却很糟。因此，采用如下函数进行加权处理：

加权后的对h的估计就表示如下：

计算得到了h的估计后，就可以通过移动F(x)进行Newton-Raphson迭代，直至收敛，得到h的最好估计，迭代表示如下：

如果将上式泛化到多维情况，则可以表示如下：

其中，
          Jianbo Shi和Carlo Tomasi两人在1994的CVPR上发表了篇论文：Good Features To Track中该该算子进行了扩展，通过一个仿射运动域来表示前面提到的h，则J(x)和I(x)表示为：

                          

其中，A是一个变形矩阵（Deformation Matrix），d是一个平移向量（Translation Vector）。对于给定的两幅图I(x)和J(x)，就是通过计算A和d，从而实现跟踪。
           由于上式J(Ax+d)=I(x)不能很好的满足，因此求解A和d一般是通过对下式进行最小化求解：

其中W是一个给定的局部区域，w(x)是一个加权函数。这个式子的含义：即找到两副图像中，在W窗口中，I、J的差异，其中I以x-d/2为中心，J以x+d/2为中心，w/2为半径的一个矩形窗口间的差异，使函数ε(d)要取得最小值。结合微分只是，这个极值点的导数一定为0，即：





为了要使d能够得到解，则Z需要满足条件为：Z*Z'矩阵可逆。

        KLT是一种优秀的算子，在目标跟踪系统中得到了广泛的应用。并且针对其速度的缺陷，现在也有基于GPU版本的加速KLT算法，具体的可以参考后面给出的参考资料。
更多资料可以参考：
1、KLT: An Implementation of the Kanade-Lucas-Tomasi Feature Tracker：http://www.ces.clemson.edu/~stb/klt/
2、Derivation of Kanade-Lucas-Tomasi Tracking Equation