0
$\begingroup$

I am a big fan of fft convolution. So, I mostly try to avoid non-fft convolution.

Suppose, I am trying to convolute an image with another image. Suppose the first image is $512\times 512$, and, the mask image is $520\times 255$. How would we convolve them in the frequency domain?

Two major issues are to be addressed here,

  1. to apply fft, images must have dimensions which are the multiple of power of 2. Our image and mask may or may not have dimensions of power of 2

  2. to apply the fft, the dimensions of the image and the mask must be equal.

So, in order to address both issues, we can do any one of the following,

  1. we can take the max of the width and heights of both image and the mask, round them to next power of 2 and, pad them.

  2. we can take the sum of the widths and heights of the image and mask, round them to next power of 2 and, pad them.

Questions:

  • So, in both of the cases we are actually obtaining oversized output images with padding. Am I right?

  • Suppose, I pad an image and get it FFT-filtered (Sharpened/Blurred/... and so on). So, I obtain a filtered image with padding. Now, I need to remove the padding to obtain the filtered image without padding. Am I correct?

  • If YES, should I just crop the image?

  • Or, is there any better way possible altogether from the ground up?

Suppose, this is the original image ($512 \times 512$),

enter image description here

And, suppose, the following is the filtered image with padding ($1024 \times 1024$),

enter image description here

Now, I want to obtain this,

enter image description here

  • How should I remove padding from this image?

  • Should I just crop, or, is there any better technique to get around this problem from start?

$\endgroup$
  • 1
    $\begingroup$ It's not clear to me what your question is. Yes, you can filter the padded image. Depending on your filter, the padded-and-then-filtered image may or may not have padding (if the original padding is larger than the filter dimension, then there may be some padding remaining). Please edit your post to clarify. $\endgroup$ – Peter K. Aug 26 '16 at 21:44
  • $\begingroup$ It's still not clear – the question which part of the result of your filtering is relevant to your application is something that only you could answer at this point. $\endgroup$ – Marcus Müller Aug 27 '16 at 17:45
0
$\begingroup$

First, let's start with the wrong part of your post:

to apply fft, images must have dimensions which are the multiple of power of 2.

This is incorrect. FFTs do not have to be a power of 2. The only requirements for applying an FFT are that you can decompose the signal length into its prime factors and that you have an FFT that can deal with these prime factors.

to apply the fft, the dimensions of the image and the mask must be equal.

This is correct. To do the point-wise multiplication in the frequency domain, it's easier to do when both image and kernel FFTs are the same size.

we can take the max of the width and heights of both image and the mask, round them to next power of 2 and, pad them.

The power of 2, as pointed out before, is incorrect.

the width and heights of both image and the mask, round them is also incorrect.

Your second option:

we can take the sum of the widths and heights of the image and mask, round them to next power of 2 and, pad them.

is closer to the truth, but still incorrect.

Suppose your image is $N\times M$ and your kernel is $K \times L$. To use the FFT to do linear convolution you need pad both of them to be $(N + K - 1) \times (M + L - 1)$. If you don't you'll get time aliasing from the circular convolution.

Now, to answer your questions:

So, in both of the cases we are actually obtaining oversized output images with padding. Am I right?

Yes, to avoid circular convolution results (and the associated "time" / "spatial" aliasing), you need to pad.

Suppose, I pad an image and get it FFT-filtered (Sharpened/Blurred/... and so on). So, I obtain a filtered image with padding. Now, I need to remove the padding to obtain the filtered image without padding. Am I correct?

Yes. If you're interested in an in-place replacement (so that the resulting image aligns with the original unfiltered image), then you need to remove the padding.

If YES, should I just crop the image? Or, is there any better way possible altogether from the ground up?

Yes, just crop the image at the right place.

$\endgroup$
  • $\begingroup$ Suppose, I have a 543X193 image, and, a 193 X 543 mask. How can I crop the output? $\endgroup$ – user18425 Aug 28 '16 at 16:30
  • $\begingroup$ @anonymous : Seems like a pathological case having a mask that is way bigger than the image in one direction. You take the sizes $(543 + 193 - 1) \times (193 + 543 - 1) $ so you obtain an output image of size $ 735 \times 735$. Without knowing more about your mask, the size of it means that the output image is shifted by 96 and 271 samples in each direction, so you start from there and go 542 in one direction and 192 in the other to get your output $543 \times 193$ image. It'll also depend on how your FFT re-indexes... :-) $\endgroup$ – Peter K. Aug 28 '16 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy