DIA第6章10

数字图象分析中国科学技术大学信息科学技术学院电子工程与信息科学系李厚强Email:[e-mail]第六章图像分割(II)Mean-shiftActiveContourModelGraphcut6.1基于MeanShift的分割算法MeanShift算法简介MeanShift分割算法桌面上相同的弹球的分布感兴趣区域堆分布的质心MeanShift向量目标:找到密度最大的区域直观图示直观图示感兴趣区域堆分布的质心桌面上相同的弹球的分布目标:找到密度最大的区域MeanShift向量直观图示感兴趣区域堆分布的质心桌面上相同的弹球的分布目标:找到密度最大的区域MeanShift向量直观图示感兴趣区域堆分布的质心桌面上相同的弹球的分布目标:找到密度最大的区域MeanShift向量直观图示感兴趣区域堆分布的质心桌面上相同的弹球的分布目标:找到密度最大的区域MeanShift向量直观图示感兴趣区域堆分布的质心桌面上相同的弹球的分布目标:找到密度最大的区域MeanShift向量直观图示感兴趣区域堆分布的质心桌面上相同的弹球的分布目标:找到密度最大的区域MeanShift定义:d维空间中的n个样本点,在点的MeanShift向量的基本形式定义:ix1()()ikixsMxxxk∈≡−∑直观图示:MeanShift向量的方向指向概率密度函数高的方向。(i=1,2,,n)x其中：Sk是感兴趣区域；K是感兴趣区域内的样本的数目。更多信息:K.Fukunaga,LarryD.Hostetler.“TheEstimationoftheGradientofaDensityFunction,withApplicationsinPatternRecognition”.1975,IEEETransonInformationTheory.引入两个参数•核函数•权重核函数•定义：D维欧式空间X,,,若函数K(x)存在一个剖面函数:,即并且k(r)满足：（1）非负的；（2）非增的；（3）分段连续的,并且•常用核函数单位均匀核函数单位高斯核函数更多信息:YizongCheng.“MeanShift,ModeSeeking,andClustering”.IEEETransonPAMI.1995xX∈2Txxx=:[0,]kR∞→2()()Kxkx=0()krdr∞∞∫1,1()0,1ifxFxifx=≥2()xFxe−=ExtendedMeanShift1()()ikixsMxxxk∈≡−∑()ixωMeanShift扩展形式：11()()()()()()nHiiiinHiiiGxxxxxmxGxxxωω==−−=−∑∑()Gx其中：：单位核函数：采样点的权值H：正定的d×d的矩阵1122()(())HiiGxxHGHxx−−−=−简化运算21200nhHh=2121()()()()()niiiiniiixxxgxhmxxxxgxhωω==−=−−∑∑MeanShift向量的方向和样本点的概率密度函数的梯度方向是一致的.?ExtendedMeanShift给定d维空间中n个样本点,f(x)的核函数估计(也称parzen窗估计)为ix11()()nHiifxKxxn∧==−∑假设:所有的样本点从同一个函数采集对核函数进行简化和引入权重211()()()()niiindiixxkwxhfxhwx∧==−=∑∑概率密度函数f(x)的梯度估计为()fx∧∇2'1212()()()()()niiiindiixxxxkwxhfxfxhwx∧∧=+=−−∇=∇=∑∑'()()gxkx=−2()()Gxgx=更多信息:YizongCheng.“MeanShift,ModeSeeking,andClustering”.IEEETransonPAMI.199522112211()()2()()nniiiiiiinndiiiiixxxxgwxgwxxhhxhxxhwxgwxh====−−=−−∑∑∑∑梯度核密度估计22112211()()2()()()nniiiiiiinndiiiiixxxxgwxgwxxhhfxxhxxhwxgwxh∧====−−∇=−−∑∑∑∑,,22()()hGhGfxmxh∧=2,,,()()2()hKhGhGfxhmxfx∧∧∇=MeanShift向量的方向和样本点的概率密度函数的梯度方向是一致的.简单的MeanShift迭代算法:1.计算MeanShift矢量2.把当前窗口移动m(x)3.返回1直至满足条件时收敛核密度估计2,,,()()2()hKhGhGfxhmxfx∧∧∇=MeanShift总是指向密度增大最快的方向；当到达密度最大时，MeanShift为0。MeanShift:•本质是一个自适应的梯度上升搜索峰值的方法，能解决多模态分布。•用途:1.寻找模值点：任意初始点，运用meanshift可以找到极值点；2.聚类：对于收敛到同一点的聚为一类即可；3.最优化：最优化目标转化为meanshift隐含估计的概率密度函数。给定一组样本，这些样本服从的分布可以估计出来，假设如图所示。给定一个初始点，那么该点就会一步步的移动直至寻到概率极大值点。峰值检测()srsrsrKCkkhh=⋅⋅xxx2()()Kxkx=特征：空间位置、颜色、纹理、形状等。MeanShift做平滑和分割中用到的特征：1.空间2.颜色特征空间:联合特征=空间位置+颜色物理意义:把图像看做的空间和颜色域的像素点集合特征选择联合特征ImageData(slice)MeanShiftvectorsSmoothingresult平滑yz平滑(,)(8,8)srhh=(,)(8,16)srhh=(,)(16,16)srhh=(,)(16,40)srhh=Originalbaboon(,)(32,16)srhh=(,)(32,40)srhh=()srsrsrKCkkhh=⋅⋅xxx平滑结果(,)(8,40)srhh=在平滑的基础上，分割算法的后续步骤：把这样的一些模态点聚集起来，他们之间的距离小于空间带宽半径，并且颜色差值小于颜色带宽半径除去这样的一些区域，包含的像素数目少于M个分割…当特征空间仅仅是颜色信息时…分割结果分割结果分割结果分割结果图像分割(II)Mean-shiftActiveContourModelGraphcut6.2基于主动轮廓模型的图像分割参数化化主动轮廓：snake几何主动轮廓：水平集方法(levelset)–FromSnaketoLevelSet–ClassicalLevelSetModels28传统的图像分割方法二值化边缘检测血管图像AnAdvancedMethod:ActiveContourModel通过在图像中演化一组动态曲线，检测出图像中感兴趣的物体主动轮廓模型的优势易于对目标进行描述亚像素的精度易于融入各种信息，如形状先验信息、运动信息成熟的数学工具：变分法、偏微分方程(PDE)，微分几何等基于主动轮廓模型的图像分割参数化化主动轮廓：snake几何主动轮廓：水平集方法(levelset)–FromSnaketoLevelSet–ClassicalLevelSetModel参数化主动轮廓(Kassetal,1988)对于一个轮廓曲线定义能量函数:()[(),()]vsxsys=主动轮廓的演化最陡梯度下降算法:内在力:规则化（Regularize）轮廓曲线外力:推动轮廓向感兴趣的物体边界运动欧拉-拉格朗日方程DemoforSnakes曲线微分几何平面曲线可以表达为,其中切向量：法向量弧线长度:从到曲率(curvature)曲率描述了曲线方向改变的速度采用弧长作为参数单位切向量定义了曲线的方向再次求导:切向矢量是一个单位向量注意曲率(curvature)对于一般的参数化形式，曲率可以表示为：和均正交于平行于动态曲线动态曲线随时间变化：曲线运动由曲线演化方程确定:切向量和法向量构成空间的正交基几何曲线演化定理:设与参数表示方式无关.若按照以下方程进行演化则存在的另一个参数化形式，使得为以下方程的解：其中对于同一个点：参数演化的一般方程:常速运动和平均曲率运动常速运动(Areadecreasing/increasing)平均曲率运动(Lengthshorteningflow)演化中间结果•常速运动(Areadecreasingflow)•平均曲率运行(Lengthshorteningflow)参数化主动轮廓的缺陷演化过程中重新参数化:对于3D曲面尤为困难不能处理拓扑变化解决途径•McInerneyandTerzopoulos,1995•RayandActon,2003•Li,Liu,andFox,2005基于参数化主动轮廓框架下的方法:T-Snakes:topologicallyadaptablesnakes更好的选择:•水平集方法(Levelsetmethods)基于主动轮廓模型的图像分割参数化化主动轮廓：snakes几何主动轮廓：水平集方法(levelset)–FromSnaketoLevelSet–ClassicalLevelSetModel曲线的水平集描述零水平集零水平集水平集函数(levelsetfunction)轮廓线零水平集相同的水平集函数符号距离函数(Signeddistancefunction)轮廓C符号距离函数−Ω+Ω符号距离函数定义如下：从曲线演化到水平集演化曲线演化方程：其中F为速度函数,N为曲线C的法向量把动态曲线作为零水平集，嵌入到一个随时间变化的函数中,使得关于时间求微分水平集演化方程:一些特殊的演化方程平均曲率运动常速率运动测地线主动轮廓对流运动演化不稳定重新初始化降质(Degraded)的水平集函数,50步迭代后,时间步长为0.1降质水平集函数的零水平集水平集方法的一般步骤重新初始化初始化演化水平集函数是否收敛?NY停止基于主动轮廓模型的图像分割参数化化主动轮廓：snakes几何主动轮廓：水平集方法(levelset)–FromSnaketoLevelSet–ClassicalLevelSetModelActivecontourswithoutedge53Mumford-ShahFunctional•分片光滑模型---用分片光滑的函数去近似图像DatafittingtermSmoothingtermLengthterm54ActiveContourswithoutEdges(Chan&Vese2001)定义基于区域的能量函数:55Chan-VeseModel的水平集表达式ResultsReference[1]M.Kass,etal,“Snakes:activecontourmodels”,IJCV,1988[2]GuillermoSapiro,“Geometricpartialdifferentialequationsandimageanalysis”,CambridgeUniversityPress,2001[3]StanleyOsher,RonaldFedkiw,“Levelsetmethodsanddynamicimplicitsurfaces”,Springer,2003AMatlabtoolboxforimplementingLevelSetMethods:图像分割(II)Mean-shiftActiveContourModelGraphcutGraphcut图割法Graphcu