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 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 $.

The Weight Function

In the classic Non Local Means implementation the Gaussian functions is used as weighing.

Assuming the $ v \left( \cdot \right) $ operator is the Vectorization operator (Column Wise) then for a $ 31 \times 31 $ window the following MATLAB code will define $ {w}_{k} \left( \sigma \right) $:

windowRadius    = 15;
kernelStd       = 3.5;

vX = -windowRadius:windowRadius;
vK = exp(-((vX .^ 2) / (2 * kernelStd * kernelStd)));
vK = vK ./ sum(vK);
mW = vK.' * vK;
vW = mW(:);

surface(vX, vX, mW);

The weight function is given by:

enter image description here

Indeed centered pixels will have higher weight.

| improve this answer | |
  • $\begingroup$ If you put the definition of the Gaussian function in $w_k(a)$, I will accept this answer, which I think clarifies my doubt (that I had at the time) indeed. Anyway, why would you use such a notation to indicate that a Gaussian function is used to weight the distance? Even after all this time, I've never seen that notation anywhere else to indicate "weighting". $\endgroup$ – nbro Sep 22 at 15:20
  • $\begingroup$ I think I tried to match the notations used by the inventor of the Non Local Means algorithm. I agree they are not wide spread. I will add the definition. $\endgroup$ – Royi Sep 22 at 16:13
  • $\begingroup$ @nbro, I added the definition of the weighing function. $\endgroup$ – Royi Sep 22 at 16:27

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

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.