CUDA - how to pad kernel before convolution?

Question

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?

That isn't padding. As the captions clearly indicate, that is cyclic shifting of the convolution kernel - the kernel must be "wrapped around" the computational domain in some edge cases. Also, the last two "CUDA" questions you have asked really have nothing to do with CUDA programming at all, they are basic algorithm/signal processing questions which apply equally if you were writing a serial implementation in matlab. Perhaps you should focus on the understanding of the operations first, then worry how to program them in parallel. — talonmies
They are written and implemented in the CUDA SDK as I reported with the pdf. If you can help me with the "weird wrapping" I'd be grateful — Johnny Pauling
Also: the documentation clearly states "Therefore, assuming the image is bigger than the convolution kernel, which is usually the case in practice, the convolution kernel needs to be expanded to the image size and padded according to Figure 1" so it's PADDED according to figure 1 — Johnny Pauling

Johnny Pauling Johnny Pauling · Accepted Answer · 2012-07-10T08:36:29

Solved by padding and extending the matrix to get rid of circular artifacts (see nvidia CUDA sdk papers)

CUDA - how to pad kernel before convolution?

1 Answers