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

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ it's a better answer than mine. $\endgroup$
    – robert bristow-johnson
    Apr 3, 2019 at 0:49
  • $\begingroup$ There are some nice animations of the convolution process on wikipedia. Also a definition in term of an integral. $\endgroup$
    – hotpaw2
    Apr 4, 2019 at 4:55
3
$\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.

Improve this answer
$\endgroup$
0
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 (Look at the SignalProcessing\Q56407 folder). 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

Improve this answer
$\endgroup$
2
  • $\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, 2019 at 20:39
  • $\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, 2019 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.