查看原文
其他

《追狗,从入门到精通》

望墨溢 科学大院 2020-08-20

“2019年度十佳科普文章”评选正在投票!后台回复“评选”可阅读入围文章   点我投票 


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


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


(图片来源:作者绘制)


追狗入门篇:

“瞄”哪打哪——尾追法


如果你要提着菜刀去收拾一条刚拆完家的二哈,你会采取什么方法追上它呢?大概会是这样的策略(算法,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.


作者单位:西北工业大学 航海学院




版权说明:未经授权严禁任何形式的媒体转载和摘编,并且严禁转载至微信以外的平台!


文章首发于科学大院,仅代表作者观点,不代表科学大院立场。转载请联系cas@cnic.cn



大院热门文章top榜

点击文章标题,可直接阅读哦~


1. FAST望远镜抓到了两只“毒蜘蛛”!

2. “起床!量体温了!”麻烦给七千万年前的恐龙发条信息

3. 从28年悬案告破说起:Y染色体的倔强进化史

4. 蚯蚓不生活在水中,鱼为什么喜欢吃它?

5. 想成为一个合格的药?选择姓什么很重要

6. 撸狗也会有“高原反应”?“藏区癌症”可能要了你的命

7. 小小的抗体,如何承担起保护我们的重任?

8. 辣啊!是山葵?辣根?还是芥菜?| 植物演义

9. 人体温度降低 难道还是微生物的锅?

10.再不好好听网课,你可能要被鹦鹉超过了




科学大院是中科院官方科普微平台,由中科院科学传播局主办、中国科普博览团队运营,致力于最新科研成果的深度解读、社会热点事件的科学发声。


转载授权、合作、投稿事宜请联系cas@cnic.cn


我知道你在看我

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存