dft_comparison.py ドキュメント

概要

本プログラムは、離散フーリエ変換 (DFT) および高速フーリエ変換 (FFT) のパフォーマンスを比較するためのベンチマークスクリプトです。計算リソース(CPUおよびGPU)や実装手法(純粋なPython実装、NumbaによるJITコンパイル、NumPy、CuPy)の違いによる実行時間の差異を計測します。

スクリプトは以下の2つのモードで動作します。

  • 1Dシグナルモード: スクリプト内部で生成した1次元の合成信号に対し、サンプル数 \(N\) を変動させながらDFT/FFTの実行時間と相対誤差を計測し、スケーリング特性を評価します。

  • 2D画像モード: ユーザーが指定した画像ファイルを入力とし、RGBチャネルの2次元FFTを実行します。CPUとGPUの実行時間を比較し、各チャネルの周波数スペクトルを可視化します。

理論的背景

1次元離散フーリエ変換 (DFT)

長さ \(N\) の複素数シグナル \(y_j\) に対する離散フーリエ変換は、以下の式で定義されます。

\[X_k = \sum_{j=0}^{N-1} y_j \exp\left(-i \frac{2\pi j k}{N}\right)\]

この計算を定義通りに素朴に実行した場合、時間計算量は \(\mathcal{O}(N^2)\) となります。一方、高速フーリエ変換 (FFT) アルゴリズムを用いた場合、計算量は \(\mathcal{O}(N \log N)\) に削減されます。本スクリプトでは、純粋なPython実装およびNumba実装のDFT関数において \(\mathcal{O}(N^2)\) のアルゴリズムを直接実行し、その非効率性をNumPyやCuPyのFFTアルゴリズムと比較します。

合成信号の生成

1Dシグナルモードにおけるベンチマーク用のテスト信号 \(y(x)\) は、区間 \([0, 1)\) に正規化された座標 \(x\) を用いて、複数の正弦波と正規分布ノイズを合成することで生成されます。

\[y(x) = \sin\left(2\pi \cdot 7x + \frac{\pi}{4}\right) + 0.3\sin\left(2\pi \cdot 31x + \frac{\pi}{3}\right) + 0.5\sin\left(2\pi \cdot 113x + \frac{\pi}{6}\right) + 0.02 \cdot \mathcal{N}(0, 1)\]

2次元画像の周波数スペクトル可視化

2D画像モードにおいて、RGB画像の各チャネルに2次元FFTを適用して得られた複素数スペクトル \(C(u, v)\) は、振幅のダイナミックレンジが非常に大きいため、可視化のために対数変換が行われます。

\[S(u, v) = \log(1 + |C(u, v)|)\]

さらに、画像として表示(0から1の範囲)するために、最小値 \(S_{min}\) と最大値 \(S_{max}\) を用いたMin-Max正規化が適用されます。

\[S_{norm}(u, v) = \frac{S(u, v) - S_{min}}{S_{max} - S_{min}}\]

動作要件・依存ライブラリ

本スクリプトは標準ライブラリに加えて、計算および可視化のための必須ライブラリ、および特定の機能を有効にするためのオプションライブラリを使用します。

  • 必須ライブラリ

    • numpy: 信号生成、配列操作、およびCPU上でのFFT計算 (np.fft) に使用。

    • matplotlib: ベンチマーク結果のグラフ作成、および画像スペクトルの可視化に使用。

  • オプションライブラリ(インストールされている場合のみ有効化)

    • psutil: システム情報(物理コア数、システムメモリ量)の取得に使用。

    • numba: 独自のPython DFT関数をJITコンパイル (@njit) して高速化するために使用。

    • cupy: CUDA対応GPUを用いた高速なFFT計算 (cp.fft) に使用。

    • Pillow: 2D画像モードを使用する際、画像ファイルの読み込みとRGB変換に使用。

入出力仕様

入力

  • 1Dシグナルモード: 追加の入力ファイルは不要です。コマンドライン引数に従い、メモリ上で動的に信号配列が構築されます。

  • 2D画像モード: コマンドラインの第一引数として、入力対象の画像ファイルパス(例: image.png)を指定します。

出力 (1Dシグナルモード)

デフォルトでは dft_benchmark というプレフィックスでファイルが出力されます(--output-prefix で変更可能)。

  • dft_benchmark.csv 各サンプル数 \(N\) ごとの計測結果を保存したCSVファイル。 出力列: N, python_dft_s, numba_dft_s, cpu_fft_s, gpu_fft_kernel_s, gpu_fft_total_s, python_rel_error, numba_rel_error, gpu_rel_error

  • dft_benchmark.png サンプル数 \(N\) と中央値実行時間 (s) の関係をプロットした両対数グラフ (Log-Log plot)。

出力 (2D画像モード)

入力画像ファイル名の拡張子を除いた部分(例: image)をプレフィックスとして出力されます。

  • image_fft.csv 画像のメタデータおよび各デバイスでのFFT実行時間を保存したCSVファイル。 出力列: file, width, height, channels, cpu_fft_s, gpu_fft_kernel_s, gpu_fft_total_s, gpu_rel_error

  • image_fft_spectrum.png 入力された元画像と、RGBの各チャネルごとに計算され、低周波成分を中央にシフト (np.fft.fftshift) した2次元パワースペクトル画像を2x2のグリッドで可視化した画像ファイル。

実行例

1Dシグナルモードのデフォルト設定(サンプル数を変動させながら計測)で実行する場合。

python dft_comparison.py

1Dシグナルモードにおいて、計測する最大サンプル数 \(N\) を \(1048576\) に設定し、GPU計算を意図的に無効化して実行する場合。

python dft_comparison.py --nmax 1048576 --no-gpu

2D画像モードとして画像ファイルを指定し、測定の繰り返し回数を10回に増やし、処理完了後に画面上にプロットウィンドウを表示 (--show) する場合。

python dft_comparison.py sample_image.png --repeat 10 --show