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.

  • $\begingroup$ Could you please review my answer? $\endgroup$ – Royi Jan 6 at 17:17
  • $\begingroup$ @Royi It's been a while since I've not had to deal with computer vision. I've read your answer and your explanations are reasonable, but I am not qualified to accept or upvote your answer now. I really appreciate your help though. In a few weeks, I will come back to this topic and I will probably review your answer again. $\endgroup$ – nbro Jan 6 at 17:34

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.

| improve this answer | |
  • $\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 '19 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 '19 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 '19 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 '19 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 '19 at 17:29

So we have 2 neighborhoods (Which are Matrices) $ v \left( {\mathcal{N}}_{i} \right) $ and $ v \left( {\mathcal{N}}_{j} \right) $. How could we calculate the distance between them?

One option would be the Euclidean Distance:

$$ {\left\| v \left( {\mathcal{N}}_{i} \right) - v \left( {\mathcal{N}}_{j} \right) \right\|}_{2}^{2} = \sum_{k} {\left( {v \left( {\mathcal{N}}_{i} \right)}_{k} - {v \left( {\mathcal{N}}_{j} \right)}_{k} \right)}^{2} $$

Yet this gives each pixel in the neighborhood window the same weight. The writes of the Non Local Means Denoising Algorithm thought it would be better to give the pixels near the center of the window higher weight.
They did it easily using by multiplying the difference window by a Gaussian Function and then summing. Something like:

$$ {\left\| v \left( {\mathcal{N}}_{i} \right) - v \left( {\mathcal{N}}_{j} \right) \right\|}_{2, a}^{2} = \sum_{k} {w}_{k} \left( a \right) {\left( {v \left( {\mathcal{N}}_{i} \right)}_{k} - {v \left( {\mathcal{N}}_{j} \right)}_{k} \right)}^{2} $$

Where $ {w}_{k} \left( a \right) $ is a weight based on a 2D Gaussian function with its center aligned to the center of the neighborhood window and its Standard Deviation is given by $ a $.

| improve this answer | |

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.