はじめに

画像のノイズ除去手法であるNon-local means filterについて記載します。

Non-local means filter

$u(\vec{r})$をフィルタ前のデータとします。$v(\vec{r})$をフィルタ後のデータとします。
$\vec{r},\vec{s}$は位置ベクトルです。$w(\vec{r},\vec{s})$は類似度に基づいた重みです。$I$は画像全体です。
フィルタ後のデータ($v(\vec{r})$)は注目点($\vec{r}$)と画像全体($\vec{s} \in I$)の重み付け和になります。
画像全体に対して重み付け和をとっていることに注目してください。これがNon-localといわれる理由です。

v(\vec{r}) = \sum_{\vec{s} \in I}{w(\vec{r},\vec{s})u(\vec{s})}

類似度に基づく重み付けは次のように行います。$\vec{N}(\vec{r})$は$\vec{r}$の周辺画素を並べたベクトルです。
$d = ||\vec{N}(\vec{r})-\vec{N}(\vec{s})||$は周辺画素ベクトルのユークリッド距離です。
ガウス関数$exp(- \frac{d^2}{\sigma ^2})$を使うことで距離0が最も重く、0から遠ざかるにしたがって軽くする重み付けをすることができます。
$\sigma$はパラメータになります。$Z(\vec{r})$は重みの総和です。規格化に使われます。

w(\vec{r},\vec{s}) = \frac{1}{Z(\vec{r})}exp(- \frac{||\vec{N}(\vec{r})-\vec{N}(\vec{s})||^2}{\sigma ^2}) \\
Z(\vec{r}) = \sum_{\vec{s} \in I} {exp(- \frac{||\vec{N}(\vec{r})-\vec{N}(\vec{s})||^2}{\sigma ^2})}

ガウス関数 $\sigma = 1$

計算例

式だけでは分かりにくいので具体例を示します。
画像サイズは幅$w=8$,高さ$h=15$です。$0\le x \le7$, $0\le y \le 14$
$\vec{r}=(4,5), \vec{s}=(1,1)$のときの図です。

簡単にするため端を含まないようにします。
つまり$\vec{r},\vec{s}$が動く範囲を$1\le x \le6$, $1\le y \le 13$に制限します。
ここでは周辺画素は注目点の周り1画素とします。
どのくらいの範囲の周辺画素を考えるかはフィルタのパラメータになります。

$\vec{r}=(4,5)$周辺画素ベクトルは次の通りです。

\vec{N}(4,5) = [u(3,4),u(3,5),u(3,6),u(4,4),u(4,5),u(4,6),u(5,4),u(5,5),u(5,6)]

$\vec{s}=(1,1)$周辺画素ベクトルは次の通りです。

\vec{N}(1,1) = [u(0,0),u(0,1),u(0,2),u(1,0),u(1,1),u(1,2),u(2,0),u(2,1),u(2,2)]

ユークリッド距離は次の通りです。

||\vec{N}(4,5) - \vec{N}(1,1)||^2 = \\
(u(3,4)-u(0,0))^2 + (u(3,5)-u(0,1))^2 + (u(3,6)-u(0,2))^2 + \\
(u(4,4)-u(1,0))^2 + (u(4,5)-u(1,1))^2 + (u(4,6)-u(1,2))^2 + \\
(u(5,4)-u(2,0))^2 + (u(5,5)-u(2,1))^2 + (u(5,6)-u(2,2))^2\\

$\vec{s}$を$1\le x \le6$, $1\le y \le 13$の範囲で動かして上記と同じ処理を行います。
その結果を使うと次の計算ができます。

Z(4,5) = \sum_{1 \le x \le 6} \sum_{1 \le y \le 13} {exp(- \frac{||\vec{N}(4,5)-\vec{N}(x,y)||^2}{\sigma ^2})}

w((4,5),(x,y)) = \frac{1}{Z(4,5)} exp(- \frac{||\vec{N}(4,5) - \vec{N}(x,y)||^2}{\sigma ^2})

重みが決定できたのでフィルタリングを行います。

v(4,5) = \sum_{1 \le x \le 6} \sum_{1 \le y \le 13} {w((4,5),(x,y))u(x,y)}

以上で$v(4,5)$のフィルタリングができました。

$\vec{r}$を$1\le x \le6$, $1\le y \le 13$の範囲で動かして上記と同じ処理を行うとフィルタリング処理が完了します。