查看原文
其他

手把手教你“狗拿耗子” |《追狗,从入门到精通3.0》

望墨溢 科学大院 2021-07-05

时光荏苒,岁月如梭。一年的时间,我们从单枪匹马追狗(戳这里回顾如何单枪匹马追狗~)到和朋友们团结协作,成为追狗大师(戳这里回顾我们成为追狗大师的日子~),小伙伴们了解到了一些经典多目标跟踪与融合的相关知识。


今天,大院er带着刚追到的狗子,利用目标跟踪领域的前沿理论,手把手教大家如何训练自家狗子“狗拿耗子”吧~


经典多目标跟踪与融合


热个身,放“狗”追“耗子”,先从复习经典多目标跟踪与融合的相关理论开始。


1.多目标跟踪


角色设定:假设家里有3只耗子,向3只耗子的大致位置放3只狗,令狗去追耗子。为了避免被狗追到,我们假设耗子各个都是忍者,可以通过幻术在周围投射若干个自己的分身,让狗分辨不出看到的目标究竟是真实的耗子还是分身。


经典目标跟踪:再多的量测,也只有已知数量的目标


耗子的信息未知,但狗子的信息已知,而狗一直在追赶耗子。因此,可将狗子的位置、速度,作为耗子位置、速度的估计值。狗子还有自己的情绪,用于衡量估计误差的大小。


耗子越近,狗子越会改变自己原有的方向,而转向它,狗子情绪就越稳定;耗子越远,狗子越会保持自己原有的方向,狗子情绪就越急躁。


可以说,目标跟踪,就是自适应地更新狗子的位置、速度和情绪这几个运动参数,用于估计耗子的运动参数。


卡尔曼滤波:偏好距离近的量测


考虑到每条狗只能抓一只耗子,为了保证每只狗追的都是当初在它附近的耗子,实现“1只狗 vs. 1只耗子”的追捕方式,可命令每条狗只关心距离近的耗子,忽视远处的耗子。这样,就可实现用3条狗跟踪3只耗子。


只看近处的量测,将多目标跟踪变为多个单目标跟踪


于是我们可以解释如下:


耗子就是目标(Target);向耗子的大致位置放狗,称为初始化(Initialize);耗子的运动方式,称为转移模型(Transition Model);狗子看到的耗子,称为量测(Measurement),其中,耗子的虚影,称为杂波(Clutter),也就是假量测。


而狗子的位置、速度等运动信息,称为状态估计(State Estimate),用于估计耗子的位置、速度;狗子的情绪,称为协方差(Covariance),用于衡量状态估计误差大小。


狗(目)拿(标)耗(跟)子(踪)可分为两步:狗子先按自己原有的速度走一步,称为预测(Prediction);狗子根据看到的耗子,改变自身的位置、速度,称为更新(Update)。这两步合在一起,就是卡尔曼滤波(Kalman Filter)


经典的卡尔曼滤波,只能跟踪一个目标(抓一个耗子),且没有杂波(虚影)。若要跟踪多目标,则还需数据关联(Data Association)算法,即判定哪些量测源自同一目标。


上文中,令狗子只关心距离近的耗子,就是数据关联。其中的“距离”,通常用椭球范数(Ellipsoid Norm)衡量,“范数”就是数学术语中的“距离”。椭球范数的计算和协方差(狗子的情绪)有关。


协方差:一项重要的参数,用于衡量状态估计误差的大小


2. 融合跟踪


1只狗抓1只耗子,误差难免较大,因此假设2人同时放狗追3只耗子,每人放3条狗。这样,每只耗子就都被2条狗追。注意,每条狗有自己的情绪。


狗子情绪越稳定(误差协方差越小),其信息(状态估计)越可靠,因此可将协方差的逆(矩阵的倒数)作为权系数,将2条狗的状态估计进行加权平均。


融合跟踪:误差大的狗子没有发言权


这样,就实现了多人一起放狗抓耗子,称为融合跟踪(Fusion Tracking)。相比一人的滤波跟踪,融合跟踪能够获得更好的性能。


上述融合算法属于分布式融合(Distributed Fusion),即对状态估计(狗子)的融合。相对的,还有集中式融合(Centralized Fusion),即对量测(看到的耗子)的融合。一般而言,分布式融合更易于工程实现。


随机有限集


通过上述总结,可以看出,经典的多目标跟踪与融合,面临两个问题:a.目标(耗子)数目必须恒定,这样才能确定狗子的数量;b.当量测(看到的耗子)较多时,数据关联的计算量过大。


这些缺陷,根本源自对多目标的建模方式。具体而言,就是将多目标理解为多个单目标,将多目标跟踪分解为多个单目标跟踪。


若把多个耗子视为一个整体,例如某时刻为{耗1,耗2,耗3},而下一时刻耗2进洞了,但叫来了自己的兄弟耗4、耗5,这时的耗子群为{耗1,耗2,耗4,耗5}。


可以看出,将多个耗子视作一个整体,可适应新耗子出现、旧耗子消失等情况。这些情况下,耗子的数目是未知且变化的。


这是另一种多目标建模方式,即随机有限集(Random Finite Set, RFS)。随机有限集是一种集合元素内容、元素数目都具有随机性的集合。相比经典方法的建模,它可以更好地适应目标数目变化的场景,且不需要计算量较大的数据关联。


随机有限集:允许目标数目发生变化


在RFS建模方式中,新耗子的出现,称为新生(Newborn);耗子的消失,称为消亡(Die Out);当然,还有一种导致目标(耗子)数目改变的情况,类似于耗子边跑边生了个崽,称为衍生(Derive)


导致目标数目变化的三种情况


高斯混合-概率假设密度滤波器


基于随机有限集,派生出多种目标跟踪算法,这里仅介绍一种——高斯混合-概率假设密度(Gauss Mixture-Probability Hypothesis Density, GM-PHD)滤波算法。


更新角色设定:由于使用了RFS理论,狗子进化为了“忍者神狗”。我们更新一下狗子的技能和属性,这一阶段的狗子有了新技能:分身术,分身可去追其他耗子。新增加的属性:狗头大小能够变化,耗子距离越近,狗头越大,反之越小。


若上一时刻已经有多条狗,每条狗都有位置、速度、情绪和狗头大小等参数。狗的位置、速度表示状态估计,情绪是估计协方差,而狗头大小是这个估计的权重(Weight)


忍者神狗:用RFS理论武装的狗


1.新生目标与预测


若在远处发现耗子的身影,可认为出现了新生目标。而已有的狗子对远处的耗子实在不感兴趣,因此需向那里投放新的狗。


新生目标:放一个新的狗子


旧的狗子按照自己原有的速度走一步(预测),把预测后的和新放的狗子视作一群狗。


2. 忍者神狗,跟踪高手(更新)


狗已不再是曾经的狗,而是忍者神狗。对看到的每只耗子,每条狗都会造个分身去追。若更新前有J条狗,看到N只耗子,那么更新后,每只耗子都被J条狗追,因此共有N×J条狗。


在更新时,一个量测更新多个狗子


每条狗根据自己追的耗子,改变位置、速度、情绪和狗头大小。距离越近,情绪越稳定,狗头也越大。在这一步骤后,还需将追同一耗子的狗头进行归一化(Normalize)


例如,有三个狗追一只耗子,狗头分别变为2倍、3倍和4倍。考虑杂波(耗子虚影)的存在,狗头将变为原先的0.2倍、0.3倍和0.4倍,即倍数/(倍数之和+1),其中1代表杂波的影响。


3. 枝剪与合并


若上一时刻有3条狗,新放了1条狗,当前看到10只耗子,那么将有(3+1)×10=40只狗。不难看出,狗的数量会呈现指数型增长,因此需要控制狗的数量。


首先,这么多狗中,一定存在狗头(权重)非常小,也就是离自己追的耗子非常远的狗。这些头太小的狗,其实并未包含多少信息,反而占据了很多的计算量。


因此,可设置一个门限,将狗头小于这个门限的狗,剔除抓耗子的队伍。这一操作,称为枝剪(Prune)处理。


枝剪融合:剔除权重过小的狗子


然后,枝剪后的狗中,一定还存在多条狗追同一只耗子的情况。这些狗包含的信息有重复,因此需进行合并(Merge)处理,目前最可靠的合并方法是协方差交叉(Covariance Intersection, CI)方法。


不难理解,狗头越大(权重越大),情绪越稳定(协方差越小),狗子的信息越可靠。因此,将(权重×协方差的逆)视为权系数,将追同一只耗子的狗,进行加权平均。这样,多条狗子就合并为一条,而新狗的头(权重)为原有狗头之和。


合并处理:多个狗子合并为一个狗子


当然,合并前还需一步操作,就是判定哪几条狗子追同一只耗子,这个操作需要使用聚类(Cluster)算法。注意,聚类不同于分类。


打个比方,有一群黄色和红色的球,按照颜色将其分开,是分类(Classification);而对一群狗而言,没有显著的特征用于区分,就是聚类


3. 目标数估计与目标状态提取


由于用随机有限集(RFS)对目标(耗子)进行了建模,因此既需要估计目标的数量,还需估计目标的状态


可以证明,经枝剪、合并处理后,剩余狗头大小之和就是目标数,假设为N。而目标的状态估计,就是前N条狗头(权重)最大的狗(包括位置、速度等)。


例如,枝剪、合并后还剩4条狗,狗头大小分别为0.8、0.2、0.7、0.3,那么耗子应有0.8+0.2+0.7+0.3=2个,而状态估计即狗头为0.8和0.7的狗(权重最大的2个)。


RFS框架下的融合跟踪


随机有限集框架下,也需融合跟踪,下文假设有2个人放忍者神狗去抓耗子,进而介绍两种融合跟踪的思路。


1. 多个人一起放狗(并行融合)


一种融合思路,是2个人独立地放狗。各自经过目标新生、预测、更新后,将2群狗合为一群,再经枝剪、合并,最后再估计目标(耗子)的数量和状态。当然,由于是将2群狗合为一群,因此目标数估计应除以2。


这种融合方法,等价于将2个人看到的耗子合为一群,再用于更新同一群狗子。


这种方法称为并行融合(Parallel Fusion)算法,即将所有量测整合起来,一次性用于滤波跟踪。这种算法计算量较大,且性能较为不稳定。


并行融合:用量测一起更新


2. 多个人按次序喂狗(序贯融合)


另一种融合思路,是2个人顺序利用看到的耗子,来更新同一群狗。对一群经新生、预测的狗,第1个人用看到的耗子更新狗,然后,第2个人再用自己看到的耗子更新狗。


这种方法称为序贯融合(Sequential Fusion)算法,即顺序利用量测,进行多次更新。这种算法计算量小,且性能更为稳定。


序贯融合:用量测顺序更新


最后


本文中的“忍者神狗”,即既有状态、协方差,又有权重的狗子,是对高斯混合(Gauss Mixture, GM)模型的比喻。GM模型,是用多个带权重的高斯分布(也称正态分布)之和,来近似非线性函数的方法。


本文中,GM模型用于近似与多目标有关的函数,这一函数被称为概率假设密度(Probability Hypothesis Density, PHD),所以这一滤波器被称为GM-PHD滤波器。


对于RFS框架下的滤波器而言,除了可用GM模型来实现,还可用序贯蒙特卡洛(Sequential Monte Carlo, SMC)模型来实现。SMC模型,是用一群采样粒子来近似非线性函数(为了你头发好,就不多说了)。


而实验证明,GM模型在多个方面均显著优于SMC模型。


(本文中所有图片均由作者提供)


参考文献:

[1] 韩崇昭, 朱洪艳, 段战胜. 多源信息融合[M]. 北京: 清华大学出版社.

[2] Ronald P. S. Mahler. Statistical Multisource-Multitarget Information Fusion[M]. Boston: Artech House.

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




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



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

推荐阅读

《追狗,从入门到精通》>>

《追狗,从入门到精通2.0》 >>

大西洋上的天然高速,飞机的必经之路>>

鸟类南飞,去的是哪个“南方”?>>




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


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



大院er拍了拍你:不要忘记 

点亮这里的 赞 和 在看 噢~ 


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

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