非常有利于mean-shift算法的理解PPT课件

.,1,MeanShiftTheoryandApplications,YaronUkrainitz&BernardSarel,.,2,Agenda,MeanShiftTheoryWhatisMeanShift?DensityEstimationMethodsDerivingtheMeanShiftMeanshiftpropertiesApplicationsClusteringDiscontinuityPreservingSmoothingObjectContourDetectionSegmentationObjectTracking,.,3,MeanShiftTheory,.,4,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,MeanShiftvector,Objective:Findthedensestregion,.,5,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,MeanShiftvector,Objective:Findthedensestregion,.,6,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,MeanShiftvector,Objective:Findthedensestregion,.,7,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,MeanShiftvector,Objective:Findthedensestregion,.,8,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,MeanShiftvector,Objective:Findthedensestregion,.,9,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,MeanShiftvector,Objective:Findthedensestregion,.,10,IntuitiveDescription,Distributionofidenticalbilliardballs,Regionofinterest,Centerofmass,Objective:Findthedensestregion,.,11,WhatisMeanShift?,Non-parametricDensityEstimation,Non-parametricDensityGRADIENTEstimation(MeanShift),DiscretePDFRepresentation,PDFAnalysis,PDFinfeaturespaceColorspaceScalespaceActuallyanyfeaturespaceyoucanconceive,Atoolfor:Findingmodesinasetofdatasamples,manifestinganunderlyingprobabilitydensityfunction(PDF)inRN,.,12,Non-ParametricDensityEstimation,Assumption:ThedatapointsaresampledfromanunderlyingPDF,AssumedUnderlyingPDF,RealDataSamples,DatapointdensityimpliesPDFvalue!,.,13,AssumedUnderlyingPDF,RealDataSamples,Non-ParametricDensityEstimation,.,14,AssumedUnderlyingPDF,RealDataSamples,?,Non-ParametricDensityEstimation,.,15,ParametricDensityEstimation,Assumption:ThedatapointsaresampledfromanunderlyingPDF,AssumedUnderlyingPDF,Estimate,RealDataSamples,.,16,KernelDensityEstimationParzenWindows-GeneralFramework,KernelProperties:NormalizedSymmetricExponentialweightdecay?,Afunctionofsomefinitenumberofdatapointsx1xn,.,17,KernelDensityEstimationParzenWindows-FunctionForms,Afunctionofsomefinitenumberofdatapointsx1xn,Inpracticeoneusestheforms:,or,Samefunctiononeachdimension,Functionofvectorlengthonly,.,18,KernelDensityEstimationVariousKernels,Afunctionofsomefinitenumberofdatapointsx1xn,Examples:EpanechnikovKernelUniformKernelNormalKernel,.,19,KernelDensityEstimation,Gradient,GiveupestimatingthePDF!EstimateONLYthegradient,UsingtheKernelform:,Weget:,Sizeofwindow,.,20,KernelDensityEstimation,Gradient,ComputingTheMeanShift,.,21,ComputingTheMeanShift,YetanotherKerneldensityestimation!,SimpleMeanShiftprocedure:ComputemeanshiftvectorTranslatetheKernelwindowbym(x),.,22,MeanShiftModeDetection,UpdatedMeanShiftProcedure:FindallmodesusingtheSimpleMeanShiftProcedurePrunemodesbyperturbingthem(findsaddlepointsandplateaus)Prunenearbytakehighestmodeinthewindow,Whathappensifwereachasaddlepoint?,Perturbthemodepositionandcheckifwereturnback,.,23,AdaptiveGradientAscent,MeanShiftProperties,Automaticconvergencespeedthemeanshiftvectorsizedependsonthegradientitself.Nearmaxima,thestepsaresmallandrefinedConvergenceisguaranteedforinfinitesimalstepsonlyinfinitelyconvergent,(thereforesetalowerbound)ForUniformKernel(),convergenceisachievedinafinitenumberofstepsNormalKernel()exhibitsasmoothtrajectory,butisslowerthanUniformKernel().,.,24,RealModalityAnalysis,Tessellatethespacewithwindows,Runtheprocedureinparallel,.,25,RealModalityAnalysis,Thebluedatapointsweretraversedbythewindowstowardsthemode,.,26,RealModalityAnalysisAnexample,Windowtrackssignifythesteepestascentdirections,.,27,AdaptiveMeanShift,.,28,MeanShiftStrengths&Weaknesses,Strengths:ApplicationindependenttoolSuitableforrealdataanalysisDoesnotassumeanypriorshape(e.g.elliptical)ondataclustersCanhandlearbitraryfeaturespacesOnlyONEparametertochooseh(windowsize)hasaphysicalmeaning,unlikeK-Means,Weaknesses:Thewindowsize(bandwidthselection)isnottrivialInappropriatewindowsizecancausemodestobemerged,orgenerateadditional“shallow”modesUseadaptivewindowsize,.,29,MeanShiftApplications,.,30,Clustering,Attractionbasin:theregionforwhichalltrajectoriesleadtothesamemode,Cluster:Alldatapointsintheattractionbasinofamode,MeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer,.,31,ClusteringSyntheticExamples,SimpleModalStructures,ComplexModalStructures,.,32,ClusteringRealExample,Initialwindowcenters,Modesfound,Modesafterpruning,Finalclusters,Featurespace:L*u*vrepresentation,.,33,ClusteringRealExample,L*u*vspacerepresentation,.,34,ClusteringRealExample,Notalltrajectoriesintheattractionbasinreachthesamemode,2D(L*u)spacerepresentation,Finalclusters,.,35,DiscontinuityPreservingSmoothing,Featurespace:Jointdomain=spatialcoordinates+colorspace,Meaning:treattheimageasdatapointsinthespatialandgrayleveldomain,ImageData(slice),MeanShiftvectors,Smoothingresult,MeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer,.,36,DiscontinuityPreservingSmoothing,Theimagegraylevels,canbeviewedasdatapointsinthex,y,zspace(joinedspatialAndcolorspace),.,37,DiscontinuityPreservingSmoothing,Flatregionsinducethemodes!,.,38,DiscontinuityPreservingSmoothing,Theeffectofwindowsizeinspatialandrangespaces,.,39,DiscontinuityPreservingSmoothingExample,.,40,DiscontinuityPreservingSmoothingExample,.,41,ObjectContourDetectionRayPropagation,VesselDetectionbyMeanShiftBasedRayPropagation,byTek,Comaniciu,Williams,Accuratelysegmentvariousobjects(roundedinnature)inmedicalimages,.,42,ObjectContourDetectionRayPropagation,Usedisplacementdatatoguideraypropagation,Discontinuitypreservingsmoothing,Displacementvectors,VesselDetectionbyMeanShiftBasedRayPropagation,byTek,Comaniciu,Williams,.,43,ObjectContourDetectionRayPropagation,Speedfunction,Normaltothecontour,Curvature,.,44,ObjectContourDetection,Originalimage,Graylevelsalongredline,Graylevelsaftersmoothing,Displacementvectors,Displacementvectorsderivative,.,45,ObjectContourDetectionExample,.,46,ObjectContourDetectionExample,Importanceofsmoothingbycurvature,.,47,Segmentation,Segment=Cluster,orClusterofClusters,Algorithm:RunFiltering(discontinuitypreservingsmoothing)Clustertheclusterswhicharecloserthanwindowsize,ImageData(slice),MeanShiftvectors,Segmentationresult,Smoothingresult,MeanShift:ArobustApproachTowardFeatureSpaceAnalysis,byComaniciu,Meer/comanici,.,48,SegmentationExample,whenfeaturespaceisonlygraylevels,.,49,SegmentationExample,.,50,SegmentationExample,.,51,SegmentationExample,.,52,SegmentationExample,.,53,SegmentationExample,.,54,SegmentationExample,.,55,Non-RigidObjectTracking,.,56,Non-RigidObjectTracking,Real-Time,Surveillance,DriverAssistance,Object-BasedVideoCompression,.,57,Mean-ShiftObjectTrackingGeneralFramework:TargetRepresentation,.,58,Mean-ShiftObjectTrackingGeneralFramework:TargetLocalization,Startfromthepositionofthemodelinthecurrentframe,Repeatthesameprocessinthenextpairofframes,.,59,Mean-ShiftObjectTrackingTargetRepresentation,KernelBasedObjectTracking,byComaniniu,Ramesh,Meer,.,60,Mean-ShiftObjectTrackingPDFRepresentation,TargetModel(centeredat0),TargetCandidate(centeredaty),.,61,Mean-ShiftObjectTrackingSmoothnessofSimilarityFunction,SimilarityFunction:,.,62,Mean-ShiftObjectTrackingFindingthePDFofthetargetmodel,Targetpixellocations,Adifferentiable,isotropic,convex,monotonicallydecreasingkernelPeripheralpixelsareaffectedbyocclusionandbackgroundinterference,Thecolorbinindex(1.m)ofpixelx,.,63,Mean-ShiftObjectTrackingSimilarityFunction,Targetmodel:,Targetcandidate:,Similarityfunction:,.,64,Mean-ShiftObjectTrackingTargetLocalizationAlgorithm,Startfromthepositionofthemodelinthecurrentframe,.,65,Linearapprox.(aroundy0),Mean-ShiftObjectTrackingApproximatingtheSimilarityFunction,Modellocation:,Candidatelocation:,Independentofy,Densityestimate!(asafunctionofy),.,66,Mean-ShiftObjectTrackingMaximizingtheSimilarityFunction,Themodeof,=soughtmaximum,.,67,Mean-ShiftObjectTrackingApplyingMean-Shift,OriginalMean-Shift:,Findmodeof,using,Themodeof,=soughtmaximum,.,68,Mean-ShiftObjectTrackingAboutKernelsandProfiles,.,69,Mean-ShiftObjectTrackingChoosingtheKernel,Epanechnikovkernel:,Aspecialclassofradiallysymmetrickernels:,ExtendedMean-Shift:,.,70,Mean-ShiftObjectTrackingAdaptiveScale,Problem:,Thescaleofthetargetchangesintime,Thescale(h)ofthekernelmustbeadapted,.,71,Mean-ShiftObjectTrackingResults,Featurespace:161616quantizedRGBTarget:manuallyselectedon1stframeAveragemean-shiftiterations:4,.,72,Mean-ShiftObjectTrackingResults,.,73,Mean-ShiftObjectTrackingResults,.,74,Mean-ShiftObjectTrackingResults,Featurespace:128128quantizedRG,.,75,Mean-ShiftObjectTrackingTheScaleSelectionProblem,Kerneltoobig,Kerneltoosmall,.,76,TrackingThroughScaleSpaceMotivation,Spatiallocalizationforseveralscales,Previousmethod,Simultaneouslocalizationinspaceandscale,Thismethod,Mean-shiftBlobTrackingthroughScaleSpace,byR.Collins,.,77,LindebergsTheorySelectingthebestscalefordescribingimagefeatures,Sca