2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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(:);

figure();
surface(vX, vX, mW);

The weight function is given by:

enter image description here

Indeed centered pixels will have higher weight.

$\endgroup$
1
  • $\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 '20 at 16:13
0
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Apr 10 '19 at 16:57
  • $\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$ Apr 10 '19 at 17:27
  • $\begingroup$ I agree with you, as state once before, without knowledge of the concepts and the math you won’t understand answers. Inform yourself in advance and make a very precise question explaining what you understand and where you are failing and why. Otherwise you are wasting everyone’s time $\endgroup$ Apr 10 '19 at 17:56
  • $\begingroup$ @Irreducible, I think the OP meant to the weighing of the Window. See my answer. $\endgroup$
    – Royi
    Jan 6 '20 at 7:10

Your Answer

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