追狗,从入门到精通

  来源:“科学大院”公众号(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.

方差概率分布
新浪科技公众号
新浪科技公众号

“掌”握科技鲜闻 (微信搜索techsina或扫描左侧二维码关注)

创事记

科学探索

科学大家

苹果汇

众测

专题

官方微博

新浪科技 新浪数码 新浪手机 科学探索 苹果汇 新浪众测

公众号

新浪科技

新浪科技为你带来最新鲜的科技资讯

苹果汇

苹果汇为你带来最新鲜的苹果产品新闻

新浪众测

新酷产品第一时间免费试玩

新浪探索

提供最新的科学家新闻,精彩的震撼图片