非常有利于meanshift算法的理解

非常有利于meanshift算法的理解第1页/共86页Agenda

MeanShiftTheoryWhatisMeanShift?DensityEstimationMethodsDerivingtheMeanShiftMeanshiftproperties

ApplicationsClusteringDiscontinuityPreservingSmoothingObjectContourDetectionSegmentationObjectTracking第2页/共86页MeanShiftTheory第3页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:Findthedensestregion第4页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:Findthedensestregion第5页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:Findthedensestregion第6页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:Findthedensestregion第7页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:Findthedensestregion第8页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassMeanShiftvectorObjective:Findthedensestregion第9页/共86页IntuitiveDescriptionDistributionofidenticalbilliardballsRegionofinterestCenterofmassObjective:Findthedensestregion第10页/共86页WhatisMeanShift?Non-parametricDensityEstimationNon-parametricDensityGRADIENTEstimation(MeanShift)DataDiscretePDFRepresentationPDFAnalysisPDFinfeaturespaceColorspaceScalespaceActuallyanyfeaturespaceyoucanconceive…Atoolfor:Findingmodesinasetofdatasamples,manifestinganunderlyingprobabilitydensityfunction(PDF)inRN第11页/共86页Non-ParametricDensityEstimationAssumption:ThedatapointsaresampledfromanunderlyingPDFAssumedUnderlyingPDFRealDataSamplesDatapointdensityimpliesPDFvalue!第12页/共86页AssumedUnderlyingPDFRealDataSamplesNon-ParametricDensityEstimation第13页/共86页AssumedUnderlyingPDFRealDataSamples?Non-ParametricDensityEstimation第14页/共86页ParametricDensityEstimationAssumption:ThedatapointsaresampledfromanunderlyingPDFAssumedUnderlyingPDFEstimateRealDataSamples第15页/共86页KernelDensityEstimation

ParzenWindows-GeneralFrameworkKernelProperties:NormalizedSymmetricExponentialweight

decay???Afunctionofsomefinitenumberofdatapointsx1…xnData第16页/共86页KernelDensityEstimation

ParzenWindows-FunctionFormsAfunctionofsomefinitenumberofdatapointsx1…xnDataInpracticeoneusestheforms:orSamefunctiononeachdimensionFunctionofvectorlengthonly第17页/共86页KernelDensityEstimation

VariousKernelsAfunctionofsomefinitenumberofdatapointsx1…xnExamples:EpanechnikovKernelUniformKernelNormalKernelData第18页/共86页KernelDensityEstimationGradientGiveupestimatingthePDF!EstimateONLY

thegradientUsingtheKernelform:Weget:Sizeofwindow第19页/共86页KernelDensityEstimationGradientComputingTheMeanShift第20页/共86页ComputingTheMeanShiftYetanotherKerneldensityestimation!SimpleMeanShiftprocedure:ComputemeanshiftvectorTranslatetheKernelwindowbym(x)第21页/共86页MeanShiftModeDetectionUpdatedMeanShiftProcedure:FindallmodesusingtheSimpleMeanShiftProcedurePrunemodesbyperturbingthem(findsaddlepointsandplateaus)Prunenearby–takehighestmodeinthewindowWhathappensifwereachasaddlepoint?Perturbthemodepositionandcheckifwereturnback第22页/共86页AdaptiveGradientAscentMeanShiftPropertiesAutomaticconvergencespeed–themeanshift

vectorsizedependsonthegradientitself.

Nearmaxima,thestepsaresmallandrefinedConvergenceisguaranteedforinfinitesimal

stepsonlyinfinitelyconvergent,

(thereforesetalowerbound)ForUniformKernel(),convergenceisachievedin

afinitenumberofstepsNormalKernel()exhibitsasmoothtrajectory,but

isslowerthanUniformKernel().第23页/共86页RealModalityAnalysisTessellatethespacewithwindowsRuntheprocedureinparallel第24页/共86页RealModalityAnalysisThebluedatapointsweretraversedbythewindowstowardsthemode第25页/共86页RealModalityAnalysis

AnexampleWindowtrackssignifythesteepestascentdirections第26页/共86页AdaptiveMeanShift第27页/共86页MeanShiftStrengths&WeaknessesStrengths:ApplicationindependenttoolSuitableforrealdataanalysisDoesnotassumeanypriorshape

(e.g.elliptical)ondataclustersCanhandlearbitraryfeature

spacesOnlyONEparametertochoose

h(windowsize)hasaphysical

meaning,unlikeK-MeansWeaknesses:Thewindowsize(bandwidth

selection)isnottrivialInappropriatewindowsizecan

causemodestobemerged,

orgenerateadditional“shallow”

modesUseadaptivewindow

size第28页/共86页MeanShiftApplications第29页/共86页ClusteringAttractionbasin:theregionforwhichalltrajectoriesleadtothesamemodeCluster:AlldatapointsintheattractionbasinofamodeMeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer第30页/共86页Clustering

SyntheticExamplesSimpleModalStructuresComplexModalStructures第31页/共86页Clustering

RealExampleInitialwindowcentersModesfoundModesafterpruningFinalclustersFeaturespace:L*u*vrepresentation第32页/共86页Clustering

RealExampleL*u*vspacerepresentation第33页/共86页Clustering

RealExampleNotalltrajectoriesintheattractionbasinreachthesamemode2D(L*u)spacerepresentationFinalclusters第34页/共86页DiscontinuityPreservingSmoothingFeaturespace:Jointdomain=spatialcoordinates+colorspaceMeaning:treattheimageasdatapointsinthespatialandgrayleveldomainImageData(slice)MeanShiftvectorsSmoothingresultMeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer第35页/共86页DiscontinuityPreservingSmoothingxyzTheimagegraylevels……canbeviewedasdatapointsinthex,y,zspace(joinedspatialAndcolorspace)第36页/共86页DiscontinuityPreservingSmoothingyzFlatregionsinducethemodes!第37页/共86页DiscontinuityPreservingSmoothingTheeffectofwindowsizeinspatialandrangespaces第38页/共86页DiscontinuityPreservingSmoothing

Example第39页/共86页DiscontinuityPreservingSmoothing

Example第40页/共86页ObjectContourDetection

RayPropagationVesselDetectionbyMeanShiftBasedRayPropagation,byTek,Comaniciu,WilliamsAccuratelysegmentvariousobjects(roundedinnature)inmedicalimages第41页/共86页ObjectContourDetection

RayPropagationUsedisplacementdatatoguideraypropagationDiscontinuitypreservingsmoothingDisplacementvectorsVesselDetectionbyMeanShiftBasedRayPropagation,byTek,Comaniciu,Williams第42页/共86页ObjectContourDetection

RayPropagationSpeedfunctionNormaltothecontourCurvature第43页/共86页ObjectContourDetectionOriginalimageGraylevelsalongredlineGraylevelsaftersmoothingDisplacementvectorsDisplacementvectors’derivative第44页/共86页ObjectContourDetection

Example第45页/共86页ObjectContourDetection

ExampleImportanceofsmoothingbycurvature第46页/共86页SegmentationSegment=Cluster,orClusterofClustersAlgorithm:RunFiltering(discontinuitypreservingsmoothing)ClustertheclusterswhicharecloserthanwindowsizeImageData(slice)MeanShiftvectorsSegmentationresultSmoothingresultMeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer/~comanici第47页/共86页Segmentation

Example…whenfeaturespaceisonlygraylevels…第48页/共86页Segmentation

Example第49页/共86页Segmentation

Example第50页/共86页Segmentation

Example第51页/共86页Segmentation

Example第52页/共86页Segmentation

Example第53页/共86页Segmentation

Example第54页/共86页Non-RigidObjectTracking……第55页/共86页Non-RigidObjectTrackingReal-TimeSurveillanceDriverAssistanceObject-BasedVideoCompression第56页/共86页Currentframe……Mean-ShiftObjectTracking

GeneralFramework:TargetRepresentationChooseafeaturespaceRepresentthemodelinthechosenfeaturespaceChooseareferencemodelinthecurrentframe第57页/共86页Mean-ShiftObjectTracking

GeneralFramework:TargetLocalizationSearchinthemodel’sneighborhoodinnextframeStartfromthepositionofthemodelinthecurrentframeFindbestcandidatebymaximizingasimilarityfunc.RepeatthesameprocessinthenextpairofframesCurrentframe……ModelCandidate第58页/共86页Mean-ShiftObjectTracking

TargetRepresentationChooseareferencetargetmodelQuantizedColorSpaceChooseafeaturespaceRepresentthemodelbyitsPDFinthefeaturespaceKernelBasedObjectTracking,byComaniniu,Ramesh,Meer第59页/共86页Mean-ShiftObjectTracking

PDFRepresentationSimilarity

Function:TargetModel(centeredat0)TargetCandidate(centeredaty)第60页/共86页Mean-ShiftObjectTracking

Smoothnessof

SimilarityFunctionSimilarityFunction:Problem:TargetisrepresentedbycolorinfoonlySpatialinfoislostSolution:Maskthetargetwithanisotropickernelinthespatialdomainf(y)becomessmoothinyfisnotsmoothGradient-basedoptimizationsarenotrobustLargesimilarityvariationsforadjacentlocations第61页/共86页Mean-ShiftObjectTracking

FindingthePDFofthetargetmodelTargetpixellocationsAdifferentiable,isotropic,convex,monotonicallydecreasingkernelPeripheralpixelsareaffectedbyocclusionandbackgroundinterferenceThecolorbinindex(1..m)ofpixelxNormalizationfactorPixelweightProbabilityoffeatureuinmodelProbabilityoffeatureuincandidateNormalizationfactorPixelweight0modelycandidate第62页/共86页Mean-ShiftObjectTracking

SimilarityFunctionTargetmodel:Targetcandidate:Similarityfunction:11TheBhattacharyyaCoefficient第63页/共86页Mean-ShiftObjectTracking

TargetLocalizationAlgorithmStartfromthepositionofthemodelinthecurrentframeSearchinthemodel’sneighborhoodinnextframeFindbestcandidatebymaximizingasimilarityfunc.第64页/共86页Linearapprox.(aroundy0)Mean-ShiftObjectTracking

ApproximatingtheSimilarityFunctionModellocation:Candidatelocation:IndependentofyDensityestimate!

(asafunctionofy)第65页/共86页Mean-ShiftObjectTracking

MaximizingtheSimilarityFunctionThemodeof=soughtmaximumImportantAssumption:OnemodeinthesearchedneighborhoodThetargetrepresentationprovidessufficientdiscrimination第66页/共86页Mean-ShiftObjectTracking

ApplyingMean-ShiftOriginalMean-Shift:FindmodeofusingThemodeof=soughtmaximumExtendedMean-Shift:Findmodeofusing第67页/共86页Mean-ShiftObjectTracking

AboutKernelsandProfilesAspecialclassofradiallysymmetrickernels:TheprofileofkernelKExtendedMean-Shift:Findmodeofusing第68页/共86页Mean-ShiftObjectTracking

ChoosingtheKernelEpanechnikovkernel:Aspecialclassofradiallysymmetrickernels:ExtendedMean-Shift:Uniformkernel:第69页/共86页Mean-ShiftObjectTracking

AdaptiveScaleProblem:ThescaleofthetargetchangesintimeThescale(h)ofthekernelmustbeadaptedSolution:Runlocalization3timeswithdifferenthChoosehthatachievesmaximumsimilarity第70页/共86页Mean-ShiftObjectTracking

ResultsFeaturespace:161616quantizedRGBTarget:manuallyselectedon1stframeAveragemean-shiftiterations:4第71页/共86页Mean-ShiftObjectTracking

ResultsPartialocclusionDistractionMotionblur第72页/共86页Mean-ShiftObjectTracking

Results第73页/共86页Mean-ShiftObjectTracking

ResultsFeaturespace:128128quantizedRG第74页/共86页Mean-ShiftObjectTracking

TheScaleSelectionProblemKerneltoobigKerneltoosmallPoorlocalizationhmustn’tgettoobigortoosmall!Problem:Inuniformlycoloredregions,similarityisinvarianttohSmallerhmayachievebettersimilarityNothingkeepshfromshrinkingtoosmall!第75页/共86页TrackingThroughScaleSpace

MotivationSpatiallocalizationforseveralscalesPreviousmethodSimultaneouslocalizationinspaceandscaleThismethodMean-shiftBlobTrackingthroughScaleSpace,byR.Collins第76页/共86页Lindeberg’sTheory

SelectingthebestscalefordescribingimagefeaturesScale-spacerepresentationDifferentialoperatorapplied50strongestresponsesxyσ第77页/共86页Scale-spacerepresentationLindeberg’sTheory

TheLaplacianoperatorforselectingblob-likefeaturesLaplacianofGaussian(LOG)Bestfeaturesareat(x,σ)thatmaximizeL2DLOGfilterwithscaleσxyσ3Dscale-spacerepresentation第78页/共86页Lindeberg’sTheory

Multi-ScaleFeatureSelectionProcessOriginalImage3D