6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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:

$ {\displaystyle 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.