12-图像分割-分水岭+MS

K-Means、WatershedMeanShift分割FeatureSpaceSource:K.GraumanFeatureSpaceSource:K.GraumanImageClustersonintensityClustersoncolorK-meansclusteringusingintensityaloneandcoloraloneSegmentationasclustering•Clusteringbasedon(r,g,b,x,y)valuesenforcesmorespatialcoherenceK-MeansprosandconsProsSimpleandfastEasytoimplementConsNeedtochooseKSensitivetooutliersUsageRarelyusedforpixelsegmentationWatershedalgorithmWatershedalgorithm分水岭算法分割原理分水岭算法标记约束分水岭算法等级分割(1)任何的灰度级图像都可以被看做是一个地形图分割原理(2)假设我们在每个区域最小值位置地方打个洞,让水以均匀的速度上升,从低到高淹没整个地形.当处在不同的汇聚盆地中的水将要聚合在一起时,修建大坝将阻止聚合,最后得到的水坝边界就是分水岭的分割线.12WatershedSegmentationAlgorithm13WatershedSegmentationAlgorithmTheobjectiveistofindwatershedlines.Theideaissimple:Supposethataholeispunchedineachregionalminimumandthattheentiretopographyisfloodedfrombelowbylettingwaterrisethroughtheholesatauniformrate.Whenrisingwaterindistinctcatchmentbasinsisaboutthemerge,adamisbuilttopreventmerging.Thesedamboundariescorrespondtothewatershedlines.定义变量iiCMM()表示与局部最小值相联系的汇水盆地内点的集合分水岭算法ni表示第阶段汇水盆地中点的集合n表示第阶段汇水盆地被水淹没部分的集合所有汇水盆地的集合定义变量(续)分水岭算法g(x,y)=n表示位于平面下方的点的集合ni表示第阶段汇水盆地中点的集合n表示第阶段汇水盆地被水淹没部分的集合所有汇水盆地的集合g(x,y)=n表示位于平面下方的点的集合a),qC[n1]C[n];2q,(),qC[n1]C[n];3cqb（1）遇到新的最小值时,符合条件(将并入构成（）位于某些局部最小值构成的汇水盆地时符合条件将并入构成（）当遇到分离全部或部分汇水盆地时,符合条件(),在建水坝.iiCMM()表示与局部最小值相联系的汇水盆地内点的集合初始化:C[min1]T[min1]C[1]C[n]n根据求得递归:定义变量初始化:递归:C[min1]T[min1]C[1]C[n]n根据求得a),qC[n1]C[n];q,(),qC[n1]C[n];cqb遇到新的最小值时,符合条件(将并入构成位于某些局部最小值构成的汇水盆地时符合条件将并入构成当遇到分离全部或部分汇水盆地时,符合条件(),在建水坝.递归(续)终止:n=max+1分水岭分割方法应用在图像的梯度,那么集水处在理论上就对应灰度变化最小的区域,而分水岭就对应灰度变化相对最大的区域.从上到下,从右到左•原始图•梯度图•梯度图的分水岭•最终轮廓缺点:由于噪声或者局部不规则而引起”过度分割”电泳凝胶图像与经过分水岭转变的分割图分水岭算法的改进对图片进行预处理分割时添加约束分割后对图像进行再处理标记约束分水岭算法改进的分水岭算法,从先前已经定好的区域开始浸水BahadirK.GunturkEE7730-ImageAnalysisI24Asolutionistolimitthenumberofregionalminima.Usemarkerstospecifytheonlyallowedregionalminima.(Forexample,gray-levelvaluesmightbeusedasamarker.)WatershedSegmentationAlgorithm防止“过度分割”电泳凝胶图像与经过标记约束分水岭转变的分割图标记约束分水岭算法应用钢的断裂面的提取银色木纹的提取等级分割(1)通过分分水岭算法,得到一张初始的分割图片(对比如下)(2)以这些相对高度为基础,再次用分水岭算法,可达下一级的分割图如下BahadirK.GunturkEE7730-ImageAnalysisI30Watershedalgorithmmightbeusedonthegradientimageinsteadoftheoriginalimage.WatershedSegmentationAlgorithmBahadirK.GunturkEE7730-ImageAnalysisI31Duetonoiseandotherlocalirregularitiesofthegradient,oversegmentationmightoccur.WatershedSegmentationAlgorithmImageGradientWatershedboundariesWatershedSegmentationAlgorithmSimpletrickUseGaussianormedianfiltertoreducenumberofregions应用应用应用Meyer’swatershedsegmentation1.Chooselocalminimaasregionseeds2.Addneighborstopriorityqueue,sortedbyvalue3.Taketopprioritypixelfromqueue1.Ifalllabeledneighborshavesamelabel,assigntopixel2.Addallnon-markedneighbors4.Repeatstep3untilfinishedMeyer1991Matlab:seg=watershed(bnd_im)WatershedprosandconsProsFast(1secfor512x512image)AmongbestmethodsforhierarchicalsegmentationConsNoteasytogetvarietyofregionsformultiplesegmentationsNotop-downinformationUsagePreferredalgorithmforhierarchicalsegmentationMeanshiftsegmentationVersatiletechniqueforclustering-basedsegmentationD.ComaniciuandP.Meer,MeanShift:ARobustApproachtowardFeatureSpaceAnalysis,PAMI2002.MeanshiftalgorithmTrytofindmodesofthisnon-parametricdensityMean-Shift分割MeanShiftTheoryWhatisMeanShift?DensityEstimationMethodsNonparametricKernelDensityEstimationDerivingtheMeanShiftMeanshiftpropertiesApplicationsClusteringDiscontinuityPreservingSmoothingSegmentationObjectContourDetectionObjectTrackingoutlineMeanShiftTheoryWhatisMeanShift?DensityEstimationMethodsNonparametricKernelDensityEstimationDerivingtheMeanShiftMeanshiftpropertiesApplicationsClusteringDiscontinuityPreservingSmoothingSegmentationObjectContourDetectionObjectTrackingIntuitiveDescriptionRegionofinterestCenterofmassMeanShiftvector目标：寻找最稠密的区域IntuitiveDescriptionRegionofinterestCenterofmassMeanShiftvector目标：寻找最稠密的区域IntuitiveDescriptionRegionofinterestCenterofmassMeanShiftvector目标：寻找最稠密的区域IntuitiveDescriptionRegionofinterestCenterofmassMeanShiftvector目标：寻找最稠密的区域IntuitiveDescriptionRegionofinterestCenterofmassMeanShiftvector目标：寻找最稠密的区域IntuitiveDescriptionRegionofinterestCenterofmassMeanShiftvector目标：寻找最稠密的区域IntuitiveDescriptionRegionofinterestCenterofmass目标：寻找最稠密的区域outlineMeanShiftTheoryWhatisMeanShift?DensityEstimationMethodsNonparametricKernelDensityEstimationDerivingtheMeanShiftMeanshiftpropertiesApplicationsClusteringDiscontinuityPreservingSmoothingSegmentationObjectContourDetectionObjectTrackingWhatisMeanShift?非参数密度估计Non-parametricDensityEstimation非参数密度梯度估计Non-parametricDensityGRADIENTEstimation(MeanShift)DataDiscretePDFRepresentationPDFAnalysis特征空间的概率密度函数•颜色空间（colorspapce）•尺度空间（Scalespace）•事实上我们可以设想的任意特征空间•…Atoolfor:在样本集合中寻找模型，确定N维空间RN里面一个潜在的概率密度函数(PDF-probabilitydensityfunction)outlineMeanShiftTheoryWhatisMeanShift?DensityEstimationMethodsNonparametricKernelDensityEstimationDerivingtheMeanShiftMeanshiftpropertiesApplicationsClusteringDiscontinuityPreservingSmoothingSegmentationObjectContourDetectionObjectTrackingNon-ParametricDensityEstimation假设:数据点是从一