0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Yes, this is correct. $\endgroup$ Jun 2, 2013 at 14:58
  • $\begingroup$ Yes, you will be multiplying 2 complex numbers at a time. $\endgroup$
    – Spacey
    Jun 2, 2013 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, 2013 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, 2013 at 16:39

1 Answer 1

2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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