If you want to compute a convolution with a DFT/FFT, you will have to do a DFT on the image and a DFT on the kernel.

And you will need to multiply the spectrum of the image with the spectrum of the kernel.

Is it correct that the multiplications in the fourier domain are complex multiplications? So, that those point-wise multiplications will require 4 real multiplications and 2 real additions?

  • $\begingroup$ Yes, this is correct. $\endgroup$ – pichenettes Jun 2 '13 at 14:58
  • $\begingroup$ Yes, you will be multiplying 2 complex numbers at a time. $\endgroup$ – Spacey Jun 2 '13 at 22:41
  • 2
    $\begingroup$ @pichenettes and Mohammad: hey guys, please make an answer out of it, even though you may think it's trivial; otherwise this question will be one more on the pile of unanswered questions ... $\endgroup$ – Matt L. Jun 3 '13 at 12:06
  • $\begingroup$ Yes :) ex. (a+jb)*(c+jd) = (ac-bd) + j (cb + ad) ==> 4 Real Multiplications, and 2 Real Additions $\endgroup$ – user5784 Oct 25 '13 at 16:39

Yes, this is correct - the DFT/FFT of a real signal (for example an image) is not necessarily real; so if you want to compute a convolution through multiplications in the Fourier domain, the coefficients to multiply will be complex numbers; and will thus cost 4 real multiplications and 2 real additions if a naive implementation is used (unless the architecture you are writing code for has hardware support for complex multiplications).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.