meanshift算法简介.ppt

Meanshift算法的概述及其应用,Meanshift的背景,Meanshift算法思想概括起来就是：利用概率密度的梯度爬升来寻找局部最优。它要做的就是输入一个在图像的范围，然后一直迭代（朝着重心迭代）直到满足你的要求为止。 不过如何用于做图像跟踪这是我看了几篇相关论文后也没有一个很清楚的理解，经过这几天的思考，和对相关数学方法推导过程的理解使得我对它的原理有了大致的认识。,直观描述,完全相同的桌球分布,感兴趣区域,质心,Mean Shift 矢量,目的：找出最密集的区域,7/12/2019,MeanShift 在反向投影图中发现目标中心 int cvMeanShift( const CvArr* prob_image, CvRect window, CvTermCriteria criteria, CvConnectedComp* comp ); prob_image 目标直方图的反向投影(见 cvCalcBackProject). window 初始搜索窗口 criteria 确定窗口搜索停止的准则 comp 生成的结构，包含收敛的搜索窗口坐标 (comp-rect 字段) 与窗口内部所有象素点的和 (comp-area 字段). 函数 cvMeanShift 在给定反向投影和初始搜索窗口位置的情况下，用迭代方法寻找目标中心。当搜索窗口中心的移动小于某个给定值时或者函数已经达到最大迭代次数时停止迭代。 函数返回迭代次数。,7/12/2019,对目标进行跟踪时，可以把图片想象成一张概率密度图。图像输入后是一个目标图像的直方图（也可以认为是目标图像），还一个输入是当前图像就是你要跟踪的全图，输出大小与全图一样大，它上像素点表征着一种概率，就是全图上这个点是目标图像一部分的概率。如果这个点越亮，就说明这个点属于物体的概率越大。现在我们明白了这原来是一张概率图了。当用meanshift跟踪时，输入的原来是这样一幅图像，如此可以实现对目标的跟踪。 关键：反向投影 如果一幅图像的区域中显示的是一种结构纹理或者一个独特的物体，那么这个区域的直方图可以看作一个概率函数，他给的是某个像素属于该纹理或物体的概率。所谓反向投影就是首先计算某一特征的直方图模型，然后使用模型去寻找测试图像中存在的该特征。,6,核函数说明,对在d维欧式空间中，x表示该空间中的一个点，K(x)表示该空间的核函数，其定义为： K (x)= ck,d k(|X|) 这里：K(x)是放射对称核函数，k(x)称为K(x)的轮廓函数，具有可微性，且；标准化常量ck,d严格正，使K(x)积分为1。,一维下的无参数估计 设X1,X2, Xn是从总体中抽出的独立同分布的样本，X具有未知的密度函数f（x），则f（x）的核估计为： h为核函数的带宽。常用的核函数如下： 分别是单位均匀核函数 和单位高斯核函数,多维空间下的无参密度估计： 在d维欧式空间X中，x表示该空间中的一个点， 表示该空间中的 核函数, 空间中点x的概率密度估计值为:,在计算机视觉中，最常用的是放射状对称核函数。,是放射状核函数 是 的轮廓函数 标准化常量 是个正数，保证 积分为1 H为带宽矩阵。,H表示d*d维的带宽矩阵,在实际中常采用H为单位矩阵的比例形式，即,若再考虑到,这个表达式就是基于核函数 的概率密度函数的估计,怎样找到数据集合中数据最密集的地方呢？,数据最密集的地方，对应于概率密度最大的地方。我们可以对概率密度求梯度，梯度的方向就是概率密度增加最大的方向，从而也就是数据最密集的方向。,令 ,假设除了有限个点，轮廓函数 的梯度对所有 均存在 。将 作为轮廓函数，核函数 为：,Mean shift向量,基于核函数G(x)的 概率密度估计,Mean shift向量的物理意义,为了更好地理解这个式子的物理意义，假设上式中g(x)=1,平均的偏移量会指向样本点最密的方向，也就是概率密度函数梯度方向,下面我们看一下mean shift算法的步骤,给定一个初始点x,核函数G(x), 容许误差 ,Mean Shift算法循环的执行下面三步,直至结束条件满足, 计算 把 赋给 . 如果 , 结束循环;若不然,循环执行,上面的步骤也就是不断的沿着概率密度的梯度方向移动,同时步长不仅与梯度的大小有关,也与该点的概率密度有关,在密度大的地方,更接近我们要找的概率密度的峰值,Mean Shift算法使得移动的步长小一些,相反,在密度小的地方,移动的步长就大一些.在满足一定条件下,Mean Shift算法一定会收敛到该点附近的峰值,均值漂移在目标跟踪中应用,1：目标模型叙述 2：候选目标叙述 3: 相似型函数比较 4：目标定位 5：整个算法流程,在起始帧，通过鼠标确定一个包含所有目标特征的椭圆，称为被跟踪目标的目标区域，这个目标区域也是核函数作用的区域，区域的大小等于核函数的带宽。 对目标区域进行描述，常用的方法是按照直方图的方式将图像像素的值域等分成k个区间，每个区间按照值域的大小对应一个特征值。然后求出图像的像素值取每个特征值的概率。 对在初始帧图像中目标区域内所有的象素点，计算每个特征值的概率，我们称为目标模型的描述。,目标模型的描述,目标区域的中心为 ，假设其中有n个象素用 表示，特征值的个数为m个 ,则目标模型的特征值 的概率密度估计为：,为核函数的轮廓函数，由于遮挡或者背景的影响，目标模型中心附近的象素比外物象素更可靠， 对中心的象素给一个大的权值，而远离中心的象素一个小的权值 总得作用是判断目标区域中象素的值是否属于第u个特征值。b(xi)是灰度值索引函数。属于该特征则值为1，否则为0(pdf)。 C是一个标准化的常量系数，使得 于是我们得到了基于图像灰度特征的颜色直方图。,运动目标在第二帧及以后的每帧中可能包含目标的区域称为候选区域，其中心坐标为y，也是核函数的中心坐标。该区域中的象素用 表示。对候选区域的描述我们成为目标候选模型，候选模型的特征值 的概率密度为：,其中 是标准化常量,候选模型的描述,相似性函数的比较,模板区域:,候选区域:,相似性函数:,相似性函数描述目标模型和候选模型之间的相似程度，在理想情况下两个模型的概率分布是完全一样的。 我们使用Bhattacharyya系数作为相似性函数,其值在0到1之间。 的值越大，表示两个模型越相似，在当前帧中不同的候选区域计算得到的候选模型，使得 最大候选区域即是在本帧中目标的位置。,目标定位,为使 最大，将当前帧的目标中心先定位为前一帧中目标中的位置 ，从这一点开始寻找最优匹配的目标，其中心为y。先计算目标候选模型 ，对 在 处进行泰勒级数展开，Bhattachcyarya系数可近似为：,其中：,类似于核函数密度估计，不过多了一个权值wi。使 式最大，就是要求 式最大，可以计算 的Mean Shift向量，这样我们就可以得到候选区域中心 移向真实目标区域y的向量:,=,值得注意的是，一般在一帧中找到目标的位置，需要Mean Shift算法从开始若干次迭代才能得到。,其中,整个算法流程 1.在当前帧以y0为起点，计算候选目标的特征pu(y0)u=1，2m; 2.计算候选目标与目标的相似度： 3.计算权值wii=1，2m 4.利用MeanShift算法，计算目标新位置： 5.若 ，则停止；否则y0y1转步骤2 限制条件：新目标中心需位于原目标中心附近。,Meanshift优缺点： 优点 1.算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪 2.采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感 缺点： 1.缺乏必要的模板更新 2.跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会