为什么使用FFT时我的卷积结果会发生偏移

Question

我正在使用基于Radix-2 Cooley-Tukey FFT / FFT-inverse的卷积实现，我的输出是正确的，但在完成后会产生位移。

我的解决方案是将输入尺寸和内核尺寸都用最小可能的m填充到2 ^ m，使用FFT转换两个元素，然后按元素相乘并使用FFT-inverse将结果转换回来。

以下是一个关于结果问题的示例：

 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

使用身份内核

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

变成

 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

似乎对于任何尺寸的输入和卷积核，都会产生相同的位移（1行和1列），但我可能错了。我在这个链接上使用在线计算器进行了相同的计算，并得到了相同的结果，所以很可能是我缺少一些基础知识。我的可用文献没有帮助我解决问题。因此，我的问题是：为什么会发生这种情况？

- Dith

---

你的身份核心应该是4x4大小，对吗？将1放在索引[2,2]（从0开始）处，我认为你会得到更好的结果。 - Anders Gustafsson

是的，内核是4x4，我已经相应地编辑了帖子。我不确定您所说的基于零，但将1放置在[2,2]会进一步移动它。将1放置在[0,0]会产生正确的结果，但我不明白为什么。这是因为我需要循环移位内核，使中心（这里是1）位于[0,0]位置吗？ - Dith

如果我表达不清楚很抱歉。FFT核中左上角元素的索引应为-n/2，其中n是行和列的数量。因此，对于4x4的核，（0,0）位置位于第三行和第三列。 - Anders Gustafsson

谢谢您的回复。然而，我仍然不清楚应该如何索引它，更不用说解释为什么会发生这种情况（理论上）。使用大小为5x5的内核，零填充到8x8会生成相同的结果（仅移动1行和1列）。您说左上角应该是-n/2。那么您的意思是，在执行FFT时应该在左上角的内容，在此之前是在-n/2处。嗯。-n/2怎么不是负索引？这是偏移量吗？我如何确定内核锚点/中心？哦，天啊，我不明白...对不起... - Dith

Answer 1

最终我自己找到了为什么会发生这种情况的答案。答案通过卷积的定义和索引发生的过程给出。因此，按照定义，s和k的卷积由以下式子给出：

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

这个公式并不“知道”卷积核的中心，因此我们需要进行抽象。定义c为卷积的中心。当在求和式中x-k = c时，s(k)等于s(x-c)。因此，包含有趣乘积s(x-c)k(c)的总和最终会在索引x处结束。换句话说，向右移动了c。

- Dith

Answer 2

FFT快速卷积执行的是循环卷积。如果您进行零填充，使得数据和核心都在大小为NxN的数组中以(0,0)为中心循环对齐，则结果也将保持对齐。否则，任何偏移量都会被添加。

- hotpaw2

---

这是否意味着例如核心[[0,0,0],[0,0,0],[0,c,0]]（其中“c”为核心中心）将向下移动2行并向右移动1列？对我来说，这有点有道理。因为你说以(0,0)为中心，我有印象你是指“相对于核心中心”，这将允许负索引。是吗？ - Dith

相对于内核中心是“是”，对于“左上”部分，使用负索引进行环绕。 - hotpaw2