0
$\begingroup$

I want to convolve 2 images I1 and I2. Let's assume they have the same size. I know 2 methods: 1) Use direct definition of 2D convolution 2) i. Computer FFT of I1 (call it I1_FFT) and FFT of I2 (call it I2_FFT) ii. Multiply I1_FFT and I2_FFT (call it I1I2_FFT) iii. Compute inverse FFT of result I1I2_FFT

I want to know the number of multiplications and additions for each case. Note I don't want the Big O type of complexity.

It would be great if the answer includes a derivation.

In the end, I want to know for a specific NxM sized image, when I should use method 1 or 2.

$\endgroup$
1
$\begingroup$

Asking for a derivation creates a suspicion that this is a homework problem, and to answer your homework is a disservice to you, your classmates and your teacher, so look at:

https://en.wikipedia.org/wiki/Multidimensional_discrete_convolution

You can derive the multiply/add counts from the article, particularly for the separable to 1-d case. You might also note that one can mix direct and fft approaches. Another complication that is introduced comes from FFT code requiring initialization, so the number of images of the same sizes you convolve, implicitly enters the operations count.

to check your results can use lightspeed in Matlab which brings back the flops counts that the Mathworks dropped. Clive Mohler wrote an article why they dropped them, and for good reasons.

https://github.com/tminka/lightspeed

On a modern multiprocessor system, I/O is often more of a bottleneck, so the only reliable way to figure out which implementation to use, is to profile and benchmark.

$\endgroup$
  • $\begingroup$ Thanks for your response. The lightspeed link is cool. In response to your answer however, it might be considerate to adjust your tone. It's aggresive. I asked for a derivation, so I could trust/verify the answers users post. Otherwise it's like I'm just trusting some unknown source. I hope this makes sense to you. $\endgroup$ – user3731622 Jul 26 '17 at 18:34
  • $\begingroup$ Part of the guidelines for this group is that the person asking the question demonstrates some effort. The advice offered here is free. I am not your employer, your teacher, or your mother. You could demonstrate some respect by showing some effort. $\endgroup$ – Stanley Pawlukiewicz Jul 26 '17 at 19:30
  • $\begingroup$ Fair enough. My post doesn't reflect my effort. In the future I will try to incorporate this group guideline. This makes sense. Nevertheless again you're last comment has taken an unnecessarily negative tone. $\endgroup$ – user3731622 Jul 26 '17 at 22:27
  • $\begingroup$ In the future, I'll try to be a bright shimmery bundle of sugar coated enthusiasm, all sparkles and unicorns $\endgroup$ – Stanley Pawlukiewicz Jul 26 '17 at 22:56

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.