meanshift算法详解.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Mean Shift,Theory and Applications,Yaron Ukrainitz&Bernard Sarel,1,Agenda,Mean Shift Theory,What is Mean Shift?,Density Estimation Methods,Deriving the Mean Shift,Mean shift properties,Applications,Clustering,Discontinuity Preserving Smoothing,Object Contour Detection,Segmentation,Object Tracking,2,Mean Shift Theory,3,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Mean Shift,vector,Objective,:Find the densest region,4,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Mean Shift,vector,Objective,:Find the densest region,5,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Mean Shift,vector,Objective,:Find the densest region,6,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Mean Shift,vector,Objective,:Find the densest region,7,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Mean Shift,vector,Objective,:Find the densest region,8,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Mean Shift,vector,Objective,:Find the densest region,9,Intuitive Description,Distribution of identical billiard balls,Region of,interest,Center of,mass,Objective,:Find the densest region,10,What is Mean Shift?,Non-parametric,Density Estimation,Non-parametric,Density,GRADIENT,Estimation,(Mean Shift),Data,Discrete PDF Representation,PDF Analysis,PDF in feature space,Color space,Scale space,Actually any feature space you can conceive,A tool for,:,Finding modes in a set of data samples,manifesting an,underlying probability density function(PDF)in,R,N,11,Non-Parametric Density Estimation,Assumption,:The data points are sampled from an underlying PDF,Assumed Underlying PDF,Real Data Samples,Data point density,implies PDF value!,12,Assumed Underlying PDF,Real Data Samples,Non-Parametric Density Estimation,13,Assumed Underlying PDF,Real Data Samples,?,Non-Parametric Density Estimation,14,Parametric,Density Estimation,Assumption,:The data points are sampled from an underlying PDF,Assumed Underlying PDF,Estimate,Real Data Samples,15,Kernel Density Estimation,Parzen Windows-General Framework,Kernel Properties:,Normalized,Symmetric,Exponential weight decay,?,A function of some finite number of data points,x,1,x,n,Data,16,Kernel Density Estimation,Parzen Windows-Function Forms,A function of some finite number of data points,x,1,x,n,Data,In practice one uses the forms:,or,Same function on each dimension,Function of vector length only,17,Kernel Density Estimation,Various Kernels,A function of some finite number of data points,x,1,x,n,Examples:,Epanechnikov Kernel,Uniform Kernel,Normal Kernel,Data,18,Kernel Density Estimation,Gradient,Give up estimating the PDF!,Estimate,ONLY,the gradient,Using the,Kernel form:,We get:,Size of window,19,Kernel Density Estimation,Gradient,Computing The Mean Shift,20,Computing The Mean Shift,Yet another Kernel,density estimation!,Simple Mean Shift procedure,:,Compute mean shift vector,Translate the Kernel window by,m(x),21,Mean Shift Mode Detection,Updated Mean Shift Procedure:,Find all modes using the Simple Mean Shift Procedure,Prune modes by perturbing them(find saddle points and plateaus),Prune nearby take highest mode in the window,What happens if we,reach a saddle point,?,Perturb the mode position,and check if we return back,22,Adaptive,Gradient,Ascent,Mean Shift Properties,Automatic convergence speed the mean shift vector size depends on the gradient itself.,Near maxima,the steps are small and refined,Convergence is guaranteed for infinitesimal steps only,infinitely convergent,(therefore set a lower bound),For Uniform Kernel(),convergence is achieved in a,finite number of steps,Normal Kernel()exhibits a smooth trajectory,but is slower than Uniform Kernel().,23,Real Modality Analysis,Tessellate the space,with windows,Run the procedure in parallel,24,Real Modality Analysis,The,blue,data points were traversed by the windows towards the mode,25,Real Modality Analysis,An example,Window tracks signify the steepest ascent directions,26,Adaptive Mean Shift,27,Mean Shift Strengths&Weaknesses,Strengths,:,Application independent tool,Suitable for real data analysis,Does not assume any prior shape (e.g.elliptical)on data clusters,Can handle arbitrary feature spaces,Only ONE parameter to choose,h,(window size)has a physical meaning,unlike K-Means,Weaknesses,:,The window size(bandwidth selection)is not trivial,Inappropriate window size can cause modes to be merged,or generate additional“shallow”modes,Use adaptive window size,28,Mean Shift Applications,29,Clustering,Attraction basin,:the region for which all trajectories lead to the same mode,Cluster,:All data points in the,attraction basin,of a mode,Mean Shift:A robust Approach Toward Feature Space Analysis,by Comaniciu,Meer,30,Clustering,Synthetic Examples,Simple Modal Structures,Complex Modal Structures,31,Clustering,Real Example,Initial window,centers,Modes found,Modes after,pruning,Final clusters,Feature space,:,L*u*v representation,32,Clustering,Real Example,L*u*v space representation,33,Clustering,Real Example,Not all trajectories,in the attraction basin,reach the same mode,2D(L*u)space representation,Final clusters,34,Discontinuity Preserving Smoothing,Feature space,:Joint domain=spatial coordinates+color space,Meaning:treat the image as data points in the spatial and gray level domain,Image Data,(slice),Mean Shift,vectors,Smoothing,result,Mean Shift:A robust Approach Toward Feature Space Analysis,by Comaniciu,Meer,35,Discontinuity Preserving Smoothing,x,y,z,The image gray levels,can be viewed as data points,in the,x,y,z,space(joined spatial,And color space),36,Discontinuity Preserving Smoothing,y,z,Flat regions induce the modes!,37,Discontinuity Preserving Smoothing,The effect of,window size,in spatial and,range spaces,38,Discontinuity Preserving Smoothing,Example,39,Discontinuity Preserving Smoothing,Example,40,Object Contour Detection,Ray Propagation,Vessel Detection by Mean Shift Based Ray Propagation,by Tek,Comaniciu,Williams,Accurately segment various objects(rounded in nature)in medical images,41,Object Contour Detection,Ray Propagation,Use displacement data to guide ray propagation,Discontinuity preserving smoothing,Displacement,vectors,Vessel Detection by Mean Shift Based Ray Propagation,by Tek,Comaniciu,Williams,42,Object Contour Detection,Ray Propagation,Speed,function,Normal to,the contour,Curvature,43,Object Contour Detection,Original image,Gray levels along,red line,Gray levels after,smoothing,Displacement vectors,Displacement vectors,derivative,44,Object Contour Detection,Example,45,Object Contour Detection,Example,Importance of smoothing by curvature,46,Segmentation,Segment,=Cluster,or Cluster of Clusters,Algorithm,:,Run Filtering(,discontinuity preserving smoothing,),Cluster the clusters which are closer than window size,Image Data,(slice),Mean Shift,vectors,Segmentation,result,Smoothing,result,Mean Shift:A robust Approach Toward Feature Space Analysis,by Comaniciu,Meer,www.caip.rutgers.edu/comanici,47,Segmentation,Example,when feature space is only,gray levels,48,Segmentation,Example,49,Segmentation,Example,50,Segmentation,Example,51,Segmentation,Example,52,Segmentation,Example,53,Segmentation,Example,54,Non-Rigid Object Tracking,55,Non-Rigid Object Tracking,Real-Time,Surveillance,Driver Assistance,Object-Based Video Compression,56,Current frame,Mean-Shift Object Tracking,General Framework:Target Representation,Choose a feature space,Represent the model in the chosen feature space,Choose a reference model in the current frame,57,Mean-Shift Object Tracking,General Framework:Target Localization,Search in the models neighborhood in next frame,Start from the position of the model in the current frame,Find best candidate by maximizing a similarity func.,Repeat the same process in the next pair of frames,Current frame,Model,Candidate,58,Mean-Shift Object Tracking,Target Representation,Choose a reference target model,Quantized Color Space,Choose a feature space,Represent the model by its PDF in the feature space,Kernel Based Object Tracking,by Comaniniu,Ramesh,Meer,59,Mean-Shift Object Tracking,PDF Representation,SimilarityFunction:,Target Model,(centered at 0),Target Candidate,(centered at y),60,Mean-Shift Object Tracking,Smoothness of,Similarity Function,Similarity Function:,Problem:,Target is represented by color info only,Spatial info is lost,Solution:,Mask the target with an isotropic kernel in the spatial domain,f,(,y,)becomes smooth in,y,f,is not smooth,Gradient-based optimizations are not robust,Large similarity variations for adjacent locations,61,Mean-Shift Object Tracking,Finding the PDF of the target model,Target pixel locations,A differentiable,isotropic,convex,monotonically decreasing kernel,Peripheral pixels are affected by occlusion and background interference,The color bin index(1.,m,)of pixel,x,Normalization factor,Pixel weight,Probability of feature u in model,Probability of feature u in candidate,Normalization factor,Pixel weight,0,model,y,candidate,62,Mean-Shift Object Tracking,Similarity Function,Target model:,Target candidate:,Similarity function:,1,1,The Bhattacharyya Coefficient,63,Mean-Shift Object Tracking,Target Localization Algorithm,Start from the position of the model in the current frame,Search in the models neighborhood in next frame,Find best candidate by maximizing a similarity func.,64,Linear approx.,(around,y,0,),Mean-Shift Object Tracking,Approximating the Similarity Function,Model location:,Candidate location:,Independent of,y,Density estimate!,(as a function of,y,),65,Mean-Shift Object Tracking,Maximizing the Similarity Function,The mode of,=sought maximum,Important Assumption:,One mode,in the searched neighborhood,The target representation provides sufficient discrimination,66,Mean-Shift Object Tracking,Applying Mean-Shift,Original Mean-Shift:,Find mode of,using,The mode of,=sought maximum,Extended Mean-Shift:,Find mode of,using,67,Mean-Shift Object Tracking,About Kernels and Profiles,A special class of radially symmetric kernels:,The profile of kernel,K,Extended Mean-Shift:,Find mode of,using,68,Mean-Shift Object Tracking,Choosing the Kernel,Epanechnikov kernel:,A special class of radially symmetric kernels:,Extended Mean-Shift:,Uniform kernel:,69,Mean-Shift Object Tracking,Adaptive Scale,Problem:,The scale of the target changes in time,The scale(,h),of the kernel must be adapted,Solution:,Run localization 3 times with different,h,Choose,h,that achieves maximum similarity,70,Mean-Shift Object Tracking,Results,Feature space:,16,16,16 quantized RGB,Target:,manually selected on 1,st,frame,Average mean-shift iterations:,4,71,Mean-Shift Object Tracking,Results,Partial occlusion,Distraction,Motion blur,72,Mean-Shift Object Tracking,Results,73,Mean-Shift Object Tracking,Results,Feature space:,128,128 quantized RG,74,Mean-Shift Object Tracking,The Scale Selection Problem,Kernel too big,Kernel too small,Poor localization,h,mustnt get too big or too small!,Problem:,In uniformly colored regions,similarity is invariant to,h,Smaller,h,may achieve better similarity,Nothing keeps,h,from shrinking too small!,75,Tracking Through Scale Space,Motivation,Spatial localization for several scales,Previous method,Simultaneous localization in space and scale,This method,Mean-shift Blob Tracking through Scale Space,by R.Collins,76,Lindebergs Theory,Selecting the best scale for describing image features,Scale-space representation,Differential operator applied,50 strongest responses,x,y,77,Scale-space representation,Lindebergs Theory,The Laplacian operator for selecting blob-like features,Laplacian of Gaussian(LOG),Best features are at(,x,)that maximize,L,2D LOG filter with scale,x,y,3D scale-space representation,78,Lindebergs Theory,Multi-Scale Feature Selection Process,Original Image,3D scale-space function,Convolve,250 strongest responses(Large circle=large scale),Maximize,79,Tracking Through Scale Space,Approximating LOG using DOG,Why DOG?,Gaussian pyramids are created faster,Gaussian can be used as a mean-shift kernel,2D LOG filter with scale,2D DOG filter with scale,2D Gaussian with,=0 and scale,2D Gaussian with,=0 and scale 1.6,DOG filters at multiple scales,3D spatial kernel,Scale-space filter bank,80,Tracking Through Scale Space,Using Lindebergs Theory,Weight image,Model:,Candidate:,Color bin:,at,Pixel weight:,Recall:,The likelihood,that each candidate pixel belongs to the target,1D scale kernel,(,Epanechnikov),3D spatial kernel(DOG),Centered at current location and scale,3D scale-space representation,Modes are blobs in the scale-space neighborhood,Need a mean-shift procedure that finds local modes in,E,(,x,),81,Tracking Through Scale Space,Example,Image of 3 blobs,A slice through the 3D scale-space representation,82,Tracking Through Scale Space,Applying Mean-Shift,Use interleaved spatial/scale mean-shift,Spatial stage:,Fix,and look for the best,x,Scale stage:,Fix x and look for the best,Iterate stages until convergence of,x,and,x,x,0,0,x,opt,opt,83,Tracking Through Scale Space,Results,Fixed-scale,Tracking through scale space,10%scale adaptation,84,Thank,You,85,