meanshift算法详解

MeanShiftTheoryandApplicationsYaronUkrainitz&BernardSarelAgenda•MeanShiftTheory•WhatisMeanShift?•DensityEstimationMethods•DerivingtheMeanShift•Meanshiftproperties•Applications•Clustering•DiscontinuityPreservingSmoothing•ObjectContourDetection•Segmentation•ObjectTrackingMeanShiftTheoryIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:FindthedensestregionIntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassObjective:FindthedensestregionWhatisMeanShift?Non-parametricDensityEstimationNon-parametricDensityGRADIENTEstimation(MeanShift)DataDiscretePDFRepresentationPDFAnalysisPDFinfeaturespace•Colorspace•Scalespace•Actuallyanyfeaturespaceyoucanconceive•…Atoolfor:Findingmodesinasetofdatasamples,manifestinganunderlyingprobabilitydensityfunction(PDF)inRNNon-ParametricDensityEstimationAssumption:ThedatapointsaresampledfromanunderlyingPDFAssumedUnderlyingPDFRealDataSamplesDatapointdensityimpliesPDFvalue!AssumedUnderlyingPDFRealDataSamplesNon-ParametricDensityEstimationAssumedUnderlyingPDFRealDataSamples?Non-ParametricDensityEstimationParametricDensityEstimationAssumption:ThedatapointsaresampledfromanunderlyingPDFAssumedUnderlyingPDF22()2iPDF()=iiicex-μxEstimateRealDataSamplesKernelDensityEstimationParzenWindows-FunctionForms11()()niiPKnxx-xAfunctionofsomefinitenumberofdatapointsx1…xnDataInpracticeoneusestheforms:1()()diiKckxxor()KckxxSamefunctiononeachdimensionFunctionofvectorlengthonlyKernelDensityEstimationVariousKernels11()()niiPKnxx-xAfunctionofsomefinitenumberofdatapointsx1…xnExamples:•EpanechnikovKernel•UniformKernel•NormalKernel211()0otherwiseEcKxxx1()0otherwiseUcKxx21()exp2NKcxxDataKernelDensityEstimationGradient11()()niiPKnxx-xGiveupestimatingthePDF!EstimateONLYthegradient2()iiKckhx-xx-xUsingtheKernelform:Weget:1111()niinniiiniiiigccPkgnngxxxSizeofwindowg()()kxxKernelDensityEstimationGradient1111()niinniiiniiiigccPkgnngxxxComputingTheMeanShiftg()()kxx1111()niinniiiniiiigccPkgnngxxxComputingTheMeanShiftYetanotherKerneldensityestimation!SimpleMeanShiftprocedure:•Computemeanshiftvector•TranslatetheKernelwindowbym(x)2121()niiiniighghx-xxmxxx-xg()()kxxMeanShiftModeDetectionUpdatedMeanShiftProcedure:•FindallmodesusingtheSimpleMeanShiftProcedure•Prunemodesbyperturbingthem(findsaddlepointsandplateaus)•Prunenearby–takehighestmodeinthewindowWhathappensifwereachasaddlepoint?PerturbthemodepositionandcheckifwereturnbackAdaptiveGradientAscentMeanShiftProperties•Automaticconvergencespeed–themeanshiftvectorsizedependsonthegradientitself.•Nearmaxima,thestepsaresmallandrefined•Convergenceisguaranteedforinfinitesimalstepsonlyinfinitelyconvergent,(thereforesetalowerbound)•ForUniformKernel(),convergenceisachievedinafinitenumberofsteps•NormalKernel()exhibitsasmoothtrajectory,butisslowerthanUniformKernel().RealModalityAnalysisTessellatethespacewithwindowsRuntheprocedureinparallelRealModalityAnalysisThebluedatapointsweretraversedbythewindowstowardsthemodeRealModalityAnalysisAnexampleWindowtrackssignifythesteepestascentdirectionsMeanShiftStrengths&WeaknessesStrengths:•Applicationindependenttool•Suitableforrealdataanalysis•Doesnotassumeanypriorshape(e.g.elliptical)ondataclusters•Canhandlearbitraryfeaturespaces•OnlyONEparametertochoose•h(windowsize)hasaphysicalmeaning,unlikeK-MeansWeaknesses:•Thewindowsize(bandwidthselection)isnottrivial•Inappropriatewindowsizecancausemodestobemerged,orgenerateadditional“shallow”modesUseadaptivewindowsizeMeanShiftApplicationsClusteringAttractionbasin:theregionforwhichalltrajectoriesleadtothesamemodeCluster:AlldatapointsintheattractionbasinofamodeMeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,MeerClusteringSyntheticExamplesSimpleModalStructuresComplexModalStructuresClusteringRealExampleInitialwindowcentersModesfoundModesafterpruningFinalclustersFeaturespace:L*u*vrepresentationClusteringRealExampleL*u*vspacerepresentationClusteringRealExampleNotalltrajectoriesintheattractionbasinreachthesamemode2D(L*u)spacerepresentationFinalclustersDiscontinuityPreservingSmoothingFeaturespace:Jointdomain=spatialcoordinates+colorspace()srsrsrKCkkhhxxxMeaning:treattheimageasdat