3
$\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$
2
  • $\begingroup$ Related - dsp.stackexchange.com/questions/52760. $\endgroup$
    – Royi
    May 26, 2021 at 5:22
  • $\begingroup$ Could you please review my question? Please mark it if it answers your question. Thank You. $\endgroup$
    – Royi
    Jan 30, 2023 at 19:02

2 Answers 2

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. Cleve Moler, MathWorks cofounder, 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$
4
  • $\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$ Jul 26, 2017 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$
    – user28715
    Jul 26, 2017 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$ Jul 26, 2017 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$
    – user28715
    Jul 26, 2017 at 22:56
0
$\begingroup$

Vanilla implementation of each method for image of size m x n and kernel of size k x l will yield:

  1. Spatial Domain Convolution - O(mnkl) as for each pixel in the image we do kl multiplications (Additions are discarded).
  2. Frequency Domain Convolution - O(mn log(mn) + mn) as the complexity of the FFT is mn log(mn) and we add the multiplication (You could add factor of 4 for doing it twice and back and forth).

But in practice there many nuances:

  1. Many times the kernel is Separable or can be approximated by 1-2 separable filters (For instance, Gaussian Filter).
  2. If the kernel is very small compared to the image, better use direct method.
  3. If you apply the same filter on many images you may even consider using Matrix Form (As done in CNN's).
  4. In Frequency Domain you apply Convolution with Circular Boundary Condition. It means that if you're after different boundary conditions you'll need to pad and then complexity is higher and many memory operations are done.

I can go on and on...

You may have a look at Filtering n×n Images by Separable m×m Filters. Computation Time for Filtering Using FFT, 2D Convolution and Two 1D Convolutions.

In order to say which is better, one must be very specific about the case.
In most cases, use efficient spatial domain code. This is my choice in most cases.

$\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.