Meanshift和粒子滤波算法

1、 Mean shift算法算法 与粒子滤波算法与粒子滤波算法YOUR SUBTITLE GOES HEREMean shift基本原理基本原理 Mean shift 这个概念最早由Fukunaga等人于1975年在一篇关于概率密度梯度函数的估计中提出来的，最初的含义就是偏移的均值向量，但随着Mean shift理论的发展，其含义也发生了变化，其含义一般是指一个迭代的步骤，即先算出当前的偏移的均值，移动到其均值，然后依次为新的起始点，继续移动，知道满足一定的条件结束。核函数核函数 例子： Obviously, we would like to generate two groups corres

2、ponding to the two parts of the feature space in which we have a high density of points How can we capture this notion of “high density”-kernel density estimation核函数核函数 Let us define a kernel function: K ( X), with the properties: K decays to zero far from 0 K is maximum at 0 K is symmetric核函数例子核函数例

3、子:Uniform:核函数例子核函数例子Mean shift 的基本形式的基本形式给定d 维空间Rd中n个样本点Xi,i=1,2,3,.n,在x点的Mean shift向量的基本形式定义为：()1 /()hhixiSMxkxx（1）其中，Sh是一个半径为h的高维球区域，满足一下关系的y点的集合，即：2( ):() ()ThSxyyxyxh（2）Mean shift 的基本形式的基本形式 K表示在这n个样本点xi中，有k个点落入Sh区域中。 可以看出，式（1）中（xi-x）是样本点xi相对于点x的偏移向量，式(1)定义的Mean shift向量 Mh(x)就是对落入区域Sh中的k个样本点相对于点

4、x的偏移向量求和然后再平均。从直观上看，如果样本点xi从一个概率密度函数f(x) 中采样得到，由于概率密度梯度指向概率密度增加最大的方向，Sh 区域内的样本点更多的落在沿着概率密度梯度的方向上。因此，Mean shift向量应该指向概率密度的方向。Mean shift 的扩展形式的扩展形式 从式(1)中可以看出，只要是落入Sh 的采样点，无论其离基准点远近，其对最终的偏移向量计算的贡献是一样的，然而一般来说，离基准点越近的采样点对估计基准点周围的统计特性越有效，因此，将核函数的概念引入均值漂移，在计算偏移向量 Mh( x)时可以考虑距离的影响。同时，在所有的样本点xi中，其重要性并不一样，因此

5、还需对每个样本引入一个权重系数。由此得到Mean shift的扩展形式：Mean shift 的扩展形式的扩展形式2( )XK xckh1( )()iif xK XXN（3）( )(t)g tk Mean shift 的扩展形式的扩展形式Mean shift 的算法步骤的算法步骤 给定一个初始点x，核函数 g( x)，误差门限设为，则Mean shift算法循环 的执行下面步骤，直到结束条件满足： (1) 计算Mean shift向量 m(x) (2) 将 m(x)赋给x； (3) 如果 则结束循环；否则，继续执行步骤(1)； 以上步骤即是不断地沿着概率密度的梯度方向移动，同时，步长不仅与梯度

6、的大小有关，也与该点的概率密度有关，在密度较大处，更接近要寻找的概率密度的峰值，因此Mean shift算法的移动步长会比较小；相反，移动的步长就会增大。(x)-x mMean shift 的算法步骤的算法步骤Mean shift 的算法步骤的算法步骤Mean shift 的算法步骤的算法步骤Mean shift 的算法步骤的算法步骤Mean shift 的算法步骤的算法步骤Mean shift 的算法步骤的算法步骤应用应用应用 粒子滤波理论粒子滤波理论 粒子滤波是指：通过寻找一组在状态空间中传播的随机样本对概率密度函数p(xk|zk)进行近似，以样本均值代替积分运算，从而获得状态最小方差估计

7、的过程，这些样本称为粒子，采用数学语言描述如下：对于平稳的随机过程，假定k-1时刻系统的后验概率密度为p(xk-1|zk-1)，依据一定原则选取n个随机样本点，k时刻获得测量信息后，经过状态和时间更新过程，n个粒子的后验概率密度可近似为p（xk|zk），随着粒子数目的增加，粒子的概率密度函数逼近状态的概率密度函数，粒子滤波估计即达到了最优贝叶斯估计的效果。2.1贝叶斯滤波原理贝叶斯滤波原理 贝叶斯滤波原理的实质是试图用所有已知信息来构造系统状态变量的后验概率密度，即用系统状态转移模型预测状态的先验概率密度，再使用最近的观测值进行修正，最后得到后验概率密度。 设x1,x2,.xn是独立同分布的随

8、机变量，每一个变量相对于未知参数 的条件概率密度为 则未知参数的后验概率密度如式(2.1)所示( | )P x111( ,.| )( |,.)( ,.,)NNNp xxpxxp xx（2.1）2.1贝叶斯滤波原理贝叶斯滤波原理式（2.1）中 表示给定数据（x1,xn）后参数的似然函数， 是待估计参数 的概率密度，称之为先验分布。 是参数的后验密度，称之为后验概率密度。 由贝叶斯定理可以看出，贝叶斯方法把待估计参数当作一个随机变量，在没有新的观测数据时，根据先验分布 对参数作出判断，在得到新的观测数据后，根据贝叶斯定理将先验分布与实际观测数据相结合得到后验分布。贝叶斯定理是一种通过更新参数值的先

9、验分布从而得出其后验分布的数学方法，是将经验知识与观测数据加以综合的过程。 1( ,.| )Np xx( )p1( |,.)Npxx1( |,.)Npxx2.2状态转移模型状态转移模型 状态转移模型是一种离散时刻的状态空间运动模型，如图2.1所示。其目的是根据当前时刻t 的观测来估计隐含目标状态的概率分布。2.2状态转移模型状态转移模型 根据图2.1所描述的状态转移模型，其中的系统隐含状态xt,t=1,2, 会由式(2.2)所示的系统方程随时间更新: 而观测yt,t=1,2,则由式（2.3）所示的观测方程描述：2.22.32.2状态转移模型状态转移模型 其中wt和vt是相互独立切概率分布已知的

10、噪声向量，并假定初始状态的概率密度函数p(x0)已知。xt称为目标状态、真实状态等。yt也称测量信息、观测等。为了使用方便，定义Xt=x0,x1,.xt,Yt=y0,y1,.yt。在状态空间模型中，系统状态满足式（2.4）所示的马尔可夫属性。 在给定状态向量Xt时，观测Yt相互独立，如式（2.5）2.42.52.3递归贝叶斯推理递归贝叶斯推理由图2.1所示的状态转移运动模型中可以看出，如果在每次获得观测时都从头开始对时刻t的隐含目标状态tx进行估计的话，会导致计算量的不断增加而影响计算的速度。为了能够实时估计目标状态，需要一种递归的方法，即仅通过时刻 t-1 的状态和新的观测信息只对时刻t 的

11、状态进行估计。递归贝叶斯估计方法为此类问题提供了一种可靠的解决方法，在给定P(xt-1|Yt-1)以及最近的观测yt时，通过如式(2.6)所示的贝叶斯定理计算后验概率密度。2.6由(2.6) 式 可得到递归贝叶斯推理的两个步骤，即如式(2.7)所示的预测步骤(时间更新)和式(2.8)所示的修正步骤(观测更新)：其推导过程如式（2.9）2.72.82.9 在递归贝叶斯推理中，根据不同的假设条件，对p(xt|yt)的计算也存在多种解决方法，当动态系统满足线性高斯假设时，可通过卡尔曼滤波器求得最优解，通常所说的“最佳”与“最优”估计是以最小均方误差为准则的。当动态系统是非线性时，递归贝叶斯推理中的高

12、维积分运算通常是难解问题，为了缓解非线性动态贝叶斯分析的计算压力，出现了许多近似方法，其中包括蒙特卡罗方法蒙特卡罗采样方法蒙特卡罗采样方法蒙特卡罗方法是一种非常简单的随机模拟方法，可用随机样本近似积分来计算难解的积分问题，其基本思想是从目标概率分布p(xt|yt) 中抽取N个独立同分布的粒子 则后验密度可以通过式(3.16)近似表达：其中 表示从后验分布采样得到的粒子， 表示Dirac delta函数。基于这种近似表达，如果对的期望进行估计，得式(3.1)：3.03.1经过随机抽样后，可通过式（3.2）计算经验估计。根据大数定理，当粒子数N趋于无穷时，近似期望收敛于真实期望，即：3.23.3重

13、要性采样重要性采样重要性取样是蒙特卡罗方法中一种常用的取样技术。后验概率密度可以由来自该密度的独立同分布粒子近似，粒子数越多，近似的后验概率密度就越逼近真实后验概率密度。但往往不可能直接从后验密度采样粒子，在实际计算中从一个已知、易于采样而且同目标概率分布相近的概率密度采样粒子，这个概率密度称为建议分布，即是如图2.2所示的重要性取样的基本思想。如果估计函数期望为 Ef(xi)如果无法直接从 p(xt|Yt)取样，就选择从与p(xt|Yt) 近似的概率分布 中取样。重要性采样重要性采样在重要性取样过程中，式（3.1）可按式（3.4）进行推理。式（3.4）可以看出，可通过从 取得的样本对于f(x

14、t)有关的各种量进行估计，概率密度 称为重要性函数，其中 称为重要性权值，重要性权值 的表达如3.53.43.5利用贝叶斯规则对式(3.5)继续推理，消去p(Yt)，得式(3.6)3.6由式（3.6）可以看出，通过从重要性函数 取样，Ef(xt)可以通过（3.7）近似为其中正则权值可按（3.8）计算：3.73.8贯序重要性取样贯序重要性取样当获得时刻t的观测时，为了能够在不修改以前状态x(0:t-1)情况下，对状态xt的概率密度进行序贯式估计，将建议分布分解为如式(3.9)所示的重要性函数：由于状态空间模型满足马尔可夫过程，在给定状态时观测之间条件独立，可得到式(4.0)3.94.0把式(4.

15、0)带入式(3.5)中，可以得到如式4.1所示的重要性加权的递归估计表达式式(4.1)表明，只要选择合适的建议分布 获得采样粒子，就可以迭代计算粒子的重要性权值4.1重要性函数的选择重要性函数的选择 如何选择重要性函数是一个很重要的问题，理想的重要性函数应该能最小化重要性权值的方差。最简单的重要性函数形式是状态的先验分布，即：则重要性权值计算简化为：式(3.29)表明，采用状态转移先验分布作为重要性函数，重要性权值和似然概率密度成正比。 尽管采用状态转移先验作为重要性函数实现较为容易，但在采样粒子的过程中没有考虑最近的观测信息，这会导致仅有少量的粒子有较大的权值。当似然在先验分布的尾端或相对先验较窄时，都会发生这种情况，因此选择合适的重要性函数很重要，最优的重要性函数应充分考虑最新的观测信息，将粒子移动到高似然区4.34.2重采样重采样序贯重要性取样方法中存在的致命缺陷是权值退化，即粒子经过若干次迭代之后，会出现其余粒子的权值可忽略不计，而其中的一个粒子的规范化权值趋于1的现象，导致大量计算资源浪费在几乎不起作用的粒子更新上的同时还降低了粒子滤波器的性能。当发生粒子退化现象时，粒子集不能有效地表达后验概率密度。权值退化问题主要原因是重要性权值的方差随时间变化不断增加，在理想情况下，如果能够直接从