How Is the Gaussian Kernel Related to the Euclidean Distance of the Neighborhoods in the Non Local Means Denoising Algorithm?

Question

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.

Answer 1

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:

Indeed centered pixels will have higher weight.

Answer 2

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.