c++ - C/C++ 中固定长度实数输入数据的高效二维 FFT

Question

我正在开发一种多次调用 FFT 函数的算法。我有几个时间限制(需要实时)，所以我需要尽量减少每次 FFT 调用所花费的时间。

我正在使用 OpenCV 库，我已经用两种不同的方法实现了我的代码:

• 使用 FFTW 库。数据/内存管理 + FFT(8ms) = 14ms(平均，FFT_MEASURE 标志)。
• 使用 OpenCV fft 函数。数据/内存管理 + FFT (21ms) = 23ms(平均值)。

由于我的输入数据总是固定为 512x512 像素的真实图像，你认为如果我自己实现基于 DFT 数学定义的 FFT 算法，存储正弦/余弦表，我可以获得更好的性能还是 FFTW库真的很优化吗？有更好的想法吗？

所有想法和建议将不胜感激。到目前为止，我不考虑并行化或 GPU 实现。

谢谢

更新:

系统:Windows 7 中的 Intel Xeon 5130 2.0GHz CPU、Visual Studio 10.0 和 FFTW 3.3.3(按照站点中的说明编译)、OpenCV 2.4.3。

使用 FFTW 进行 FFT 调用的代码示例(输入:OpenCV Mat CV_32F(1 channel ，浮点型)，输出 OpenCV Mat CV_32FC2(2 channel ，浮点型):

float           *im_data;

fftwf_complex    *data_in;
fftwf_complex    *fft;      

fftwf_plan       plan_f;

int             i, j, k;

int height=I.rows;
int width=I.cols;
int N=height*width;


float* outdata = new float[2*N];
im_data = ( float* ) I.data;

data_in = ( fftwf_complex* )fftwf_malloc( sizeof( fftwf_complex ) * N );
fft     = ( fftwf_complex* )fftwf_malloc( sizeof( fftwf_complex ) * N );

plan_f = fftwf_plan_dft_2d( height , width , data_in , fft ,  FFTW_FORWARD ,  FFTW_MEASURE );

for(int i = 0,k=0; i < height; ++i) {
    float* row = I.ptr<float>(i);
    for(int j = 0; j < width; j++) {
        data_in[k][0]=(float)row[j];
        data_in[k][1] =(float)0.0;
        k++;
    }
} 

fftwf_execute( plan_f );

int width2=2*width;
// writing output matrix: RealFFT[0],ImaginaryFFT[0],RealFFT[1],ImaginaryFFT[1],...
for( i = 0, k = 0 ; i < height ; i++ ) {
    for( j = 0 ; j < width2 ; j++ ) {

        outdata[i * width2 + j] = ( float )fft[k][0];
        outdata[i * width2 + j+1] = ( float )fft[k][1];
        j++;
        k++;
    }
}

Mat fft_I(height,width,CV_32FC2,outdata);

fftwf_destroy_plan( plan_f );
fftwf_free( data_in );
fftwf_free( fft );


return fft_I;

Answer 1

您使用 FFTW 的 FFT 时间似乎非常长。要使用固定大小的 FFT 充分利用 FFTW，您应该使用 FFTW_PATIENT 标志生成一个计划，然后最好保存生成的“智慧”以供后续重复使用。您可以从自己的代码或使用 fftw-wisdom 生成智慧。工具。