接触这一类的跟踪方法，是2015年初通过一篇论文：Efficient Learning of Linear Predictors for Template Tracking . 其实在这篇论文前好几年就有非常多这一类论文了。当时由于看到论文作者放到youtube的视频，效果很好，所以就学习了一下。
不过最终我也只是实现了Offline的LP tracker。作者本人对LP的训练复杂度做了很大优化，其中主要是通过对训练计算的一个算法进行了修改，让训练部分的效率提高到可以在手机上实时。由于数学基础薄弱，这个地方在最后一直卡住了。希望看到这篇文章的人如果有这方面经验的给予指导。
一般来说对于图像的跟踪，有几种思路。有针对全图进行跟踪的，也有针对图像中的特征点进行局部跟踪的。LP这种方法主要是针对全图进行跟踪，但是它的思路比较特别。针对全图进行跟踪自然是利用图像的像素颜色，例如使用SSD或者NCC等对两幅图进行匹配，一般都是先选定一个区域，用像素点的灰度值进行差异比较，最终选取差异最小的区域作为最佳匹配。而LP采取的思路很奇特，作为一个很少接触深入算法的码农，最初接触这种非常「数学」的思路时还是比较震撼的。
上面一幅图其实就已经把整个思路说明白了，如上的这幅图像，看到一定密度的白色取点为H，而红色的线框的四个顶点表示为Y。
再细化的来说，H也就是在一幅图像中按照一定的密度均匀的取得颜色值，代表着某图像颜色（灰度）的分布情况。对于图像来说可以说这就是图像的一种具备唯一性的特征。
而Y就是一幅图像四个顶点的位置信息，也是跟踪匹配算法想要计算的结果。
从肉眼的角度，颜色值分布和图像位置是存在关系的。比如，把一个图像左移，位置自然是左移了，而（原位置）颜色值分布也产生了左移的差异。
LP算法的模型 Y = A H 意义在于，通过计算一个矩阵A，在颜色分布H 和 顶点位置信息 Y之间建立一种关系。 这样对于当前摄像头取到的一幅图像，只需要通过获取颜色得到H，然后通过A矩阵和H矩阵相乘就可以直接得到图像当前的位置。如下图，输入不同的图像可以直接得到位移。
注意实际中Y 和 H 都是取相对于原图像的差值。
Linear Predictor分析和测试
如果接触过光流法（KLT OpticalFlow）或者ESM算法或者其他类似的算法，会清楚，在一个小的位移变化、旋转变化或者尺度变化时，同一位置图像的颜色变化和位置是有一定规律的。比如位移为0的时候，同一位置图像颜色不发生变化，位移非常小的时候，这个变化也会很小。但是如何根据变化直接获取位置呢，这里LP使用的是基于大量的训练。
训练
首先把一幅图像置为标准状态。这个状态就是跟踪的起点，以此为基础需要计算下一帧图像的状态所对应的位置。所以需要预先把下一帧全部可能的姿态变化都计算出来（位移、旋转、缩放都在一个小范围内进行随机组合，这里一般会到几千种姿态）。这几千种姿态计算出来以后，每一个姿态所对应的Y，以及H自然也就计算出来了，通过大量数据最终计算出一个A矩阵。作为上文提到的最终姿态计算矩阵。
具体计算A的过程如图，具体推导过程就不写了，感兴趣的看原文。值得一说的是，作者基于这个公式后面进行了大幅度优化，极大缩短了这个训练的时间。此部分个人理解的不到位，没有实现优化后的手机端实时训练，所以我的实现都是基于下面这个基础公式，训练时间较长（针对320x240的图，台式机都要几秒十几秒）。
跟踪
训练完毕后，首先讨论第一帧如何跟踪。
第一帧相对于基本图像，姿态发生了改变，但是属于较小的改变，毕竟只经过了几十分之一秒。理论上来说，上面的训练的几千个姿态是覆盖当前图像姿态的。此时，取得当前摄像头拍到的图像，根据具体密度进行取点，得到H矩阵。然后直接用A*H就可以得到Y，也就是和原图像位置的差值。用原图像位置加Y就可以得到当前图像的位置了。这样就计算出来了当前图像的姿态。
第一帧计算完毕后。新姿态可以用于下一帧的计算。只要把这个新姿态代入作为输入，就可以取得新姿态下原图像采样位置的采样点，从而得到H，从而像第一帧一样得到Y，只不过这个Y是相对于第一帧的姿态，计算完毕后，把原姿态和相对姿态矩阵相乘，可以得到第二帧的姿态，同时也成为下一帧的基准姿态。
当然实际实现时，为了对应多尺度，是先对小尺度跟踪，再将计算结果作为基准姿态切换到大尺度，同时每一个尺度迭代多次增强健壮性。实际实现算法如下：
总结
这个方法优点在于，跟踪计算非常迅速，拿到摄像机的图像后，取点，然后一次矩阵乘法就可以得到姿态的差值（但由于要多尺度每个尺度多次迭代，实际手机端实现速度还是需要几毫秒）。但缺点是训练时间太长无法实时，不过论文中已经给出了优化方案可以做到手机端实时训练。另外个人实现发现该方案由于基于完整图跟踪，所以对光照和遮挡都较为敏感，不过类似论文中也有人针对光照和遮挡做了特别的优化方案。
Linear Predictor运行视频
【版权声明】泡泡机器人SLAM的所有文章全部由泡泡机器人的成员花费大量心血制作而成的原创内容，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！
【注】商业转载请联系刘富强（[email protected]）进行授权。普通个人转载，请保留版权声明，并且在文章下方放上“泡泡机器人SLAM”微信公
众账号的二维码即可。
【编辑】王琛
