Mathematical operation in signal processing
信号処理において、 多次元離散畳み込みとは、 n 次元格子 上の2つの関数 f と g の間の数学的演算を指し、同様に n次元の第3の関数を生成します。多次元離散畳み込みは、 ユークリッド空間 上の関数の 多次元畳み込み の離散的な類似物です。また、 n 組の整数からなる 群 を群とする 場合には、 群上の畳み込み の特殊なケースでもあります。
意味
問題の定義と基礎 1次元の場合と同様に、畳み込み演算を表すためにアスタリスクが用いられます。演算の次元数はアスタリスクの数で表されます。例えば、 M次元畳み込みは M 個のアスタリスクで表されます 。以下は、 離散信号の M次元畳み込みを表しています。
y ( n 1 , n 2 , . . . , n M ) = x ( n 1 , n 2 , . . . , n M ) ∗ ⋯ M ∗ h ( n 1 , n 2 , . . . , n M ) {\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})}
離散値信号の場合、この畳み込みは次のように直接計算できます。
∑ k 1 = − ∞ ∞ ∑ k 2 = − ∞ ∞ . . . ∑ k M = − ∞ ∞ h ( k 1 , k 2 , . . . , k M ) x ( n 1 − k 1 , n 2 − k 2 , . . . , n M − k M ) {\displaystyle \sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }...\sum _{k_{M}=-\infty }^{\infty }h(k_{1},k_{2},...,k_{M})x(n_{1}-k_{1},n_{2}-k_{2},...,n_{M}-k_{M})}
離散多次元畳み込みの結果の出力サポート領域は、2 つの入力信号のサイズとサポート領域に基づいて決定されます。
2つの単純な2次元信号間の畳み込みの可視化 2次元畳み込み演算子のいくつかの性質を列挙する。これらは - 次元信号にも拡張できる点に注意されたい。 N {\displaystyle N}
交換法則:
x ∗ ∗ h = h ∗ ∗ x {\displaystyle x**h=h**x}
関連プロパティ:
( x ∗ ∗ h ) ∗ ∗ g = x ∗ ∗ ( h ∗ ∗ g ) {\displaystyle (x**h)**g=x**(h**g)}
分配法則:
x ∗ ∗ ( h + g ) = ( x ∗ ∗ h ) + ( x ∗ ∗ g ) {\displaystyle x**(h+g)=(x**h)+(x**g)}
これらの特性は、下の図でどのように用いられているかを示しています。 インパルス応答 を持つフィルタに入力が与えられ 、次にインパルス応答 を持つ別のフィルタに入力が与えられると 、出力は で与えられます 。最初のフィルタの出力が で与えられると仮定すると 、次の式が成り立ちます。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} g ( n 1 , n 2 ) {\displaystyle g(n_{1},n_{2})} y ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})} w ( n 1 , n 2 ) {\displaystyle w(n_{1},n_{2})}
w = x ∗ ∗ h {\displaystyle w=x**h}
さらに、その中間関数は 2 番目のフィルタのインパルス応答と畳み込まれ、出力は次のように表すことができます。
y = w ∗ ∗ g = ( x ∗ ∗ h ) ∗ ∗ g {\displaystyle y=w**g=(x**h)**g}
結合法則を使用すると、次のように書き直すことができます。
y = x ∗ ∗ ( h ∗ ∗ g ) {\displaystyle y=x**(h**g)}
つまり、カスケードシステムの等価インパルス応答は次のように表されます。
h e q = h ∗ ∗ g {\displaystyle h_{eq}=h**g}
どちらの図もカスケード接続されたシステムを表しています。フィルターの順序は出力に影響を与えないことに注意してください。 以下に示す一連の並列システムに対しても同様の分析を実行できます。
並列フィルターのセットを備えたシステム。 この場合、次のことは明らかです。
y = ( x ∗ ∗ h ) + ( x ∗ ∗ g ) {\displaystyle y=(x**h)+(x**g)}
分配法則を使用すると、次のことが証明されます。
y = x ∗ ∗ ( h + g ) {\displaystyle y=x**(h+g)}
つまり、並列システムの場合、等価インパルス応答は次のように提供されます。
h e q = h + g {\displaystyle h_{eq}=h+g}
カスケードシステムと並列システムの両方における等価インパルス応答は、 フィルタの数を持つシステムに一般化できます。 [1] N {\displaystyle N}
動機と応用 1 次元の畳み込みは、フィルタ システムのインパルス応答がわかっていれば、線形シフト不変 (LSI) システム ( LTI システム理論 を参照) の入力と出力を簡単に比較できるという強力な発見でした。この概念は多次元畳み込みにも引き継がれ、多次元フィルタのインパルス応答がわかっていれば、システムの入力と出力を直接比較できるようになります。今日のデジタルの世界で転送される信号の多くは、画像や動画など多次元であるため、これは大きな意味を持ちます。1 次元畳み込みと同様に、多次元畳み込みを使用すると、特定の入力信号に対する LSI システムの出力を計算できます。
例えば、電気光学ノイズの影響を受ける無線ネットワークを介して送信される画像を考えてみましょう。ノイズ源としては、チャネル伝送、アナログ/デジタル変換器、 画像センサーの エラーなどが考えられます。通常、チャネルやセンサーによって発生するノイズは、空間的に独立した高周波信号成分を生み出し、実際の画像上に任意の明暗の斑点として現れます。画像データから高周波スペクトル成分を取り除くには、ローパスフィルタの周波数応答を掛け合わせます。これは、畳み込み定理に基づき、時間/空間領域における信号をローパスフィルタのインパルス応答で畳み込むことと等価です。以下に、そのようなインパルス応答の例をいくつか示します。 [2]
典型的な多次元ローパスフィルタのインパルス応答 多次元畳み込みは、スペクトル成分の除去に加え、 エッジ検出 と平滑化も実現できます。これもまた、入力画像との畳み込みに用いられるインパルス応答の値に完全に依存します。エッジ検出における典型的なインパルス応答を以下に示します。
エッジ検出の典型的なインパルス応答 元の画像（左）とエッジ検出フィルタを通過した後の画像（右） 画像処理に加えて、多次元畳み込みは様々なアプリケーションに実装できます。フィルタはデジタル通信システムで広く使用されているため、多次元データを伝送する必要があるシステムには、フィルタリング技術が不可欠です。これは、リアルタイムビデオ処理、ニューラルネットワーク解析、デジタル地球物理データ解析など、様々な分野で利用されています。 [3]
画像や動画のキャプチャや伝送アプリケーションで発生する典型的な歪みの一つに、ローパスフィルタリング処理によって生じるぼかしがあります。このぼかしは、ガウスローパスフィルタリングを用いてモデル化できます。
ガウス畳み込みを使用して実行された元の画像（左）とぼかし画像（右）
分離可能な信号による行-列分解
分離可能な信号 信号が複数の1次元信号の積として表せる場合、その信号は 分離 可能と言われます。 [1] 数学的には、これは次のように表現されます。
x ( n 1 , n 2 , . . . , n M ) = x ( n 1 ) x ( n 2 ) . . . x ( n M ) {\displaystyle x(n_{1},n_{2},...,n_{M})=x(n_{1})x(n_{2})...x(n_{M})}
すぐに認識できる分離可能な信号としては、単位 ステップ関数 、ディラックデルタインパルス関数などがあります。
u ( n 1 , n 2 , . . . , n M ) = u ( n 1 ) u ( n 2 ) . . . u ( n M ) {\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})} （単位ステップ関数）
δ ( n 1 , n 2 , . . . , n M ) = δ ( n 1 ) δ ( n 2 ) . . . δ ( n M ) {\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{M})} （ディラックデルタインパルス関数）
畳み込みは線形演算です。したがって、分離可能な信号の多次元畳み込みは、多数の1次元畳み込みの積として表すことができます。例えば、 x と h がどちらも分離可能な関数である場合を考えてみましょう。
x ( n 1 , n 2 ) ∗ ∗ h ( n 1 , n 2 ) = ∑ k 1 = − ∞ ∞ ∑ k 2 = − ∞ ∞ h ( k 1 , k 2 ) x ( n 1 − k 1 , n 2 − k 2 ) {\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}
分離可能性の特性を適用すると、これは次のように書き直すことができます。
x ( n 1 , n 2 ) ∗ ∗ h ( n 1 , n 2 ) = ( ∑ k 1 = − ∞ ∞ h ( k 1 ) x ( n 1 − k 1 ) ) ( ∑ k 2 = − ∞ ∞ h ( k 2 ) x ( n 2 − k 2 ) ) {\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg (}\sum _{k_{1}=-\infty }^{\infty }h(k_{1})x(n_{1}-k_{1}){\bigg )}{\bigg (}\sum _{k_{2}=-\infty }^{\infty }h(k_{2})x(n_{2}-k_{2}){\bigg )}}
これは1次元畳み込みの積に簡約されることが容易に分かる。
x ( n 1 , n 2 ) ∗ ∗ h ( n 1 , n 2 ) = [ x ( n 1 ) ∗ h ( n 1 ) ] [ x ( n 2 ) ∗ h ( n 2 ) ] {\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}}
この結論は、次のように2つの分離可能なM 次元信号の畳み込みに拡張できます 。
x ( n 1 , n 2 , . . . , n M ) ∗ ⋯ M ∗ h ( n 1 , n 2 , . . . , n M ) = [ x ( n 1 ) ∗ h ( n 1 ) ] [ x ( n 2 ) ∗ h ( n 2 ) ] . . . [ x ( n M ) ∗ h ( n M ) ] {\displaystyle x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}...{\bigg [}x(n_{M})*h(n_{M}){\bigg ]}}
したがって、2 つの信号が分離可能な場合は、 1 次元畳み込み を計算することによって多次元畳み込みを計算できます。 n M {\displaystyle n_{M}}
行-列分解 行列法は、畳み込みの対象となる信号の1つが分離可能な場合に適用できます。この手法は、分離可能性の性質を利用することで、2つの多次元信号の畳み込みを計算する手法を実現し、各サンプルを直接計算するよりも計算効率を高めます（信号の1つが分離可能である場合）。 [4] 以下は、行列分解アプローチ（通常 は分離可能な信号）の背後にある数学的根拠を示しています。 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})}
y ( n 1 , n 2 ) = ∑ k 1 = − ∞ ∞ ∑ k 2 = − ∞ ∞ h ( k 1 , k 2 ) x ( n 1 − k 1 , n 2 − k 2 ) = ∑ k 1 = − ∞ ∞ ∑ k 2 = − ∞ ∞ h 1 ( k 1 ) h 2 ( k 2 ) x ( n 1 − k 1 , n 2 − k 2 ) = ∑ k 1 = − ∞ ∞ h 1 ( k 1 ) [ ∑ k 2 = − ∞ ∞ h 2 ( k 2 ) x ( n 1 − k 1 , n 2 − k 2 ) ] {\displaystyle {\begin{aligned}y(n_{1},n_{2})&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h_{1}(k_{1})h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}
の値は、 の共有値を持つ 他の値を評価するときに再利用できるようになりました 。 ∑ k 2 = − ∞ ∞ h 2 ( k 2 ) x ( n 1 − k 1 , n 2 − k 2 ) {\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})} y {\displaystyle y} n 2 {\displaystyle n_{2}}
y ( n 1 + δ , n 2 ) = ∑ k 1 = − ∞ ∞ h 1 ( k 1 ) [ ∑ k 2 = − ∞ ∞ h 2 ( k 2 ) x ( n 1 − [ k 1 − δ ] , n 2 − k 2 ) ] = ∑ k 1 = − ∞ ∞ h 1 ( k 1 + δ ) [ ∑ k 2 = − ∞ ∞ h 2 ( k 2 ) x ( n 1 − k 1 , n 2 − k 2 ) ] {\displaystyle {\begin{aligned}y(n_{1}+\delta ,n_{2})&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-[k_{1}-\delta ],n_{2}-k_{2}){\Bigg ]}\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}+\delta ){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}
したがって、畳み込み演算をまず のすべての行に対して実行し 、次に のすべての列に対して実行することで、結果として得られる畳み込みを効率的に計算できます。このアプローチは、コンピュータプロセッサ内でのメモリアクセス方法を考慮することで、さらに最適化できます。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})}
プロセッサは、与えられた操作に必要な信号データをロードします。現代のプロセッサでは、データはメモリからプロセッサのキャッシュにロードされます。キャッシュはメモリよりもアクセス時間が高速です。キャッシュ自体はラインに分割されています。キャッシュラインがメモリからロードされると、複数のデータオペランドが一度にロードされます。信号データの行がプロセッサのキャッシュ内に完全に収まる最適化されたケースを考えてみましょう。この特定のプロセッサは、行方向には効率的にデータにアクセスできますが、列方向にはアクセスできません。これは、同じ列内の異なるデータオペランドが異なるキャッシュラインに存在するためです。 [5] メモリへのアクセス方法を活用するには、データセットを転置してから行方向にアクセスする方が、列方向にアクセスするよりも効率的です。アルゴリズムは次のようになります。
分離可能な2次元信号を 2つの1次元信号に分離し 、 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} h 1 ( n 1 ) {\displaystyle h_{1}(n_{1})} h 2 ( n 2 ) {\displaystyle h_{2}(n_{2})} 信号の水平成分に対して行方向の畳み込みを実行し て 、 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} h 1 ( n 1 ) {\displaystyle h_{1}(n_{1})} g ( n 1 , n 2 ) {\displaystyle g(n_{1},n_{2})} ステップ 2 で得られた 信号の垂直成分を転置します。 g ( n 1 , n 2 ) {\displaystyle g(n_{1},n_{2})} 転置された垂直成分に対して行方向の畳み込みを実行して、 目的の出力を得る。 g ( n 1 , n 2 ) {\displaystyle g(n_{1},n_{2})} y ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})}
行-列分解による計算の高速化 サイズの画像が サイズ の 分離可能なフィルタ を通過する場合について検討します 。画像自体は分離可能ではありません。フィルタの分離可能性を利用せずに直接畳み込みアプローチを使用して結果を計算すると、約 回分の 乗算と加算が必要になります。フィルタの分離可能性を考慮すると、フィルタリングは2段階で実行できます。最初のステップでは 乗算と加算が行われ、2番目のステップ では が行われ、合計で 回 または回分の 乗算と加算が行われます。 [6] 直接畳み込みと分離可能な畳み込みの計算の複雑さの比較を次の図に示します。 X × Y {\displaystyle X\times Y} J × K {\displaystyle J\times K} X Y J K {\displaystyle XYJK} X Y J {\displaystyle XYJ} X Y K {\displaystyle XYK} X Y J + X Y K {\displaystyle XYJ+XYK} X Y ( J + K ) {\displaystyle XY(J+K)}
10 x 10の画像を J x K （ J = K） のフィルタに 通す計算回数は、 1から 10 まで 変化する。
離散値多次元信号の循環畳み込み 多次元信号に対する循環畳み込み アプローチの前提は、 畳み込み定理 と 離散フーリエ変換 （DFT）の関係を開発することであり、 これを使用して2つの有限範囲の離散値信号間の畳み込みを計算することができます。 [7]
多次元における畳み込み定理 1次元信号の場合、 畳み込み定理は 、2つの信号間の畳み込みの フーリエ変換は、 それらの2つの信号のフーリエ変換の積に等しいことを述べています。したがって、時間領域における畳み込みは、周波数領域における乗算に等しいです。数学的には、この原理は以下のように表現されます。 この原理は、多次元信号の処理に直接拡張できます。この特性は 、離散フーリエ変換 （DFT）を用いる場合にも容易に拡張できます （線形畳み込みは、 サイズ の円周畳み込み演算を表すために が使用される円周畳み込みに置き換えられることに留意してください ）。 y ( n ) = h ( n ) ∗ x ( n ) ⟷ Y ( ω ) = H ( ω ) X ( ω ) {\displaystyle y(n)=h(n)*x(n)\longleftrightarrow Y(\omega )=H(\omega )X(\omega )} y ( n 1 , n 2 , . . . , n M ) = h ( n 1 , n 2 , . . . , n M ) ∗ ⋯ M ∗ x ( n 1 , n 2 , . . . , n M ) ⟷ Y ( ω 1 , ω 2 , . . . , ω M ) = H ( ω 1 , ω 2 , . . . , ω M ) X ( ω 1 , ω 2 , . . . , ω M ) {\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(\omega _{1},\omega _{2},...,\omega _{M})=H(\omega _{1},\omega _{2},...,\omega _{M})X(\omega _{1},\omega _{2},...,\omega _{M})} ⊗ {\displaystyle \otimes } N {\displaystyle N}
y ( n ) = h ( n ) ⊗ x ( n ) ⟷ Y ( k ) = H ( k ) X ( k ) {\displaystyle y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)}
多次元の信号を扱う場合: ここでの循環畳み込みのサイズは になります 。 y ( n 1 , n 2 , . . . , n M ) = h ( n 1 , n 2 , . . . , n M ) ⊗ ⋯ M ⊗ x ( n 1 , n 2 , . . . , n M ) ⟷ Y ( k 1 , k 2 , . . . , k M ) = H ( k 1 , k 2 , . . . , k M ) X ( k 1 , k 2 , . . . , k M ) {\displaystyle y(n_{1},n_{2},...,n_{M})=h(n_{1},n_{2},...,n_{M})\otimes {\overset {M}{\cdots }}\otimes x(n_{1},n_{2},...,n_{M})\longleftrightarrow Y(k_{1},k_{2},...,k_{M})=H(k_{1},k_{2},...,k_{M})X(k_{1},k_{2},...,k_{M})} N 1 , N 2 , . . . , N M {\displaystyle N_{1},N_{2},...,N_{M}}
循環畳み込みアプローチ 巡回畳み込みアプローチを使用する理由は、それがDFTに基づいているからです。巡回畳み込みの前提は、入力信号のDFTをそれぞれ乗算し、逆DFTを実行することです。エイリアシングが発生しないように、十分に大きなDFTを使用するように注意する必要があります。有限範囲の信号を扱う場合、DFTは数値的に計算可能です。このアプローチの利点の一つは、DFTと逆DFTを実行する必要があるため、 高速フーリエ変換 （FFT）などの効率的なアルゴリズムを利用できることです。巡回畳み込みは、周波数領域だけでなく、時間/空間領域でも計算できます。
2M 次元信号 による巡回畳み込みのブロック図
エイリアシングを回避するためのDFTサイズの選択 有限範囲の信号 x と h が2つ入力される次のようなケースを考えてみましょう。どちらの信号にも、対応するDFTは以下のように存在します。
x ( n 1 , n 2 ) ⟷ X ( k 1 , k 2 ) {\displaystyle x(n_{1},n_{2})\longleftrightarrow X(k_{1},k_{2})} そして h ( n 1 , n 2 ) ⟷ H ( k 1 , k 2 ) {\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}
のサポート領域は および で あり、 のサポート領域は および です 。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} 0 ≤ n 1 ≤ P 1 − 1 {\displaystyle 0\leq n_{1}\leq P_{1}-1} 0 ≤ n 2 ≤ P 2 − 1 {\displaystyle 0\leq n_{2}\leq P_{2}-1} h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} 0 ≤ n 1 ≤ Q 1 − 1 {\displaystyle 0\leq n_{1}\leq Q_{1}-1} 0 ≤ n 2 ≤ Q 2 − 1 {\displaystyle 0\leq n_{2}\leq Q_{2}-1}
これら 2 つの信号の線形畳み込みは次のように表されます。 および のサポート領域が与えられている場合 、 のサポート領域は 次のように表されます。 y l i n e a r ( n 1 , n 2 ) = ∑ m 1 ∑ m 2 h ( m 1 , m 2 ) x ( n 1 − m 1 , n 2 − m 2 ) {\displaystyle y_{linear}(n_{1},n_{2})=\sum _{m_{1}}\sum _{m_{2}}h(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})} x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} y l i n e a r ( n 1 , n 2 ) {\displaystyle y_{linear}(n_{1},n_{2})}
0 ≤ n 1 ≤ P 1 + Q 1 − 1 {\displaystyle 0\leq n_{1}\leq P_{1}+Q_{1}-1} 0 ≤ n 2 ≤ P 2 + Q 2 − 1 {\displaystyle 0\leq n_{2}\leq P_{2}+Q_{2}-1} 2つの信号のサポート領域に基づき、両方の信号に同じサイズのDFTを 使用する必要があるため 、サイズの DFTを使用する必要があります。信号の長さよりも大きなDFTサイズが必要な場合は、必要な長さに達するまで信号にゼロパディングを行います。DFTを乗算し、その結果に対して逆DFTを実行すると、結果として得られる巡回畳み込みは次のように表されます。 N 1 × N 2 {\displaystyle N_{1}\times N_{2}} N 1 ≥ max ( P 1 , Q 1 ) {\displaystyle N_{1}\geq \max(P_{1},Q_{1})} N 2 ≥ max ( P 2 , Q 2 ) {\displaystyle N_{2}\geq \max(P_{2},Q_{2})}
y c i r c u l a r ( n 1 , n 2 ) = ∑ r 1 ∑ r 2 [ ∑ m 1 = 0 Q 1 − 1 ∑ m 2 = 0 Q 2 − 1 h ( m 1 , m 2 ) x ( n 1 − m 1 − r 1 N 1 , n 2 − m 2 − r 2 N 2 ) ] {\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}{\Bigg [}\sum _{m_{1}=0}^{Q_{1}-1}\sum _{m_{2}=0}^{Q_{2}-1}h(m_{1},m_{2})x(n_{1}-m_{1}-r_{1}N_{1},n_{2}-m_{2}-r_{2}N_{2}){\Bigg ]}} のために ( n 1 , n 2 ) ∈ R N 1 N 2 {\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}
R N 1 N 2 ≜ { ( n 1 , n 2 ) : 0 ≤ n 1 ≤ N 1 − 1 , 0 ≤ n 2 ≤ N 2 − 1 } {\displaystyle R_{N_{1}N_{2}}\triangleq \{(n_{1},n_{2}):0\leq n_{1}\leq N_{1}-1,0\leq n_{2}\leq N_{2}-1\}}
結果は、 線形畳み込みの結果の空間エイリアシング版となります 。これは次のように表すことができます。 y c i r c u l a r ( n 1 , n 2 ) {\displaystyle y_{circular}(n_{1},n_{2})} y l i n e a r ( n 1 , n 2 ) {\displaystyle y_{linear}(n_{1},n_{2})}
y c i r c u l a r ( n 1 , n 2 ) = ∑ r 1 ∑ r 2 y l i n e a r ( n 1 − r 1 N 1 , n 2 − r 2 N 2 ) f o r ( n 1 , n 2 ) ∈ R N 1 N 2 {\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}y_{linear}(n_{1}-r_{1}N_{1},n_{2}-r_{2}N_{2}){\mathrm {\,\,\,for\,\,\,} }(n_{1},n_{2})\in R_{N_{1}N_{2}}}
次に、空間的にエイリアスされたレプリカ間のエイリアシングを回避するために、 次 の条件を満たすように選択する必要があります。 N 1 {\displaystyle N_{1}} N 2 {\displaystyle N_{2}}
N 1 ≥ P 1 + Q 1 − 1 {\displaystyle N_{1}\geq P_{1}+Q_{1}-1}
N 2 ≥ P 2 + Q 2 − 1 {\displaystyle N_{2}\geq P_{2}+Q_{2}-1}
これらの条件が満たされる場合、円畳み込みの結果は線形畳み込みの結果と等しくなります（円畳み込みの主周期をサポート領域とみなします）。つまり、
y c i r c u l a r ( n 1 , n 2 ) = y l i n e a r ( n 1 , n 2 ) {\displaystyle y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})} のために ( n 1 , n 2 ) ∈ R N 1 N 2 {\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}
DFTを用いた手順の概要 畳み込み定理と円畳み込みは次のように使用して、線形畳み込みを実行するのと同等の結果を得ることができます。 [8]
選択し て 満足し て N 1 {\displaystyle N_{1}} N 2 {\displaystyle N_{2}} N 1 ≥ P 1 + Q 1 − 1 {\displaystyle N_{1}\geq P_{1}+Q_{1}-1} N 2 ≥ P 2 + Q 2 − 1 {\displaystyle N_{2}\geq P_{2}+Q_{2}-1} 信号をゼロパディングし 、 サイズ が一致するようにする h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} N 1 × N 2 {\displaystyle N_{1}\times N_{2}} 両方のDFTを計算し 、 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} DFTの結果を掛け合わせると Y ( k 1 , k 2 ) = H ( k 1 , k 2 ) X ( k 1 , k 2 ) {\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})} IDFTの結果は 、2つの信号に対して線形畳み込みを実行した結果と等しくなります。 Y ( k 1 , k 2 ) {\displaystyle Y(k_{1},k_{2})}
重ねて追加 多次元畳み込みを実行するもう一つの方法は、 オーバーラップ・アンド・アド・ アプローチです。この方法は、現代のデジタルシステムに固有の膨大なデータ量に起因する、多次元畳み込みに伴う計算の複雑さを軽減するのに役立ちます。 [9] 簡潔にするために2次元の例を使用していますが、同じ概念を多次元にも拡張できます。
直接計算を使用した 2 次元畳み込みを考えてみましょう。
y ( n 1 , n 2 ) = ∑ k 1 = − ∞ ∞ ∑ k 2 = − ∞ ∞ x ( n 1 − k 1 , n 2 − k 2 ) h ( k 1 , k 2 ) {\displaystyle y(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }x(n_{1}-k_{1},n_{2}-k_{2})h(k_{1},k_{2})}
出力信号が N個の非ゼロ係数を持ち、インパルス応答がM個の非ゼロサンプルを持つと仮定すると、この直接計算にはMN回の乗算とMN - 1回の加算が必要になります。代わりにFFTを使用する場合、フィルタの周波数応答と入力のフーリエ変換をメモリに保存する必要があります。 [10] 次元が追加されるにつれて、膨大な計算量とメモリストレージスペースの過剰な使用が問題を引き起こします。ここで、オーバーラップ・アンド・アド畳み込み法が登場します。 y ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})}
小さな畳み込みブロックへの分解 情報ブロック全体に対して畳み込みを行う代わりに、情報を x次元のより小さなブロックに分割することで 、FFTの規模が縮小され、計算の複雑さが軽減され、必要なストレージ容量も削減されます。これは数学的に次のように表現できます。 L 1 {\displaystyle L_{1}} L 2 {\displaystyle L_{2}}
x ( n 1 , n 2 ) = ∑ i = 1 P 1 ∑ j = 1 P 2 x i j ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})}
ここで、 は x入力信号 を表します。これは、 および のブロック セグメント の合計です 。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} N 1 {\displaystyle N_{1}} N 2 {\displaystyle N_{2}} P 1 P 2 {\displaystyle P_{1}P_{2}} P 1 = N 1 / L 1 {\displaystyle P_{1}=N_{1}/L_{1}} P 2 = N 2 / L 2 {\displaystyle P_{2}=N_{2}/L_{2}}
出力信号を生成するために、2次元畳み込みが実行されます。
y ( n 1 , n 2 ) = x ( n 1 , n 2 ) ∗ ∗ h ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})=x(n_{1},n_{2})**h(n_{1},n_{2})}
を代入すると、 次のようになります。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})}
y ( n 1 , n 2 ) = ∑ i = 1 P 1 ∑ j = 1 P 2 x i j ( n 1 , n 2 ) ∗ ∗ h ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})**h(n_{1},n_{2})}
この畳み込みは直接畳み込みを行うよりも複雑になりますが、FFT 高速畳み込みと統合されているため、オーバーラップ加算はより高速に実行され、メモリ効率の高い方法となり、大規模な多次元データ セットに実用的になります。
手順の詳細 を の大きさとし ます 。 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} M 1 × M 2 {\displaystyle M_{1}\times M_{2}}
入力を 重複しない次元ブロックに分割します 。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} L 1 × L 2 {\displaystyle L_{1}\times L_{2}} 次元が ( ) ( )となるように ゼロパディングします。 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} L 1 + M 1 − 1 {\displaystyle L_{1}+M_{1}-1} × {\displaystyle \times } L 2 + M 2 − 1 {\displaystyle L_{2}+M_{2}-1} DFT を使用して を取得します 。 H ( k 1 , k 2 ) {\displaystyle H(k_{1},k_{2})} 各入力ブロックについて: ゼロパッド の寸法は ( ) ( ) です。 x i j ( n 1 , n 2 ) {\displaystyle x_{ij}(n_{1},n_{2})} L 1 + M 1 − 1 {\displaystyle L_{1}+M_{1}-1} × {\displaystyle \times } L 2 + M 2 − 1 {\displaystyle L_{2}+M_{2}-1} 各ブロックの離散フーリエ変換を行うと、次のようになります 。 X i j ( k 1 , k 2 ) {\displaystyle X_{ij}(k_{1},k_{2})} 掛け算して になります 。 Y i j ( k 1 , k 2 ) = X i j ( k 1 , k 2 ) H ( k 1 , k 2 ) {\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})} を逆離散フーリエ変換して を 取得します 。 Y i j ( k 1 , k 2 ) {\displaystyle Y_{ij}(k_{1},k_{2})} y i j ( n 1 , n 2 ) {\displaystyle y_{ij}(n_{1},n_{2})} 重複部分を見つけ て、最後の サンプル と最初の サンプル を加算して 結果を取得します。 [11] y ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})} ( M 1 − 1 ) {\displaystyle (M_{1}-1)} × {\displaystyle \times } ( M 2 − 1 ) {\displaystyle (M_{2}-1)} y i j ( n 1 , n 2 ) {\displaystyle y_{ij}(n_{1},n_{2})} ( M 1 − 1 ) {\displaystyle (M_{1}-1)} × {\displaystyle \times } ( M 2 − 1 ) {\displaystyle (M_{2}-1)} y i + 1 , j + 1 ( n 1 , n 2 ) {\displaystyle y_{i+1,j+1}(n_{1},n_{2})}
図解による操作方法 オーバーラップ加算法をより明確に視覚化するために、以下の 図ではこの手法をグラフィカルに検証します。入力は、下図に示すように、縦横ともに長さ N の正方形領域サポートを持つものとします。この領域は、4 つの小さなセグメントに分割され、4 つの小さな正方形で構成されます。集約信号の各ブロックは、次元 を持ちます 。 x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} ( N / 2 ) {\displaystyle (N/2)} × {\displaystyle \times } ( N / 2 ) {\displaystyle (N/2)}
分解された入力信号 次に、各成分はフィルタのインパルス応答と畳み込み演算されます。この実装の利点は、コンピュータが十分なメモリとリソースを備え、同時に保存と計算を行うことができれば、各畳み込みをコンピュータ上で並列化できることです。
下の図では、左側の最初のグラフは、入力の成分と対応 するインパルス応答との畳み込みを表しています 。その右側では、入力が インパルス応答と畳み込まれています 。 x 0 , 0 {\displaystyle x_{0,0}} h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} x 1 , 0 {\displaystyle x_{1,0}} h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})}
インパルス応答による個別コンポーネント畳み込み 重なり合う部分を強調表示した各コンポーネントの畳み込み 他の2つの入力に対しても同様の処理が行われ、それらが加算されて畳み込みが形成されます。これは左側に示されています。
フィルタのインパルス応答が 両次元で のサポート領域を持つと仮定します。これは、各畳み込みが と の 両方向の次元を持つ信号を畳み込むことを意味します 。これにより、各畳み込みの長さが以下の式に等しいため、重なりが生じます（青色で強調表示）。 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} ( N / 8 ) {\displaystyle (N/8)} ( N / 2 ) {\displaystyle (N/2)} × {\displaystyle \times } ( N / 8 ) {\displaystyle (N/8)} n 1 {\displaystyle n_{1}} n 2 {\displaystyle n_{2}}
( N / 2 ) {\displaystyle (N/2)} + {\displaystyle +} ( N / 8 ) {\displaystyle (N/8)} − {\displaystyle -} 1 {\displaystyle 1} ＝ ( 5 / 8 ) N − 1 {\displaystyle (5/8)N-1}
両方向で。明るい青色の部分は隣接する2つの畳み込みの重なりに対応し、暗い青色の部分は4つの畳み込みすべての重なりに対応しています。これらの重なり部分はすべて畳み込みに加えて加算され、複合畳み込みを形成します 。 [12] y ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})}
重ねて保存 オーバーラップ＆セーブ法は、オーバーラップ＆加算法と同様に、離散時間畳み込みに伴う計算量を削減するために使用されます。この手法をFFTと組み合わせることで、膨大な量のデータをデジタルシステムでフィルタリングしながら、膨大なデータ配列の計算に必要なメモリ空間を最小限に抑えることができます。
重ねて追加する比較 オーバーラップ・アンド・セーブ法は、いくつかの注目すべき例外を除けば、オーバーラップ・アンド・アド法と非常によく似ています。オーバーラップ・アド法は離散時間信号の線形畳み込みを行うのに対し、オーバーラップ・セーブ法は巡回畳み込みの原理を利用します。さらに、オーバーラップ・アンド・セーブ法ではインパルス応答のゼロパディングを一度だけ行うのに対し、オーバーラップ・アド法では各入力成分の畳み込みごとにゼロパディングを行います。オーバーラップ・アド法のように時間領域エイリアシングを防ぐためにゼロパディングを使用するのに対し、オーバーラップ・セーブ法ではエイリアシングの発生点をすべて破棄し、前のデータを1つのブロックに保存して、次のブロックの畳み込みにコピーします。
1次元の場合、2つの手法のパフォーマンスとストレージ容量の差はわずかです。しかし、多次元畳み込みの場合、速度とストレージ容量の点で、オーバーラップ・セーブ法の方がオーバーラップ・アド法よりも優れています。 [13] オーバーラップ・アド法の場合と同様に、この手順は2次元の場合を想定していますが、すべての多次元手順に簡単に拡張できます。
手順の詳細 を の大きさとし ます 。 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} M 1 × M 2 {\displaystyle M_{1}\times M_{2}}
両方の次元 の入力信号の先頭にゼロの 列と行 を挿入します。 ( M 1 − 1 ) {\displaystyle (M_{1}-1)} ( M 2 − 1 ) {\displaystyle (M_{2}-1)} x ( n 1 , n 2 ) {\displaystyle x(n_{1},n_{2})} 対応する信号を、 各2次元ブロックが だけ重なり合う次元の重なり合うセグメント ( ) ( ) に分割します 。 L 1 + M 1 − 1 {\displaystyle L_{1}+M_{1}-1} × {\displaystyle \times } L 2 + M 2 − 1 {\displaystyle L_{2}+M_{2}-1} ( M 1 − 1 ) {\displaystyle (M_{1}-1)} × {\displaystyle \times } ( M 2 − 1 ) {\displaystyle (M_{2}-1)} 次元が ( ) ( )となるように ゼロパディングします。 h ( n 1 , n 2 ) {\displaystyle h(n_{1},n_{2})} L 1 + M 1 − 1 {\displaystyle L_{1}+M_{1}-1} × {\displaystyle \times } L 2 + M 2 − 1 {\displaystyle L_{2}+M_{2}-1} DFT を使用して を取得します 。 H ( k 1 , k 2 ) {\displaystyle H(k_{1},k_{2})} 各入力ブロックについて: 各ブロックの離散フーリエ変換を行うと、次のようになります 。 X i j ( k 1 , k 2 ) {\displaystyle X_{ij}(k_{1},k_{2})} 掛け算して になります 。 Y i j ( k 1 , k 2 ) = X i j ( k 1 , k 2 ) H ( k 1 , k 2 ) {\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})} を逆離散フーリエ変換して を 取得します 。 Y i j ( k 1 , k 2 ) {\displaystyle Y_{ij}(k_{1},k_{2})} y i j ( n 1 , n 2 ) {\displaystyle y_{ij}(n_{1},n_{2})} 各出力ブロックの 最初のものを削除します 。 ( M 1 − 1 ) {\displaystyle (M_{1}-1)} × {\displaystyle \times } ( M 2 − 1 ) {\displaystyle (M_{2}-1)} y i j ( n 1 , n 2 ) {\displaystyle y_{ij}(n_{1},n_{2})} 各出力ブロックの 最後のサンプルを添付して 検索します 。 [11] y ( n 1 , n 2 ) {\displaystyle y(n_{1},n_{2})} ( L 1 × L 2 ) {\displaystyle (L_{1}\times L_{2})} y i j ( n 1 , n 2 ) {\displaystyle y_{ij}(n_{1},n_{2})}
ヘリックス変換は、行-列分解と同様に、1次元畳み込みの特性と演算子を組み込むことで多次元畳み込みを計算します。ただし、信号の分離可能性を利用する代わりに、直交座標空間をヘリックス座標空間にマッピングすることで、多次元空間から1次元空間へのマッピングを可能にします。
1次元畳み込み法による多次元畳み込み ヘリックス変換を理解するには、まず多次元畳み込みを1次元畳み込みに分解する方法を理解することが有用です。畳み込み対象となる2つの信号が と である と仮定すると 、出力 が生成されます 。これは次のように表されます。 X M × N {\displaystyle X_{M\times N}} Y K × L {\displaystyle Y_{K\times L}} Z ( M − K + 1 ) × ( N − L + 1 ) {\displaystyle Z_{(M-K+1)\times (N-L+1)}}
Z ( i , j ) = ∑ m = 0 M − 1 ∑ n = 0 N − 1 X ( m , n ) Y ( i − m , j − n ) {\displaystyle Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(i-m,j-n)}
次に、各入力が同等の次元を持つように、両方の次元で各入力をゼロパディングする2つの行列を作成します。
X ′ = [ X 0 0 0 ] {\displaystyle \mathbf {X'} ={\begin{bmatrix}X&0\\0&0\\\end{bmatrix}}} そして Y ′ = [ Y 0 0 0 ] {\displaystyle \mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}}
ここで、各入力行列は次元 になります 。列方向の辞書式順序付けを実装することで、変更された行列をベクトル 、 およびに変換できます。各ベクトル内の重要でないサンプル数を最小化するために、各ベクトルはそれぞれ元の行列 、および の最後のサンプルの後で切り捨てられます。このことから、ベクトル 、 の長さは 次のように与えられます。 ( M + K − 1 ) {\displaystyle (M+K-1)} × {\displaystyle \times } ( N + L − 1 ) {\displaystyle (N+L-1)} X ″ {\displaystyle X''} Y ″ {\displaystyle Y''} X {\displaystyle X} Y {\displaystyle Y} X ″ {\displaystyle X''} Y ″ {\displaystyle Y''}
l X ″ = {\displaystyle l_{X''}=} ( M + K − 1 ) {\displaystyle (M+K-1)} × {\displaystyle \times } ( N − 1 ) {\displaystyle (N-1)} + M {\displaystyle M}
l Y ″ = {\displaystyle l_{Y''}=} ( M + K − 1 ) {\displaystyle (M+K-1)} × {\displaystyle \times } ( L − 1 ) {\displaystyle (L-1)} + K {\displaystyle K}
これら 2 つのベクトルの畳み込みの長さは、 次のように導出および示されます。 Z ″ {\displaystyle Z''}
l Z ″ = {\displaystyle l_{Z''}=} l Y ″ + {\displaystyle l_{Y''}+} l X ″ {\displaystyle l_{X''}} = ( M + K − 1 ) {\displaystyle =(M+K-1)} × {\displaystyle \times } ( N + L − 1 ) {\displaystyle (N+L-1)}
このベクトルの長さは元の行列出力の次元に等しい ため、行列への変換は直接的な変換となります。したがって、ベクトル は 行列形式に再変換され、2次元離散畳み込みの出力が生成されます。 [14] Z {\displaystyle Z} Z ″ {\displaystyle Z''}
らせん状のフィルタリング 2次元直交座標メッシュを扱う場合、いずれかの軸に沿ったフーリエ変換を行うと、2次元平面は円筒形になります。これは、各列または行の端がそれぞれの上面に接して円筒形を形成するためです。らせん状のフィルタリングも同様の動作をしますが、この場合、各列の底部が次の列の上端に接し、らせん状のメッシュになります。これは以下の図に示されています。暗い色のタイルはフィルタ係数を表しています。
2D カテシアン フィルタリング プレーンからヘリックス フィルタへの変換。 この螺旋構造をスライスして1次元のストリップに展開すると、2次元直交座標平面上の同じフィルタ係数が同じ入力データと一致し、等価なフィルタリング方式が得られます。これにより、2次元フィルタが1次元フィルタに展開され、フィルタ係数間にゼロギャップが設けられるため、1次元畳み込み演算子で2次元畳み込みを実行できるようになります。
巻き戻された後の 1 次元フィルタリング ストリップ。 次のようなローパス 2 次元フィルタが使用されたと仮定します。
次に、2 次元空間をらせんに変換すると、1 次元フィルターは次のようになります。
h ( n ) = − 1 , 0 , . . . , 0 , − 1 , 4 , − 1 , 0 , . . . , 0 , − 1 , 0 , . . . {\displaystyle h(n)=-1,0,...,0,-1,4,-1,0,...,0,-1,0,...}
1次元フィルタでは、展開後の1次元フィルタリングストリップに示すように、先頭のゼロが存在しないことに注意してください。1次元ストリップ全体を畳み込むことも可能ですが、先頭のゼロを無視する方が計算コストが低くなります。さらに、これらの後方のゼロ値はメモリに格納する必要がないため、貴重なメモリリソースを節約できます。 [15]
アプリケーション 畳み込みによって再帰フィルタを実装するヘリックス変換は、信号処理の様々な分野で用いられています。周波数領域フーリエ解析は、定数係数と周期的にサンプリングされたデータを持つ定常システムでは有効ですが、不安定なシステムでは困難になります。ヘリックス変換は、3次元の速度変化に対応するデータ処理を可能にする3次元ポストスタックマイグレーションプロセスを可能にします。 [15] さらに、暗黙的な3次元波動場外挿の問題の解決にも応用できます。 [16] その他の応用としては、地震データの正規化、予測誤差フィルタ、地球物理学的デジタルシステムにおけるノイズ減衰などの有用なアルゴリズムが挙げられます。 [14]
ガウス畳み込み 信号処理および画像処理において用いられる多次元畳み込みの応用例の一つに、ガウス畳み込みがあります。これは、入力信号をガウス分布関数で畳み込むことを指します。
2Dガウス可視化、 および μ 1 = μ 2 = 0 {\displaystyle \mu _{1}=\mu _{2}=0} σ 1 = σ 2 = 1 {\displaystyle \sigma _{1}=\sigma _{2}=1} 1 次元の離散値でサンプリングされたガウス分布は、次のように表されます ( と仮定 )。これは、 M 次元の信号に簡単に拡張できます ( は すべての次元で一定であり、 と仮定 )。 認識しておくべき重要な特性の 1 つは、 M 次元信号が次のように分離可能であることです。 この場合、離散値信号とのガウス畳み込みは、次のように表すことができます。 μ = 0 {\displaystyle \mu =0} G ( n ) = 1 2 π σ 2 e − n 2 2 σ 2 {\displaystyle G(n)={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}e^{-{\frac {n^{2}}{2\sigma ^{2}}}}} σ {\displaystyle \sigma } μ 1 = μ 2 = . . . = μ M = 0 {\displaystyle \mu _{1}=\mu _{2}=...=\mu _{M}=0} G ( n 1 , n 2 , . . . , n M ) = 1 ( 2 π ) M / 2 σ M e − ( n 1 2 + n 2 2 + . . . + n M 2 ) 2 σ 2 {\displaystyle G(n_{1},n_{2},...,n_{M})={\frac {1}{(2\pi )^{M/2}\sigma ^{M}}}e^{-{\frac {({n_{1}}^{2}+{n_{2}}^{2}+...+{n_{M}}^{2})}{2\sigma ^{2}}}}} G ( n 1 , n 2 , . . . , n M ) = G ( n 1 ) G ( n 2 ) . . . G ( n M ) {\displaystyle G(n_{1},n_{2},...,n_{M})=G(n_{1})G(n_{2})...G(n_{M})}
y ( n ) = x ( n ) ∗ G ( n ) {\displaystyle y(n)=x(n)*G(n)}
y ( n 1 , n 2 , . . . , n M ) = x ( n 1 , n 2 , . . . , n M ) ∗ . . . ∗ G ( n 1 , n 2 , . . . , n M ) {\displaystyle y(n_{1},n_{2},...,n_{M})=x(n_{1},n_{2},...,n_{M})*...*G(n_{1},n_{2},...,n_{M})}
FIRフィルタによる近似 ガウス畳み込みは、有限インパルス応答 （FIR）フィルタの実装によって効果的に近似できます 。このフィルタは、ガウス畳み込みの切り捨てバージョンを用いて設計されます。2次元フィルタの場合、このようなフィルタの伝達関数は次のように定義されます。 [17]
H ( z 1 , z 2 ) = 1 s ( r 1 , r 2 ) ∑ n 1 = − r 1 r 1 ∑ n 2 = − r 2 r 2 G ( n 1 , n 2 ) z 1 − n 1 z 2 − n 2 {\displaystyle H(z_{1},z_{2})={\frac {1}{s(r_{1},r_{2})}}\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2}){z_{1}}^{-n_{1}}{z_{2}}^{-n_{2}}}
どこ
s ( r 1 , r 2 ) = ∑ n 1 = − r 1 r 1 ∑ n 2 = − r 2 r 2 G ( n 1 , n 2 ) {\displaystyle s(r_{1},r_{2})=\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2})}
と に低い値を選択する と 計算回数は減りますが、近似値の精度は低くなります。一方、高い値を選択すると近似値の精度は高くなりますが、必要な計算回数は多くなります。 r 1 {\displaystyle r_{1}} r 2 {\displaystyle r_{2}}
ボックスフィルタによる近似 ガウス畳み込みを近似する別の方法は、ボックスフィルタを再帰的に通過させることである。1次元畳み込みを近似する場合、このフィルタは次のように定義される。 [17]
H ( z ) = 1 2 r + 1 z r − z − r − 1 1 − z − 1 {\displaystyle H(z)={\frac {1}{2r+1}}{\frac {z^{r}-z^{-r-1}}{1-z^{-}1}}}
通常、正確な近似値を得るために、3回、4回、または5回の再帰パスが実行されます。 [17] r を計算するための提案された方法 は次のようになります。 [18]
σ 2 = 1 12 K ( ( 2 r + 1 ) 2 − 1 ) {\displaystyle \sigma ^{2}={\frac {1}{12}}K((2r+1)^{2}-1)} ここで、 K はフィルターを再帰的に通過する回数です。
そして、ガウス分布は異なる次元間で分離可能であるため、1次元フィルタ（各次元を個別に分離する）を再帰的に通過させることで、多次元ガウス畳み込みの近似が得られる。つまり、 M 次元ガウス畳み込みは、以下の1次元フィルタを再帰的に通過させることで近似できる。
H ( z 1 ) = 1 2 r 1 + 1 z 1 r 1 − z 1 − r 1 − 1 1 − z 1 − 1 {\displaystyle H(z_{1})={\frac {1}{2r_{1}+1}}{\frac {{z_{1}}^{r_{1}}-{z_{1}}^{-r_{1}-1}}{1-{z_{1}}^{-}1}}}
H ( z 2 ) = 1 2 r 2 + 1 z 2 r 2 − z 2 − r 2 − 1 1 − z 2 − 1 {\displaystyle H(z_{2})={\frac {1}{2r_{2}+1}}{\frac {{z_{2}}^{r_{2}}-{z_{2}}^{-r_{2}-1}}{1-{z_{2}}^{-}1}}}
⋮ {\displaystyle \vdots }
H ( z M ) = 1 2 r M + 1 z M r M − z M − r M − 1 1 − z M − 1 {\displaystyle H(z_{M})={\frac {1}{2r_{M}+1}}{\frac {{z_{M}}^{r_{M}}-{z_{M}}^{-r_{M}-1}}{1-{z_{M}}^{-}1}}}
アプリケーション ガウス畳み込みは、信号処理や画像処理において広く用いられています。例えば、画像のぼかしはガウス畳み込みを用いて実現できます 。パラメータはぼかしの強さを制御します。したがって、値が大きいほど、最終的な結果はよりぼやけたものになります。 [19]また、 スケール不変特徴変換 （SIFT）による特徴検出などの コンピュータービジョン アプリケーションでも広く用いられています 。 [20] σ {\displaystyle \sigma }
参照
参考文献 ^ ab Dudgeon, Dan; Mersereau, Russell (1983), 多次元デジタル信号処理 , Prentice-Hall, pp. 21– 22 ^ 「MARBLE: Interactive Vision」. homepages.inf.ed.ac.uk . 2015年11月12日 閲覧 。 ^ 「デジタル地球物理解析の再設計」 www-rohan.sdsu.edu . 2015年11月12日 閲覧。 ^ Sihvo, Tero; Niittylahti, Jarkko (2005年6月5日). 「サブワード並列プロセッサにおける行-列分解に基づく2次元変換最適化」. 国際信号回路システムシンポジウム, 2005. ISSCS 2005. 第1巻. pp. 99– 102. doi :10.1109/ISSCS.2005.1509860. ISBN 978-0-7803-9029-4 。 ^ 「キャッシュ入門」 メリーランド大学コンピュータサイエンス学部。 2015年 11月10日 閲覧 。 ^ Eddins, Steve. 「Separable Convolution」. Mathwords . 2015年 11月10日 閲覧 。 ^ ダッジョン、ダン；マーセロー、ラッセル（1983年）、 多次元デジタル信号処理 、プレンティス・ホール、p. 70 ^ ダッジョン、ダン；マーセロー、ラッセル（1983年）、 多次元デジタル信号処理 、プレンティス・ホール、p. 72 ^ Fernandez, Joseph; Kumar, Vijaya (2013). 相関と畳み込みのための多次元オーバーラップ加算とオーバーラップ保存 . pp. 509– 513. doi :10.1109/ICIP.2013.6738105. ISBN 978-1-4799-2341-0 。 ^ 「2D信号処理」 （PDF） EE502 ：デジタル信号処理 ダブリンシティ大学p.24 。 2015年 11月11日 閲覧 。 ^ ab Kundur, Deepa. 「Overlap-Save and Overlap-Add」 （PDF） . トロント大学. 2015年 11月12日 閲覧 。 ^ 「2D信号処理」 （PDF） EE502 ：デジタル信号処理 ダブリンシティ大学p.26 。 2015年 11月11日 閲覧 。 ^ Kim, Chang; Strintzis, Michael (1980年5月). 「高速多次元畳み込み」. IEEE Transactions on Pattern Analysis and Machine Intelligence . PAMI-2 (3): 269– 273. doi :10.1109/tpami.1980.4767017. ^ ab Naghizadeh, Mostafa; Sacchi, Mauricio (2009年11月). 「1D畳み込みアルゴリズムによる多次元畳み込み」. The Leading Edge . ^ ab Claerbout、ジョン (1998 年 9 月)。 「らせんを介した多次元再帰フィルター」。 地球物理学 。 63 (5): 9. Bibcode :1998Geop...63.1532C。 CiteSeerX 10.1.1.76.1193 。 土井 ：10.1190/1.1444449。 ^ Fomel, Sergey; Claerbout, Jon (1997). 「らせん変換を用いた3次元暗黙波動場外挿の探究」 (PDF) . SEPレポート : 43–60 . 2019年1月4日時点のオリジナル (PDF) からのアーカイブ。 ^ abc Getreuer, Pascal (2013). 「ガウス畳み込みアルゴリズムの概観」 Image Processing on Line . 3 : 286–310 . doi : 10.5201/ipol.2013.87 . ^ Wells, WM (1986). 「カスケード接続された均一フィルタによるガウスフィルタの効率的な合成」 IEEE Transactions on Pattern Analysis and Machine Intelligence . PAMI-8 (2): 234– 239. doi :10.1109/TPAMI.1986.4767776. ^ 「ガウスぼかし - 科学者とエンジニアのための画像処理、パート4」 patrick-fuller.com . 2015年11月12日 閲覧 。 ^ Lowe, DG (1999). 「局所スケール不変特徴からの物体認識」 (PDF) . 国際コンピュータビジョン会議論文集 . 2 : 1150–1157 . 
![{\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f71c141b786fcce579b75251e82759f9cf61ec26)
![{\displaystyle x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}...{\bigg [}x(n_{M})*h(n_{M}){\bigg ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bacab914a45991be9fa6c6a4cfc10fd4dcde7977)
![{\displaystyle {\begin{aligned}y(n_{1},n_{2})&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h_{1}(k_{1})h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f1c70ca8840903d029d57545a0c6c9d2bfb93f)
![{\displaystyle {\begin{aligned}y(n_{1}+\delta ,n_{2})&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-[k_{1}-\delta ],n_{2}-k_{2}){\Bigg ]}\\&=\sum _{k_{1}=-\infty }^{\infty }h_{1}(k_{1}+\delta ){\Bigg [}\sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}){\Bigg ]}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bac2dc2611f396121edc50328a4f3d5890e71236)
![{\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}{\Bigg [}\sum _{m_{1}=0}^{Q_{1}-1}\sum _{m_{2}=0}^{Q_{2}-1}h(m_{1},m_{2})x(n_{1}-m_{1}-r_{1}N_{1},n_{2}-m_{2}-r_{2}N_{2}){\Bigg ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b357fcd547e161addd82bb52a99ec6a92ef013e4)
