第五课均值漂移分析

第五课均值漂移分析演示文稿现在是1页\一共有92页\编辑于星期二优选第五课均值漂移分析现在是2页\一共有92页\编辑于星期二目录

MeanShift原理MeanShift介绍密度估计方法MeanShift算法推导Meanshift算法特点

应用聚类间断保持平滑边缘检测图像分割目标跟踪现在是3页\一共有92页\编辑于星期二MeanShift原理现在是4页\一共有92页\编辑于星期二均值漂移法(MeanShift)算法思想：对相似度概率密度函数或者后验概率密度函数采用直接的连续估计。Meanshift：均值偏移方法。采用彩色直方图作为匹配特征。MeanShift跟踪算法反复不断地把数据点朝向MeanShift矢量方向进行移动，最终收敛到某个概率密度函数的极值点。在MeanShift跟踪算法中，相似度函数用于刻画目标模板和候选区域所对应的两个核函数直方图的相似性，采用的是Bhattacharyya系数。因此，这种方法将跟踪问题转化为MeanShift模式匹配问题。核函数是MeanShift算法的核心，可以通过尺度空间差的局部最大化来选择核尺度，若采用高斯差分计算尺度空间差，则得到高斯差分MeanShift算法。现在是5页\一共有92页\编辑于星期二直观说明感兴趣区域质心MeanShift向量目的:寻找样本分布最密集的区域现在是6页\一共有92页\编辑于星期二直观说明感兴趣区域质心MeanShift向量目的:寻找样本分布最密集的区域现在是7页\一共有92页\编辑于星期二直观说明感兴趣区域质心MeanShift向量目的:寻找样本分布最密集的区域现在是8页\一共有92页\编辑于星期二直观说明感兴趣区域质心MeanShift向量目的:寻找样本分布最密集的区域现在是9页\一共有92页\编辑于星期二直观说明感兴趣区域质心MeanShift向量目的:寻找样本分布最密集的区域现在是10页\一共有92页\编辑于星期二直观说明感兴趣区域质心MeanShift向量目的:寻找样本分布最密集的区域现在是11页\一共有92页\编辑于星期二直观说明感兴趣区域质心目的:寻找样本分布最密集的区域现在是12页\一共有92页\编辑于星期二WhatisMeanShift?非参数密度估计非参数密度梯度估计(MeanShift)样本点离散PDF表示法PDF分析特征空间的概率密度函数PDF颜色空间尺度空间任何你想得到的特征空间…作用:在一组样本点中寻找一个体现在样本RN中隐含的概率密度函数(PDF)的方法现在是13页\一共有92页\编辑于星期二参数化估计：ML方法和Bayesian估计。假设概率密度形式已知。实际中概率密度形式往往未知。实际中概率密度往往是多模的，即有多个局部极大值。实际中样本维数较高，且关于高维密度函数可以表示成一些低维密度函数乘积的假设通常也不成立。非参数密度估计方法：能处理任意的概率分布，而不必假设密度函数的形式已知。非参数密度估计现在是14页\一共有92页\编辑于星期二直方图方法：非参数概率密度估计的最简单方法

1.把x的每个分量分成k个等间隔小窗，（x∈Ed

，则形成kd

个小舱）

2.统计落入各个小舱内的样本数qi3.相应小舱的概率密度为：qi/(NV)

（N：样本总数，V：小舱体积）非参数密度估计现在是15页\一共有92页\编辑于星期二直方图的例子非参数密度估计现在是16页\一共有92页\编辑于星期二非参数概率密度估计的核心思路：一个向量x落在区域R中的概率P为：因此，可以通过统计概率P来估计概率密度函数p(x)非参数密度估计现在是17页\一共有92页\编辑于星期二非参数密度估计假设:数据点是从一个隐含的PDF中采样得出概率密度函数PDF的估计真实样本点数据数据点密度意味着PDF值!现在是18页\一共有92页\编辑于星期二概率密度函数PDF的估计真实样本点数据非参数密度估计现在是19页\一共有92页\编辑于星期二概率密度函数PDF的估计真实样本点数据?非参数密度估计现在是20页\一共有92页\编辑于星期二参数密度估计假设:数据点是从一个隐含的PDF中采样得出概率密度函数PDF的估计估计真实样本点数据现在是21页\一共有92页\编辑于星期二核密度估计

总体框架核函数特点:归一化对称性指数权重衰减???关于有限数据点x1…xn的函数

数据点现在是22页\一共有92页\编辑于星期二核密度估计

函数形式关于有限数据点x1…xn的函数

数据点实际使用形式:or与每个维度均相关仅与向量长度相关现在是23页\一共有92页\编辑于星期二核密度估计

常用核函数关于有限数据点x1…xn的函数Examples:Epanechnikov核函数单位均匀核函数Normal核函数数据点现在是24页\一共有92页\编辑于星期二核密度估计梯度不估计PDF!仅仅估计梯度利用公式:得:窗口大小现在是25页\一共有92页\编辑于星期二核密度估计梯度计算MeanShift现在是26页\一共有92页\编辑于星期二计算MeanShift另一个核密度估计!简化的MeanShift计算过程:计算meanshift向量利用m(x)更新核窗口现在是27页\一共有92页\编辑于星期二MeanShift模式检测MeanShift更新过程:FindallmodesusingtheSimpleMeanShiftProcedurePrunemodesbyperturbingthem(findsaddlepointsandplateaus)Prunenearby–takehighestmodeinthewindowWhathappensifwereachasaddlepoint?Perturbthemodepositionandcheckifwereturnback现在是28页\一共有92页\编辑于星期二自适应梯度上升MeanShift算法特点自动收敛速度–meanshift向量大小仅仅取决于向量本身

中心附近的最大值，该步骤小而精在无穷步的迭代后算法才能保证收敛无限收敛,

(因此要设定一个下限)对于单位均匀核函数(),在有限次迭代后算法收敛Normal核函数()呈现出平滑的迭代轨迹，但是迭代速度要慢于Uniform核函数().现在是29页\一共有92页\编辑于星期二真正的形态分析利用窗口来细分空间分别进行Meanshift迭代现在是30页\一共有92页\编辑于星期二真正的形态分析Thebluedatapointsweretraversedbythewindowstowardsthemode现在是31页\一共有92页\编辑于星期二真正的形态分析

Anexample窗口轨迹代表最陡的上升方向现在是32页\一共有92页\编辑于星期二自适应MeanShift现在是33页\一共有92页\编辑于星期二MeanShift算法的优势&缺点优势:应用独立的工具适用于实时数据分析不需要在数据集群中事先假设轮廓（例如椭圆形）能够处理任意特征空间只需要选择一个参数和K-Means算法不同的是，h(窗口大小)具有物理意义缺点:窗口尺寸(由带宽决定)是微不足道的不适当的窗口大小导致漠视被合并,

或者产生额外的“阴影”模式

使用自适应窗口大小现在是34页\一共有92页\编辑于星期二MeanShift应用现在是35页\一共有92页\编辑于星期二聚类吸引区域:在这个区域里，所有的轨迹导致相同的模式聚类:在吸引区域中的所有数据点都有相同的模式MeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer现在是36页\一共有92页\编辑于星期二聚类合成案例简单模态结构复杂模态结构现在是37页\一共有92页\编辑于星期二聚类真实案例初始化窗口中心寻找模态修剪后的模态最终聚类结果特征空间:用L*u*v来表示现在是38页\一共有92页\编辑于星期二聚类真实案例L*u*v3维空间现在是39页\一共有92页\编辑于星期二聚类真实案例吸引区域中不是所有的轨迹都会达到相同的模态2维空间(L*u)聚类结果现在是40页\一共有92页\编辑于星期二间断保持平滑特征空间:联合域=空间坐标+颜色空间意义:把图像看做在空间域和灰度域上的数据点图像数据MeanShift向量平滑结果MeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer现在是41页\一共有92页\编辑于星期二间断保持平滑xyz图像灰度级……可以看做是在空间x,y,z的数据点(结合空间坐标和颜色信息)现在是42页\一共有92页\编辑于星期二间断保持平滑yzFlatregionsinducethemodes!现在是43页\一共有92页\编辑于星期二间断保持平滑在空间和空间范围中窗口大小的作用现在是44页\一共有92页\编辑于星期二间断保持平滑

Example现在是45页\一共有92页\编辑于星期二间断保持平滑

Example现在是46页\一共有92页\编辑于星期二边缘存在于目标与背景、目标与目标、区域与区域之间，是图像最基本的特征之一为人们描述或识别目标以及解释图像提供了一个重要的特征参数。它蕴含了图像丰富的内在信息（如方向、阶越性质与形状等）；纹理特征的重要信息源和形状特征的基础；图像分割、图像分类、图像配准和模式识别所依赖的重要特征。如果能成功地检测出图像的边缘，图像分析、图像识别就会方便得多，精确度也会得到提高。边缘检测现在是47页\一共有92页\编辑于星期二边缘检测

射线传播VesselDetectionbyMeanShiftBasedRayPropagation,byTek,Comaniciu,Williams在医学图像中准确区分各种物体现在是48页\一共有92页\编辑于星期二边缘检测

射线传播使用位移数据来指导射线传播间断平滑位移矢量VesselDetectionbyMeanShiftBasedRayPropagation,byTek,Comaniciu,Williams现在是49页\一共有92页\编辑于星期二边缘检测

射线传播速度公式与轮廓正交曲率现在是50页\一共有92页\编辑于星期二边缘检测原始图像沿红线处的灰度等级平滑处理后的灰度图位移矢量位移矢量求导现在是51页\一共有92页\编辑于星期二边缘检测

Example现在是52页\一共有92页\编辑于星期二边缘检测

Example利用曲率进行平滑的重要性现在是53页\一共有92页\编辑于星期二图像分割的概念在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣，这些部分一般称为目标或前景。为了辨识和分析目标，需要将有关区域分离提取出来，在此基础上对目标进一步利用，如进行特征提取和测量。图像分割就是指把图像分成各具特性的区域，并提取出感兴趣目标的技术和过程。图像分割现在是54页\一共有92页\编辑于星期二图像分割片段=集群,或者集群的集群算法:进行滤波(间断保持平滑)聚集比窗口大小更接近的集群图像数据(片段)MeanShift向量分割结果平滑处理MeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer/~comanici现在是55页\一共有92页\编辑于星期二图像分割

Example…当特征空间只有图像灰度的时候…现在是56页\一共有92页\编辑于星期二图像分割

Example现在是57页\一共有92页\编辑于星期二图像分割

Example现在是58页\一共有92页\编辑于星期二图像分割

Example现在是59页\一共有92页\编辑于星期二图像分割

Example现在是60页\一共有92页\编辑于星期二图像分割

Example现在是61页\一共有92页\编辑于星期二图像分割

Example现在是62页\一共有92页\编辑于星期二所谓目标跟踪，可以简单地定义为对连续的视频序列中的目标维持一条航迹，进而获得目标的位置、速度等运动参数，以及形状、大小、颜色等对后续目标分析与理解非常重要的测量信息。目标跟踪现在是63页\一共有92页\编辑于星期二非刚性目标跟踪……现在是64页\一共有92页\编辑于星期二非刚性目标跟踪实时监控辅助驾驶基于对象的视频压缩现在是65页\一共有92页\编辑于星期二当前帧……Mean-Shift目标跟踪

总体框架:目标表示选择特征空间利用选择的特征空间表示目标模板在当前帧中选择目标模板现在是66页\一共有92页\编辑于星期二Mean-Shift目标跟踪

总体框架:目标定位在下一帧的模板位置附近搜索从当前帧中选定的模板位置开始通过最大化相似性函数来匹配模板在下一帧中重复相同的过程当前帧……目标模板候选模板现在是67页\一共有92页\编辑于星期二Mean-Shift目标跟踪

目标表示选择目标模板量化的色彩特征空间选择特征空间通过模板在特征空间的PDF来表示模板KernelBasedObjectTracking,byComaniniu,Ramesh,Meer现在是68页\一共有92页\编辑于星期二Mean-Shift目标跟踪

PDF表示相似性函数:目标模板(以0点为中心)候选模板(以y点为中心)现在是69页\一共有92页\编辑于星期二Mean-Shift目标跟踪

平滑相似性函数相似性函数:问题:目标仅依靠颜色信息来表示空间信息丢失解决方案:在空间域中使用各向同性核函数掩盖目标f(y)在y点变得平滑f不平滑基于梯度的优化是不稳健的相邻点相似度变化很大现在是70页\一共有92页\编辑于星期二Mean-Shift目标跟踪

寻找目标模板的PDF目标像素位置一个可微，各向同性的，凸函数且单调递减的核函数周边像素收到遮挡和背景干扰像素x在索引(1..m)中的对应值归一化因子像素权重目标模板中特征u的概率候选模板中特征u的概率归一化因子像素权重0目标模板y候选模板现在是71页\一共有92页\编辑于星期二Mean-Shift目标跟踪

相似性函数目标模板:候选模板:相似性函数:11巴氏系数现在是72页\一共有92页\编辑于星期二Mean-Shift目标跟踪

目标定位算法从当前帧中选定的模板位置开始在下一帧的模板位置附近搜索通过最大化相似性函数来匹配模板现在是73页\一共有92页\编辑于星期二线性近似(以y0为中心)Mean-Shift目标跟踪

逼近相似性函数模板中心:候选位置:与y无关密度估计！(关于y的函数)现在是74页\一共有92页\编辑于星期二Mean-Shift目标跟踪

最大化相似性函数求解=寻找最大值重要假设:目标在搜索区域附近目标有足够的区分度现在是75页\一共有92页\编辑于星期二Mean-Shift目标跟踪

应用Mean-Shift原始Mean-Shift:求解利用求解=寻找最大值扩展Mean-Shift:求解利用现在是76页\一共有92页\编辑于星期二Mean-Shift目标跟踪

关于核函数和轮廓函数一类特殊的径向对称内核：核函数K的轮廓函数扩展Mean-Shift:求解利用现在是77页\一共有92页\编辑于星期二Mean-Shift目标跟踪

核函数选取Epanechnikov核函数:一类特殊的径向对称内核：扩展Mean-Shift:单位均匀核函数:现在是78页\一共有92页\编辑于星期二Mean-Shift目标跟踪

自适应窗口大小问题:目标大小随时间变化必须调整核函数窗宽(h)

解决方案:利用不同的h进行3次定位选择使相似度最大化的窗宽(h)

现在是79页\一共有92页\编辑于星期二Mean-Shift目标跟踪

结果特征空间:161616量化RGB颜色值目标:在第一帧中手动选择平均mean-shift迭代次数:4现在是80页\一共有92页\编辑于星期二Mean-Shift目标跟踪

结果部分遮挡干扰运动模糊现在是81页\一共有92页\编辑于星期二Mean-Shift目标跟踪

结果现在是82页\一共有92页\编辑于星期二Mean-Shift目标跟踪

结果特征空间:128128量化RG颜色值现在是83页\一共有92页\编辑于星期二Mean-Shift目标跟踪

尺度选择问题窗口选择过大窗口选择过小定位效果差核窗口宽度h不能选择过大或者过小问题:在颜色均匀区域,相似度不随h的大小改变小的窗口宽度h可能达到更好的相似性无法保证h不会变得太小!现在是84页\一共有92页\编辑于星期二尺度空间跟踪

Motivation对数个尺度进行定位先前的方法在空间和尺度上同时定位当前方法Mean-shiftBlobTrackingthroughScaleSpace,byR.Collins现在是85页\一共有92页\编辑于星期二Lindeberg’s理论

选择最佳尺度来描述图