追狗，从入门到精通

来源：“科学大院”公众号（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<10cm2），因此我们可以用预测位置乘以可信度10/16，用量测位置乘以可信度6/16，两个结果相加，表示融合预测和量测信号后的估计（Estimate）；

(5)误差方差：这一估计的误差方差是多少呢？如果认为上述算法是用量测修正预测，那么应该是预测误差-量测的相对误差，即6*(1-6/16)=3.75 cm2；如果认为是用预测修正量测，那么应该是量测误差-预测的相对误差，即10*(1-10/16)，依旧等于3.75cm2。

不难看出，估计误差的方差3.75 cm2既小于量测的10cm2，也小于预测的6cm2。如此一来，便实现了更准确地追狗（目标跟踪），这便叫做Kalman滤波器[1]。当年的阿波罗飞船首次用它来进行目标跟踪，实现了飞行器间的高精度对接，证实了其有效性。

“阿波罗”飞船总高110米，在登月舱和指挥舱进行对接时，需要对准上百个插针、插孔和连接管路。误差必须保持在0.1米以内，按等比例缩放就相当于，一个人手穿针线，还是那种上下左右都得对齐的那种。而Kalman滤波器，做到了。

至于误差的概率分布，可能是均匀分布（Uniform Distribution），也可能是其它分布，但根据中心极限定理（Central Limit Theorem），管他什么分布，样本多了都是正态分布，也叫高斯分布（Gaussian Distribution）。

追狗进阶篇:

出现好多狗——数据关联

道高一尺，狗高一丈，二哈邪魅一笑，叫来了自己的兄弟姐妹（杂波，Clutter，也就是会产生量测来干扰我们的事物），用来迷惑我们，该怎么办？（如果导弹跟踪的敌机放出诱饵，鱼雷打击的敌舰处在多个渔船间，量测便不只一个）这里就要涉及到数据关联，Data Association。

可以这样做，由于你知道“凶手”是做匀速直线运动，可以预测它下一时刻的位置，那么可以认为：距离这个预测的位置越近，凶手的可能性越大；反之越小。

最简单的方法就是“找最近”[2]，即将最近的量测作为正确量测（Correct Measurement）。但不太可靠，因为这种数据关联算法把其余嫌疑狗直接排除。

后来，学者用量测与位置预测间距（新息，Innovation）来量化源自目标的概率（关联概率，Association Probabilities），利用关联概率对量测求平均，计算结果作为真凶[3]。这样虽然牺牲了一定的精度，但保证了不误杀（只要二哈的狗命）。

当然，实际中为了更加准确地跟（杀）踪（狗），算法不仅要估计位置，还估计坐标、速度、加速度等，即估计目标状态（State）。状态间距的计算方式有很多，但把距离度量统称为范数（Norm）。当噪声服从高斯分布时，距离范数的计算和关联概率的计算有特殊的方式。

追狗精通篇：

如果狗子太狡猾——交互多模型

经典的Kalman滤波器认为，目（狗）标（子）的运动模型已知，然而实际中这一假设难以保障，尤其是狗子经常改变运动模型时（机动目标跟踪，Maneuvering Target Tracking）。

若已知二哈在有限个运动模型中运动（左、右、匀速直线、匀速圆周），不难想象，量测与正确模型下的预测间距最短，因此可以用这一距离来量化各模型正确的概率（模型概率，Model Probabilities），再用模型概率对各模型下的Kalman滤波估计进行加权[4]。

值得注意的是，每次模型概率更新后，除了进行加权平均，还要把各模型估计结果进行某种转移（Transition）。这就像买股票，不同股票的价格发生变化，需要相应地对投资金额进行调整（把前景不太好的股票卖掉一部分，用于购买前景喜人的股票）。

将Kalman滤波器、数据关联和交互多模型结合起来，便是目前最成熟的目标跟踪算法之一（其实不想说之一，但怕得罪人），全称：Interactive Multi-Model-Joint Probabilistic Data Association-Kalman Filter，别晕，有个简写IMM-JPDA-KF。即在杂波环境下（真假量测共存），对多个机动目标（目标运动模型未知），进行持续且可靠地跟踪（准确估计位置、速度、加速度等运动量）。

“追狗”这门学科的前沿

以数据关联为核心的经典跟踪算法，也有其局限性，包括计算量随量测和目标数呈现指数型增长，需要已知目标的个数（对目标数量变化响应滞后）等。

目标跟踪的研究历史久远，但又在不断地涌现新的方法。例如用机器学习（Machine Learning, ML）、稀疏表示（Sparse Representation，SR）等。

然而上述跟踪算法都是“自下而上“被设计出的，即符合人类的直观逻辑（详见《追狗，从入门到精通》）。目前人类最为前沿的跟踪理论，是基于随机有限集（Random Finite Set, RFS）的各种滤波器[5]。

它是”自上而下“被设计的，从FISST理论出发（给大家翻译一下：就是”没基础就别好奇，保证听不懂“的意思）。需要的基础呢，也不多，包括Bayes最优滤波、集合空间积分，高斯混合模型、序贯Monte-Carlo、粒子滤波……

在你还在用倍镜瞄人头的时候，人类机器早以借助概率等数学工具，居高临下地看到了更为宏大、更为完备的世界。

作者：望墨溢

文中图片均为作者制作

参考文献:

[1] R. E. Kalman, R. S. Bucy. New results in linear filtering and prediction theory. Journal of Basic Engineering[J]. 1961(3): 95-108.

[2] Singer R. A., Sea R. G.. A New Filter for Optimal Tracking in Dense Multitarget Environment[C]. Proceedings of the 9th Allerton Conference Circuit and System Theory, 1971: 201-211.

[3] Fortmann T. E., Bar-Shalom Y., Scheffe M.. Sonar Tracking of Multiple Targets Using Joint Probabilistic Data Association[J]. IEEE Journal of Oceanic Engineering, 1983, 8(3): 173-184.

[4] Blom H. A. P.. An Efficient Filter for Abruptly Changing Systems[C]. IEEE 23th Conference on Decision & Control, 1984, 12: 1-4.

[5] R. Mahler. Statistical Multisource-Multitarget Information Fusion[M]. Norwood, MA: Artech House, 2007.