非常有利于meanshift算法的理解

1、Mean Shift Theory and Applications 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 Mean Shift Theory Intuitive Descr

2、iption Distribution of identical billiard balls Region of interest Center of mass Mean Shift vector Objective : Find the densest region Intuitive Description Distribution of identical billiard balls Region of interest Center of mass Mean Shift vector Objective : Find the densest region Intuitive Des

3、cription Distribution of identical billiard balls Region of interest Center of mass Mean Shift vector Objective : Find the densest region Intuitive Description Distribution of identical billiard balls Region of interest Center of mass Mean Shift vector Objective : Find the densest region Intuitive D

4、escription Distribution of identical billiard balls Region of interest Center of mass Mean Shift vector Objective : Find the densest region Intuitive Description Distribution of identical billiard balls Region of interest Center of mass Mean Shift vector Objective : Find the densest region Intuitive

5、 Description Distribution of identical billiard balls Region of interest Center of mass Objective : Find the densest region What is Mean Shift ? Non-parametric Density Estimation Non-parametric Density GRADIENT Estimation (Mean Shift) Data Discrete PDF Representation PDF Analysis PDF in feature spac

6、e 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 RN Non-Parametric Density Estimation Assumption : The data points are sampled from an underlying PDF Assumed Under

7、lying PDFReal Data Samples Data point density implies PDF value ! Assumed Underlying PDFReal Data Samples Non-Parametric Density Estimation Assumed Underlying PDFReal Data Samples ?Non-Parametric Density Estimation Parametric Density Estimation Assumption : The data points are sampled from an underl

8、ying PDF Assumed Underlying PDF 2 2 () 2 i PDF( ) = i i i c e x- x Estimate Real Data Samples Kernel Density Estimation Parzen Windows - General Framework 1 1 ( )() n i i PK n xx-x Kernel Properties: Normalized Symmetric Exponential weight decay ? ( )1 d R Kd xx ( )0 d R Kd xxx lim( )0 d K x xx ( )

9、d T R Kdc xxxxI A function of some finite number of data points x1xn Data Kernel Density Estimation Parzen Windows - Function Forms 1 1 ( )() n i i PK n xx-xA function of some finite number of data points x1xn Data In practice one uses the forms: 1 ( )( ) d i i Kck x xor ( )Kckxx Same function on ea

10、ch dimension Function of vector length only Kernel Density Estimation Various Kernels 1 1 ( )() n i i PK n xx-xA function of some finite number of data points x1xn Examples: Epanechnikov Kernel Uniform Kernel Normal Kernel 2 11 ( ) 0 otherwise E c K xx x 1 ( ) 0 otherwise U c K x x 21 ( )exp 2 N Kc

11、xx Data Kernel Density Estimation Gradient 1 1 ( ) () n i i PK n xx-x Give up estimating the PDF ! Estimate ONLY the gradient 2 () i i Kck h x-x x-x Using the Kernel form: We get : 1 11 1 ( ) n iinn i iin ii i i g cc Pkg nn g x xx Size of window g( )( ) k xx Kernel Density Estimation Gradient 1 11 1

12、 ( ) n iinn i iin ii i i g cc Pkg nn g x xx Computing The Mean Shift g( )( ) k xx 1 11 1 ( ) n iinn i iin ii i i g cc Pkg nn g x xx Computing The Mean Shift Yet another Kernel density estimation ! Simple Mean Shift procedure: Compute mean shift vector Translate the Kernel window by m(x) 2 1 2 1 ( )

13、n i i i n i i g h g h x-x x m xx x-x g( )( ) k xx 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 sadd

14、le point ? Perturb the mode position and check if we return back 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 i

15、nfinitely 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 ( ). Real Modality Analysis Tessellate the space with windows Run the procedure in paralle

16、l Real Modality Analysis The blue data points were traversed by the windows towards the mode Real Modality Analysis An example Window tracks signify the steepest ascent directions Adaptive Mean Shift Mean Shift Strengths G x 2 ;G x ; k G x Lindebergs Theory The Laplacian operator for selecting blob-

17、like features Laplacian of Gaussian (LOG) f x Best features are at (x,) that maximize L 1 ( ;)LOG x 2 ( ;)LOG x ( ;) k LOG x 2 2 2 2 2 6 2 ; 2 x x LOG xe 2D LOG filter with scale 1. ,: ,; k xf L xLOG xf x x y 3D scale-space representation 2 1 ;G x 2 2 ;G x 2 ; k G x Lindebergs Theory Multi-Scale Fea

18、ture Selection Process Original Image fx 3D scale-space function ,;L xLOG xfx Convolve 250 strongest responses (Large circle = large scale) Maximize Tracking Through Scale Space Approximating LOG using DOG Why DOG? Gaussian pyramids are created faster Gaussian can be used as a mean-shift kernel ;1.6

19、LOG xDOG xG xG x 2D LOG filter with scale 2D DOG filter with scale 2D Gaussian with =0 and scale 2D Gaussian with =0 and scale 1.6 ,K x DOG filters at multiple scales 3D spatial kernel 2 1 k Scale-space filter bank Tracking Through Scale Space Using Lindebergs Theory Weight image ( ) ( )0 b x b x q

20、w x py 1 , m p ypypy 1, , m qqq Model: Candidate: ( )b xColor bin: 0 y 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 ,E x Modes are bl

21、obs in the scale-space neighborhood Need a mean-shift procedure that finds local modes in E(x,) Tracking Through Scale Space Example Image of 3 blobs A slice through the 3D scale- space representation Tracking Through Scale Space Applying Mean-Shift Use interleaved spatial/scale mean-shift Spatial s

22、tage: Fix and look for the best x Scale stage: Fix x and look for the best Iterate stages until convergence of x and x x0 0 xopt opt Tracking Through Scale Space Results Fixed-scale Tracking through scale space 10% scale adaptation Agenda Mean Shift Theory What is Mean Shift ? Density Estimation Met

23、hods Deriving the Mean Shift Mean shift properties Applications Clustering Discontinuity Preserving Smoothing Object Contour Detection Segmentation Object Tracking Mean Shift Mode Detection Updated Mean Shift Procedure: Find all modes using the Simple Mean Shift Procedure Prune modes by perturbing t

24、hem (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 Real Modality Analysis Tessellate the space with windows Run the procedure in parallel Mean-Shift Object Tracking General Framework: Target Localization Search in the models neigh