《均值漂移分析》PPT课件.ppt

Mean Shift聚类分析与应用,张旭光,目录,Mean Shift 原理 Mean Shift 介绍 密度估计方法 Mean Shift算法推导 Mean shift 算法特点 应用 聚类 间断保持平滑 边缘检测 图像分割 目标跟踪,Mean Shift 原理,均值漂移法(Mean Shift),算法思想：对相似度概率密度函数或者后验概率密度函数采用直接的连续估计。Mean shift：均值偏移方法。采用彩色直方图作为匹配特征。Mean Shift 跟踪算法反复不断地把数据点朝向MeanShift 矢量方向进行移动，最终收敛到某个概率密度函数的极值点。在Mean Shift 跟踪算法中，相似度函数用于刻画目标模板和候选区域所对应的两个核函数直方图的相似性，采用的是Bhattacharyya 系数。因此，这种方法将跟踪问题转化为Mean Shift 模式匹配问题。核函数是Mean Shift 算法的核心，可以通过尺度空间差的局部最大化来选择核尺度，若采用高斯差分计算尺度空间差，则得到高斯差分Mean Shift 算法。,直观说明,感兴趣区域,质心,Mean Shift向量,目的:寻找样本分布最密集的区域,直观说明,感兴趣区域,质心,Mean Shift向量,目的:寻找样本分布最密集的区域,直观说明,感兴趣区域,质心,Mean Shift向量,目的:寻找样本分布最密集的区域,直观说明,感兴趣区域,质心,Mean Shift向量,目的:寻找样本分布最密集的区域,直观说明,感兴趣区域,质心,Mean Shift向量,目的:寻找样本分布最密集的区域,直观说明,感兴趣区域,质心,Mean Shift向量,目的:寻找样本分布最密集的区域,直观说明,感兴趣区域,质心,目的:寻找样本分布最密集的区域,What is Mean Shift?,非参数密度估计,非参数密度 梯度 估计(Mean Shift),离散 PDF 表示法,PDF 分析,特征空间的概率密度函数PDF 颜色空间 尺度空间 任何你想得到的特征空间,作用:在一组样本点中寻找一个体现在样本RN中隐含的概率密度函数(PDF)的方法,参数化估计：ML方法和Bayesian估计。假设概率密度形式已知。实际中概率密度形式往往未知。实际中概率密度往往是多模的，即有多个局部极大值。实际中样本维数较高，且关于高维密度函数可以表示成一些低维密度函数乘积的假设通常也不成立。非参数密度估计方法：能处理任意的概率分布，而不必假设密度函数的形式已知。,非参数密度估计,直方图方法：非参数概率密度估计的最简单方法 1.把x的每个分量分成k 个等间隔小窗，（xEd，则形成kd 个小舱）2.统计落入各个小舱内的样本数qi 3.相应小舱的概率密度为：qi/(NV)（N：样本 总数，V：小舱体积）,非参数密度估计,直方图的例子,非参数密度估计,非参数概率密度估计的核心思路：,一个向量x落在区域R中的概率P为：,因此，可以通过统计概率P来估计概率密度函数p(x),非参数密度估计,非参数密度估计,假设:数据点是从一个隐含的PDF中采样得出,概率密度函数PDF的估计,真实样本点数据,数据点密度 意味着 PDF 值!,概率密度函数PDF的估计,真实样本点数据,非参数密度估计,概率密度函数PDF的估计,真实样本点数据,?,非参数密度估计,参数 密度估计,假设:数据点是从一个隐含的PDF中采样得出,概率密度函数PDF的估计,估计,真实样本点数据,核密度估计总体框架,核函数特点:归一化 对称性 指数权重衰减?,关于有限数据点x1xn的函数,核密度估计函数形式,关于有限数据点x1xn的函数,实际使用形式:,or,与每个维度均相关,仅与向量长度相关,核密度估计常用核函数,关于有限数据点x1xn的函数,Examples:Epanechnikov 核函数 单位均匀核函数 Normal 核函数,核密度 估计,梯度,不估计 PDF!仅仅估计梯度,利用公式:,得:,窗口大小,核密度 估计,梯度,计算 Mean Shift,计算 Mean Shift,另一个核密度估计!,简化的 Mean Shift 计算过程:计算 mean shift 向量利用 m(x)更新核窗口,Mean Shift 模式检测,Mean Shift 更新过程:Find all modes using the Simple Mean Shift Procedure Prune modes by perturbing them(find saddle points and plateaus)Prune nearby take highest mode in the window,What happens if wereach a saddle point?,Perturb the mode positionand check if we return back,自适应梯度上升,Mean Shift 算法特点,自动收敛速度 mean shift 向量大小仅仅取决于 向量本身 中心附近的最大值，该步骤小而精 在无穷步的迭代后算法才能保证收敛 无限收敛,(因此要设定一个下限)对于单位均匀核函数(),在有限次迭代后算法收敛 Normal 核函数()呈现出平滑的迭代轨迹，但是迭代 速度要慢于 Uniform 核函数().,真正的形态分析,利用窗口来细分空间,分别进行Mean shift迭代,真正的形态分析,The blue data points were traversed by the windows towards the mode,真正的形态分析An example,窗口轨迹代表最陡的上升方向,自适应 Mean Shift,Mean Shift 算法的优势&缺点,优势:应用独立的工具 适用于实时数据分析 不需要在数据集群中事先假设 轮廓（例如椭圆形）能够处理任意特征空间 只需要选择一个参数 和K-Means 算法不同的是，h(窗口大小)具有物理意义,缺点:窗口尺寸(由带宽决定)是 微不足道的 不适当的窗口大小 导致漠视被合并,或者产生额外的“阴影”模式 使用自适应窗口大小,Mean Shift 应用,聚类,吸引区域:在这个区域里，所有的轨迹导致相同的模式,聚类:在 吸引区域 中的所有数据点都有相同的模式,Mean Shift:A robust Approach Toward Feature Space Analysis,by Comaniciu,Meer,聚类合成案例,简单模态结构,复杂模态结构,聚类真实案例,初始化窗口中心,寻找模态,修剪后的模态,最终聚类结果,特征空间:用L*u*v 来表示,聚类真实案例,L*u*v 3维空间,聚类真实案例,吸引区域中不是所有的轨迹都会达到相同的模态,2维空间(L*u),聚类结果,间断保持平滑,特征空间:联合域=空间坐标+颜色空间,意义:把图像看做在空间域和灰度域上的数据点,图像数据,Mean Shift向量,平滑结果,Mean Shift:A robust Approach Toward Feature Space Analysis,by Comaniciu,Meer,间断保持平滑,图像灰度级,可以看做是在空间 x,y,z 的数据点(结合空间坐标和颜色信息),间断保持平滑,Flat regions induce the modes!,间断保持平滑,在空间和空间范围中窗口大小的作用,间断保持平滑Example,间断保持平滑Example,边缘存在于目标与背景、目标与目标、区域与区域之间，是图像最基本的特征之一为人们描述或识别目标以及解释图像提供了一个重要的特征参数。它蕴含了图像丰富的内在信息（如方向、阶越性质与形状等）；纹理特征的重要信息源和形状特征的基础；图像分割、图像分类、图像配准和模式识别所依赖的重要特征。如果能成功地检测出图像的边缘，图像分析、图像识别就会方便得多，精确度也会得到提高。,边缘检测,边缘检测射线传播,Vessel Detection by Mean Shift Based Ray Propagation,by Tek,Comaniciu,Williams,在医学图像中准确区分各种物体,边缘检测射线传播,使用位移数据来指导射线传播,间断平滑,位移矢量,Vessel Detection by Mean Shift Based Ray Propagation,by Tek,Comaniciu,Williams,边缘检测射线传播,速度公式,与轮廓正交,曲率,边缘检测,原始图像,沿红线处的灰度等级,平滑处理后的灰度图,位移矢量,位移矢量求导,边缘检测Example,边缘检测Example,利用曲率进行平滑的重要性,图像分割的概念在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣，这些部分一般称为目标或前景。为了辨识和分析目标，需要将有关区域分离提取出来，在此基础上对目标进一步利用，如进行特征提取和测量。图像分割就是指把图像分成各具特性的区域，并提取出感兴趣目标的技术和过程。,图像分割,图像分割,片段=集群,或者集群的集群,算法:进行滤波(间断保持平滑)聚集比窗口大小更接近的集群,图像数据(片段),Mean Shift向量,分割结果,平滑处理,Mean Shift:A robust Approach Toward Feature Space Analysis,by Comaniciu,Meerhttp:/www.caip.rutgers.edu/comanici,图像分割Example,当特征空间只有图像灰度的时候,图像分割Example,图像分割Example,图像分割Example,图像分割Example,图像分割Example,图像分割Example,所谓目标跟踪，可以简单地定义为对连续的视频序列中的目标维持一条航迹，进而获得目标的位置、速度等运动参数，以及形状、大小、颜色等对后续目标分析与理解非常重要的测量信息。,目 标 跟 踪,非刚性目标跟踪,非刚性目标跟踪,实时,监控,辅助驾驶,基于对象的视频压缩,当前帧,Mean-Shift 目标跟踪总体框架:目标表示,Mean-Shift 目标跟踪总体框架:目标定位,从当前帧中选定的模板位置开始,在下一帧中重复相同的过程,当前帧,目标模板,候选模板,Mean-Shift 目标跟踪目标表示,Kernel Based Object Tracking,by Comaniniu,Ramesh,Meer,Mean-Shift 目标跟踪PDF 表示,相似性函数:,目标模板(以0点为中心),候选模板(以y点为中心),Mean-Shift 目标跟踪平滑相似性函数,相似性函数:,Mean-Shift 目标跟踪寻找目标模板的 PDF,目标像素位置,一个可微，各向同性的，凸函数且单调递减的核函数 周边像素收到遮挡和背景干扰,像素 x 在索引(1.m)中的对应值,目标模板,候选模板,Mean-Shift 目标跟踪相似性函数,目标模板:,候选模板:,相似性函数:,Mean-Shift 目标跟踪目标定位算法,从当前帧中选定的模板位置开始,线性近似(以 y0 为中心),Mean-Shift 目标跟踪逼近相似性函数,模板中心:,候选位置:,与 y 无关,密度估计！(关于 y 的函数),Mean-Shift 目标跟踪最大化相似性函数,求解,=寻找最大值,Mean-Shift 目标跟踪应用 Mean-Shift,原始Mean-Shift:,求解,利用,求解,=寻找最大值,Mean-Shift 目标跟踪关于核函数和轮廓函数,一类特殊的径向对称内核：,核函数 K 的轮廓函数,Mean-Shift 目标跟踪核函数选取,Epanechnikov 核函数:,一类特殊的径向对称内核：,扩展Mean-Shift:,Mean-Shift 目标跟踪自适应窗口大小,问题:,目标大小随时间变化,必须调整核函数窗宽(h),Mean-Shift 目标跟踪结果,特征空间:161616 量化RGB颜色值目标:在第一帧中手动选择平均 mean-shift 迭代次数:4,Mean-Shift 目标跟踪结果,Mean-Shift 目标跟踪结果,Mean-Shift 目标跟踪结果,特征空间:128128 量化 RG 颜色值,Mean-Shift 目标跟踪尺度选择问题,窗口选择过大,窗口选择过小,尺度空间跟踪Motivation,对数个尺度进行定位,先前的方法,在空间和尺度上同时定位,当前方法,Mean-shift Blob Tracking through Scale Space,by R.Collins,Lindebergs 理论选择最佳尺度来描述图像特征,尺度空间表示,微分算子应用,选取50个较大值,尺度空间表示法,Lindebergs 理论使用拉普拉斯算子选择斑点状特征,高斯拉普拉斯（LOG）,在(x,)处 L 达到最大化,以 为尺度进行二位LOG滤波,Lindebergs 理论多尺度特征选择过程,原始图像,尺度空间跟踪使用DOG逼近LOG,为什么选用 DOG?高斯金字塔的创建速度更快 高斯函数可以作为 mean-shift 核函数,以 为尺度进行二维 LOG 滤波2D LOG,以 为尺度进行二维 DOG 滤波2D LOG,尺度空间跟踪利用 Lindebergs 理论,权重图像,每个像素点数与目标位置的可能性,一维空间核函数(Epanechnikov),尺度空间跟踪Example,图像中有3个斑点,通过三维尺度空间表示,尺度空间跟踪应用 Mean-Shift,使用交错的空间/尺度的 mean-shift 算法,空间阶段:,设置 寻找最佳的 x,尺度阶段:,设置 x 寻找最佳的,尺度空间跟踪Results,固定尺寸,通过尺度空间跟踪,10%空间自适应,ThankYou,