# How is the Gaussian kernel related to the Euclidean distance of the neighbourhoods in the non-local means algorithm?

I am reading the paper A non-local algorithm for image denoising that describes the original non-local means algorithm. They define (p. 3 of the pdf) the distance between two square fixed neighbourhoods of two pixels as

\begin{align} \|v(\mathcal{N}_i) - v(\mathcal{N}_j) \|_{2, a}^2 \end{align}

where $$a> 0$$ is the standard deviation of the Guassian kernel. However, I don't understand this notation. How is the Gaussian kernel used in the formulation? How is it related to the Euclidean distance?

I would appreciate if someone more familiar with image processing and computer vision and all this notation can give me an explanation.

So lets do it step by step:

Let us define $$k$$ as the norm on Gaussian Kernel with standard deviation $$a$$

$$k(i,j)=\|v(\mathcal{N}_i) - v(\mathcal{N}_j) \|_{2, a}^2$$

and the Gaussian kernel with the parameter $$a$$ is defined as:

$$G_a (x)= \frac{1}{4\pi a^2} e^{-\frac{\mid{x}\mid^2}{4a^2}}$$

And combining it you get:

$$k(i,j)=\frac{1}{4\pi a^2} e^{-\frac{\|v(\mathcal{N}_i) - v(\mathcal{N}_j) \|_{2}^2}{4a^2}}$$

So finally $$w$$ is defined as

$$w(i,j)=\frac{1}{Z(i)} e^{ -\frac{k(i,j)}{h^2} }$$

Coming back to your last question: "So, what is the difference between this exponential function that defines w and the Gaussian kernel? "

Difference is not the right question, $$w$$ depends on $$k$$ in a nested way as it is the argument of the exponential function.

• You do not explain the only thing that I did not understand: what is the relation between the $a$ in the norm $k(i, j)$ and $G_a(x)$? How are they connected, in terms of formulas? – nbro Apr 10 at 16:49
• I knew the definition of the "kernel function" (from the paper), but I didn't know how the kernel function was related to the weights. This was my doubt since the beginning. So, are you saying that the subscript $a$ in the first definition of $k(i, j)$ means that that Euclidean distance is the input to the Gaussian kernel function? So, the weights will be defined as an exponential to an exponential?! I guess I will have to look at the definition of the Gaussian kernel function somewhere else, but this does not make any intuitive sense. Why would we do such a thing? – nbro Apr 10 at 17:17