Introduction KErnel 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 Kerne 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 nttp: /en.wikipedia. org/wikilKernel_density_estimation 1-dimension example sity Kernel (Gaussian)del Camshift v 0.a 11
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 v.0.a 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 v 0.a
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 v.0.a 12
IntroductionKKernel density Kernel choices I Peak finding IMean-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 (x)=∑K X- nhd h total area i=1 Kernel functions at fr(x)dx=1 each sample point SThe area under each Gaussian curve 1 Modified from http://ww.cs.cornell.edu/courses/cs664/2005fa/lectures/lecture3.pdf Camshift v 0.a
Introduction | Kernel density | Kernel choices | Peak finding | Mean-shift | Cam-shift The concept: General form of a Kernel density function (1-D example) • Camshift v.0.a 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 KErnel 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 in f,()=m 2x/x-x 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 x the probability fh(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 v 0.a 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 v.0.a 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 KErnel 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=o 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人“ Radius In the diagram= Sr 3. Move the circle for xt+1 at mean loc(x+ 4. m(t)=mean_loc(x, ) -.=mean-shift vector 5.t=t+1 °X」为 Repeat steps 1-5, till m(t) is small enoug X is the result(peak 15 Camshift V.0.a
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 v.0.a 15 Search Radius = Sr xt Mean-shift-vector m(t) mean_loc(xt ) of the green dots in the circle x1 x2 ‘*’