Meanshift和粒子滤波算法

Meanshift算法

与粒子滤波算法YOURSUBTITLEGOESHERE目前一页\总数五十三页\编于十四点Meanshift基本原理

Meanshift这个概念最早由Fukunaga等人于1975年在一篇关于概率密度梯度函数的估计中提出来的，最初的含义就是偏移的均值向量，但随着Meanshift理论的发展，其含义也发生了变化，其含义一般是指一个迭代的步骤，即先算出当前的偏移的均值，移动到其均值，然后依次为新的起始点，继续移动，知道满足一定的条件结束。目前二页\总数五十三页\编于十四点核函数例子：Obviously,wewouldliketogeneratetwogroupscorrespondingtothetwopartsofthefeaturespaceinwhichwehaveahighdensityofpointsHowcanwecapturethisnotionof“highdensity”----kerneldensityestimation目前三页\总数五十三页\编于十四点核函数Letusdefineakernelfunction:K(X),withtheproperties:Kdecaystozerofarfrom0Kismaximumat0Kissymmetric目前四页\总数五十三页\编于十四点核函数例子:Uniform:目前五页\总数五十三页\编于十四点核函数例子目前六页\总数五十三页\编于十四点Meanshift的基本形式给定d维空间R^d中n个样本点Xi,i=1,2,3,….n,在x点的Meanshift向量的基本形式定义为：（1）其中，Sh是一个半径为h的高维球区域，满足一下关系的y点的集合，即：（2）目前七页\总数五十三页\编于十四点Meanshift的基本形式

K表示在这n个样本点xi中，有k个点落入Sh区域中。可以看出，式（1）中（xi-x）是样本点xi相对于点x的偏移向量，式(1)定义的Meanshift向量Mh(x)就是对落入区域Sh中的k个样本点相对于点x的偏移向量求和然后再平均。从直观上看，如果样本点xi从一个概率密度函数f(x)中采样得到，由于概率密度梯度指向概率密度增加最大的方向，Sh区域内的样本点更多的落在沿着概率密度梯度的方向上。因此，Meanshift向量应该指向概率密度的方向。目前八页\总数五十三页\编于十四点Meanshift的扩展形式从式(1)中可以看出，只要是落入Sh的采样点，无论其离基准点远近，其对最终的偏移向量计算的贡献是一样的，然而一般来说，离基准点越近的采样点对估计基准点周围的统计特性越有效，因此，将核函数的概念引入均值漂移，在计算偏移向量Mh(x)时可以考虑距离的影响。同时，在所有的样本点xi中，其重要性并不一样，因此还需对每个样本引入一个权重系数。由此得到Meanshift的扩展形式：目前九页\总数五十三页\编于十四点Meanshift的扩展形式（3）目前十页\总数五十三页\编于十四点Meanshift的扩展形式目前十一页\总数五十三页\编于十四点Meanshift的算法步骤给定一个初始点x，核函数g(x)，误差门限设为，则Meanshift算法循环的执行下面步骤，直到结束条件满足：

(1)计算Meanshift向量m(x)(2)将m(x)赋给x；

(3)如果则结束循环；否则，继续执行步骤(1)；以上步骤即是不断地沿着概率密度的梯度方向移动，同时，步长不仅与梯度的大小有关，也与该点的概率密度有关，在密度较大处，更接近要寻找的概率密度的峰值，因此Meanshift算法的移动步长会比较小；相反，移动的步长就会增大。目前十二页\总数五十三页\编于十四点Meanshift的算法步骤目前十三页\总数五十三页\编于十四点Meanshift的算法步骤目前十四页\总数五十三页\编于十四点Meanshift的算法步骤目前十五页\总数五十三页\编于十四点Meanshift的算法步骤目前十六页\总数五十三页\编于十四点Meanshift的算法步骤目前十七页\总数五十三页\编于十四点Meanshift的算法步骤目前十八页\总数五十三页\编于十四点应用应用目前十九页\总数五十三页\编于十四点粒子滤波理论粒子滤波是指：通过寻找一组在状态空间中传播的随机样本对概率密度函数p(xk|zk)进行近似，以样本均值代替积分运算，从而获得状态最小方差估计的过程，这些样本称为粒子，采用数学语言描述如下：对于平稳的随机过程，假定k-1时刻系统的后验概率密度为p(xk-1|zk-1)，依据一定原则选取n个随机样本点，k时刻获得测量信息后，经过状态和时间更新过程，n个粒子的后验概率密度可近似为p（xk|zk），随着粒子数目的增加，粒子的概率密度函数逼近状态的概率密度函数，粒子滤波估计即达到了最优贝叶斯估计的效果。目前二十页\总数五十三页\编于十四点2.1贝叶斯滤波原理贝叶斯滤波原理的实质是试图用所有已知信息来构造系统状态变量的后验概率密度，即用系统状态转移模型预测状态的先验概率密度，再使用最近的观测值进行修正，最后得到后验概率密度。设x1,x2,….xn是独立同分布的随机变量，每一个变量相对于未知参数的条件概率密度为则未知参数的后验概率密度如式(2.1)所示（2.1）目前二十一页\总数五十三页\编于十四点2.1贝叶斯滤波原理式（2.1）中表示给定数据（x1,…xn）后参数的似然函数，是待估计参数的概率密度，称之为先验分布。是参数的后验密度，称之为后验概率密度。由贝叶斯定理可以看出，贝叶斯方法把待估计参数当作一个随机变量，在没有新的观测数据时，根据先验分布对参数作出判断，在得到新的观测数据后，根据贝叶斯定理将先验分布与实际观测数据相结合得到后验分布。贝叶斯定理是一种通过更新参数值的先验分布从而得出其后验分布的数学方法，是将经验知识与观测数据加以综合的过程。目前二十二页\总数五十三页\编于十四点2.2状态转移模型状态转移模型是一种离散时刻的状态—空间运动模型，如图2.1所示。其目的是根据当前时刻t的观测来估计隐含目标状态的概率分布。目前二十三页\总数五十三页\编于十四点2.2状态转移模型根据图2.1所描述的状态转移模型，其中的系统隐含状态{xt},t=1,2,…会由式(2.2)所示的系统方程随时间更新:而观测{yt},t=1,2,…则由式（2.3）所示的观测方程描述：2.22.3目前二十四页\总数五十三页\编于十四点2.2状态转移模型其中wt和vt是相互独立切概率分布已知的噪声向量，并假定初始状态的概率密度函数p(x0)已知。{xt}称为目标状态、真实状态等。{yt}也称测量信息、观测等。为了使用方便，定义Xt={x0,x1,...xt},Yt={y0,y1,..yt}。在状态空间模型中，系统状态满足式（2.4）所示的马尔可夫属性。在给定状态向量Xt时，观测Yt相互独立，如式（2.5）2.42.5目前二十五页\总数五十三页\编于十四点2.3递归贝叶斯推理由图2.1所示的状态转移运动模型中可以看出，如果在每次获得观测时都从头开始对时刻t的隐含目标状态tx进行估计的话，会导致计算量的不断增加而影响计算的速度。为了能够实时估计目标状态，需要一种递归的方法，即仅通过时刻t-1的状态和新的观测信息只对时刻t的状态进行估计。递归贝叶斯估计方法为此类问题提供了一种可靠的解决方法，在给定P(xt-1|Yt-1)以及最近的观测yt时，通过如式(2.6)所示的贝叶斯定理计算后验概率密度。2.6目前二十六页\总数五十三页\编于十四点由(2.6)式可得到递归贝叶斯推理的两个步骤，即如式(2.7)所示的预测步骤(时间更新)和式(2.8)所示的修正步骤(观测更新)：其推导过程如式（2.9）2.72.8目前二十七页\总数五十三页\编于十四点2.9目前二十八页\总数五十三页\编于十四点在递归贝叶斯推理中，根据不同的假设条件，对p(xt|yt)的计算也存在多种解决方法，当动态系统满足线性高斯假设时，可通过卡尔曼滤波器求得最优解，通常所说的“最佳”与“最优”估计是以最小均方误差为准则的。当动态系统是非线性时，递归贝叶斯推理中的高维积分运算通常是难解问题，为了缓解非线性动态贝叶斯分析的计算压力，出现了许多近似方法，其中包括蒙特卡罗方法目前二十九页\总数五十三页\编于十四点蒙特卡罗采样方法蒙特卡罗方法是一种非常简单的随机模拟方法，可用随机样本近似积分来计算难解的积分问题，其基本思想是从目标概率分布p(xt|yt)中抽取N个独立同分布的粒子则后验密度可以通过式(3.16)近似表达：其中表示从后验分布采样得到的粒子，表示Diracdelta函数。基于这种近似表达，如果对的期望进行估计，得式(3.1)：3.03.1目前三十页\总数五十三页\编于十四点经过随机抽样后，可通过式（3.2）计算经验估计。根据大数定理，当粒子数N趋于无穷时，近似期望收敛于真实期望，即：3.23.3目前三十一页\总数五十三页\编于十四点重要性采样重要性取样是蒙特卡罗方法中一种常用的取样技术。后验概率密度可以由来自该密度的独立同分布粒子近似，粒子数越多，近似的后验概率密度就越逼近真实后验概率密度。但往往不可能直接从后验密度采样粒子，在实际计算中从一个已知、易于采样而且同目标概率分布相近的概率密度采样粒子，这个概率密度称为建议分布，即是如图2.2所示的重要性取样的基本思想。如果估计函数期望为E[f(xi)]如果无法直接从p(xt|Yt)取样，就选择从与p(xt|Yt)近似的概率分布中取样。目前三十二页\总数五十三页\编于十四点重要性采样在重要性取样过程中，式（3.1）可按式（3.4）进行推理。式（3.4）可以看出，可通过从取得的样本对于f(xt)有关的各种量进行估计，概率密度称为重要性函数，其中称为重要性权值，重要性权值的表达如3.53.43.5目前三十三页\总数五十三页\编于十四点利用贝叶斯规则对式(3.5)继续推理，消去p(Yt)，得式(3.6)3.6目前三十四页\总数五十三页\编于十四点由式（3.6）可以看出，通过从重要性函数取样，E[f(xt)]可以通过（3.7）近似为其中正则权值可按（3.8）计算：3.73.8目前三十五页\总数五十三页\编于十四点贯序重要性取样当获得时刻t的观测时，为了能够在不修改以前状态x(0:t-1)情况下，对状态xt的概率密度进行序贯式估计，将建议分布分解为如式(3.9)所示的重要性函数：由于状态空间模型满足马尔可夫过程，在给定状态时观测之间条件独立，可得到式(4.0)3.94.0目前三十六页\总数五十三页\编于十四点把式(4.0)带入式(3.5)中，可以得到如式4.1所示的重要性加权的递归估计表达式式(4.1)表明，只要选择合适的建议分布获得采样粒子，就可以迭代计算粒子的重要性权值4.1目前三十七页\总数五十三页\编于十四点重要性函数的选择如何选择重要性函数是一个很重要的问题，理想的重要性函数应该能最小化重要性权值的方差。最简单的重要性函数形式是状态的先验分布，即：则重要性权值计算简化为：式(3.29)表明，采用状态转移先验分布作为重要性函数，重要性权值和似然概率密度成正比。尽管采用状态转移先验作为重要性函数实现较为容易，但在采样粒子的过程中没有考虑最近的观测信息，这会导致仅有少量的粒子有较大的权值。当似然在先验分布的尾端或相对先验较窄时，都会发生这种情况，因此选择合适的重要性函数很重要，最优的重要性函数应充分考虑最新的观测信息，将粒子移动到高似然区4.34.2目前三十八页\总数五十三页\编于十四点重采样序贯重要性取样方法中存在的致命缺陷是权值退化，即粒子经过若干次迭代之后，会出现其余粒子的权值可忽略不计，而其中的一个粒子的规范化权值趋于1的现象，导致大量计算资源浪费在几乎不起作用的粒子更新上的同时还降低了粒子滤波器的性能。当发生粒子退化