3
$\begingroup$

Consider an $M\times N$ image $f$ and an $G \times K$ filter $h$. Given that convolution in the spatial domain corresponds to multiplication in the Fourier domain, then we can perform a convolution of $f$ with $h$ (that is, we can filter image $f$ using filter $h$) by multiplying the Fourier transforms of $f$ and $h$, $\hat{f}* \hat{h}$, and then perform an inverse discrete Fourier transform of the result, $\hat{f}* \hat{h}$, where $\hat{f}$ and $\hat{h}$ are respectively the Fourier transform of image $f$ and kernel $h$.

However, to do that, we need to make sure that $\hat{f}$ and $\hat{h}$ have the same dimension. So, we use the zero padding technique. We pad both the image $f$ and $h$, before finding their Fourier transforms. More precisely, we pad each of them with zeros, such that their new size is $(M + G - 1) \times (N + K - 1)$. This padding is apparently required (for both $f$ and $h$), but I am trying to understand why.

Why exactly is this the case? I think it has something to do with the assumption that $f$ is periodic. So, the conclusion would be that we can't simply zero pad $h$ (without also zero padding $f$), but I don't get why.

$\endgroup$
  • $\begingroup$ Do you want code? See my answer and let me know if you have any interest in code. $\endgroup$ – Royi Apr 3 at 19:37
4
$\begingroup$

The result of a convolution of a data vector of length M with a kernel of length G is of length M + G - 1. (the maximum length of the non-zero portion, even though the limits of integration is sometimes written as from -infinity to +infinity)

This is clearly (G - 1) elements longer than the original data vector.

So where do these new, "extra", additional result values go? If you don't zero pad when doing an FFT fast convolution, these "extra" result values simply get added into some portion of the first part of the length M convolution result, wrapping around the edge, which likely messes up your desired linear convolution result.

But if you zero-pad, then these "extra" values get added to the zero-padding, which is less likely to wrap-around far enough to mess up your desired convolution result.

Both are circular convolution, but a circular wrap into a bunch of zero-padding is far far easier to delete or remove, then when it's added into, and thus all mixed up with the results you most likely actually want. e.g. becoming artifacts along the edge of your filtered image.

You have to zero pad the kernel to the same length as the data so that their FFTs also end up the same length, which allows straight forward multiplication of those 2 equal length FFT vectors, before IFFT-ing the multiplied result.

So, how much to zero-pad? By any amount >= (G - 1). Perhaps rounding up to the nearest size for which your chosen FFT implementation is performant, usually a size which is the product of only very small primes, such as 2 (and/or maybe 3, 5 or perhaps 7 as well).

$\endgroup$
  • $\begingroup$ it's a better answer than mine. $\endgroup$ – robert bristow-johnson Apr 3 at 0:49
  • $\begingroup$ Why is the result of the convolution of a signal of length $M$ with a kernel of length $G$ a signal of length $M + G - 1$. Where can we see this from the definition? I am not yet very familiar with the convolution operation. $\endgroup$ – nbro Apr 3 at 20:56
  • $\begingroup$ There are some nice animations of the convolution process on wikipedia. Also a definition in term of an integral. $\endgroup$ – hotpaw2 Apr 4 at 4:55
2
$\begingroup$

The reason why this zero-padding is necessary is that if you will be filtering (or convolving) $f$ and $h$ using multiplication in the frequency domain and you're using a computer to do it to the numerical data representing $f$ and $h$, you will be using the Discrete Fourier Transform (DFT). but the only kind of convolution that is done with the DFT is circular-convolution.

The zero-padding is necessary to make the circular data appear as the linear data.

$\endgroup$
  • $\begingroup$ Can you elaborate this "but the only kind of convolution that is done with the DFT is circular-convolution"? I don't understand this part, because I am not familiar with circular and non-circular convolutions. $\endgroup$ – nbro Apr 3 at 8:26
  • $\begingroup$ @nbro, do you understand the periodic extension of data that is inherent to the DFT? when you "Perform Filtering in the Fourier Domain" using a computer and discrete-time representation of signals, the Fourier Transform used is the Discrete Fourier Transform. the FFT is a "fast" or efficient method of computing the DFT. $\endgroup$ – robert bristow-johnson Apr 3 at 19:43
1
$\begingroup$

There are 2 things to take under consideration in order to apply 2D Convolution in Frequency Domain:

  1. Padding and Shifting the Filter in order to match the size of the image.
    See my answer to Applying Image Filtering (Circular Convolution) in Frequency Domain.
  2. working with the fact that DFT means there is an implicit assumption the signals are periodic. It means it is equivalent to applying convolution in spatial domain with Periodic / circular Extension / Padding. In order to apply regular linear convolution one must pad the image in spatial domain prior to the transformation into the frequency domain. The padding must be larger then the radius of the filter. Once the transformation is reversed after frequency domain multiplication the extra padding should be removed.

There is a code to see how it is implemented in real world, See my StackExchange Signal Processing Q56407 GitHub Repository. Specifically have a look at ImageFilteringFrequencyDomain() to see the proper method to pad the image in order to have the correct output.
I implemented the 4 most used padding to match MATLAB's imfilter() function.

Reference

$\endgroup$
  • $\begingroup$ What do you mean by "radius" of the filter? $\endgroup$ – nbro Apr 3 at 20:38
  • $\begingroup$ Usually in image processing the size of the filter is odd number. Let's say 11 x 13 so the radius is 5 and 6. Again, If oyu want, we can create a MATLAB code to well define it in code. $\endgroup$ – Royi Apr 3 at 20:39
  • $\begingroup$ If you're willing to do it, it might be useful, but I am not forcing you. I have also tried to filter an image (both in spatial and frequency domain) using a Gaussian filter, and I had to pad the image using the numbers I described in my question. However, there are a few concepts I am still not fully grasping. For example, the concept of a periodic signal or the difference between circular and non-circular convolution. I have to check these out. $\endgroup$ – nbro Apr 3 at 20:41
  • $\begingroup$ No need to force me :-). I'm asking if you think it will assist you to understand better the answer. $\endgroup$ – Royi Apr 3 at 20:43
  • $\begingroup$ Maybe yes. A simple example which shows the importance of padding (both the image and the filter) I think will help. $\endgroup$ – nbro Apr 3 at 20:44

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.