画像の周波数データ変換(DFT,FFT,CZT)と逆変換
           (IDFT,IFFT,ICZT)
   離散フーリエ変換: 周波数空間データの更なる応用


高速DFTによる画像の周波数データ形式への変換と、その応用の考察 (2017/02/01)

ダイナミックレンジ・カメラは
 ウェルドビジョン合同会社 
https://www.weldvision.jp/.../734/
製品を利用させて頂いています
目次
0、はじめに
1、基本的な演算の考え方 (離散フーリエ変換)
2、プログラムのソースコードとWindows用実行形式の提供
3、64bit(マルチスレッド対応)版 dft・idft ソフトを使用する時の注意事項
4、変換処理サンプル
5、データファイルとヘダー情報
6、コマンドの機能と使い方
7、高速処理に関しては ...  FFT,IFFT CZT,ICZT (補足情報3, Smart_2D_CZT_ICZT)
8、ライセンス及び免責事項
9、終わりに

   追記 Chirp Z-transform, CZT ICZT について (2023/07/12)
      任意サイズの1次元及び、2次元データ(画像)に対する高速フーリエ変換
      CZT ICZT のソースコード(任意長用 FFTのC言語での実装)も掲載

     CZT の考え方は、任意データ長の FFT に限定されず、1億 や 10億ベクトルといった
     非常に大きな行列の逆行列を高速計算する手法としても応用できそうである。 併せて、
     この応用手法に関しても検討することとする。


0、はじめに

古くから画像処理の技術の1つとして利用されている離散フーリエ変換ですが、
計算量が非常に多いので高速化が難しく利用が限られてしまいます。
周波数領域のデータの特徴性を利用する処理が再認識されて来ている様ですので
2次元の画像(空間領域)データに対するDFT・IDFT処理の実装を考えてみます。

C99 と C11で大きく異なる点としては、複素数型と可変長配列が省略可能なもの
に変更されている点です。その為ここで使用する規格は C99 となります。
以前の C言語の不便さも解消されているので、レガシー C の必要がない限りは
C99 が良い選択だと考えます。


1、基本的な演算の考え方 (離散フーリエ変換)

基本原理は、詳しく説明している他のサイトでの確認をお願いします。
 キーワード:フーリエ変換、離散フーリエ変換、オイラーの公式、三角関数、対称性

DFT/IDFT
1次元の DFT・IDFT の考え方とデータ操作方法

DFT/IDFT Y_axis
2次元の画像データに対する DFT・IDFT の考え方(Step1、横1行分の処理を縦方向分繰り返す)

DFT/IDFT X_axis
2次元の画像データに対する DFT・IDFT の考え方(Step2、縦1行分の処理を横方向分繰り返す)


2次元の画像データに対する DFT・IDFT 操作を行う C 言語の ソースコードを掲載。
 画像データは既に、複素数型(COMPLEX)の実部に登録されている事が前提(虚部は 0で初期化済み)
enum { DFT, IDFT };        //#define M_PI      3.14159265358979323846
typedef struct COMPLEX { double r, i; } COMPLEX; // Define the new COMPLEX type. There's no entity yet. #define RotorCOMPLEX(a) (COMPLEX){ cos(a), sin(a) } // IDFT: e j(2Πai/elements), DFT: e -j(2Πai/elements) #define AddCOMPLEX(a,b) (COMPLEX){ (a).r + (b).r, (a).i + (b).i } #define MulCOMPLEX(a,b) (COMPLEX){ (a).r*(b).r - (a).i*(b).i, (a).r*(b).i + (a).i*(b).r } #define ImeDivCOMPLEX(a,b)(COMPLEX){ (a).r / (b), (a).i / (b) } #define ImeMulCOMPLEX(a,b)(COMPLEX){ (a).r * (b), (a).i * (b) } void dft_TwoDimensional( COMPLEX **d, int lx, int ly, int flag ) {
int x, y, u, v, elements;
double unit;
COMPLEX t[(lx>ly?lx:ly)]; // See REMARK
elements = lx; unit = (flag==IDFT) ? 2*M_PI/elements : -2*M_PI/elements;
for( y=0; y<ly; y++ ) { // Σdft_oneDimensional( for Y axis ...);
for( u=0; u<elements; u++ ) t[u]=(COMPLEX){0,0}; // From 0 To LX -1. Initialize the work area with 0.
for( u=0; u<elements; u++ ) {// "for(v=0;v<elements;v++)" is performing a convolutional operation. for( v=0; v<elements; v++ ) t[u] = AddCOMPLEX( t[u], MulCOMPLEX(d[y][v],RotorCOMPLEX((unit*u)*v)) );
}
if(flag==IDFT) for( u=0; u<elements; u++ ) d[y][u] = ImeDivCOMPLEX(t[u],elements);
else for( u=0; u<elements; u++ ) d[y][u] = t[u];
} //////////////////////////////////////////////////////////////////////////
elements = ly; unit = (flag==IDFT) ? 2*M_PI/elements : -2*M_PI/elements;
for( x=0; x<lx; x++ ) { // Σdft_oneDimensional( for X axis ...);
for( u=0; u<elements; u++ ) t[u]=(COMPLEX){0,0}; // From 0 To LY -1. Initialize the work area with 0.
for( u=0; u<elements; u++ ) {// "for(v=0;v<elements;v++)" is performing a convolutional operation. for( v=0; v<elements; v++ ) t[u] = AddCOMPLEX( t[u], MulCOMPLEX(d[v][x],RotorCOMPLEX((unit*u)*v)) );
}
if(flag==IDFT) for( u=0; u<elements; u++ ) d[u][x] = ImeDivCOMPLEX(t[u],elements);
else for( u=0; u<elements; u++ ) d[u][x] = t[u];
} //////////////////////////////////////////////////////////////////////////
}
 補足事項:正規化は逆変換時にまとめて行われるので、この関数で 順変換 逆変換を行う事。
     順変換 逆変換の間で、周波数空間でのフィルター処理を行う場合は、本点を考慮する事
     #define AppendCOMPLEX(a,b) { (a).r += (b).r, (a).i += (b).i ;} も利用可
     C言語の難しさかは、同じ事を複数の記述が可能な表現力の自由さに起因するのかも
  // REMARK
  // Compare lx and ly and use the larger number as the reserved area size.
  // This memory dynamic allocation method does not require free().
  // It's allocated in stack area, so you should care stack overflow.

  //  t[u] = (COMPLEX){0,0};   /*構造体への一括代入・初期化 古典的記述方法*/
  //  キャスト演算子を用いて、データセットの属性(型)を代入先と合わせることが必須条件
  //  Classic description method: Conform to the ISO 1990 C standard, known as c89.
  //  At the time of execution, data is collectively assigned, or initialize, to
  //  the structure. A cast operation is required for synchronizing object type.
  //  As an element of the structure, the integer 0 is automatically converted to
  //  the real 0.0. (COMPLEX){0,0}=>(COMPLEX){0.,0.}=>t[u] Even gcc 3.x works well.

  //  "COMPLEX **d, int lx, int ly" same as "COMPLEX d[y][x], {0<=y<ly,0<=x<lx}"
  //  If the two-dimensional array was generated by the following way.
  //  COMPLEX **d = (COMPLEX **)alloc2Darray( sizeof(COMPLEX), lx, ly ); 
  //  Finally, you need to free the allocated memory pointer, like the following "free(d);".

// The worth and positioning of the structure
// Defining a structure in C is the same as defining a database field in a database.
// Defining the simplest and most effective primitives in building a system is equi-
// valent to a complete understanding of the features and requirements of the system.
// In addition, 'smart' expressions are required in terms of notation and operation,
// which are highly readable and less prone to errors.
// After learning the basic grammar of C language, it is need to think about the
// gathering elements, the operation method may be included, to operate for the your
// creations efficiently, and "define it as a structure".  I think it will be good
// training for your skill. 


2、プログラムのソースコードとWindows用実行形式の提供

source_r1.zip
New
dft_2D.c
idft_2D.c
complex_array_info.c
showPowerSpectrum.c
upgrade版 (メモリがゆるせば三角関数の値をテーブル化)
dft・idft ソフト及び、複素数型データのファイルヘッダー部
確認用ツール、パワースペクトル表示ツールの各ソースコード
MD5SUM: 8aeed47886b706c8b93cdb886037cfa1
winexe_r1.zip
New
dft_2D.exe
idft_2D.exe
complex_array_info.exe
showPowerSpectrum.exe
参考用 コンパイルオプションが大きく影響するので。
64bit Windows用 バイナリファイル(実行形式のファイル)
  ※マルチスレッド対応は、2D FFT(2K,4K,8K)版のみ
AVXレジスターを持つCPU環境での利用(マルチスレッド非対応版)
MD5SUM: c944f7c56ee1a9edd88ca01e9b70035d
プログラムが使用する、ディフォルトのファイル名前を用いての操作説明
 ・winexe_r1.zipをダウンロード後解凍する。 (下記の sample.bmp に対する変換処理時間は、1秒程度)
 ・解答したディレクトリwinexe_r1にサンプル画像sample.bmpをダウンロードする。(Windows形式のBMPファイルのみサポート)
 ・ディレクトリ内の dft_2D.exe をダブルクリックすると、sample.bmpを読み込みDFT処理を行い、変換結果を dft_complex.datとして書き出す。
 ・idft_2D.exe をダブルクリックすると、dft_complex.datを読み込みIDFT処理を行い、変換した結果を、 idft_2D.bmpとして書き出す。

source_r0.zip
修正版
dft_2D.c
idft_2D.c
complex_array_info.c
showPowerSpectrum.c
dft・idft ソフト及び、複素数型データのファイルヘッダー部
確認用ツール、パワースペクトル表示ツールの各ソースコード
MD5SUM: c0b396850ca4d36782c218d9269f3c9e
x32_r0.zip
修正版
dft_2D.exe
idft_2D.exe
complex_array_info.exe
showPowerSpectrum.exe
32bit Windows用 バイナリファイル(実行形式のファイル)
離散フーリエ変換ソフトは非常にシンプルなCPUの命令のみ使用
ほぼどの環境でも動くが、異常に遅く実用性は疑わしい。
MD5SUM: 16e711c0e6e1d06169b76dd0a76e47ab
・サンプル用の画像としては、処理対象のBMPファイルが利用可能
alloca相当,下記 temp[n], 手法で一時作業用メモリー領域の割り当てているので、巨大な画像は対象外
・C99 の複素数型 #include <complex.h> なら、表記は美しい
#include <math.h>
#include <complex.h>

#define M_PI      3.14159265358979323846
#define Rotor(a)  (double _Complex)( cos(a) + I*sin(a) )

enum { DFT, IDFT };

void dft_TwoDimensional( double _Complex **d, int lx, int ly, int flag ) {
int     x, y, u, v, elements;
double  unit, basis = (flag==DFT) ? -2*M_PI : 2*M_PI;
double _Complex temp[(lx>ly?lx:ly)];

    /// ...........   START, Two Dimensional DFT,IDFT Operation  ........... ///
    for( elements=lx, unit=basis/elements, y=0; y<ly; y++ ) {
        for( u=0; u<elements; u++ ) temp[u] = (double _Complex)( 0. + I*0. );
        for( u=0; u<elements; u++ ) {// Euler's formula: eθ = cosθ +sinθ
          //for( v=0; v<elements; v++ ) temp[u] += d[y][v] * cexp(unit*u*v);
            for( v=0; v<elements; v++ ) temp[u] += d[y][v] * Rotor(unit*u*v);
        }
        if(flag==DFT) for( u=0; u<elements; u++ ) d[y][u] = temp[u];
        else          for( u=0; u<elements; u++ ) d[y][u] = temp[u] / elements;
    }// ............. End of Y direction, Σ dft_oneDimensional( X elements ) //
    for( elements=ly, unit=basis/elements, x=0; x<lx; x++ ) {
        for( u=0; u<elements; u++ ) temp[u] = (double _Complex)( 0. + I*0. );
        for( u=0; u<elements; u++ ) {// Euler's formula: eθ = cosθ +sinθ
          //for( v=0; v<elements; v++ ) temp[u] += d[v][x] * cexp(unit*u*v);
            for( v=0; v<elements; v++ ) temp[u] += d[v][x] * Rotor(unit*u*v);
        }
        if(flag==DFT) for( u=0; u<elements; u++ ) d[u][x] = temp[u];
        else          for( u=0; u<elements; u++ ) d[u][x] = temp[u] / elements;
    }// ............. End of X direction, Σ dft_oneDimensional( Y elements ) //
}
[別画面] (改訂版)ですが、gcc(MinGW 6.3.0)では遅い。
  Ex. #define Rotor(a) (double _Complex)( cos(a) + I*sin(a) )
    double _Complex  tmp[n], **d; =>  temp[u] += d[y][v] * Rotor(unit*u*v);



4、変換処理サンプル

lena 処理対象のBMPファイル
color2gray dft_2D.exe(dft_2Dx64.exe)は、
入力画像を濃淡画像に変換し、
変換後の画像データに対して
DFT 変換を行います。

濃淡画像に変換された画像は、
BMPファイルとして保存されます。
PowerSpectrum dft_2D.exe(dft_2Dx64.exe)は同時に、
フーリエ変換後の周波数データに対し、
そのパワースペクトラム像を作成し、
BMPファイルとして、保存します。
(波形の状態を確認し易いように、
 輝度情報は、log10の対数表示)

また、複素データ形式(2つの連続した
DOUBLE型の領域に実部、虚部を格納)
に変換された情報は、dft_complex.dat
と言う名前で、保存されます。
idft_2D 逆変換により生成された画像
idft_2D.exe(idft_2Dx64.exe)は、
dft_2D.exe(dft_2Dx64.exe)が作成した
ヘダー情報付き複素データ形式の
データを読み込み、逆フーリエ変換
して、結果をBMPファイルとして保存
します。
ヘダーに記載されている情報に
関しては、別項目の”データファイルと
ヘダー情報”を参照してください。
 
 
   
filter dft_2D.exe(dft_2Dx64.exe)が作成した、
周波数変換情報(複素データ形式)に、
フィルター処理を施した、複素数型
データを、idft_2D.exe(idft_2Dx64.exe)
で、逆変換した画像。

"ネコ" ではなくて、"レナ" 画像。
(あの有名な猫のパワースペクトラム)
周波数領域での特徴量を更に符号化
すると......
新たな有益な利用方法が、見つかる
かも知れない   記憶、認識とは?
idft_2D
周波数空間で、異なる画像に
属している、周波数情報間の
加算処理をした結果に対して
逆変換を行い再生成した画像





idft_2D
波の独立性より、加算データに
対して、片方の画像に属している
周波数のデータ分を削除処理した
結果に対して、逆変換を行う事で
再生成した画像 説明用(意図的な残部有)

恰も、記憶の一部が削除された
様な結果を生む


1領域(本説明に於いては画面が変換された周波数領域に相当)に記録可能な情報量は2つに制限されない。
総情報量は2以上(公知の事実)であって良い。 lena, Traffic sign, etc
これは、一つの境域に異なる情報を多重化して、追加、削除等の操作が出来る事を意味する。

また、画像による説明は、単なるメタファーに過ぎない。(画像処理に限定されない)

同時に、如何に複雑な情報 (画像を含む)であっても、周波数、振幅、位相(空間)の3基本量で表現できる事が真実且つ本質



5、データファイルとヘダー情報


typedef struct COMPLEX { double r, i; } COMPLEX;
複素数型のデータ構造は、二つの double 型変数(r,i)から構成されており、
r 部には実部情報が格納され、 i 部には虚部情報が格納される。

struct HEADERCX { // COMPLEX => bfType = 0x585043 (0x43,0x50,0x58)
unsigned int cxType, zero; // identification 0x43='C',0x50='P',0x58='X'
unsigned int cxSize; // ?? cxOffByts+cxSizeData +sizeof(message)
unsigned int cxDataByte; // 16 sizeof(COMPLEX) 固定値
unsigned int cxOffByts; // ?? 32+α sizeof(HEADER) +sizeof(message)
unsigned int cxSizeData; // ?? lx*ly*sizeof(COMPLEX)
signed int cxWidth; // ?? lx
signed int cxHeight; // ?? ly
///////////////////////////////////////////////////////////////////////////
char message[]; // オプション:使用バイト数は cxSize に含む
} HEADERCX ; // cxOffByts の +α の部分
#define COMPLEXID 0x585043 // マジックナンバー(識別子) 0x585043 'CPX'

本ツール群が使用する複素数型のデータは、ファイルの先頭に上記ヘッダー情報を持ち、この後に COMPLEX 型のデータが lx * ly 個続く単純な構造をしている。
ヘッダー部(64バイト)に続けてユーザーの任意の情報を付加する事が可能であるが、追加情報
を使用する場合は、ファイル全体のバイト数を表す cxSize とファイルの先頭から COMPLEX型の実
データが開始される場所までのオフセットを表す cxOffByts が正しく設定されなければならない。
HEADERCX h = { COMPLEXID, // unsigned int 識別子 0x585043 'CPX'
0, // unsigned int 予約領域 0 固定値
HEADERSIZE +message +
lx*abs(ly)*sizeof(COMPLEX), // unsigned int ファイル全体の大きさ
sizeof(COMPLEX), // unsigned int 複素数型のバイト数
HEADERSIZE+message, // unsigned int ファイルの先頭から、
// 複素数型データ列までのバイト数
lx*ly*sizeof(COMPLEX), // unsigned int 複素データ総バイト数
lx, // signed int x軸方向の要素数
ly // signed int y軸方向の要素数
}; ※ 各変数は4バイト unsigned int, signed int
この後に、複素数型のデータが続く。 COMPLEX data[lx*ly]

6、コマンドの機能と使い方

dft_2D.exe, dft_2Dx64.exe
入力されたBMP画像ファイルを読み込み、画像データに対し離散フーリエ変換を行います。
 ・入力されたBMPファイルを濃淡画像に変換(変換画像は、BMPファイルとして保存)
 ・濃淡画像を周波数データに変換(変換データは、datファイルとして保存)
 ・周波数データをパワースペクトラム画像に変換(変換データは、BMPファイルとして保存)

usage: dft_2D.exe [-t] [-h] [input_bmp [complex_out.dat]]

        -t: Show run time.
        -h: This option shows only this message.
 

idft_2D.exe, idft_2Dx64.exe
入力された周波数データファイルを読み込み、波形データに対し逆離散フーリエ変換を行います。
 ・逆離散フーリエ変換された波形データは、画像データとして復元されます。
  復元された画像データは、BMPファイルとして保存されます。
  workaround: 入出力用のファイル名を指定する。(無指定時、bmp名が idft_2D.datになる)
usage: idft_2D.exe [-t] [-h] [complex_in.dat [output_bmp]]

        -t: Show run time.
        -h: This option shows only this message.
 

complex_array_info.exe
入力された周波数データファイルを読み込み、ヘッダーに記録されている情報を表示します
 ・データの縦、横の大きさ等が確認出来ます。

usage: complex_array_info.exe [-h] [complex.dat]

        -h: This option shows only this message.
 

showPowerSpectrum.exe
入力された周波数データファイルを読み込み、パワースペクトラム画像作成します
 ・d オプションを指定すると、低周波成分が四隅に、高周波成分が中心に表示されます
 ・n オプションを指定すると、パワースペクトラムの輝度を log10 変換しません
 ・生成されたパワースペクトラム画像は、BMPファイルとして保存されます。
 ・ソースコードは、独自フィルタープログラムを作成する時の雛形

usage: showPowerSpectrum.exe [-d] [-n] [-h] [complex_in.dat [output_bmp]]

        -d: Not replace the power spectrum.
        -n: normal power spectrum. default display log10.
        -h: This option shows only this message.
 


7、実際の処理は速度的に優れた FFTW 等 CZTを利用して下さい。

マルチスレッド化した、64ビットアプリケーションも用意しましたが、FFTW がはるかに優れ
且つ、任意の画像サイズも扱えるので、このアプリケーションの提供は中止しました。
32ビット版のアプリは残してありますが、あまりに遅いので実用性は期待できません。
必要なら、ソースを64Bitモードでコンパイルした実行形式を作成して、使用して下さい。


// fftw を使う場合の参考イメージ
#include "fftw3.h"

void dft_TwoDimensional( COMPLEX **d, int lx, int ly, int flag ) {
fftw_complex *in=(fftw_complex *)&d[0][0], *out=(fftw_complex *)&d[0][0];
fftw_plan    plan;

    if( flag==DFT ) plan=fftw_plan_dft_2d(ly,lx,in,out,FFTW_FORWARD, FFTW_ESTIMATE);
    else            plan=fftw_plan_dft_2d(ly,lx,in,out,FFTW_BACKWARD,FFTW_ESTIMATE);
    fftw_execute( plan );
    fftw_destroy_plan( plan );
}// ※逆変換した後、要素数で割る処理はしてい無い様なので、自身の処理ルーチン中で行う事

FFTWは、非常に高速で処理速度も安定(常に一定)なソフトですが、ここで提供しているFFT,IFFT 及び
CZT,ICZTは処理速度がシステムの状態に依存して揺らいでしまいます。ただし、実行環境と状態次第では、
FFTW より速く処理が完了する場合さえありますので、ここのコードは自作時の参考になると考えます。


EXTRA  2018/08/18 追記

2kx2k の画像に対する DFT があまりに遅いので、若干の修正(FFT)を検討。
・ソフトウエアのライセンスが問題となるコードを含まない事と、マルチスレッド化が容易な事が前提。
・CPU: Xeon E5-1650 v4 @3.60GHz 相当を使用する場合の処理時間(カラー)に対する期待値は、1秒未満。
 (カラー画像は 赤、緑、青の 3要素構成なので、各要素【2048x2048】毎の処理時間は、300ms以下)

FFT処理に関しては、RIMS, 京都大学数理解析研究所の 標準的FFT 説明コードを参照の事
(参照リスト1.2.1-3.): http://www.kurims.kyoto-u.ac.jp/~ooura/fftman/ftmn1_2.html
可読性を考慮し、C99 の複素数拡張機能を用いた記述。 (もしFFT自体の説明が必要なら参照)

画像の読込みには、Mr.Sean Barrett http://nothings.org/、のコードをベースに、
参照: https://github.com/nothings/stb/blob/master/stb_image.h
それぞれ利用させていただいています。

・2D FFT,  IFFT   Source code in C99 format  別画面で開く
詳細表示
#include <math.h>
#include <complex.h>

#define FFT2K     (2048)
#define M_PI      3.14159265358979323846
#define Rotor(a)  (double _Complex)( cos(a) + I*sin(a) )

enum { FFT, IFFT };    // ∵ ennm { DFT, IDFT };  also enum { FFT=DFT, IFFT=IDFT };

void FFT2k_TwoDimensionalC99( double _Complex **d, int flag ) { // ∵d[2048][2048]
#define elements  FFT2K
int     x, y, e;    // flag   IFFT(2*M_PI/e..), FFT(-2*M_PI/e..)
double  unit = (flag==IFFT) ? 2*M_PI/elements : -2*M_PI/elements;
double _Complex rotor[elements]; for(e=0;e<elements;e++) rotor[e]=Rotor(unit*e);

    for( y=0; y<elements; y++ ) {  // x軸方向の1次元FFT(IFFT)をy行分行う
        int     i, j, k, m, mh, ir;// ir:irev
        double _Complex  w, t;     // t: temp
        for( i=0, j=1; j<elements-1; j++ ) { // scrambler, for initial placement
            for( k=elements>>1; k>(i^=k); k>>=1 );
            if( j<i ){ t=d[y][j]; d[y][j]=d[y][i]; d[y][i]=t; } //exchange
        }
        for( mh=1; (m=mh<<1)<=elements; mh=m ) {
            for( ir=0, i=0; i<elements; i+=m ) {
                for( w=rotor[ir], k=elements>>2; k>(ir^=k); k>>=1 );//for next ir
                for( j=i; j<mh+i; j++ ) {
                         k  = j + mh;
                         t  = d[y][j] - d[y][k];
                    d[y][j] = d[y][j] + d[y][k];    // a ->- (a + b) ->- a
                    d[y][k] = t * w;                // b ->- (a-b)*w ->- b
        }   }   }
        if(flag==IFFT) for( i=0; i<elements; i++ ) d[y][i] /= elements;
    } // X_END
    for( x=0; x<elements; x++ ) {  // y軸方向の1次元FFT(IFFT)をx列分行う
        int     i, j, k, m, mh, ir;// ir:irev
        double _Complex  w, t;     // t: temp
        for( i=0, j=1; j<elements-1; j++ ) { // scrambler, for initial placement
            for( k=elements>>1; k>(i^=k); k>>=1 );
            if( j<i ){ t=d[j][x]; d[j][x]=d[i][x]; d[i][x]=t; } //exchange
        }
        for( mh=1; (m=mh<<1)<=elements; mh=m ) {
            for( ir=0, i=0; i<elements; i+=m ) {
                for( w=rotor[ir], k=elements>>2; k>(ir^=k); k>>=1 );//for next ir
                for( j=i; j<mh+i; j++ ) {
                         k  = j + mh;
                         t  = d[j][x] - d[k][x];
                    d[j][x] = d[j][x] + d[k][x];    // a ->- (a + b) ->- a
                    d[k][x] = t * w;                // b ->- (a-b)*w ->- b
        }   }   }
        if(flag==IFFT) for( i=0; i<elements; i++ ) d[i][x] /= elements;
    } // Y_END
}


////////////////////////////////////////////////////////////////////////
// How to use FFT2k_TwoDimensionalC99(...)  2019/04/01
//
void dft_TwoDimensional( COMPLEX **s, int lx, int ly, int flag ) {
int     w = lx>ly ? lx : ly;
COMPLEX **spreadsheet = NULL;

    double _Complex **ss = (double _Complex **)s;
    if( lx==2048 && ly==2048 ) return FFT2k_TwoDimensionalC99(ss,flag);
    if( (spreadsheet=(COMPLEX**)alloc2Darray(sizeof(COMPLEX),w,w)) ) {
       dft_TwoDimensionalWithTable( spreadsheet, w, s, lx, ly, flag );
       free(spreadsheet);
    } else dft_TwoDimensionalStandard( s, lx, ly, flag );
}

・画像読込  (一般的な各種画像フォーマットに対応)  別画面で開く
詳細表示
#define  STB_IMAGE_IMPLEMENTATION
#include "stb_image.h"

    :
int   lx, ly, bpp;
char  *raw=NULL;    // Initialization required
PIXEL **sour=NULL;  // Initialization required

    if( (raw=(char*)stbi_load( ifname, &lx, &ly, &bpp, 4 ))==NULL ) {
        fprintf(stderr,"Couldn't load the image '%s'.\n",ifname);  goto GOOD_BY;
    } else if( (sour=(PIXEL**)alloc2D( raw, sizeof(PIXEL), lx, ly ))==NULL ) {
        fprintf(stderr, "Couldn't allocate memory. source\n");     goto GOOD_BY;
    } else imageFittingOperation( sour, lx, ly );
    :
    :
GOOD_BY:; //Goodbye with doing the following process
    free(sour);
    stbi_image_free(raw);
}

void imageFittingOperation( PIXEL **s, int lx, int ly ) {
int   x, y, ey=(ly +1)/2, ty=ly-1;
PIXEL p;

    for( y=0; y<ey; y++ ) for( x=0; x<lx; x++ ) {
        p       = (PIXEL){ s[y][x].R, s[y][x].G, s[y][x].B, 0 };
        s[y][x] = (PIXEL){ s[ty-y][x].R, s[ty-y][x].G, s[ty-y][x].B, 0 };
        s[ty-y][x] = p;
    }// 色要素順の変更( B ⇔ R )及び 左上原点系 から 左下原点系への変換
}


diff: // stb_image - v2.19  (warning: unused parameter) ‘req_comp’‘ri’
  static stbi_uc *stbi__gif_load_next(stbi__context *s, stbi__gif *g, int *comp, int req_comp, stbi_uc *two_back)
< {
> {  (void)req_comp;
  static void *stbi__gif_load(stbi__context *s, int *x, int *y, int *comp, int req_comp, stbi__result_info *ri)
< {
> {  (void)ri;

diff: // stb_image - v2.26   (warning: comparison between signed and unsigned integer expressions)
<    if (b >= sizeof(z->size)) return -1; // some data was corrupt somewhere!
>    if ((long long)b >= (long long)sizeof(z->size)) return -1; // some data was corrupt somewhere!




 ※ 恒常的にソースコード表示させる場合は、”別画面で開く” をクリックして下さい。

  追加対応版: 2D(2k,4k,8k 対応) FFT, IFFT Multi-threaded Version  別画面で開く

      マルチスレッドは、汎用性の高い OpenMP による実装版(ソース内緑色による記述部分)
      参考データ 8Kx8K 濃淡画像の Ryzen 7 3700X (8core) での処理時間は、5秒未満
            Ryzen 3700X (≒4.3sec), 3900X (≒3.7sec), 3950X (≒3.5sec)
            3950X のメモリチャネルは 2ch しかないので飽和状態と考えられる。
            DDR4-3200(4ch)対応のThreadripper か、GPU の併用が必要かも。

※ 2019/10/25 補足と可読性の改善に関連する追記
Ryzen Threadripper Pro 3975WX with 2T memory  欲しい。
数値計算以外に、部品情報管理(10G「100億個」程度)も十分に行けそう。



8、ライセンス及び免責事項

ライセンスは、二条項BSDライセンスに準拠する。

本ソフトウェアは、著作権者およびコントリビューターによって「現状のまま」提供
されており、明示黙示を問わず、商業的な使用可能性、および 特定の目的に対する
適合性に関する暗黙の保証も含め、またそれに限定されない、いかなる保証もない。
著作権者もコントリビューターも、事由のいかんを問わず、損害発生の原因いかんを
問わず、かつ責任の根拠が契約であるか厳格責任であるか(過失その他の)不法行為
であるかを問わず、仮にそのような損害が発生する可能性を知らされていたとしても、
本ソフトウェアの使用によって発生した(代替品または代用サービスの調達、使用の
喪失、データの喪失、利益の喪失、業務の中断も含め、またそれに限定されない)
直接損害、間接損害、偶発的な損害、特別損害、懲罰的損害、または結果損害について、
一切責任を負わないものとする。


9、終わりに

コンピュータの性能が著しく向上しているので、今までは処理時間の問題で難しかった手法も、
利用できる様になった事の意義は大きい。手段の変更はまた、アルゴリズムをより柔軟に考え
る事を可能にすることも意義深い事実である。
心技体(発想力・実装能力・実行環境)何れが欠けても、成果が厳しい事は何処でも同じ

画像処理では、概ね限られた大きさ(2のn乗)のデータにを扱う事が多いと思われますが、
音声等の1次元のデータではデータ数を特定して使用する事は難しいと思われます。
(画像処理においても、任意サイズで FFT 出来る事は思いのほか便利。有って悪く無い機能)
任意サイズのデータに対して、高速にフーリエ変換する手法として、Chirp z-変換 (CZT,
ICZT)が有るので(Bluestein's algorithm)、そちらも実装しておくのが良いのかも。
ここでは順変換と逆変換で大きな速度差が出なくなる方法で、且つ任意サイズのデータを処理
出来る方式での実装を行っていますので、下記の例は、6,000,000点のデータをフーリエ変換
していますが、16,777,216要素のデータに変換して、通常のFFTを介して変換した例であり、
順変換と逆変換の処理時間はほぼ同じです。 順変換、逆変換、比較等の全て含む時間ですが、
非力なノートPCでも20秒以内で変換出来ますので、そこそこ実用性はあると思われます。

簡単な互換性試験としては、画像データを CZT でフーリエ変換し、その結果を IDFT で復元
させて画像が正しく復元できる事を確認し、ICZT でも同様に正しく復元するか確認します。
視覚情報として確認するのが最も簡単な方法です。

C言語による実装例 可読性重視 CZT & ICZT   画像用     Smart-2D_FT  
CZT.cebf01550e0449c567a0cc825fe903f63
CZT.zipbd0a90ae35fc0382f2bf60692e37858d

> CZT_OneDimensionalPlus -q -t -V -N6000000

         original data             Fourier transform         inverse transformation


 The result of comparing the original data and the inverse transformed data
 is Matched.                     (  6000000   6000000   16777216 )


START:  15:05:56.003369
  START  CZT: 15:06:00.285575
  E N D  CZT: 15:06:06.643770
  START ICZT: 15:06:06.699835
  E N D ICZT: 15:06:12.939845
E N D:  15:06:12.984706

> CZT_OneDimensionalPlus -t -v -N11

         original data             Fourier transform         inverse transformation
   0 |   6.0000000   0.0000000 |  -0.0000000  -0.0000000 |   6.0000000   0.0000000
   1 |  -3.8768873   0.0000000 |   0.0000000  -0.0000000 |  -3.8768873  -0.0000000
   2 |  -1.7976721   0.0000000 |   0.0000000   0.0000000 |  -1.7976721  -0.0000000
   3 |   0.3299268   0.0000000 |  33.0000000   0.0000000 |   0.3299268  -0.0000000
   4 |   3.9205910   0.0000000 |  -0.0000000  22.0000000 |   3.9205910  -0.0000000
   5 |  -0.2906364   0.0000000 |   0.0000000   0.0000000 |  -0.2906364   0.0000000
   6 |  -7.5676924   0.0000000 |  -0.0000000  -0.0000000 |  -7.5676924  -0.0000000
   7 |   6.1744514   0.0000000 |  -0.0000000 -22.0000000 |   6.1744514   0.0000000
   8 |   4.6550533   0.0000000 |  33.0000000  -0.0000000 |   4.6550533  -0.0000000
   9 |  -9.7162436   0.0000000 |   0.0000000  -0.0000000 |  -9.7162436  -0.0000000
  10 |   2.1691093   0.0000000 |   0.0000000   0.0000000 |   2.1691093   0.0000000
                                   cos_part    sin_part
                      Fourier transform[0]: 直流成分、信号成分は、1 ~ (N-1)の部分
                       ◯ 位相はずらしていないので、cos, sin の単体で表現されている
                        1, (N-1): データ数が1周期である信号の情報が格納される部分
                        2, (N-2): データ数が2周期である信号の情報が格納される部分
                        3, (N-3): データ数が3周期である信号の情報が格納される部分

 The result of comparing the original data and the inverse transformed data
 is Matched.                     (     11      11      32 )

START:  15:06:16.931929
E N D:  15:06:17.044486

> 
参考情報
 ソースコード小屋(https://cetus.sakura.ne.jp/softlab/srcpatch/index.html)
   czt-20030915.zip - 2003-09-15 / 10,356 bytes / ZIPアーカイブ
   czt-20021129.zip - 2002-11-29 / 9,872 bytes / ZIPアーカイブ
 にて2000(1990)年代初頭には、既に CZT、ICZT が実装されて、ソースも公開されているのですが...
 計算結果が変数内に収まらない等を除く、自分たちが扱うデータの範囲内に於いての話ではありますが、
 少なくとも日本では、CZT、ICZT(共役複素数を使用) の実装はあまり新しい話ではないと思います。



  参考資料 (追加情報)

1、慶應大学講義 物理情報数学 C   (strongly recommend)
第一回 信号とシステム
第二回 三角関数と基本周期
信号の表現,重ね合わせの理とたたみこみ積分
第四回 たたみこみ積分の計算法,内積と直交
第五回 フーリエ級数
第六回 複素フーリエ級数からフーリエ変換
第七回 フーリエ変換
第八回 フーリエ変換の性質,ラプラス変換

Z変換 1
Z変換 2 ,Z変換を用いた差分方程式の解法




正誤表
idft_2D.c #define EXTRACTING(foname)           FINALFNAMEIS(foname.dat)
#define EXTRACTING(foname)           FINALFNAMEIS(foname.bmp)
dft_2D.c
idft_2D.c
complex_array_info.c
showPowerSpectrum.c
    for( i=strlen(p); i>0 && p[i]!='\\' && p[i]!='/'; i-- );
    if(i) p++;
    fprintf( stderr, "\nusage: %s %s[........]\n\n", p, op );
    for( i=strlen(p); i>0 && p[i]!='\\' && p[i]!='/'; i-- );; if(i) i++;
    fprintf( stderr, "\nusage: %s %s[........]\n\n", &p[i], op );
idft_2D.c complexReal2grayEX( ... ) は説明用関数 下記関数に置換

void complexReal2gray( COMPLEX **u, PIXEL **a, int lx, int ly ) {
int  x, y, g;

    for( y=0; y<ly; y++ ) {
        for( x=0; x<lx; x++ ) {
            g = u[y][x].r>255 ? 255 : ( u[y][x].r<0 ? 0 : u[y][x].r );
            a[y][x] = (PIXEL){ g, g, g, 0 };
        }
    }
}
IDFT で BMP 保存する時に、データの最大値と最小値で表示レベルの変更を行っているが、本来は不要な処理。

追加分ソースコード (別ファイル化)
FFT, IFFT Multi-threaded (2D: 2k,4k,8k) FFT_TwoDimensionalC99
画像読込 stb_image_load
2D FFT,IFFT Source code in C99 FFT2k_TwoDimensionalC99
2D DFT,IDFT Source code in native C dft_TwoDimensional


補足情報1、正弦波画像と周波数の関連性に関する簡略説明

補足情報2
COMPLEX rotor[max];    // 可変長配列(VLA:variable-length array)表記
可変長配列(VLA:variable-length array)がサポートされていないコンパイラでは、
alloca(_alloca)で代用する事も可能であるが、利便性は著しく劣る。
Ex.  COMPLEX *rotor=(COMPLEX*)alloca(sizeof(COMPLEX)*max);


補足情報3、Extra sample, 2DFT.c: DFT,FFT Sample Full Source Code
簡単にテスト出来る様に、実行形式を直ぐに生成できる、短い完全なコードのサンプル提供
この版は、DFT、FFT 共にマルチスレッド対応済み


補足情報4 ICZT と IDFT の処理速度比較   (Ryzen 3950X での結果)
2000x1500 の2次元配列に格納されている、複素数データの逆変換を各方法で、
行った結果、ICZT なら、1秒以下だが、IDFT だと20秒弱かかってしまう


>powershell-c Get-WmiObject Win32_Processor | grep -i name
Name             : Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz

>FT_TwoDimensional -v -t -p sample.bmp sample_iczt.bmp

2000 x 1500      'sample.bmp'
execution: czt_TwoDimensional   0
execution: czt_TwoDimensional   1

START: 10:18:52.268671   CZT
E N D: 10:18:52.993966   CZT


START: 10:18:53.134274  ICZT
E N D: 10:18:53.815167  ICZT


>FT_TwoDimensional -v -t -p sample.bmp sample_idft.bmp -d

2000 x 1500      'sample.bmp'
execution: czt_TwoDimensional   0
execution: dft_TwoDimensional   1

START: 10:19:13.925000   CZT
E N D: 10:19:14.652063   CZT

START: 10:19:14.793005  IDFT
E N D: 10:19:33.534563  IDFT


>
>md5sum sample_*.bmp

28681751e6c228cca866aa08ac7b342c *sample_iczt.bmp
28681751e6c228cca866aa08ac7b342c *sample_idft.bmp


逆 Chirp Z変換(ICZT)は結果の示す通り、任意長用の非常に高速な逆フーリエ変換です


go to TopPage go to CategoryTop