CODEWITHSUNDEEP
signal-processingfftshiftconvolution
Dith
Dith

Reputation: 151

Why is my convolution result shifted when using FFT

I'm implementing Convolutions using Radix-2 Cooley-Tukey FFT/FFT-inverse, and my output is correct but shifted upon completion.

My solution is to zero-pad both input size and kernel size to 2^m for smallest possible m, tranforming both input and kernel using FFT, then multiply the two element-wise and transform the result back using FFT-inverse.

As an example on the resulting problem:

 0  1  2  3  0  0  0  0
 4  5  6  7  0  0  0  0
 8  9 10 11  0  0  0  0
12 13 14 15  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

with identity kernel

0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0

becomes

 0  0  0  0  0  0  0  0
 0  0  1  2  3  0  0  0
 0  4  5  6  7  0  0  0
 0  8  9 10 11  0  0  0
 0 12 13 14 15  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

It seems any sizes of inputs and kernels produces the same shift (1 row and 1 col), but I could be wrong. I've performed the same computations using the online calculator at this link! and get same results, so it's probably me missing some fundamental knowledge. My available litterature has not helped. So my question, why does this happen?

Upvotes: 3

Views: 2370

Answers (2)

Dith
Dith

Reputation: 151

So I ended up finding the answer why this happens myself. The answered is given through the definition of the convolution and the indexing that happens there. So by definition the convolution of s and k is given by

(s*k)(x) = sum(s(k)k(x-k),k=-inf,inf)

The center of the kernel is not "known" by this formula, and thus an abstraction we make. Define c as the center of the convolution. When x-k = c in the sum, s(k) is s(x-c). So the sum containing the interesting product s(x-c)k(c) ends up at index x. In other words, shifted to the right by c.

Upvotes: 5

hotpaw2
hotpaw2

Reputation: 70673

FFT fast convolution does a circular convolution. If you zero pad so that both the data and kernel are circularly centered around (0,0) in the same size NxN arrays, the result will also stay centered. Otherwise any offsets will add.

Upvotes: 3

Related Questions