使用傅里叶变换进行卷积？

Question

根据卷积定理，我们可以将傅里叶变换算子转换为卷积。

使用Python和Scipy，我的代码如下但不正确。 你能帮我解决问题并解释一下吗？

import tensorflow as tf
import sys
from scipy import signal

from scipy import linalg
import numpy as np

x = [[1 , 2] , [7 , 8]]

y = [[4 , 5] , [3 , 4]]


print "conv:" ,  signal.convolve2d(x , y , 'full')

new_x = np.fft.fft2(x)
new_y = np.fft.fft2(y)


print "fft:" , np.fft.ifft2(np.dot(new_x , new_y))

代码的结果：

conv: [[ 4 13 10]
 [31 77 48]
 [21 52 32]]

fft: [[  20.+0.j   26.+0.j]
 [ 104.+0.j  134.+0.j]]

我很困惑！

- zhangqianhui

---

你是否知道 scipy.signal.fftconvolve？ - user7138814

我没有安装Scipy，所以不知道它产生了什么输出。你应该将代码的输出添加到你的问题中。你希望Numpy产生[[ 67. 65.] [ 79. 77.]]吗？ - PM 2Ring

我不知道scipy.signal.fftconvolve，谢谢。 - zhangqianhui

@PM2Ring，是的，我希望结果是[[4 13 10] [31 77 48] [21 52 32]]，而不是你所说的。 - zhangqianhui

@user7138814 谢谢，这种方法很有用，结果与conv2d相同。 - zhangqianhui

请参阅https://dev59.com/nofca4cB1Zd3GeqPncm1。 - Warren Weckesser

Answer 1

问题可能在于离散和连续卷积的差异。卷积核（即y）将延伸到x的边界之外，这些区域需要在卷积中进行计算。

默认情况下，scipy.signal.convolve将使用0填充超出边界的区域，这会导致结果偏差： https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.signal.convolve2d.html 傅里叶乘法不会默认执行此操作 - 您可以通过创建填充的x、y数组并比较结果来测试这一点。

随着核大小远小于图像尺寸，这些技术之间的差异应该会减小。

进一步说明 - 不应使用new_x、new_y之间的点积。相反，只需使用*运算符乘以数组。

希望这有所帮助。

- danjampro

---

区别不在于离散与连续，而在于循环与填充。请参见https://dev59.com/nofca4cB1Zd3GeqPncm1。 - Warren Weckesser

Answer 2

我回答了我的问题。 正确的代码。

import sys
from scipy import signal

from scipy import linalg
import numpy as np

x = [[1 , 0 , 0 , 0] , [0 , -1 , 0 , 0] , [0 , 0 , 3 , 0] , [0 , 0 , 0 , 1]]
x = np.array(x)
y = [[4 , 5] , [3 , 4]]
y = np.array(y)

print "conv:" ,  signal.convolve2d(x , y , 'full')

s1 = np.array(x.shape)
s2 = np.array(y.shape)

size = s1 + s2 - 1


fsize = 2 ** np.ceil(np.log2(size)).astype(int)
fslice = tuple([slice(0, int(sz)) for sz in size])


new_x = np.fft.fft2(x , fsize)


new_y = np.fft.fft2(y , fsize)
result = np.fft.ifft2(new_x*new_y)[fslice].copy()

print "fft for my method:" , np.array(result.real , np.int32)

print "fft:" , np.array(signal.fftconvolve(x ,y) , np.int32)

- zhangqianhui

---

感谢您发布正确的代码。一个快速的问题：告诉您如何计算size、fsize和fslice的来源/书籍/讲座是什么？ - ady

我几乎确定这个fsize与fft计算速度的事实有关，如果大小是“2的幂”（2^n），则fft计算速度会快得多。因此，如果您有一个大小为1000的数组，它会将其变为1024以更快地计算，然后使用fslice来剪切结果中多出来的24个值。 - J Agustin Barrachina

为什么对于这些情况，计算速度会更快，可以通过任何有关fft工作原理的教程轻松理解（我指的是计算fft的算法，而不是傅里叶变换理论本身）。 - J Agustin Barrachina