1
$\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
1
$\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, privacy policy and cookie policy

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