多次元離散畳み込み

信号処理において、多次元離散畳み込みとは、 n次元格子上の2 つの関数fとgの間の数学的演算を指し、 n次元の 3 番目の関数を生成します。多次元離散畳み込みは、ユークリッド空間上の関数の多次元畳み込みの離散類似物です。また、グループがn 組の整数の グループである場合、グループ上の畳み込みの特殊なケースでもあります。

1 次元の場合と同様に、畳み込み演算を表すためにアスタリスクが使用されます。特定の演算の次元数は、アスタリスクの数に反映されます。たとえば、M次元畳み込みは、 M 個のアスタリスクで表されます。以下は、離散信号の 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})}$

離散値信号の場合、この畳み込みは次のように直接計算できます。

${\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 次元畳み込み演算子のいくつかの特性を示します。これらは- 次元の信号にも拡張できることに注意してください。 ${\displaystyle N}$

交換法則:

${\displaystyle x**h=h**x}$

関連プロパティ:

${\displaystyle (x**h)**g=x**(h**g)}$

分配法則:

${\displaystyle x**(h+g)=(x**h)+(x**g)}$

これらの特性は、以下の図でどのように使用されているかを示しています。インパルス応答 を持つフィルタに何らかの入力が入り、次にインパルス応答 を持つ別のフィルタに入ると、出力は で与えられます。最初のフィルタの出力が で与えられると仮定すると、次のようになります。 ${\displaystyle x(n_{1},n_{2})}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle g(n_{1},n_{2})}$${\displaystyle y(n_{1},n_{2})}$${\displaystyle w(n_{1},n_{2})}$

${\displaystyle w=x**h}$

さらに、その中間関数は 2 番目のフィルタのインパルス応答と畳み込まれ、出力は次のように表すことができます。

${\displaystyle y=w**g=(x**h)**g}$

結合法則を使用すると、次のように書き直すことができます。

${\displaystyle y=x**(h**g)}$

つまり、カスケードシステムの等価インパルス応答は次のように表されます。

${\displaystyle h_{eq}=h**g}$

以下に示す一連の並列システムに対しても同様の分析を行うことができます。

この場合、次のことが明らかです。

${\displaystyle y=(x**h)+(x**g)}$

分配法則を使用すると、次のことが証明されます。

${\displaystyle y=x**(h+g)}$

つまり、並列システムの場合、等価インパルス応答は次のように提供されます。

${\displaystyle h_{eq}=h+g}$

カスケードシステムと並列システムの両方における等価インパルス応答は、フィルタの数を持つシステムに一般化できます。^[1]${\displaystyle N}$

1 次元の畳み込みは、フィルタ システムのインパルス応答がわかっていれば、線形シフト不変 (LSI) システム ( LTI システム理論を参照) の入力と出力を簡単に比較できるという強力な発見でした。この概念は多次元畳み込みにも適用され、多次元フィルタのインパルス応答がわかっていれば、システムの入力と出力を直接比較できるようになります。今日のデジタル世界で転送される信号の多くは、画像やビデオなど複数の次元であるため、これは大きな意味を持ちます。1 次元畳み込みと同様に、多次元畳み込みを使用すると、特定の入力信号に対する LSI システムの出力を計算できます。

たとえば、電気光学ノイズの影響を受けるワイヤレス ネットワーク経由で送信される画像について考えてみましょう。考えられるノイズ源には、チャネル伝送、アナログ/デジタル コンバータ、およびイメージ センサーのエラーなどがあります。通常、チャネルまたはセンサーによって発生するノイズは、空間的に独立した高周波信号成分を作成し、実際の画像に任意の明るいスポットと暗いスポットとして変換されます。画像データから高周波スペクトル成分を取り除くには、ローパス フィルターの周波数応答を掛け合わせます。これは、畳み込み定理に基づいて、時間/空間領域の信号をローパス フィルターのインパルス応答で畳み込むことと同等です。これを行うインパルス応答をいくつか以下に示します。^[2]

多次元畳み込みは、スペクトル成分をフィルタリングするだけでなく、エッジ検出とスムージングも実行できます。これもまた、入力画像との畳み込みに使用されるインパルス応答の値に完全に依存します。エッジ検出の一般的なインパルス応答を以下に示します。

画像処理に加えて、多次元畳み込みはさまざまなアプリケーションを可能にするために実装できます。フィルタはデジタル通信システムで広く使用されているため、多次元データを送信する必要があるシステムはフィルタリング技術によってサポートされています。これは、リアルタイムビデオ処理、ニューラルネットワーク分析、デジタル地球物理学的データ分析などで使用されています。^[3]

画像やビデオのキャプチャまたは転送アプリケーション中に発生する典型的な歪みの 1 つは、ローパス フィルタリング プロセスによって発生するぼかしです。発生するぼかしは、ガウス ローパス フィルタリングを使用してモデル化できます。

信号は、複数の1次元信号の積として表すことができる場合、分離可能であると言われます。 ^[1]数学的には、これは次のように表現されます。

${\displaystyle x(n_{1},n_{2},...,n_{M})=x(n_{1})x(n_{2})...x(n_{M})}$

すぐに認識できる分離可能な信号には、単位ステップ関数やディラックデルタインパルス関数などがあります。

${\displaystyle u(n_{1},n_{2},...,n_{M})=u(n_{1})u(n_{2})...u(n_{M})}$ （単位ステップ関数）

${\displaystyle \delta (n_{1},n_{2},...,n_{M})=\delta (n_{1})\delta (n_{2})...\delta (n_{M})}$ （ディラックデルタインパルス関数）

畳み込みは線形演算です。したがって、分離可能な信号の多次元畳み込みは、多数の 1 次元畳み込みの積として表現できます。たとえば、xとhが両方とも分離可能な関数である場合を考えてみましょう。

${\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})}$

分離可能性の特性を適用すると、これは次のように書き直すことができます。

${\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次元畳み込みの積に簡約されることがすぐに分かります。

${\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次元信号の畳み込みに拡張できます。

${\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 次元畳み込み を計算することによって多次元畳み込みを計算できます。${\displaystyle n_{M}}$

行列法は、畳み込み内の信号の 1 つが分離可能な場合に適用できます。この方法では、分離可能性の特性を利用して、各サンプルを直接計算するよりも計算効率の高い 2 つの多次元信号の畳み込みを計算する方法を実現します (信号の 1 つが分離可能である場合)。^[4] 以下は、行列分解アプローチ (通常は分離可能な信号) の背後にある数学的推論を示しています。 ${\displaystyle h(n_{1},n_{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}}}$

の値は、 の共有値を持つ他の値を評価するときに再利用できるようになりました。 ${\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}$${\displaystyle y}$${\displaystyle n_{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}}}$

したがって、最初に のすべての行に対して畳み込み演算を実行し、次に のすべての列に対して畳み込み演算を実行することで、結果として得られる畳み込みを効果的に計算できます。このアプローチは、コンピュータ プロセッサ内でメモリがどのようにアクセスされるかを考慮することで、さらに最適化できます。 ${\displaystyle x(n_{1},n_{2})}$

プロセッサは、特定の操作に必要な信号データをロードします。最近のプロセッサでは、データはメモリからプロセッサのキャッシュにロードされます。プロセッサのキャッシュはメモリよりもアクセス時間が高速です。キャッシュ自体は行に分割されています。キャッシュ ラインがメモリからロードされると、複数のデータ オペランドが一度にロードされます。信号データの行がプロセッサのキャッシュ内に完全に収まる最適化されたケースを考えてみましょう。この特定のプロセッサは、行方向には効率的にデータにアクセスできますが、列方向にはアクセスできません。同じ列の異なるデータ オペランドは異なるキャッシュ ラインにあるためです。^[5]メモリへのアクセス方法を利用するには、データ セットを転置してから行方向にアクセスする方が、列方向にアクセスするよりも効率的です。アルゴリズムは次のようになります。

1. 分離可能な2次元信号を2つの1次元信号に分離し、${\displaystyle h(n_{1},n_{2})}$${\displaystyle h_{1}(n_{1})}$${\displaystyle h_{2}(n_{2})}$
2. 信号の水平成分に対して行方向の畳み込みを実行して、${\displaystyle x(n_{1},n_{2})}$${\displaystyle h_{1}(n_{1})}$${\displaystyle g(n_{1},n_{2})}$
3. ステップ 2 で得られた信号の垂直成分を転置します。${\displaystyle g(n_{1},n_{2})}$
4. 転置された垂直成分に対して行方向の畳み込みを実行して、目的の出力を得る。${\displaystyle g(n_{1},n_{2})}$${\displaystyle y(n_{1},n_{2})}$

サイズの画像がサイズ の分離可能なフィルタを通過する場合について検討します。画像自体は分離可能ではありません。フィルタの分離可能性を利用せずに直接畳み込みアプローチを使用して結果を計算すると、約 回乗算と加算が必要になります。フィルタの分離可能性を考慮すると、フィルタリングは 2 つのステップで実行できます。最初のステップでは乗算と加算が行われ、2 番目のステップでは が行われ、合計で 回または回乗算と加算が行われます。^[6]直接畳み込みと分離可能畳み込みの計算の複雑さの比較を次の図に示します。 ${\displaystyle X\times Y}$${\displaystyle J\times K}$${\displaystyle XYJK}$${\displaystyle XYJ}$${\displaystyle XYK}$${\displaystyle XYJ+XYK}$${\displaystyle XY(J+K)}$

多次元信号に対する循環畳み込みアプローチの前提は、畳み込み定理と離散フーリエ変換（DFT）の関係を開発することであり、これを使用して2つの有限範囲の離散値信号間の畳み込みを計算することができます。^[7]

1 次元信号の場合、畳み込み定理によれば、 2 つの信号間の畳み込みのフーリエ変換は、その 2 つの信号のフーリエ変換の積に等しいとされています。したがって、時間領域での畳み込みは、周波数領域での乗算に等しくなります。数学的には、この原理は次のように表現されます。この原理は、多次元信号の処理に直接拡張できます。この特性は、次のように離散フーリエ変換(DFT)での使用に簡単に拡張できます(線形畳み込みは、サイズ の円周畳み込み演算を表すために が使用されている円周畳み込みに置き換えられることに注意してください)。 $${\displaystyle y(n)=h(n)*x(n)\longleftrightarrow Y(\omega )=H(\omega )X(\omega )}$$$${\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 }$${\displaystyle N}$

${\displaystyle y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)}$

多次元の信号を扱う場合:ここでの円畳み込みのサイズは になります。 $${\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})}$$${\displaystyle N_{1},N_{2},...,N_{M}}$

循環畳み込みアプローチを使用する理由は、それが DFT に基づいているからです。循環畳み込みの前提は、入力信号の DFT を取得し、それらを掛け合わせてから、逆 DFT を取得することです。エイリアシングが発生しないように、十分に大きな DFT を使用するように注意する必要があります。有限範囲の信号を処理する場合、DFT は数値的に計算可能です。このアプローチの利点の 1 つは、DFT と逆 DFT を取得する必要があるため、高速フーリエ変換(FFT) などの効率的なアルゴリズムを利用できることです。循環畳み込みは、周波数領域だけでなく、時間/空間領域でも計算できます。

2 つの有限範囲信号xとhが取得される次のケースを考えます。両方の信号に対して、対応する DFT は次のようになります。

${\displaystyle x(n_{1},n_{2})\longleftrightarrow X(k_{1},k_{2})}$ そして ${\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}$

のサポート領域はであり、 のサポート領域はであり、 です。 ${\displaystyle x(n_{1},n_{2})}$${\displaystyle 0\leq n_{1}\leq P_{1}-1}$${\displaystyle 0\leq n_{2}\leq P_{2}-1}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle 0\leq n_{1}\leq Q_{1}-1}$${\displaystyle 0\leq n_{2}\leq Q_{2}-1}$

これら 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})}$$${\displaystyle x(n_{1},n_{2})}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle y_{linear}(n_{1},n_{2})}$

$${\displaystyle 0\leq n_{1}\leq P_{1}+Q_{1}-1}$$$${\displaystyle 0\leq n_{2}\leq P_{2}+Q_{2}-1}$$2 つの信号のサポート領域に基づいて、両方の信号に同じサイズの DFT を使用する必要があるため、サイズのDFT を使用する必要があります。信号の範囲よりも大きい DFT サイズが必要な場合は、必要な長さに達するまで信号にゼロが埋め込まれます。DFT を乗算し、その結果に対して逆 DFT を実行すると、結果として得られる循環畳み込みは次のようになります。 ${\displaystyle N_{1}\times N_{2}}$${\displaystyle N_{1}\geq \max(P_{1},Q_{1})}$${\displaystyle N_{2}\geq \max(P_{2},Q_{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 ]}}$のために${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

${\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\}}$

結果は、線形畳み込みの結果の空間的にエイリアスされたバージョンになります。これは次のように表現できます。 ${\displaystyle y_{circular}(n_{1},n_{2})}$${\displaystyle y_{linear}(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}}}$

次に、空間的にエイリアスされたレプリカ間のエイリアスを回避するために、次の条件を満たすように選択する必要があります。 ${\displaystyle N_{1}}$${\displaystyle N_{2}}$

${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$

${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$

これらの条件が満たされると、円畳み込みの結果は線形畳み込みの結果と等しくなります (円畳み込みの主周期をサポート領域としてとらえます)。つまり、次のようになります。

${\displaystyle y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})}$のために${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

畳み込み定理と円畳み込みは、次のように使用して線形畳み込みを実行するのと同等の結果を達成することができる。^[8]

1. 選択して満足して${\displaystyle N_{1}}$${\displaystyle N_{2}}$${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$
2. 信号をゼロパディングし、サイズが一致するようにします${\displaystyle h(n_{1},n_{2})}$${\displaystyle x(n_{1},n_{2})}$${\displaystyle N_{1}\times N_{2}}$
3. 両方のDFTを計算し、${\displaystyle h(n_{1},n_{2})}$${\displaystyle x(n_{1},n_{2})}$
4. DFTの結果を掛け合わせると${\displaystyle Y(k_{1},k_{2})=H(k_{1},k_{2})X(k_{1},k_{2})}$
5. IDFTの結果は、2つの信号に対して線形畳み込みを実行した結果と等しくなります。${\displaystyle Y(k_{1},k_{2})}$

多次元畳み込みを実行する別の方法は、オーバーラップと加算のアプローチです。この方法は、現代のデジタルシステムに固有の膨大なデータ量により、多次元畳み込みに伴う計算の複雑さを軽減するのに役立ちます。^[9]簡潔にするために、2次元の場合を例として使用しますが、同じ概念を複数の次元に拡張できます。

直接計算を使用した 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] 次元が追加されるにつれて、膨大な量の計算とメモリストレージスペースの過剰な使用が問題を引き起こします。ここで、オーバーラップと加算の畳み込み法が登場します。 ${\displaystyle y(n_{1},n_{2})}$

情報ブロック全体に対して畳み込みを実行する代わりに、情報をx次元のより小さなブロックに分割する ことで、FFT が小さくなり、計算の複雑さが軽減され、必要なストレージも少なくなります。これは数学的に次のように表現できます。 ${\displaystyle L_{1}}$${\displaystyle L_{2}}$

${\displaystyle x(n_{1},n_{2})=\sum _{i=1}^{P_{1}}\sum _{j=1}^{P_{2}}x_{ij}(n_{1},n_{2})}$

ここで、 はx入力信号を表します。これは、およびのブロックセグメントの合計です。 ${\displaystyle x(n_{1},n_{2})}$${\displaystyle N_{1}}$${\displaystyle N_{2}}$${\displaystyle P_{1}P_{2}}$${\displaystyle P_{1}=N_{1}/L_{1}}$${\displaystyle P_{2}=N_{2}/L_{2}}$

出力信号を生成するために、2 次元畳み込みが実行されます。

${\displaystyle y(n_{1},n_{2})=x(n_{1},n_{2})**h(n_{1},n_{2})}$

を に代入すると、次のようになります。 ${\displaystyle x(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 高速畳み込みと統合されているため、オーバーラップ加算はより高速に実行され、メモリ効率の高い方法であり、大規模な多次元データ セットに実用的です。

をサイズ とします。 ${\displaystyle h(n_{1},n_{2})}$${\displaystyle M_{1}\times M_{2}}$

1. 入力を重複しない次元のブロックに分割します。${\displaystyle x(n_{1},n_{2})}$${\displaystyle L_{1}\times L_{2}}$
2. 次元が ( ) ( )となるようにゼロパディングします。${\displaystyle h(n_{1},n_{2})}$${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times }$${\displaystyle L_{2}+M_{2}-1}$
3. DFT を使用して を取得します。${\displaystyle H(k_{1},k_{2})}$
4. 各入力ブロックについて:
   1. ゼロパッドは次元 ( ) ( ) になります。${\displaystyle x_{ij}(n_{1},n_{2})}$${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times }$${\displaystyle L_{2}+M_{2}-1}$
   2. 各ブロックの離散フーリエ変換を行うと、 が得られます。${\displaystyle X_{ij}(k_{1},k_{2})}$
   3. 掛け算して になります。${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}$
   4. を逆離散フーリエ変換してを取得します。${\displaystyle Y_{ij}(k_{1},k_{2})}$${\displaystyle y_{ij}(n_{1},n_{2})}$
5. 重複部分を見つけて、最後のサンプルと最初のサンプル を加算して結果を取得します。^[11]${\displaystyle y(n_{1},n_{2})}$${\displaystyle (M_{1}-1)}$${\displaystyle \times }$ ${\displaystyle (M_{2}-1)}$${\displaystyle y_{ij}(n_{1},n_{2})}$${\displaystyle (M_{1}-1)}$ ${\displaystyle \times }$${\displaystyle (M_{2}-1)}$${\displaystyle y_{i+1,j+1}(n_{1},n_{2})}$

オーバーラップ加算法をより明確に視覚化するために、次の図では、この方法をグラフィカルに検証します。入力には、次の図に示すように、垂直方向と水平方向の両方に長さ N の正方形領域サポートがあると仮定します。次に、4 つの小さなセグメントに分割され、4 つの小さな正方形で構成されます。集約信号の各ブロックの次元は です。${\displaystyle x(n_{1},n_{2})}$${\displaystyle (N/2)}$ ${\displaystyle \times }$ ${\displaystyle (N/2)}$

次に、各コンポーネントはフィルターのインパルス応答と畳み込まれます。コンピューターに十分なメモリとリソースがあり、同時に保存および計算できる限り、これらの畳み込みのそれぞれをコンピューター上で並列化できるため、このような実装の利点がここで視覚化されることに注意してください。

下の図では、左側の最初のグラフは、入力の成分と対応するインパルス応答との畳み込みを表しています。その右側では、入力がインパルス応答と畳み込まれています。 ${\displaystyle x_{0,0}}$${\displaystyle h(n_{1},n_{2})}$${\displaystyle x_{1,0}}$${\displaystyle h(n_{1},n_{2})}$

他の 2 つの入力に対しても同じプロセスが実行され、畳み込みを形成するためにそれらが累積されます。これは左側に示されています。

フィルタのインパルス応答が 両次元でのサポート領域を持つと仮定します。これは、各畳み込みがと の両方向の次元を持つ信号を畳み込むことを意味し、各畳み込みの長さが次式に等しいため、重複が発生します (青で強調表示)。 ${\displaystyle h(n_{1},n_{2})}$${\displaystyle (N/8)}$${\displaystyle (N/2)}$ ${\displaystyle \times }$ ${\displaystyle (N/8)}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$

${\displaystyle (N/2)}$ ${\displaystyle +}$${\displaystyle (N/8)}$ ${\displaystyle -}$${\displaystyle 1}$=${\displaystyle (5/8)N-1}$

両方向で。明るい青の部分は2つの隣接する畳み込みの重なりに対応し、暗い青の部分は4つの畳み込みすべての重なりに対応しています。これらの重なり部分はすべて畳み込みに加えて加算され、複合畳み込みを形成します。^[12]${\displaystyle y(n_{1},n_{2})}$

オーバーラップと保存法は、オーバーラップと追加法と同様に、離散時間畳み込みに関連する計算の複雑さを軽減するために使用されます。この方法を FFT と組み合わせると、大量のデータをデジタル システムでフィルタリングしながら、大量のデータ配列の計算に必要なメモリ領域を最小限に抑えることができます。

オーバーラップと保存法は、いくつかの注目すべき例外を除いて、オーバーラップと加算法と非常によく似ています。オーバーラップ加算法では離散時間信号の線形畳み込みが行われますが、オーバーラップ保存法では循環畳み込みの原理が用いられます。さらに、オーバーラップと保存法ではインパルス応答のゼロ パディングを 1 回だけ使用しますが、オーバーラップ加算法では各入力コンポーネントの畳み込みごとにゼロ パディングが行われます。オーバーラップ加算法のように時間領域のエイリアシングを防ぐためにゼロ パディングを使用する代わりに、オーバーラップ保存法ではエイリアシングのすべてのポイントを破棄し、前のデータを 1 つのブロックに保存して、次のブロックの畳み込みにコピーします。

1次元では、2つの方法のパフォーマンスとストレージメトリックの違いは最小限です。ただし、多次元畳み込みの場合、速度とストレージ能力の点で、オーバーラップ保存法がオーバーラップ追加法よりも優れています。^[13]オーバーラップと追加のケースと同様に、この手順は2次元の場合を呼び出しますが、すべての多次元手順に簡単に拡張できます。

をサイズ とします。 ${\displaystyle h(n_{1},n_{2})}$${\displaystyle M_{1}\times M_{2}}$

1. 両方の次元の入力信号の先頭にゼロの列 と行を挿入します。${\displaystyle (M_{1}-1)}$${\displaystyle (M_{2}-1)}$${\displaystyle x(n_{1},n_{2})}$
2. 対応する信号を、各2次元ブロックが だけ重なり合う次元の重なり合うセグメント ( ) ( ) に分割します。${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times }$${\displaystyle L_{2}+M_{2}-1}$${\displaystyle (M_{1}-1)}$ ${\displaystyle \times }$ ${\displaystyle (M_{2}-1)}$
3. 次元が ( ) ( )となるようにゼロパディングします。${\displaystyle h(n_{1},n_{2})}$${\displaystyle L_{1}+M_{1}-1}$${\displaystyle \times }$${\displaystyle L_{2}+M_{2}-1}$
4. DFT を使用して を取得します。${\displaystyle H(k_{1},k_{2})}$
5. 各入力ブロックについて:
   1. 各ブロックの離散フーリエ変換を行うと、 が得られます。${\displaystyle X_{ij}(k_{1},k_{2})}$
   2. 掛け算して になります。${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2})H(k_{1},k_{2})}$
   3. を逆離散フーリエ変換してを取得します。${\displaystyle Y_{ij}(k_{1},k_{2})}$${\displaystyle y_{ij}(n_{1},n_{2})}$
   4. 各出力ブロックの最初のものを削除します。${\displaystyle (M_{1}-1)}$${\displaystyle \times }$${\displaystyle (M_{2}-1)}$${\displaystyle y_{ij}(n_{1},n_{2})}$
6. 各出力ブロックの最後のサンプルを添付して見つけます。^[11]${\displaystyle y(n_{1},n_{2})}$${\displaystyle (L_{1}\times L_{2})}$${\displaystyle y_{ij}(n_{1},n_{2})}$

行-列分解と同様に、らせん変換は、1 次元の畳み込み特性と演算子を組み込むことによって多次元畳み込みを計算します。ただし、信号の分離可能性を使用する代わりに、直交座標空間をらせん座標空間にマッピングして、多次元空間から 1 次元空間へのマッピングを可能にします。

らせん変換を理解するには、まず多次元畳み込みを 1 次元畳み込みに分解する方法を理解することが役立ちます。畳み込み対象となる 2 つの信号が と で、出力 が生成されると仮定します。これは次のように表されます。 ${\displaystyle X_{M\times N}}$${\displaystyle Y_{K\times L}}$${\displaystyle Z_{(M-K+1)\times (N-L+1)}}$

${\displaystyle Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(i-m,j-n)}$

次に、各入力が同等の次元を持つように、両次元の各入力をゼロパディングする2つの行列が作成されます。

${\displaystyle \mathbf {X'} ={\begin{bmatrix}X&0\\0&0\\\end{bmatrix}}}$ そして ${\displaystyle \mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}}$