Efficient 2D FFT of fixed length real input data in C/C++
c++, fft, fftw, opencv, optimization
Solution
Your FFT time with FFTW seems very high. To get the best of out FFTW with fixed size FFTs you should generate a plan using the `FFTW_PATIENT` flag and then ideally save the generated "wisdom" for subsequent re-use. You can generate wisdom either from your own code or using the fftw-wisdom tool.
Problem
I'm developing an algorithm that calls several times to a FFT function. I have several time constraints (real-time desired) so I need to minimize the time expended in every FFT call. I'm working with OpenCV library and I have already implemented my code with two different approaches: - Using FFTW library. Data/memory management + FFT(8ms) = 14ms (in mean, FFT_MEASURE flag). - Using OpenCV fft function. Data/memory management + FFT (21ms) = 23ms (in mean). As my input data is always fixed as a real image of 512x512 pixels, do you think if I implement myself the FFT algorithm based in the mathematical definition of DFT, storing the sine/cosine tables can I achieve better performance or the FFTW library is really very optimized? Any better ideas? All ideas and suggestions will be really appreciated. By now, I don't consider paralellization or GPU implementation. Thank you Update: System: Intel Xeon 5130 2.0GHz CPU in Windows 7, Visual Studio 10.0 and FFTW 3.3.3 (compiled following instructions in the site), OpenCV 2.4.3. Code example for FFT call with FFTW (input: OpenCV Mat CV_32F (1 channel, float type), output OpenCV Mat CV_32FC2 (2 channels, float type): ``` 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; ```