5
$\begingroup$

To filter an image we can:

  1. Use a 3x3, 5x5, 7x7, etc. filter, that is convolve the image and the filter in the space domain.
  2. Use a FFT on both the image and the filter, multiply them together in the frequency domain, and then perform an IFFT on the image to get the filtered result.

These two approaches should produce equivalent result.

Questions:

  1. Are there any conditions placed on the filter so that the results are equal?
  2. Will there be any information loss in the second approach or will the images be exactly equal (neglecting floating point precision error)?
  3. As the kernel size increases, will the second approach start outperforming the first?
Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Wouldn't the second approach be circular, such that they are not equivalent unless you zero pad? $\endgroup$
    – Dan Boschen
    Commented Mar 22, 2017 at 1:16
  • $\begingroup$ @DanBoschen: Does this mean that I would use a larger image for the FFT, the extended regions being filled with zero-valued pixels taking the image size up to NxN where N is a power of 2? Also for the first approach, is it customary to assign zero value to pixels outside of the defined range (e.g., when processing the upper left pixel, the kernel reaches outside the defined area). $\endgroup$
    – pseudomarvin
    Commented Mar 22, 2017 at 10:43
  • 1
    $\begingroup$ I am less familiar with image processing so may be off-base so did not answer below but relating it to what I would do in a simpler 1D case. That said, yes fill larger area with zeros and then truncate the result back to the original area and the results should match the first case, after you have gone through the initial values for the filter. I would test this to check. $\endgroup$
    – Dan Boschen
    Commented Mar 22, 2017 at 11:51
  • $\begingroup$ @pseudomarvin, when using fft, do we need to pad the signal to have base two size? Doesn't the FFT do it internally? $\endgroup$
    – Eduardo Reis
    Commented May 14, 2020 at 13:57
  • $\begingroup$ @EduardoReis Hi, frankly I have no idea. My guess would be that it is implementation dependent (i.e., read the docs/source of the library you're using). But your assumption seems quite reasonable! $\endgroup$
    – pseudomarvin
    Commented May 17, 2020 at 18:54

1 Answer 1

Reset to default
3
$\begingroup$

In my StackExchange Signal Processing Q38542 GitHub Repository (Look at the SignalProcessing\Q38542 folder) you will be able to see a code which implements 2D Circular Convolution both in Spatial and Frequency Domain.

Pay attention to the function CircularExtension2D().
This function align the axis origin between the image and the kernel before working in the Frequency Domain.
Remember that for Discrete Signals the implicit assumption on signals, In frequency Domain analysis, is being periodic (Circular).

In the discrete case one could indeed apply Circular Convolution by element wise multiplication in the Frequency Domain.

With proper padding one could apply linear convolution using circular convolution hence Linear Convolution can also be achieved using multiplication in the Frequency Domain.

See:

Gaussian Kernel Convolution

In depth description can be found in FFT Based 2D Cyclic Convolution.

Regarding your questions:

  1. The filter is just an array of numbers. As long as you are after 2D Circular Convolution there is no constraints on the Filter. If it is valid for 2D Spatial Circular Convolution it is valid for Frequency Domain Circular Convolution.
  2. Up to Floating Point Quantization errors both are mathematically equivalent (See Convolution Theorem).
  3. If the Convolution Kernel is similar in its size to the image and both are large enough Frequency Domain Convolution becomes more efficient than Spatial Domain.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer, In the code you provided you create another kernel using CircularExtension2D. Why we need to create a kernel corresponding to the origin of the image? Can you give the reference of the reason? Thanks $\endgroup$
    – stander Qiu
    Commented Dec 29, 2019 at 10:34
  • $\begingroup$ I'm not sure I understand your question. If I got you correctly the shift is done to match the fft2() operation. $\endgroup$
    – Royi
    Commented Dec 29, 2019 at 14:22
  • $\begingroup$ I understand now. Thanks $\endgroup$
    – stander Qiu
    Commented Dec 29, 2019 at 14:34

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.