我正在开发一种算法,该算法多次调用FFT函数。我有几个时间限制(需要实时),所以我需要尽量减少每次FFT调用所花费的时间。
我正在使用OpenCV库,我已经用两种不同的方法实现了我的代码:
- 使用FFTW库。数据/内存管理+FFT(8ms)=14ms(平均值,FFT_MEASURE标志)
- 使用OpenCV fft函数。数据/内存管理+FFT(21ms)=23ms(平均值)
由于我的输入数据总是固定为512x512像素的真实图像,你认为如果我自己实现基于DFT数学定义的FFT算法,存储正弦/余弦表可以获得更好的性能吗?或者FFTW库真的非常优化了吗?有更好的主意吗?
我们将非常感谢所有的想法和建议。到目前为止,我还没有考虑并行化或GPU实现。
谢谢
更新:
系统:Windows 7、Visual Studio 10.0和FFTW 3.3.3中的Intel Xeon 5130 2.0GHz CPU(按照网站中的说明编译),OpenCV 2.4.3。
使用FFTW进行FFT调用的代码示例(输入:OpenCV Mat CV_32F(1个通道,浮点型),输出OpenCV MatCV_32FC2(2个通道,浮动型):
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;
使用FFTW的FFT时间似乎很长。为了使用固定大小的FFT获得最佳的FFTW,您应该使用FFTW_PATIENT
标志生成一个计划,然后理想地保存生成的"智慧"以供后续重用。您可以从自己的代码或使用fftw智慧工具生成智慧。
"英特尔数学内核库"(与英特尔编译器分离)中的FFT在大多数情况下都比FFTW快。不过,我不知道你的情况是否有足够的改善来证明价格合理。
我同意其他人的观点,滚动自己的FFT可能不会很好地利用你的时间(除非你想学习如何做)。可用的FFT实现(FFTW、MKL)经过多年的微调。我并不是说你不能做得更好,但这可能需要大量的工作和时间来获得边际收益。
相信我,fftw确实非常优化,只有很小的机会,你可以做得更好。
您使用了哪个编译器来编译fftw?有时,英特尔的编译器比gcc 提供更好的性能