你是否好奇过,人类的机器(飞船、导弹、鱼雷)是怎么“看”到目标的?是像吃鸡中那样用“眼睛”瞄目标么?最初的机器是这样看世界的,可从阿波罗飞船开始,借助一些新奇的“眼睛”,人类开始看到了一个又一个不一样的世界。机器的眼睛,就是目标跟踪算法了。算法是怎么回事?为了关爱没学过算法的朋友,我们将用故事《追狗,从入门到精通》来说明。追狗入门篇:“瞄”哪打哪——尾追法。
如果你要提着菜刀去收拾一条刚拆完家的二哈,你会采取什么方法追上它呢?大概会是这样的策略(算法,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)以及过程噪声和量测噪声的概率分布,那么就可以改进追狗的算法。追狗进阶篇:出现好多狗——数据关联。
道高一尺,狗高一丈,二哈邪魅一笑,叫来了自己的兄弟姐妹(杂波,Clutter,也就是会产生量测来干扰我们的事物),用来迷惑我们,该怎么办?(如果导弹跟踪的敌机放出诱饵,鱼雷打击的敌舰处在多个渔船间,量测便不只一个)这里就要涉及到数据关联,Data Association。
可以这样做,由于你知道“凶手”是做匀速直线运动,可以预测它下一时刻的位置,那么可以认为:距离这个预测的位置越近,凶手的可能性越大;反之越小。最简单的方法就是“找最近”,即将最近的量测作为正确量测(Correct Measurement)。但不太可靠,因为这种数据关联算法把其余嫌疑狗直接排除。
后来,学者用量测与位置预测间距(新息,Innovation)来量化源自目标的概率(关联概率,Association Probabilities),利用关联概率对量测求平均,计算结果作为真凶。这样虽然牺牲了一定的精度,但保证了不误杀(只要二哈的狗命)。当然,实际中为了更加准确地跟(杀)踪(狗),算法不仅要估计位置,还估计坐标、速度、加速度等,即估计目标状态(State)。
状态间距的计算方式有很多,但把距离度量统称为范数(Norm)。当噪声服从高斯分布时,距离范数的计算和关联概率的计算有特殊的方式。追狗精通篇:如果狗子太狡猾——交互多模型。经典的Kalman滤波器认为,目(狗)标(子)的运动模型已知,然而实际中这一假设难以保障,尤其是狗子经常改变运动模型时(机动目标跟踪,Maneuvering Target Tracking)。
若已知二哈在有限个运动模型中运动(左、右、匀速直线、匀速圆周),不难想象,量测与正确模型下的预测间距最短,因此可以用这一距离来量化各模型正确的概率(模型概率,Model Probabilities),再用模型概率对各模型下的Kalman滤波估计进行加权。值得注意的是,每次模型概率更新后,除了进行加权平均,还要把各模型估计结果进行某种转移(Transition)。
这就像买股票,不同股票的价格发生变化,需要相应地对投资金额进行调整(把前景不太好的股票卖掉一部分,用于购买前景喜人的股票)。
将Kalman滤波器、数据关联和交互多模型结合起来,便是目前最成熟的目标跟踪算法之一,全称:Interactive Multi-Model-Joint Probabilistic Data Association-Kalman Filter,别晕,有个简写IMM-JPDA-KF。
即在杂波环境下(真假量测共存),对多个机动目标(目标运动模型未知),进行持续且可靠地跟踪(准确估计位置、速度、加速度等运动量)。“追狗”这门学科的前沿。以数据关联为核心的经典跟踪算法,也有其局限性,包括计算量随量测和目标数呈现指数型增长,需要已知目标的个数(对目标数量变化响应滞后)等。目标跟踪的研究历史久远,但又在不断地涌现新的方法。
例如用机器学习(Machine Learning, ML)、稀疏表示(Sparse Representation,SR)等。然而上述跟踪算法都是“自下而上“被设计出的,即符合人类的直观逻辑。目前人类最为前沿的跟踪理论,是基于随机有限集(Random Finite Set, RFS)的各种滤波器。它是”自上而下“被设计的,从FISST理论出发。
需要的基础呢,也不多,包括Bayes最优滤波、集合空间积分,高斯混合模型、序贯Monte-Carlo、粒子滤波……