Introduction KKernel density Kernel choices I Peak finding I Mean-shift I Cam-shift Non-parametric methods -Histogram Kernel density estimation (discuss here General form of a Kernel density function f(x)=∑ K h Add kernel d functions Each one to become is a kernel the finayPpF function KI(X-Xi)/h) 8 8 5 Histogram Kernel(Gaussian) density nttp: //en. wikipedia.org/wiki/Kernel_density_estimation 1-dimension example Camshift vod
Introduction | Kernel density | Kernel choices | Peak finding | Mean-shift | Cam-shift Non-parametric methods --Histogram --Kernel density estimation (discuss here) • = − = n i i h d h x x K nh C f x 1 ( ) ˆ Camshift v9d 11 http://en.wikipedia.org/wiki/Kernel_density_estimation Histogram Kernel (Gaussian) density 1-dimension example General form of a Kernel density function Each one is a kernel function K[(x-xi )/h)] Add kernel functions to become the final P.D.F
Introduction Kernel density I Kernel choices Peak finding Mean-shift Cam-shift Example of a histogram and kernel density function Kernel density estimates are closely related to histograms, but can be endowed with properties such as smoothness or continuity by using a suitable kernel. To see this, we compare the construction of histogram and kernel density estimators, using these 6 data points: x,=-2.1, X2=-1.3, X3=-0 4, X 4 1.9,X5=5.1, X6=6.2. For the histogram, first the horizontal axis is divided into sub-intervals or bins which cover the range of the data. In this case, we have 6 bins each of width 2 Whenever a data point falls inside this interval, we place a box of height 1/ 12. f more than one data point falls inside the same bin, we stack the boxes on top of each other. Fromhttp://en.wikipediaorg/wiki/kerneldensityestimation Camshift vod
Introduction | Kernel density | Kernel choices | Peak finding | Mean-shift | Cam-shift Example of a histogram and kernel density function • Kernel density estimates are closely related to histograms, but can be endowed with properties such as smoothness or continuity by using a suitable kernel. To see this, we compare the construction of histogram and kernel density estimators, using these 6 data points: x1 = −2.1, x2 = −1.3, x3 = −0.4, x4 = 1.9, x5 = 5.1, x6 = 6.2. For the histogram, first the horizontal axis is divided into sub-intervals or bins which cover the range of the data. In this case, we have 6 bins each of width 2. Whenever a data point falls inside this interval, we place a box of height 1/12. If more than one data point falls inside the same bin, we stack the boxes on top of each other. • From http://en.wikipedia.org/wiki/Kernel_density_estimation Camshift v9d 12
IntroductionKKernel density Kernel choices |Peak finding/Mean-shiftICam-shift The concept: General form of a Kernel density function(1-d example The area under each small gaussian curve is 1. When n curves are summed together and divided by n, the total area under the The summed PDF curve of the summed pdf is also 1 summation of many small Gaussian kernel functions C =∑k X- nhd h total area i=1 Kernel functions at ()dk=1 each sample point The area under each Gaussian curve 1 Modified from http://ww.cs.cornell.edu/courses/cs664/2005fa/lectures/lecture3.pdf Camshift vod
Introduction | Kernel density | Kernel choices | Peak finding | Mean-shift | Cam-shift The concept: General form of a Kernel density function (1-D example) • Camshift v9d 13 Modified from http://www.cs.cornell.edu/courses/cs664/2005fa/Lectures/lecture3.pdf The summed_PDF = summation of many small Gaussian kernel functions Kernel functions at each sample point The area under each Gaussian curve 1. = − = n i i h d h x x K nh C f x 1 ( ) ˆ The area under each small Gaussian curve is 1. When n curves are summed together and divided by n, the total area under the curve of the summed_PDF is also 1 ( ) 1 ˆ total area = = − f x dx h
Introduction KKernel density Kernel choices I Peak finding I Mean-shift I Cam-shift Kernel density in 2D(x1, 2 as coordinates) example E.g PDF of mosquitoes ir ()=C∑ K h At time t, if you can find one mosquito at a location Each x has such a bandwidth h to X; =(x1, x2)i, mark it green in the diagram contribute to the final probability fh(x) Assumption: at a position h x the probability f (x of finding a mosquito is proportional to the number of mosquitos =1Xi2 found in that circle It can be calculated by y f(x), e.g. h=1 meter 00o Camshift vod PDF of mosquitoes in CU 14 X
Introduction | Kernel density | Kernel choices | Peak finding | Mean-shift | Cam-shift Kernel density in 2D (x1,x2 as coordinates) example • E.g PDF of mosquitoes in CU. • At time t, if you can find one mosquito at a location xi =(x1,x2)i , mark it green in the diagram. • Assumption: at a position x, the probability fh (x) of finding a mosquito is proportional to the number of mosquitos found in that circle. • It can be calculated by fh (x), e.g. h=1 meter = − = n i i h d h x x K nh C f x 1 ( ) ˆ Camshift v9d 14 x x1 x2 PDF of mosquitoes in CU h Xi=1 Each x has such a bandwidth h to contribute to the final probability fh (x) = Xi=2
Introduction KKernel density Kernel choices I Peak finding I Mean-shift I Cam-shift Illustration of the mean -shift idea You want to find the location of a circle fixed radius to enclose the biggest number of points. The more points, the bigger the pdf. e.g. you find the area where the biggest number of mosquitos are found The mean shift algorithm X2 Guess the peak is at xt=0 Mean-shift-vect m(t) mean loc(x) 1. Draw a circle of radius h of the green 2. Find mean of points(mosquitos) inside the Search dots in the circle window=mean loc(x k, Radius in the diagram= Si 3. Move the circle for x +1 at mean loc(x, 4. m(t =mean_loc(x,)-x=mean-shift vector 5.t=t+1 °X」为 Repeat steps 1-5, till m(t) is small enough X is the result(peak 15 Camshift vod
Introduction | Kernel density | Kernel choices | Peak finding | Mean-shift | Cam-shift Illustration of the mean-shift idea You want to find the location of a circle (fixed radius) to enclose the biggest number of points. ➔ The more points, the bigger the PDF. E.g. you find the area where the biggest number of mosquitos are found. • The mean shift algorithm • Guess the peak is at xt=0 1. Draw a circle of radius h 2. Find mean of points (mosquitos) inside the window=mean_loc(xt ) =‘*’in the diagram 3. Move the circle for xt+1 at mean_loc(xt ) 4. m(t)=mean_loc(xt )-xt=mean-shift vector 5. t=t+1 • Repeat steps 1-5 , till m(t) is small enough • X is the result. (peak) Camshift v9d 15 Search Radius = Sr xt Mean-shift-vector m(t) mean_loc(xt ) of the green dots in the circle x1 x2 ‘*’