2D fft - Null imaginary part

Question

I am integrating a Python routine into C++ code.

There is the computation of the fft 2D of some real matrix, using in Python

F_BLK=np.fft.fft2(blk)

F_BLK is a complex 512*24 matrix, with coefficients complex with real and imag part with order of magnitude 10e5.

When I compute the fft2 of the matrix in C++ i get a complex matrix with complex coefficients with real part with order of magnitude 10e6 and with null imaginary part.

• What does it mean if the fft2 has got null imaginary part ?
• What are possible sources for such wrong results ?
• Would you recommend one library in C++ for computing fft2 ?

Answer 1

1. if you use real input for FFT

   • then you do not need to have so much calculations ( C += R * C is simpler then C += C * C)
   • so if you have FFT C = f(R) coded for such input data then it is usually faster
   • then standard FFT C= f(C)
   • and also you do not need to have allocated memory for the input imaginary part
   • also when input data is real only then the FFT output is symmetric
   • so you can just compute only first half of output data and mirror the rest

2. the magnitude difference

   • either you have wrong implementation of FFT (in python or in C++)
   • or you just have different normalization coefficients
   • plot the data and compare if the difference is just constant scale factor
   • if not then you have bug in FFT implementation somewhere or the python FFT is not FFT
   • also do not forget that data size for any FFT must be power of 2
   • if your implementation expects that then also that could be the cause of error
   • so try resize matrix 512x24 to 512x32 by zero padding before FFT
   • another thing that can cause this can be overflow errors
   • if you mix huge and small numbers together your accuracy get lost
   • especially by FFT recursions the output magnitude can be 10e5 but the subresults can be much much bigger !!!

3. 2D FFT

   • look here 2D FFT,DCT by 1D FFT,DCT
   • it contains slow 1D DFT,iDFT implementations in C++ (R->C,C->R)
   • and algorithm how to compute 2D transforms with it
   • with correct results so you can check yours