非局部平均

非局部平均（Non-local means）是一种影像降噪的算法，相较于局部（local）的算法（如高斯模糊、非等向性扩散）只使用各个目标像素附近的点来将影像平滑化来去除噪声，非局部平均算法则对各个目标像素周围定义一个区块，并且对整个影像的所有像素依照该像素周围区块的区块与目标像素区块的相似度赋予权重、进行平均，如此可以使经过处理的影像更为清晰，并且损失较少的细节。

相较于其他的影像降噪算法，非局部平均在的方法噪声（method noise，定义为影像及其降噪后的结果的差值）与白噪声较为相似，而通常认为方法噪声应与白噪声尽可能相似，因此这是一个正向的结果。非局部平均也被延伸至其他应用如去交错及影像内插等。

如同其他影像降噪算法，最简单并且普遍的噪声模型为在原始的图片上加上白噪声：

${\displaystyle v(i)=u(i)+n(i)}$

其中${\displaystyle u(i)}$为原始的图片，${\displaystyle n(i)}$为噪声，在白噪声的情况下为平均0标准差${\displaystyle \mathrm{\sigma <!--\; \sigma \; -->}}$的i.i.d. 高斯函数，${\displaystyle v(i)}$为所观测到包含噪声的图片。

非局部平均的定义为：

${\displaystyle N{L}_u(x)=\frac{1}{C(x)}{\int <!--\; \int \; -->}_{\mathrm{\Omega <!--\; \Omega \; -->}}^{}f(d(B(x),B(y)))u(y)dy}$

其中${\displaystyle u}$为要处理的图片，${\displaystyle \mathrm{\Omega <!--\; \Omega \; -->}}$为整张图片的区域，${\displaystyle B(x)}$为以${\displaystyle x}$为中心的一个区块

${\displaystyle d(x,y)}$为${\displaystyle x}$及${\displaystyle y}$的欧几里得距离：${\displaystyle d(x,y)=|x-<!--\; -\; -->y{|}_2^2}$

${\displaystyle f}$为一递减函数，常见的如：${\displaystyle f(x)=exp(-<!--\; -\; -->x^2/h^2)}$

${\displaystyle C(x)}$为标准化的因子：${\displaystyle C(x)={\int <!--\; \int \; -->}_{\mathrm{\Omega <!--\; \Omega \; -->}}f(d(B(x),B(y)))dy}$

此式可以解释为图上一点${\displaystyle x}$经过降噪后的值为整张图片上所有点的加权平均，其中每个点的权重为该点的附近区块与${\displaystyle x}$附近区块的相似度（将两个区块各自的点以相同的排列视为一向量，计算欧几里得距离），再经过一指数衰减的的函数（权重将落在(0,1]区间）。

相较于局部的算法指考虑了每个点附近的点，非局部平均考虑了图上所有的点，故称为非局部。由于一张图片中最相似的点不一定是距离近的点，反之亦然，故搜寻整张图片上相似的点，利用周期性重复出现的部分如材质纹理或是伸长的边缘等进行降噪可以得到更好的结果，但由于对每个点都要搜寻整张图片上其他的点来比较相似度，故运算复杂度往往会比局部的算法高。

上述的式子所定义的算法为连续的，无法在实际的数位影像中使用，在实际应用中离散化的版本为：

${\displaystyle N{L}_u=\frac{1}{C(i)}\underset{j\in <!--\; \in \; -->\mathrm{\Omega <!--\; \Omega \; -->}}{\sum <!--\; \sum \; -->}w(i,j)u(j)}$

${\displaystyle C(i)=\underset{j\in <!--\; \in \; -->\mathrm{\Omega <!--\; \Omega \; -->}}{\sum <!--\; \sum \; -->}w(i,j)}$

其中${\displaystyle w(i,j)}$为以${\displaystyle i}$及${\displaystyle j}$为中心的点的区块的相似度，作为计算点${\displaystyle i}$降噪后的值时点${\displaystyle j}$的权重，常见的作法为计算以${\displaystyle i}$及${\displaystyle j}$为中心的正方形区块的欧几里得距离的平方，再经过一个指数递减的函数，与前一节连续版本的例子相似，以彩色图片为例，完整的式子如下：

${\displaystyle w(i,j)=e^{-<!--\; -\; -->\frac{max(d^2(B(i,f),B(j,f))-<!--\; -\; -->2{\mathrm{\sigma <!--\; \sigma \; -->}}^2,0)}{h^2}}}$

${\displaystyle d^2(B(i,f),B(j,f))=\frac{1}{3(2f+1{)}^2}\underset{m=1}{\overset{3}{\sum <!--\; \sum \; -->}}\underset{n\in <!--\; \in \; -->B(0,f)}{\sum <!--\; \sum \; -->}(u_m(i+n)-<!--\; -\; -->u_m(j+n){)}^2}$

${\displaystyle B(i,f)}$为以点${\displaystyle i}$为中心宽度为${\displaystyle 2f+1}$的正方形区域，即${\displaystyle \times <!--\; \times \; -->}$区间。

${\displaystyle u}$的下标代表图片每个像素值的三个分量（如RGB），黑白影像则无此项。

${\displaystyle \mathrm{\sigma <!--\; \sigma \; -->}}$为噪声的标准差，${\displaystyle h}$为与${\displaystyle \mathrm{\sigma <!--\; \sigma \; -->}}$相关的滤波器参数。

此权重函数可解释为将区块相似度大于某个程度（欧几里得距离的平方小于等于${\displaystyle 2{\mathrm{\sigma <!--\; \sigma \; -->}}^2}$）的所有点都给予权重1，区块相似度较小的点权重则由于指数递减函数迅速的衰减。

除了上述以像素为单位的实作外（pixelwise），还有一种以区块为单位的实作（patchwise implementation）：

对于一个以${\displaystyle i}$为中心的${\displaystyle (2f+1)\times <!--\; \times \; -->(2f+1)}$区块${\displaystyle B(i,f)}$，处理后的值

${\displaystyle {\stackrel{^<!--\; ^\; -->}{B}}_m(i,f)=\frac{1}{C}\underset{Q(j,f)\in <!--\; \in \; -->B(i,r)}{\sum <!--\; \sum \; -->}{u}_m(Q)w(B,Q)}$

其中${\displaystyle w}$的算法与前一节的实作相同，${\displaystyle B(i,r)}$以${\displaystyle r}$的大小限制搜索区域以降低计算复杂度。

最后将这些值平均可得降噪后的图片

${\displaystyle N{L}_u=\frac{1}{(2f+1{)}^2}\underset{j\in <!--\; \in \; -->B(i,f)}{\sum <!--\; \sum \; -->}\stackrel{^<!--\; ^\; -->}{B}(j)}$

与前一节像素级的实作相比，由于最后一步集成的步骤降低了噪声，PSNR较高，并且也减少了在边缘附近震荡的噪声，不过在保留图片细节的方面则没有明显的进步。