cBlog

Tips for you.

畳み込み警察です! たまには反転のことも思い出してやってください

圧倒的知名度を誇るからあげ (id:karaage)先生を通して啓蒙したいことがあります。

karaage.hatenadiary.jp

\begin{align}
x&(i - 1, j - 1) \times A + x(i, j - 1) \times B + x(i + 1, j - 1) \times C \\
{} + x&(i - 1, j) \times D + x(i, j) \times E + x(i + 1, j) \times F \\
{} + x&(i - 1, j + 1) \times G + x(i, j + 1) \times H + x(i + 1, j + 1) \times I
\end{align}

ほんとは、違います(爆)

正しくは以下です。

\begin{align}
x&(i - 1, j - 1) \times I + x(i, j - 1) \times H + x(i + 1, j - 1) \times G \\
{} + x&(i - 1, j) \times F + x(i, j) \times E + x(i + 1, j) \times D \\
{} + x&(i - 1, j + 1) \times C + x(i, j + 1) \times B + x(i + 1, j + 1) \times A
\end{align}

カーネルを各軸に対して反転(180°回転)させる必要があります。

いや、大抵の基礎的なフィルタは中心に対して点対称だし、あらかじめ回転させたものをカーネルとして用いていると考えれば一緒なんですけどね… でも、本来の畳み込みは反転を含めた演算であることを周知させたかったのです。

私はかねてよりこのことを主張してきたのですが、以前の記事(読まれないだけ)

yaritakunai.hatenablog.com

あと、ちゃんと各軸についてひっくり返して(2次元の場合180度回転させて)計算を行っていることにも好感。大抵のフィルタは原点に対して対称なので結果は変わらないですが、こちらのように違いますからね、畳み込みと相関。

でもはてブ(コメントするのが遅いだけ)

サルでも分かるwaifu2xのアルゴリズム

waifu2xの機械学習の部分じゃないけど、やっとわかったかも。パッチを1pxずらしながら平均とっていくから畳み込みなのか。とすると、畳み込みの計算逆じゃない? 2x2だったらAd+Bc+Cb+Daみたいな

2016/03/10 07:25

b.hatena.ne.jp

でも大した影響はありませんでした。

えらーいMATLAB先生もこう言っています。

jp.mathworks.com

たたみ込みカーネルは、相関カーネルを 180 度回転させたものです。

両者の違いは、"相関カーネル" と呼ばれる重み行列で、計算中に回転を行いません。

SciPyのndimage.convolveもちゃんと反転を行なっています。

scipy.ndimage.convolve — SciPy v0.19.1 Reference Guide

>>> a = np.array([[1, 2, 0, 0],
...               [5, 3, 0, 4],
...               [0, 0, 0, 7],
...               [9, 3, 0, 0]])
>>> k = np.array([[1,1,1],[1,1,0],[1,0,0]])
>>> from scipy import ndimage
>>> ndimage.convolve(a, k, mode='constant', cval=0.0)
array([[11, 10,  7,  4],
       [10,  3, 11, 11],
       [15, 12, 14,  7],
       [12,  3,  7,  0]])

(1, 1)要素を計算してみましょう。11ではなく3になっていますね。

私は信号処理を中心に学んできました。そこでは畳み込みに加え、後述する相互相関も教わるので、反転するかしないかは重要です。画像処理界では反転させない(あるいは、あらかじめ反転している)ということが暗黙の了解なのかもしれませんが、画像処理やCNNから入った人にも本来の畳み込みを知っておいてほしくてこの記事を書いています。

 

なぜ反転させるのか

畳み込みはもともとシステム(フィルタ)に信号が入力されたときの出力信号を表す演算です。

\begin{align}
y(t) = \int_{-\infty}^\infty f(\tau)g(t - \tau)\,d\tau
\end{align}

説明をすっ飛ばすと、システムに入力される信号は頭から突っ込む(時間的に過去の部分から先に入る)はずです。だからです。

画像で見た方がいいですよね。

f:id:cruller:20170802235951p:plain

出典:Cross-correlation - Wikipedia

ところで、反転させない場合の式にも意味があり、名前が付いています。(相互)相関です(こっちはすれ違う)。

\begin{align}
R(\tau) = \int_{-\infty}^\infty f(t)g(t - \tau)\,dt
\end{align}

つまり…どういうことでしょうか。畳み込みの式を変形させてみましょう。

\begin{align}
y(t) &= \int_{-\infty}^\infty f(\tau)g(t - \tau)\,d\tau \\
&= \int_{-\infty}^\infty f(\tau)g(-(\tau - t))\,d\tau
\end{align}

ここからg(\tau)\tau軸上で反転させ、t\tauを入れ替えれば、畳み込みと相互相関は一致(y(t) = R(t))することがわかります。もっと言うと、g(\tau)が偶対称なら無条件で畳み込みと相互相関は等しいことになります。まさに、画像処理のフィルタが点対称なら畳み込みと相関の違いを無視しても問題となっていないことを示しています。

 

追記

同じ「畳み込み」という言葉を使っているだけ説もありかなあ。

例えば、CNNだとストライド1サンプルに限らないですし。

信号処理、画像処理、CNNに詳しい方いらっしゃいますか? それぞれの見解を。

 

追記2

OpenCVに頼らないでpython+numpy+PILで画像処理のフィルタを1から作って理解する - karaage. [からあげ]

こんなん見つけましたワン https://books.google.co.jp/books?id=Np9SDQAAQBAJ&pg=PA324&lpg=PA324&dq=convolution+flip+kernel&source=bl&ots=kRHdrGy4W0&sig=nAozBTx-Gc-irM1EwwB094P-9SM&hl=ja&sa=X&ved=0ahUKEwjnraH1z7nVAhXMQpQKHf4rCYM4ChDoAQgPMAI#v=onepage&q=convolution%20flip%20kernel&f=false

2017/08/03 07:53

b.hatena.ne.jp

機械学習の分野では慣習とのこと。このように、理解しての混同ならいいのですが。