-3
$\begingroup$

Is it true that convolving a 3x3 matrix and a Full HD (1920×1080) image is slower with FFT, than with normal for-loops? Because you have to do zeropadding to get to a power of 2? (with the traditional Cooley-Tukey FFT for example)

Because when using the FFT, you have to zeropad the 3x3 kernel as well... log(1920*1080)/log(2) is roughly 21. That means I need 21 adds and 15.5 multiplies is 36.5 operations for each pixels. But I need to do 2 FFT and one IFFT. So, I need to multiply 36.5 by 3: 36.5*3=109.5 operations for each pixel?

When calculating the convolution directly using for-loops, you need 9 multiplications and 9 additions = 18 operations for each pixel.

I guess I made a mistake somewhere. One of those is '21 multiplies'... Please provide a better mathmatical proof.

$\endgroup$
  • 3
    $\begingroup$ Please stop simultaneously crossposting on multiple forums! cs.stackexchange.com/questions/12217/…. Post on one forum or the other, and if your question doesn't get an adequate response after a couple of days request the moderator to move to the other forum. $\endgroup$ – Wandering Logic May 22 '13 at 17:29
  • 1
    $\begingroup$ As @WanderingLogic says, please stop duplicate posting. It is against the spirit of the SE series of sites. Please choose one site, and ask there. If it's off-topic for the site, the moderators will move it. $\endgroup$ – Peter K. May 22 '13 at 17:41
  • 1
    $\begingroup$ Re-opening after duplicate was removed from sister site. $\endgroup$ – Peter K. May 23 '13 at 11:40
  • 1
    $\begingroup$ As well as not cross-posting, it might also be a good idea to stick to just the one user account. $\endgroup$ – Paul R May 23 '13 at 12:18
2
$\begingroup$

This is probably correct. Frequency domain convolution is typically only worthwhile for larger kernels. For convolution in the spatial domain the number of operations tends to increases as a square law with kernel dimension, whereas frequency domain convolution is constant time. The "tipping point" tends to be at kernel dimensions of the order of 10s of pixels, e.g. 31x31.

So, rule of thumb: for small kernels use direct convolution, for large kernels do it in the frequency domain.

$\endgroup$
  • $\begingroup$ When do you really need kernel dimensions like 31x31? But log(1920*1080)/log(2) is roughly 21 operations in total OR 21 additions and 21 multiplications = 42 operations in total? $\endgroup$ – user8005 May 23 '13 at 12:46
  • 1
    $\begingroup$ It's not at all unusual to have filter kernels this large (or even larger). There are also mathematically similar operations such as cross-correlation, e.g. for template matching, where the "kernel" is the same size as the target image. Note that for frequency domain convolution (or correlation) there are two forward FFTs and one reverse FFT, so you probably need to multiply your operation count by 3 (or possibly just 2, since one forward FFT can usually be amortised, as it's normally constant). $\endgroup$ – Paul R May 23 '13 at 13:29
  • $\begingroup$ " two forward FFTs and one reverse FFT" Why 2 forward and one reverse? And not 1 forward and 1 reverse? Again: log(1920*1080)/log(2) is roughly 21 operations in total OR 21 additions and 21 multiplications = 42 operations in total? $\endgroup$ – user8005 May 23 '13 at 14:09
  • 1
    $\begingroup$ To clarify further: you need to transform both your image and your kernel to the frequency domain, so that's 2 x forward FFTs. Then after multiplying in the frequency domain you need to apply an inverse FFT on the product to get back to the spatial domain. So 2 x forward FFT and 1 x inverse FFT in total (although one of the forward FFTs typically needs to be done only once). $\endgroup$ – Paul R May 23 '13 at 14:33
  • 1
    $\begingroup$ Please ask another question on this forum, and accept this answer for the current question. This comment train is being flagged by the system as excessive. Use a chat room if you need discussion. Comments are not the place for discussion. $\endgroup$ – Peter K. May 23 '13 at 21:41

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.