《追狗，从入门到精通》

作者：望墨溢（西北工业大学 航海学院）

文章来源于科学大院公众号（ID：kexuedayuan）

——

你是否好奇过，人类的机器（飞船、导弹、鱼雷）是怎么“看”到目标的？是像吃鸡中那样用“眼睛”瞄目标么？最初的机器是这样看世界的，可从阿波罗飞船开始，借助一些新奇的“眼睛”，人类开始看到了一个又一个不一样的世界。机器的眼睛，就是目标跟踪算法了。

算法是怎么回事？为了关爱没学过算法的朋友，我们将用故事《追狗，从入门到精通》来说明~

（图片来源：作者绘制）

追狗入门篇:“瞄”哪打哪——尾追法

如果你要提着菜刀去收拾一条刚拆完家的二哈，你会采取什么方法追上它呢？大概会是这样的策略（算法，Algorithm）：

(1)你用眼睛看它在什么位置（量测，Measurement。对，搞科研的喜欢把AB叫BA，以显得高大上，例如还有把“简约”叫“约简”，把“积累”叫“累积”），你就朝向它跑；

(2)如果它也在动，你每隔一段时间，根据它最新的位置，调整自己的方向（更新，Update）；

(3)如果它跑步是有规律的（先验信息，Priori Information，也就是已知的信息），例如匀速直线地朝狗窝跑，你还可以直接到它的必经之路去堵它（预测，Prediction）。

（图片来源：作者绘制）

(4)如果你俩一直在靠近（收敛，Converge），当某项数值（追狗这件事是看距离）低于预先设定好的指标（门限，Threshold），直接扑过去或者扔菜刀（结束）。

你用来追杀凶狗的算法，曾经被人类用在了最初的导弹、鱼雷上，这就是目标跟踪中最简单的“尾追法”。那时人类的机器跟踪目标，就跟吃鸡时我们用倍镜锁定对手一样：瞄。

（图片来源：作者绘制）

追狗提高篇:已知狗的路线——Kalman滤波器

随着技术的进步，对目标跟踪精度的要求越来越高，尤其是在航空航天领域，例如在太空执行任务，几厘米的差距就可能会造成严重的后果（你也想远远地镖那条狗18刀，刀刀避开要害，但差1厘米可能就要了你的狗的命）。

这里有个问题，看到了就是看到了，怎么还有精度这一说法？实际上，任何量测都有误差（量测噪声，Measurement Noise），且误差还是随机数，我们只可能知道误差的概率分布，却不知道误差具体的值（否则用量测值减去误差不就完了，还研究什么算法？）。

例如，你突然想起平日里买狗粮，包装袋上写着“10Kg±500g”，就是在讲：一袋狗粮重10Kg，但由于各种因素，实际可能刚够，也可能少了若干g，也可能多若干g，但多与少都不会大于500g。

（图片来源：作者绘制）

同时，目标运动也是有噪声的（狗以为它逃跑路线是直线，但其实也有误差的），通常把这个误差叫过程噪声（Process Noise）。若已知狗的潜逃路线（运动模型，Motion Model）以及过程噪声和量测噪声的概率分布，那么就可以改进追狗的算法：

(1)上一时刻：如果已知上一时刻狗跑到了狗窝处，但就像狗粮的“10Kg±500g”一样，这一位置是有误差的，比如说方差为1cm2的误差（具体值是多少不知道，但概率分布知道）；

(2)预测：按照运动模型（假设匀速直线运动），它当前时刻应该跑到冰箱处，但由于它脑子不好使，其实这一过程是有方差为5cm2的误差（依旧具体值是多少不知道，但概率分布知道）。由于上一时刻狗窝的方差是1cm2，因此冰箱处实际方差应该是1+5=6 cm2；

（图片来源：作者绘制）

(3)量测：若人眼看到它在电视处，但这个量测是有方差为10cm2的误差（同上）；

(4)状态更新：这两个信息（预测和量测）都不完全可信，但可以知道，预测相对于量测更可信，因为预测的误差方差小（6cm2