Cyclic convolution with CUDA

Question

In the FFT2D paper

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

in the figure 1 and 2 it's stated that:

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. As can be seen on figures 2 and 3 (see below), cyclic convolution with the expanded kernel is equivalent to cyclic convolution with initial convolution kernel.

If I perform the convolution between the kernel and the image for an element and I try to perform the convolution between the expanded kernel and the image for the same element, it yields different results.

I read somewhere that "cyclic convolution" is the same as a classic "convolution", is this correct? Otherwise how should I interpret this?

FFT always performs cyclic convolution. If you don't want that, you need to pad both the image and the kernel, then crop the result. — Ben Voigt

tskuzzy tskuzzy · Accepted Answer · 2012-07-03T18:05:56

No, a cyclic convolution, also known as a circular convolution, is not the same as a regular convolution. The kernel "wraps around" in a circular convolution.

Take x=[1 2 3 4 5] and h=[1 2 3] for example:

First you flip h and pad with zeros: h'=[0 0 3 2 1]. Then to get the first element, you do the usual dot product:

(x*h)[0] = 0*1 + 0*2 + 3*3 + 2*4 + 1*5

To get the second element, you shift the kernel over by one and dot again:

(x*h)[1] = 0*1 + 1*2 + 2*3 + 3*4 + 0*5

Same with the third. To get the fourth though, the kernel wraps around so you get:

(x*h)[3] = 2*1 + 3*2 + 0*3 + 0*4 + 1*5

Cyclic convolution with CUDA

1 Answers