1. 畳み込み (convolution) とは [概要]
畳み込み(convolution)とは，関数$f$と関数*$g$から，相手の関数の形状によってもう一方の関数の形状がどのように変化するかの結果を表した新たな関数$(f * g)$を出力する演算である．特にデジタル信号処理においては，関数の代わりに信号（1次元 or 2次元データ）のフィルタリングに応用される．
この記事では，畳み込みを用いたフィルタリングの中でも，画像フィルタリング（Image Filtering）に用いる場合の（離散）畳み込み演算についてまとめたい．
画像の畳み込み計算は，現代ではCNNの畳み込み層にも用いられている意味で，昔から現代に到るまで継続的に中心的であり続けている処理でもある：
画像の畳み込みでは，正方形のカーネル(またはフィルタと呼ぶ)を用いた「スライディングウィンドウ処理」を通して，入力画像の各参照画素$(x,y)$の近傍において「カーネル値と参照画素値による，局所的な畳み込み演算（積和）」をおこなう．これにより，カーネルの値に沿って入力画像を変換する処理である(例：平滑化，エッジ候補検出など)．
1.1 記事の構成
2節以降では，以下の構成で画像フィルタによる畳み込みについて紹介する：
- 2節：畳み込みの定義と性質．
- 2.1 連続系：「畳み込み積分」
- 2.2 離散系：「畳み込み和」
- 2.3 畳み込みの演算手順：”convolve”の原義も考慮して理解する．
- 2.4 相互相関と畳み込みの類似点・相違点
- 3節：画像フィルタリングでの「2次元離散畳み込み」処理．
- 3.1 「畳み込みの離散化」とスライディングウィンドウ．
- 3.2 パディング処理
- 3.3「関数」と「信号」．空間周波数と巡回畳み込み．
- 4節：まとめ
前半の2節では，まず準備として，畳み込み演算の一般的な定義と性質を紹介する（一次元の畳み込みと二次元の畳み込み）．後半の3節では，本題である「画像のフィルタリング」について，スライディングウィンドウ処理やパディング処理の視点から，処理の全体像を紹介したい．
「畳み込み演算を用いた画像処理フィルタ」の具体例については，以下の２つのサブ記事において，目的別に分けて紹介する：
繰り返すが，ディープラーニング向けの畳み込み層については述べない．そちらも興味ある方は，畳み込み層とその発展型の記事のうち「2節 畳み込み層(2D)の基本型」も，同時に参照していただくと理解が増すはずである．
2. 畳み込みの定義および性質
まず2節では一般的な畳み込み演算の定義を，連続（2.1節）→ 離散 （2.2節）の順に行なう．これらは，3節においてデジタル画像フィルタリングのアルゴリズムを説明するための，事前準備である．
そして，”convolve（巻き込む）“という英語の原義に沿って説明することで，畳み込みについて定義を暗記せずとも演算をイメージできるようにし（2.3節），畳み込みと類似した演算である「相互相関(cross correlation)」との比較も述べる（2.4節）．
2.1 連続系:「畳み込み積分」(1D)
まず2.1節では，1次元信号（関数）についての，畳み込み演算の数学的な定義を確認していきたい．
時間軸方向を$t$軸方向とした際の，時刻$t$における畳み込み演算$(f * g)(t)$は，以下のように定義される：
\begin{equation}(f * g)(t) = \int_{-\infty}^{-\infty} f(\tau)g(t-\tau)d\tau\tag{2.1}\end{equation}
この演算では，時刻$t$において以下の2つのサブ演算を行う：
- 現在の参照位置$t$からみて，対称的位置にある$f(\tau)$と$g(t-\tau)$のあいだで積値をとる．
- その積値$f(\tau)g(t-\tau)$を，$\tau$をスライドさせながら全定義域区間$(-\infty ,\infty)$で積分する．
ここで$\tau$は，時刻$t$において2つの関数間の「相対的なスライド量」の変数である．
連続系での畳み込み演算(2.1)式のことを，畳み込み積分とも呼ぶ．畳み込み積分は，アナログの制御工学・信号処理などにおいて，線形時不変(LTI)システムの出力をインパルス応答から算出してシステムの振る舞いを解析する目的などに用いられる (連続系での応用の話題は本記事の目的外なので，これ以上は触れない)．
また，畳み込み演算には交換律が成立し， $(f * g) = (g * f)$ となる．(※ この性質は，別記事の周波数フィルタリングに関係してくる)
2.2 離散形:「畳み込み和」(1D)
画像処理や音響処理などのデジタル信号処理分野において，畳み込み演算は「局所演算子カーネルを用いた，空間ドメインにおけるフィルタリング演算」によく用いられる．デジタルでのエコーやリバーブなどの「エフェクター」にも用いられるなど，畳み込み処理は音声・音響分野でも広く活用されている．
それでは，離散系での「1次元信号同士における畳み込み」の定義をまずみていきたい．時間幅の大きな1次元関数$f$（入力信号に相当）に対して，それよりも小さな時間幅$(2k+1)$の1次元カーネル関数$h$を畳み込み相手のカーネル(1次元の窓関数)として用意する．
この時，離散形の時刻$x$における畳み込み演算$(h*f)(x)$は，以下の式で表すことができる：
\begin{equation}(f*g)(x) = \sum_{i=-k}^{k} f(i)g(x-i)\tag{2.2}\end{equation}
この離散形での畳み込み(2.2)は，積の和として演算することから畳み込み和とも呼ぶ．
離散フーリエ変換やFFTなどの「周波数ドメインにおけるフィルタリング」では，畳み込み演算は畳み込み定理(Convolution theorem)を通じて周波数ドメイン側で計算される．その際に，FFT(高速フーリエ変換)を活用した畳み込み演算の高速化も頻繁に行われる (詳しくは「画像フィルタリング(2)：周波数フィルタリング」を参照) ．
2.3 畳み込みの演算手順 (2D)：”convolve”の原義も考慮して理解する．
この2.3節では「畳み込み(convolution)」の2D演算の振る舞いを，原義である「渦状に巻き込む（convolve）」に結びつけながら説明する．原義通りの説明を行うことにより，読者が，畳み込みの計算手順をイメージしやすくなり，語義から演算内容を思い出せるようにもしたい．畳み込みは数式を丸暗記するように教えられてきた方が多いとは思うが，ぜひ「巻いて積を取る」というconvolutionの原義通り，畳み込み演算式を理解できるようになっていただければと思う．
2.3.1 一次元信号の畳み込み
以下にまず，2.1節にも示した時刻$t$における，信号$f$とカーネル$g$間の畳み込み演算の定義（一次元連続空間）を，再掲しておく：
\begin{equation}(f * g)(t) = \int_{-\infty}^{-\infty} f(\tau)g(t-\tau)d\tau\tag{2.1} \end{equation}
式(2.1)では「$\tau$と$t-\tau$の2引数が，合計すると常に$t$になっている」というところを理解するのが，まず最初に重要となる．合計すると$\tau +(t-\tau) = t$となる位置関係を保ちながら積$f(\tau)g(t-\tau)$の積分を計算する．そして，その積値を$\tau$に関してスライドさせて，全区間積分した値が，時刻$t$における畳み込みの結果値である．
すなわち，1D畳み込みの式(2.1)は，原義”convolve”の通りに「対象信号の各位置$t$において，渦巻き順に$f(t)$の周辺値$f(\tau)g(t-\tau)$を積分した結果を，その各位置$t$の出力$(f * g)(t)$としている」と理解できると，演算内容を素直に理解しやすい．つまり，竜巻のように相手を巻き混みながらスライドし，積分合成していく演算がconvolutionである．(※ 中国語では，その通りにconvolutionが，巻積と翻訳されている).
それでは今度は，離散の1次元畳み込みの例を通して，その「各位置で巻き込んで積分を取った結果で，各位置の合成結果を出力していく」様子を具体的に見てみよう．
2.3.2 一次元信号の畳み込み(離散での例)
スライド図1は，画像フィルタリングにおいて，入力画像とカーネルの各1次元 （$x$軸方向の1列）を取り出して図示した，1次元畳み込み演算の例である．図1では，$3 \times 1$のカーネル$g$の値を$[1 2 1]$としたとき，カーネル$g$を$x$軸方向に移動し，画像$f$の各点$x$において$(f * g)(t)$の畳み込み演算を行う様子を示している．
図1の3つの矢印（紫色）のように，カーネルがスライド移動していく最中の各位置において，カーネルと画像信号のあいだで積値を取る2点の位置関係が，$t$周辺をぐるっと渦巻き状に巻き込みながら移動(積分)していくことから，この演算はConvolution（渦巻き込み）と呼ばれる．
2.3.3 画像フィルタリングでの畳み込み
続いて画像フィルタリング（2D）における畳み込み演算について述べる．ここでは，畳み込みのスライディングウィンドウ中に，各位置でカーネルと各座標の積を取る2点間の位置関係が「2次元渦巻き」であることを確認していこう．
関連記事「画像のフィルタリング: (1) 空間フィルタリング(Spatial Filtering)」2.1節の「線形フィルタの一般系」では，反転済みのカーネル$W^{\prime}(i,j)$を用いて，以下のように畳み込み演算式を記している：
\begin{equation} (I * W^{\prime})(x,y) = \frac{1}{S} \sum^{k}_{i=-k} \sum^{k}_{j=-k} W^{\prime}(i,j) \cdot I(x+i, y+j) \tag{2.3}\end{equation}
このみなさんがよく見る，式(2.3)の定義では，「反転カーネル$W^{\prime}$の空間座標$(i,j)$の値同士の積」の和をとっていた．この式を，本記事では「反転無しの元のカーネル$W(x,y)$」を用いた，元の畳み込みの定義式通りの線形フィルタの式で表してみたい．
そうすると，式(2.3)は，カーネルの各引数が反転前の反対側座標$(-i,-j)$に変えた，以下の式でも表すことができる：
\begin{equation} (I * W)(x,y) = \frac{1}{S} \sum^{k}_{i=-k} \sum^{k}_{j=-k} W(\textcolor{red}{-}i,\textcolor{red}{-}j) \cdot I(x+i, y+j)\tag{2.5} \end{equation}
この表現に変えた場合，カーネルの局所座標上では，画像の$(i,j)$と，対称に位置する$(-i,-j)$のカーネル値で積を取る．その積を，画像全体で総和さえ取れれば，$i$と$j$のアクセス順番は自由であり，1次元での図1のように隣接画素に順にアクセスしてカーネル全座標で和を取っていくする．
そうすると，以下の図2のように「2次元の渦巻（$\ast$）の形に沿って，添字アクセスを行う」と解釈できるようになる：
以上のように，1次元でも2次元でも畳み込み演算は「渦状巻き込みの形状上に，(カーネル中心を対象にして反対同士の)画素カーネル値のペアで積をとり，それら積値の和(積分)を計算する」演算である．これで，畳み込みは「convolve(渦巻く)」という意味通りの演算手順であることが，2次元畳み込みにおいても理解できたと思う．
ただし，カーネル内で積分or和を取っていく順番は自由である．従って，カーネル内で渦巻き順をイメージしないかぎりは，2次元画像フィルタリングの場合，渦巻きの順で積を取っていく必要性は特に無い点には注意されたい．
2.4 相互相関 と 畳み込み の比較
デジタル画像処理の「テンプレートマッチング」に主に用いられる相互相関（cross-correlation）は，畳み込み演算とかなり類似しているものの少しだけ異なる演算同士である．そこで，両者の類似点と相違点を整理してまとめておきたい (※ 別の記事で「CNNの畳み込み層」の説明時にも必要となるのも理由)．
両者の相違点は以下の通りである：
- 相互相関：$f$に$g$をスライドさせて，各位置$t$で相互相関を計算．
- 畳み込み：$f$に$g$をスライドさせて，$t$を中心に左右反転させた=(渦巻き位置関係で)畳み込みを計算．
図3(b)は，図1,2の図をもとに，1次元の畳み込みと相互相関を比較したものである．
図3(b)を見てわかるとおり，両者の違いは，カーネルと画像で要素積を取る2画素の位置関係が「同じ画素位置同士（相互相関）」なのか，それとも「参照画素$x$を中心に対称（渦巻状にアクセス）」なのかの１点だけである．カーネルが中心に対して対称である場合，畳み込みと相互相関は等価な演算となる．
以上を一旦まとめると，相互相関と畳み込みは，以下のように対称的・対照的な性質および用途を持つこととなる：
| 画像の相互相関 | 画像の畳み込み | |
| 計算 | 同画素位置の画素値同士の積の総和を計算(図3-(b)下) |
|
| 出力 | 画像$f$の小窓内と，小テンプレ$g$が 似ている(＝相関の強い)座標 | 画像と，カーネルの 合成関数(形状) |
| 適した用途 | 2関数間の相関(類似)を出力 →テンプレートマッチングによる「テンプレート類似した局所領域の識別」に向く． | カーネルに沿って画像信号(形状)を変化 →フィルタリング(ノイズ除去や平滑化)や特徴抽出（コーナー検出やエッジ検出）に向く． |
| 交換律と結合律 | 成立しない | 成立する |
3 画像フィルタリングでの，2次元離散畳み込みの手順．
3節では，「2次元画像平面上での離散畳み込み (＝画像の空間フィルタリング)」について，スライディングウィンドウ処理を用いた具体的な処理手順をみていきたい．
3.1 「畳み込みの離散化」とスライディングウィンドウ処理．
画像フィルタリングにおける，入力グレー画像$I$の座標$\bm{p} = (x,y)$における画素値を$I(\bm{p})$とする．
このとき，カーネルと入力画像の間の畳み込み処理は，各画素$\bm{p} = (x,y)$（画像の左上が原点の$x,y$座標系）の周辺において独立に行われる．
カーネル窓内の局所座標系を$(i,j)$と表す（カーネル中心を原点とする）．そして，スライディングウィンドウ処理中はカーネル中心$(i,j)=(0,0)$が，現在の参照座標$\bm{p} = (x,y)$に対応する．このとき，サイズ$(2k+1) \times (2k+1)$の画像フィルタ上の局所座標$(i,j)$における値$\bm{W}(i,j)$は，目的ごとにあらかじめ決められた固定値のカーネルを使用する（例：$x$方向のSobelフィルタ，ガウシアンフィルタなど）．
3.1.1 スライディングウィンドウ処理でのフィルタの走査順
以下の図4のように，画像データの原点がある左上から$x$方向に順に走査し，各行の走査が終われば次の行順に移っていき，最終的に画像の右下で終える：
また，走査する画像上の全位置$\bm{p}$において，画像$I$とカーネル$W^{\prime}$の間の畳み込みは，離散系の畳み込み(2.1節)の2次元版を用いて，以下の演算により行う（既に2.3.1節で見た式と同じ）：
\begin{equation} (I * W^{\prime})(x,y) = \frac{1}{S} \sum^{k}_{i=-k} \sum^{k}_{j=-k} W^{\prime}(i,j) \cdot I(x+i, y+j) \tag{3.1}\end{equation}
また，カーネルを先に反転させておかない表現の場合は，以下のようにカーネル$W(-i,-j)$とカーネル中心に対して反対側に位置するより$I(x+i, y+j)$の2つの位置で積を取る（こちらも既に2.3.1節で見た式と同じ）：
\begin{equation} (I * W)(x,y) = \frac{1}{S} \sum^{k}_{i=-k} \sum^{k}_{j=-k} W(-i,-j) \cdot I(x+i, y+j)\tag{3.2}\end{equation}
3.2 画像境界周辺のパディング
スライディングウィンドウの走査処理中は，カーネル中心の参照画素$\bm{p}$の座標が入力画像$I$の端の境界あたりにある際に，画像領域外にカーネルの一部がはみだしてしまい，$I(x+i, y+j)$の値が用意できない．
この対処法として，こ画像のパディング(padding)と呼ぶの「境界外の仮想画素も画素値を用意しておく処理」の．事前に画像の外の周辺の(仮想)画素を指定した画素値をコピーして埋めておき，カーネルによる畳み込み演算が境界付近でも実施できるように準備しておく．
空間ドメインのフィルタリングでもパディングで前処理しておくのは良いが，周波数空間での離散フーリエ変換のために巡回畳み込み(circular convolution)を行う際にも必要となる処理である．
パディング処理では，以下のような方法で値を埋めることが多い．画像フィルタリングの前処理でパディング用いる場合は，このうち特にゼロパディングを使う機会が多い：
- ゼロパディング：入力画像の外側の画素値を，カーネル計算や窓計算ができる幅の分だけ，外周を全て0値の画素で埋める．CNNでも各畳み込み層で頻繁に使われる．
- 鏡面(reflect)パディング：境界線を中心に，対称的な鏡のような画素値で埋める．
- 反復(replicate)パディング：画像端の境界の画素値をずっと繰り返すして埋める．
- 巻き付け(wrap)パディング：同じ画像のコピーが何度も左右に続いていくように画素値で埋める（巻き寿司の表面に周期的なテクスチャが貼られた場合を想像すると良い）．
OpenCVでは copyMakeBorder関数でパディングを実施できるので，Python OpenCVチュートリアルに描かれてあるcv2.copyMakeBorderの実施結果比較画像が参考になる．
3.3 関数としての信号：空間周波数と巡回畳み込み．
畳み込み演算では，音響信号などを入力とする「1次元の（サンプリングされた）デジタル信号の処理」に対して使用する場合は，「関数=デジタル信号」であるとみなして「信号同士の畳み込み信号を求めている」と捉えなおすと，元の「関数による畳み込み演算」の定義とイメージ一致させられるので直感的に理解しやすい．
同様に，画像処理の「2次元」離散畳み込みも，入力「画像信号」とカーネル「画像信号」の間で演算を行っていると捉えなおすと理解しやすい．すなわち，画像もデジタル信号の１種とみなし，$x$軸と$y軸$を，それぞれ時間軸$t$のようにみなすことで，２次元の（波のような）データであると解釈でき，周波数ドメインでの演算や解析のイメージもつかみやすくなる．関連記事の「画像フィルタリング：(2)周波数フィルタリング」でより詳しく述べるが，画像の$x$方向の画素値系列や$y$方向の画素値系列を1次元の波形信号とみなして，周波数ドメインでの処理や解析などを行う際の周波数のことを(伝統的に)「空間周波数」とも呼ぶ．
また，この後説明する画像フィルタリングや，音響信号の窓関数フィルタなどの場合は，例えばカーネルの定義域が$(-3,3)$のようになっていると，各$t$における積分範囲も$(-3,3)$の有限範囲となり，畳み込みの定義の通りに無限遠まで積分することができない．しかし，この有限定義行きの場合でも（空間周波数的な）周期的ドメインを仮定し，画像の一端と他端のあいだの連続性をみる 巡回畳み込み(circular convolution)を用いれば，無限遠まで積分しなくとも問題なくなる．
4. まとめ
この記事では，画像のフィルタリングにおける「畳み込み」処理について紹介した
2節では，まず3節の準備として，1次元連続空間における畳み込みの定義を紹介した．その後3節では，(サンプリングされた) 2次元離散画像における畳み込みについて紹介した．
畳み込み操作では，注目画素の周辺局所ウィンドウ内において，範囲内の画素値をカーネル値で「巻いて，積分する」ことで，出力値を得る操作である．また，注目画素に対して，周辺のアクセス順を対称にすると「相関」操作となり，つまりは「畳み込み」と「相関」は対称関係にあることも述べた (ちなみにCNNの畳み込み層では，この関係を利用して，相互相関を畳み込みの代わりに用いる)．
関連書籍
- Concise Computer Vision, Reinhard Klette, Springer, 2014.
- ディジタル画像処理 [改訂第二版] , ディジタル画像処理編集委員会， 公益財団法人画像情報教育振興協会（CG-ARTS協会）, 2020.
- 音響学入門ペディア, 日本音響学会(編), コロナ社, 2017．