《多目标跟踪算法.doc》由会员分享，可在线阅读，更多相关《多目标跟踪算法.doc（23页珍藏版）》请在三一办公上搜索。
1、多目标跟踪算法先来回顾下卡尔曼滤波器： 假定表示当前k时刻目标的状态，表示下一个时刻目标的状态，则表示k时刻的实际观测。一般地模型都假定为线性的：这里的为k+1时刻目标的状态，为k时刻的状态，为状态转移矩阵，而是服从均值为0方差为的正态分布，表示由噪声等引起的干扰。卡尔曼滤波采取初步估计： 这里的估计只是初步的估计，状态估计与实际状态的误差矩阵等于状态的的方差，即： 更新（修正）：这里已知了实际观察，同样是假定观测与状态的似然关系是线性的，即满足： 服从一个均值为0方差为 的正态分布。卡尔曼滤波器给出了经过更新后得到的比较合理的k+1时刻的估计为： 相应地得到了更新后方差的估计： 这里： 其实
2、这些都是通过最小二乘法推出来的，即使得误差： 最小，而初步估计也是通过最小二乘法获得，即使得： 最小。有了上述估计方程后，便可以获得一个估计流程： 下面再介绍下贝叶斯公式先看一个定义马氏链：设为有限集或可列集，称为定义在概率空间上，取值于空间E的马氏链，如果满足下面的马氏性：对一切有 若左边的条件概率有定义，则称为在n-1时刻状态为i,在n时刻在j的转移概率函数，若它与n无关，则记为，并称为时齐的或齐次的。显然这里的马氏性接近于独立性，在一定程度上可以称为无记忆性或无后效性。下面我们来推导贝叶斯公式：容易由条件概率公式定义知而就得到了更新后的公式如下：这里记 于是就可以得到贝叶斯滤波器跟踪流程
3、如下：实际上可以证明，卡尔曼滤波器是贝叶斯滤波器的一种特殊形式，由于假定噪声服从正态分布，同样地观测与状态估计的误差也是服从正态分布，那么不难得：那么： 这里由模型假设可知，似然分布为一个正态分布，即： 又由前面可得 那么： 从而得到更新公式： 这里： 实际上卡尔曼估计是一个最优估计：那么不难由正态分布的性质得：高斯混合滤波 以卡尔曼滤波器为代表，这类滤波器都是假定概率分布为正态分布，并且模型是线性的，故而在实际应用中有较大局限性。高斯混合模型就是用高斯概率密度函数（正态分布曲线）精确地量化事物，将一个事物分解为若干的基于高斯概率密度函数（正态分布曲线）形成的模型。例如图像背景建立高斯模型的原
4、理及过程：图像灰度直方图反映的是图像中某个灰度值出现的频次，也可以以为是图像灰度概率密度的估计。如果图像所包含的目标区域和背景区域相比比较大，且背景区域和目标区域在灰度上有一定的差异，那么该图像的灰度直方图呈现双峰-谷形状，其中一个峰对应于目标，另一个峰对应于背景的中心灰度。对于复杂的图像，尤其是医学图像，一般是多峰的。通过将直方图的多峰特性看作是多个高斯分布的叠加，可以解决图像的分割问题。 在智能监控系统中，对于运动目标的检测是中心内容，而在运动目标检测提取中，背景目标对于目标的识别和跟踪至关重要。而建模正是背景目标提取的一个重要环节。算法的一般描述：假定马尔科夫转移密度函数和目标状态与观测
5、似然函数为非线性的，但是可以用一个结合权重的高斯混合密度表示：这里。那么还假定两个后验分布也是高斯混合的，即：那么就可以得到一个高斯混合滤波器，流程如下：下面是具体步骤：1. 初始化：给定目标的一个初始分布，这里记为。若不知分布，那么就取为均匀分布。预测：那么显然可得，也是一个高斯混合形式，它由个成员组成，每个成员相应的权重为，而相应高斯分布部分为 。更新： 利用贝叶斯公式，容易算出也是高斯混合的形式。它的组成成员个数为。满足：这里： 记，则 状态估计： 可以证明期望最大估计如下： 当概率密度函数显著多峰时，EAP估计不如MAP估计，这便是需要求出具有最大权重的高斯分布部分。一般来说，我们可以
6、采用近似处理方法，即通过对的组员的修剪方法，使得最后选择：，这里对应着最大权重。若每个单个的都满足充分有效时，那么得到的这个近似估计也是有效的估计。粒子滤波经典粒子滤波算法的一般描述：1.初始化：取k0，按抽取N个样本点，i1,N。2.重要性采样：，令，其中i1,N。3.计算权值： 若采用一步转移后验状态分布，该式可简化为。4.归一化权值：5.重采样：根据各自归一化权值的大小复制/舍弃样本，得到N个近似服从分布的样本。令1/N，i1,N。6.输出结果：算法的输出是粒子集，用它可以近似表示后验概率和函数的期望 7.K=K+1,重复2步至6步。其它粒子滤波高斯粒子滤波Jayesh和Petar提出的
7、，将高斯滤波和粒子滤波结合，称为高斯粒子滤波(Gaussian Particle Filter，GPF)。该方法的前提是用高斯分布来近似后验分布，它比其它的高斯滤波方法适用性更强，能处理更多非线性动态系统问题；而与一般的粒子滤波相比，因为GPF用高斯分布近似后验分布，所以只要所用的高斯分布是正确的，就不会产生粒子退化问题，就不需要对粒子进行重采样，从而使算法的计算量降低，复杂度也降低。通常一个高斯随机变量的密度可表示为 其中，为的维向量均值；为的协方差矩阵。GPF假设后验分布可以近似成高斯分布，即下式成立 其中，。GPF测量更新是通过一个高斯分布近似上述滤波概率分布，即 和一般不能用解析表达式
8、直接求出，在GPF中，用蒙特卡罗方法计算式中 和的估计值，通过对重要性密度函数抽取样本并计算其权值，表示样本数，然后基于这些样本及权值来获得状态的均值和协方差。计算公式为 上式中，表示样本总数。高斯粒子滤波比其它高斯滤波有更好的性能，而与一般的粒子滤波相比计算量大大减小，复杂度降低。但是高斯滤波在后验分布不能用高斯分布近似的非线性动态空间模型或者非线性系统非加性高斯噪声模型时，滤波性能却不怎么能令人满意。正则粒子滤波正则粒子滤波(Regularized Particle Filter，RPF)是为了解决由重采样引入的新问题而提出的一种改进的粒子滤波。当通过序贯重要性采样后引起粒子退化问题时，前
9、面提到可以用重采样的方法来减小退化的影响，但是引入重采样策略同时也引入了新的问题，即粒子匮乏问题，经过若干次迭代之后，所有粒子都趋向于同一个粒子，导致粒子的多样性丧失。这是因为在重采样过程中，粒子是从离散分布中采样取得的，而不是从连续分布中采样得到的。正则粒子滤波正是为了解决上述问题而提出的。它与SIR粒子滤波的区别在于：在重采样过程中，SIR从离散近似的分布中重采样，而正则粒子滤波则从连续近似的分布中重采样。 其中,是对核密度进行了重新标度后的结果，为的维数,h称为核带宽，满足，并且核密度满足 的对称概率密度函数。对核带宽h的选择，要求满足后验密度和相应的正则经验密度表示之间的平均积分方差最
10、小。 其中，表示对的近似。在所有权值相等的特殊情况下，最佳的核密度是Epanechnikov核密度 其中，是内单位超球体的体积。根据正则化在选择步骤之前还是之后，RPF分为Post-RPF和Pre-RPF，两种RPF在弱意义下收敛于最优滤波器，收敛率为；在强意义下，估计误差正比于。辅助粒子滤波Pitt和Shephard在标准SIR滤波算法的基础上提出了辅助粒子滤波(Auxiliary Particle Filter, APF)。与标准序列重要性重采样(SIR)算法相比，APF也是以序列重要性采样(SIS)算法为基础，只是选择了不同的重要性密度函数,它在粒子集合上进行采样，其中是k-1时刻粒子的
11、标号 。根据贝叶斯准则 辅助粒子滤波在联合概率密度上进行采样，忽略中的标号,在边缘概率密度函数上获得一个样本集合。令以前的重要性密度函数满足如下的比例关系 其中，是在己知的情况下，的概率特性，可以是均值或者是一个采样。令 并且 在每个采样点上，粒子权值的更新公式如下 与SIR滤波算法相比，辅助粒子滤波算法的优势在于它在k-1时刻的样本集合上随机抽取了一些点，抽取时以当前的观测数据为条件，这样可以更加接近真实的状态。辅助粒子滤波可以看作是在一些点的估计的基础上，在之前时间点上进行重采样。当噪声比较小的时候，可以很好地用来表示，这时辅助粒子滤波算法就不像SIR算法一样对局外点比较敏感，权值的大小也
12、更加均匀。然而，过程噪声比较大时，单一的点估计不能很好地表示，ASIR性能下降。多目标粒子滤波 我们已经知道了单目标粒子滤波的具体思路，即具有下列流程： 这里（abbr表示简写）。这里的表示由单目标状态向量形成的粒子。相应地，我们将它推广到多目标上面，即用表示由多目标状态集合形成的粒子，那么，进一步得到多目标跟踪粒子滤波器。多目标粒子近似系统是通过一些粒子来近似表示多目标后验分布。这些表示状态集合的粒子具有各自相应的权重，且满足权重和为1。那么后验分布可以近似地表示如下： 这里是状态向量集合的一个无单位函数。由大树定律，不难得出：那么，可以将多目标粒子是通过从多目标后验分布中取随机样本得到，即
13、：同单目标粒子滤波一样，我们取那么同单目标粒子滤波器一样，可以用下面的近似： 多目标粒子系统要远比单目标粒子系统复杂。我们同样是采用顺序重要性采样法。用表示代表没有目标的粒子的权重，即取。再接下来用粒子代表具有具有一个目标的样本，即 接下来用粒子代表具有两个目标的样本： 同理依次下去，可以通过粒子代表具有n个目标的样本：直到代表完目标最大数目的样本为止，即：那么可以得到总粒子数目为： 这里1表示没有目标的粒子。初始化： 如果已知初始多目标分布为，那么就可按分布取样得到多目标粒子系统，即：可以通过下面方法完成：1 当目标数目已知时，那么，否则： 这里的表示1到n中任意一个数，故而有n!个组合。用
14、表示目标初始分布。那么初始化程序需要包括：决定粒子数目v需要满足跟踪每个目标，按照下面分布取v个单目标粒子，那么初始粒子系统可以通过v个有限集合组合而得，每一个粒子都有n个元素。即： 我们取每个粒子等权重，即，这里尽管有v+1个多目标粒子，但我们仍然只考虑转化为nv个单目标粒子。（1）如果多目标模型为一个birth模型，那么初始分布可以取： 那就是说，我们初始假定目前没有目标以及初始粒子系统刚好为，相应权重为。（2）如果先验分布为一个泊松分布，那么我们取，以及这里。取样，得到个单目标粒子，接下来表示两目标粒子，即，从而得到个这样的两目标粒子。依次进行下去，直到目标数目最大值为止，得到粒子预测
15、我们假定一个多目标粒子这里。考虑多目标跟踪的实际情况，我们得。这里计算量较大，故不在此列出了。需要对三种情况分别考虑 更新在这里 以及估计 目标数目比较容易估计： 但是对于状态估计来说，计算量十分大，故不再列出。随机有限集理论 集合导数 先介绍函数导数的概念，我们先看Frechet导数(偏导数)的定义： 那么不难得： 再来就引入函数导数： 这里h是一个一般函数，而为狄拉克函数。由狄拉克函数性质可知： 则： 进一步就有： 那么我们便可以定义一个函数导数Fh如下： 下面来定义一个集合导数，只要取,那么记，则，不妨取为y的一个小邻域，满足，则由狄拉克密度定义就有： 那么取极限得： 则可以定义随机有限
16、集空间上的一个随机集Y的集合导数如下： 集合的积分下面引入集合积分的概念，假定为随机有限集Y的一个实值函数，那么随机有限集空间上的一个子空间S上有：=（这容易推得，因为向量有顺序，但是集合没有顺序，）不难推得下面两个性质：有了集合导数与集合积分的概念后，我们便可以定义有限集空间上一个有限随机变量集Y的狄拉克概率密度函数，它满足：。进一步地，我们可以定义一个随机有限集的概率密度函数，这里由一些随机变量集合组成，故是由所有可能的组成，它满足。取S为整个空间，便可以得到。当然不难推出下面的性质。下面再介绍几个定义如下：1信任概率函数：若Y表示一个随机变量，那么记为信任概率。2. 信任质量函数：若为随
17、机有限空间上的一个随机有限集，那么称：为一个信任质量函数。3. 矩母函数：我们一般假定h(y)为一个模糊成员函数，即满足，如果Y是一个有限集空间上的有限集，定义Y的一个强度： 那么我们定义一个矩母函数，满足： 可以证明，并且它单调递增，它与信任质量函数可以相互推导，在一定条件下可以说它等价于推广的信任质量函数。由以上定义，不难建立集合导数与集合积分的相互关系如下： 于是进一步推导出推广的R-N理论如下。 ，这里。那么不难得： 以及如果对于一个随机有限集，它满足，这里为独立的随机有限子集，那么，那么的概率密度函数满足： 这里为互不相连的子集，且他们满足。下面再定义一个集合的基数分布（基数便是指集
18、合元素的个数）如下：有了以上一套较完整的随机有限集理论以后，那么便可以直接以集合的观点来解决多目标跟踪问题。对于多目标观测与多目标状态我们可以用以下两个随机有限集表示： 其中和分别是空间和所有子集的集合，即一个代数。和分别是在k时刻目标数目和观测集合中元素的数目。这里的多目标状态集合与多目标观测集合都是有限随机集合。我们记有限随机集的后验信任质量函数为它满足 ，其中记描述多目标传感器观测模型的有限随机集的信任质量函数为，它满足： 记描述多目标状态运动模型的有限随机集的信任质量函数为，它满足： 而相应地，和它们三个的对应的密度函数分别为基于随机有限集理论的多目标后验概率密度函数，多目标状态转移密
19、度函数以及多目标传感器似然函数。于是就可以得到基于随机有限集理论的多目标跟踪的最优贝叶斯递推公式如下： 下面是滤波器的实现，在单目标跟踪问题上，我们也是先得到贝叶斯公式：然后建立贝叶斯滤波器： 一般地，找出密度函数十分困难，并且积分计算也较复杂，对于这个问题，我们都是考虑期望函数也就是一阶矩母函数来近似处理，即是通过估计来近似处理。由于在信噪比较高的情况下，我们可以忽略更高阶的矩母函数，从而有那么，当分布为正态分布时，此时，那么得到的估计为无偏估计，从而可以将问题转化：这样就可以用来间接地处理问题，这就是著名的卡尔曼滤波器算法的思想。这里只有当函数分布为正态分布时，此时的最大后验期望估计才是无
20、偏估计，得到的估计才是最优估计。当信噪比较高时，得到的估计可以看做是一个有效估计，故而用期望函数滤波器来处理问题是比较合理的，而当信噪比较低时，此时的滤波器效能就不是很好了，需要考虑更高阶的矩母函数近似。而当信噪比更高时，我们可以进一步忽略方差也就是二阶矩的影响，得到一个近似，从而获得一个滤波器： 这就是不变卡尔曼滤波器算法的思想。由于集合积分不易计算，故而直接实现随机有限集贝叶斯最优滤波器是十分困难的。同单目标跟踪问题相似，我们也来考虑通过间接近似实现的方法，即建立随机有限集变量的类似期望函数的滤波器递推，也就是将解决密度函数问题化为解决类似于一个期望函数的问题，当然同上面一样，假定信噪比较
21、高时，我们考虑随机有限集E的一阶类似矩母函数，也称它为概率假设密度函数或者强度函数。它满足：之所以称为类似期望函数，那是因为集合加法不同于数的加法不能简单的相加，故而积分上无法定义，我们可以采用一个转换的方法解决，从而得到随机有限集E的类似期望函数：可以证明它是一个单目标空间上的密度函数，但不是一个概率密度函数，因为为积分空间内元素的个数，可以证明，即积分得到的值为S中元素的个数。对于随机有限集E，不难有： 那么还可以证明，强度函数可以由矩母函数与信任质量函数导出。这里矩母函数，那么取h=1时，就等价于强度函数。而矩母函数与信任质量函数是可以相互转化的。有了上述分析，故针对信噪比较高的情况，我
22、们可将看为一个充分统计量，满足： 其实可以证明确实是多目标密度函数的一个信息论最优估计，记强度函数，而多目标泊松密度函数满足：，那么对于Kullback-Leibler交叉熵，可以证明当时交叉熵取得最小值。从而同单目标跟踪一样，可以建立一个滤波器如下: 下面是滤波器算法的具体步骤：那就是说，如果给定以下假设条件：1. 每一个目标的运动和产生的观测都是相互独立的。2. 杂波RFS也是服从Poisson分布，并且和目标产生的观测也是相互独立的。3. 预测多目标RFS状态也服从Poisson分布。1.PHD滤波器初始化选择一个初始先验PHD，满足 这里是先验目标位置的密度函数的最高点，是初始目标数目
23、的均值的估计。若目标初始位置的信息不够，则可以选择一个一致PHD，即为D区域内的均匀分布，而为目前目标数目的一个大致猜测。2.PHD粒子滤波器预测先假定：1. 每个目标更新是按单目标马尔科夫密度转移的2. 在k时刻状态为到k+1时刻生还的概率为3令为k时刻状态为的目标在k+1时刻产生新目标集合X的似然函数，并且它的的PHD函数满足4.令表示在k+1时刻突然出现目标状态集合X的似然函数，它的函数为：这里我们需要考虑五种情况：1.当前没有目标 2.目前最多一个目标 3.目标数有随机多个，但是没有丢失观测或误报 4.随机数个目标，没有丢失观测但有误报 5.随机数个目标，有丢失观测有误报假定在时刻我们
24、已知了函数为则可以证明：这里：相应的可得到目标数目均值预测：这里：.滤波器更新假定： 单目标观测得到的似然函数为 令表示在k+1时刻传感器的状态为，可以观测到目标状态为x的概率 泊松误报，即在k+1时刻，对每个传感器都可能收集到一个均值为的泊松误报。并且相应的分布概率密度为同传统多目标跟踪方法一样，我们需要考虑以下几种情况：1. 目前最多一个目标 2. 随机多个目标，没有目标birth和death 3. 随机多个目标，有随机多个目标death但是没有目标birth 4. 有随机多个目标，并且有随机多个目标birth和death 5. 随机多个目标，并且有随机多个目标birth和death以及s
25、pawn下面是先考虑PHD单传感器修正公式：简记 那么：，这里：而目标数目均值更新公式为：而对于多传感器情况，那么计算量十分大，有采用跟踪标签PHD滤波器法，SMC-PHD（618页）滤波器法，还有GM-PHD法。下面就只介绍GM-PHD滤波器算法假定那么它是通过计算来估计目标状态，滤波器流程为：先假定满足下面条件：1.单目标马尔科夫转移密度是线性高斯的.2.单目标似然函数也是线性高斯的3.观测概率是常数，目标persist的概率也是常数4.目标birth以及目标spawn过程都是高斯混合的，即 4. PHD函数和也是高斯混合的： 那么可计算得到目标数目均值为：初始化初始PHD选择一个高斯混合
26、的形式，即 因此可计算得初始目标数均值为：进一步，每一个高斯组合都安上一个标签来标记，那么就可以得到一个标签表如下：。预测我们假定有一个先验标签表以及一个先验GM-PHD为： 可以证明预测公式为： 这里： ，而预测GM-PHD有个组合。我们还要预测标签表，预测组合和他的祖先按同样的标签，而对于每个birth成员都按一个新标签，同样对每个spawn成员这样处理。那么可得。更新假定先前时刻我们有一个预测标签表和一个预测GM-PHD： 我们获得一个新观测集合，那么可以证明：这里 不难得：同样地，也必须更新标签表，每个都保持他祖先的一样的标签，对于每个成员也保持他祖先的一样的标签，这便导致了不同组员有相同标签的情况，需要通过后面的修剪法处理。GM-PHD修剪法 假定已知当前集合的组合为，对于那些具有充分小的权重的组员我们应该消除，再对那些保留下来的组员重新正规化。一般是采用下面的融合距离公式如果它充分小的话，我们就把相应的两个组员与融合成一个组员满足：融合后得到的组员的标签与融合前两个组员中权重较大的那个的标签保持一致。当然，由于在更新步会使得出现两个或更多组员有相同标签，即使是修剪后还会出现这种情况。那么在这种情况下，我们使其中权重最大的那个组员保持原来的标签，而其他组员被安排新的标签，重复这个过程直到所有的组员都有一致的标签为止。
