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.

So as mentioned in my comments, everything is in the article, take your time to read it focused. Write it down on paper and it will help you to structure your thoughts.

  • $\begingroup$ 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? $\endgroup$ – nbro Apr 10 at 16:49
  • $\begingroup$ I am surprised, first you don't know the definition, then you don't understand the relation between and so on and now you only don't understand the kernel. Have you ever considered to google "euclidean distance and gaussian kernel", nevertheless I edited my answer $\endgroup$ – Irreducible Apr 10 at 16:57
  • $\begingroup$ 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? $\endgroup$ – nbro Apr 10 at 17:17
  • $\begingroup$ I am not saying anything. I am just summarising the information of the paper for you. Besides that I wouldn’t be so fast to judge anything what I don’t understand. Once again take your time to understand it. Put some number in and see how it behaves. Nevertheless your main question is answered. For further question open a new post. But accept this one $\endgroup$ – Irreducible Apr 10 at 17:27
  • $\begingroup$ "I am just summarising the information of the paper for you", no, I could not have inferred what you wrote in your answer given my current knowledge of image processing, which is very limited. I couldn't understand that notation. You are not summarising anything. You have performed inference, not compression of information (summary). I will accept this answer once I understand that your answer is really correct, given that you don't want to explain it. $\endgroup$ – nbro Apr 10 at 17:29

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.