背景
画像処理100本ノックに挑戦中です。Q.32からフーリエ変換の話に入ります。いい機会なので少し離散フーリエ変換について考察します。
周期性と離散性
サンプリング定理と画像処理における補間において示しましたが、連続信号を離散サンプリングすると、そのフーリエ変換は元のフーリエ変換を周期的に並べたものになります。同様に考えれば、連続信号を周期的に並べれば、そのフーリエ変換は離散的になります(フーリエ級数)。周期性と離散性の関係は表裏一体にあると言えます。
フーリエ変換を計算機で取り扱うために
今、連続信号$f(x)$があるとします。これのフーリエ変換を計算機で数値的に行いたいとします。数値的に取り扱うためには、$f(x)$を離散サンプリングする必要があります。
f(x) \to \tilde f(x) = f(x)\sum_{n=-\infty}^{\infty}\delta(x-nS)
$S$はサンプリング間隔です。フーリエ変換は
\begin{eqnarray}
\tilde F(\nu) &=& \frac{1}{S}\sum_{n=-\infty}^\infty F(\nu-\frac{n}{S})
\end{eqnarray}
となります。つまり、元の信号のフーリエ変換を周期的に並べたものになります。数値的に得るためには
\begin{eqnarray}
\tilde F(\nu) &=& \int f(x)\sum_{n=-\infty}^{\infty}\delta(x-nS)e^{-2\pi i \nu x}dx
\end{eqnarray}
を実行する必要があります。$-\infty \sim \infty$の範囲の和を取ることは計算機では出来ませんが、$f(x)$がある有限の範囲でのみ値を持つと仮定すればその範囲内の$n$で和を取れば問題ありません。サンプリング間隔を十分に小さく取れば$F(\nu)$を求めることが出来ます。
ここで取り扱ったように、実空間での信号を離散サンプリングしたフーリエ変換を離散時間フーリエ変換というそうです。
離散フーリエ変換
フーリエ空間でのフィルタ処理を考えれば、フーリエ空間上でも離散的である方が便利です。双方のサンプリング間隔が細かければそれでも情報は失わないはずです。
そこで、実空間における連続信号を離散化 & 周期化します。
f(x) \to g(x) = \sum_n f(x-nX)\sum_m \delta(x-mS)
フーリエ変換すれば
G(\nu) = \frac{1}{SX}\sum_{n,m}\delta(\nu-\frac{n}{S}-\frac{m}{X})F(\nu-\frac{n}{S})
となります。これから、
\nu = n'/S + m'/X
のみ値を持つことがわかります。また、$G$は$1/S$の周期関数であることがわかります。$S=1$という単位系を採用すると、
\nu = m'/X \;(0 \leq m' < X)
のみ考えればよいことがわかります。さて、具体的にフーリエ変換を評価する方法を考えます。
G(\nu) = \int g(x)e^{-2\pi i\nu x}dx = \sum_{n,m}f(m-nX)e^{-2\pi i \nu m}= \sum_{n,m}f(m)e^{-2\pi i \nu(m+nX)}
より
G(\nu = m'/X) = \sum_{n,m}f(m)e^{-2\pi i \frac{m'}{X}(m+nX)} = \sum_{m}f(m)e^{-2\pi i \frac{m'}{X}m}
となります。これが離散フーリエ変換の式に他なりません。
$F(\nu)$を推定するためには、実空間において信号を非周期化します。つまり矩形関数でフィルタをかけます。これはフーリエ空間で言えばsinc関数を畳み込むことと等価です。実空間で離散的なままなので、フーリエ空間での周期性はなくなりませんが、1周期だけ取り出せば連続関数$F(\nu)$の推定が出来ます。
まとめ
離散フーリエ変換は、離散信号に対する厳密なフーリエ変換であり、連続信号に対する近似的なフーリエ変換と言えます。近似精度を上げるためには台形公式等を使えばよいと思われます。ただし、サンプリング間隔が十分に小さければ、sinc関数を畳み込むことにより、正確なフーリエ変換が求まります。