4
$\begingroup$

I don't know whether this is the right place to post this, but I suppose it is.

I know that frequency multiplication = circular convolution in time space for discrete signals (vectors).

I also know that "the convolution theorem yields the desired linear convolution result only if x(n) and h(n) are padded with zeros prior to the DFT such that their respective lengths are Nx+Nh-1, essentially zeroing out all circular artifacts."

and everything works with vectors.. but my goal is circular convolution with matrices as in this paper:

http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/convolutionFFT2D/doc/convolutionFFT2D.pdf

If you watch the first two figures (figure 1 and 2) you'll see that the kernel is padded in a weird way I've never seen before, what's this?

$\endgroup$
1
$\begingroup$

Figures 1 and 2 are not showing any padding whatsoever. The larger matrix is the data (probably image) matrix, not a padded kernel matrix. The figures are simply showing how the circular aspect of the convolution works in 2 dimensions.

$\endgroup$
  • $\begingroup$ How can I find more information on how the circular convolution works with matrices? $\endgroup$ – Johnny Pauling Jul 4 '12 at 7:08
  • 1
    $\begingroup$ @JohnPell I would concentrate on really understanding one-dimensional convolution, and then the generalization to two dimensions is pretty simple. Starting with two-dimensions, though, I think makes understanding convolution more difficult. Pretty much any introduction to signal processing will talk about convolution. $\endgroup$ – Jim Clay Jul 5 '12 at 2:59
  • $\begingroup$ Regarding circular convolution there aren't many resources talking about it in 2D, you can find a lot of stuff about 1D though $\endgroup$ – Johnny Pauling Jul 5 '12 at 6:10
0
$\begingroup$

In my StackExchange Signal Processing Q38542 GitHub Repository 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).
This is basically what's in FFT Based 2D Cyclic Convolution.

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:

enter image description here

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