# Understanding the mean shift algorithm with Gaussian kernel

I am referring here to the Wikipedia article regarding the mean shift algorithm.

Here the Gaussian kernel is denoted as $e^{-c\|x_i - x\|^2 }$

My questions are the following:

• Is $c$ always positive? I.e. are hence the "weights" given by the kernel always between 0 and 1?
• Looking at a picture explaining the algorithm, I have seen that in the two-dimensional case, the kernel can be understood as a circle..how do I see it from the formula above that it is indeed a circle, i.e. only points in this circle are considered at each iteration?

Thanks

if I were you I would refer to one of the main mean shift papers: Mean Shift: A Robust Approach Toward Feature Space Analysis. The short answer to your questions: yes c is always positive and no the kernel (window) is not a circle.

Now the long version. The kernel density estimator is: $\hat{f}_h(x) = \frac{1}{nh} \sum_{i=1}^n K\Big(\frac{x-x_i}{h}\Big)$,

where K(•) is the kernel and h is called bandwidth. Your question is about two-dimensional data and in practice we usually have to deal with multivariate data and things are a bit trickier for multivariate data. That's why in Mean Shift we are only interested in a special case of radially symmetric kernels satisfying: $K(x)= c_{k,d} k(\|x\|^2)$ where $c_{k,d}$, the normalization constant, makes $K(x)$ integrate to one and $k(x)$ is called the profile of the kernel. It helps us simplify the calculation in the case of multivariate data.

The profile of the Gaussian kernel is: $e^{-\frac{1}{2}x^{2}}$ and therefore, the multivariate Gaussian kernel with the standard deviation $\sigma$, will be:

$K(x)=\frac{1}{\sqrt{2\pi}\sigma^d}e^{-\frac{1}{2}\frac{\|x\|^2}{\sigma^2}}$,

where $d$ is the number of dimensions. It's also worth mentioning that the standard deviation for the Gaussian kernel works as the bandwidth parameter, $h$.

Now having sample points $\{x_i\}_{i=1..n}$, each mean shift procedure starts from a sample point $y_j = x_j$ and update $y_j$ until convergence as follows:

$y_{j}^{t+1}=\frac{\sum_{i=1}^{n}x_{i}e^{-\frac{1}{2}\frac{\|y_{j}^{t}-x_{i}\|^{2}}{\sigma^{2}}}}{\sum_{i=1}^{n}e^{-\frac{1}{2}\frac{\|y_{j}^{t}-x_{i}\|^{2}}{\sigma^{2}}}}$

So basically all the points are considered in calculation of the mean shift but there is a weight assigned to each point that decays exponentially as the distance from the current mean increases and the value of $\sigma$ determines how fast the decay is.