logo标签列表

Python中基于FFT的2D卷积和相关性。

pythonimagenumpysignal-processingfft
24

scipy（或其他流行的库）中是否内置了基于FFT的2D交叉相关或卷积函数？

这里有一些类似的函数：

  • scipy.signal.correlate2d - "通过 convolveND 实现的直接方法，对于大数据而言速度较慢"
  • scipy.ndimage.correlate - "使用精确计算 (即非FFT) 对给定的核心进行相关的数组"
  • scipy.fftpack.convolve.convolve，我不太理解，但似乎是错误的

Numarray 有一个带有 fft = True 开关的 correlate2d() 函数，但我猜Numarray被合并到Numpy中，我找不到是否包括此函数。

1
请注意，在编程中使用精确计算（而不是快速傅里叶变换）几乎等同于说它很慢:) 更确切地说，如果信号和核的大小大致相同（如果核比输入小得多，则傅里叶变换实际上可能比直接计算更慢），则基于傅里叶变换的方法将更快。 - David Cournapeau
理想情况下，FFT算法会自动处理零填充以达到最佳速度的正确大小。 - endolith
1
哦，你不是在谈论零填充，而是在讨论如何将一个5x5的图像与一个2000x2000的图像匹配。为什么算法不能猜测使用快速傅里叶变换（FFT）更有效，并以更快的方式执行呢？ - endolith
2
scipy有一个fftconvolve函数。http://docs.scipy.org/doc/scipy/reference/generated/scipy.signal.fftconvolve.html#scipy.signal.fftconvolve - endolith
6个回答
25
我发现了scipy.signal.fftconvolve，正如magnus指出的那样（链接），但当时没有意识到它是n维的。由于它是内置的并且产生正确的值，似乎是理想的解决方案。
来自2D卷积示例：
In [1]: a = asarray([[ 1, 2, 3],
   ...:              [ 4, 5, 6],
   ...:              [ 7, 8, 9]])

In [2]: b = asarray([[-1,-2,-1],
   ...:              [ 0, 0, 0],
   ...:              [ 1, 2, 1]])

In [3]: scipy.signal.fftconvolve(a, b, mode = 'same')
Out[3]: 
array([[-13., -20., -17.],
       [-18., -24., -18.],
       [ 13.,  20.,  17.]])

正确！另一方面，STSCI版本需要额外的工作才能使边界正确吗？

In [4]: stsci.convolve2d(a, b, fft = True)
Out[4]: 
array([[-12., -12., -12.],
       [-24., -24., -24.],
       [-12., -12., -12.]])

(The STSCI方法还需要编译，但我没有成功（我只是注释掉了非Python部分），有一些错误，例如 this 并且会修改输入（[1, 2] 变成 [[1, 2]]）等。因此，我将我的接受答案更改为内置的 fftconvolve() 函数。)

当然，相关性与卷积是相同的，但一个输入被反转：

In [5]: a
Out[5]: 
array([[3, 0, 0],
       [2, 0, 0],
       [1, 0, 0]])

In [6]: b
Out[6]: 
array([[3, 2, 1],
       [0, 0, 0],
       [0, 0, 0]])

In [7]: scipy.signal.fftconvolve(a, b[::-1, ::-1])
Out[7]: 
array([[ 0., -0.,  0.,  0.,  0.],
       [ 0., -0.,  0.,  0.,  0.],
       [ 3.,  6.,  9.,  0.,  0.],
       [ 2.,  4.,  6.,  0.,  0.],
       [ 1.,  2.,  3.,  0.,  0.]])

In [8]: scipy.signal.correlate2d(a, b)
Out[8]: 
array([[0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [3, 6, 9, 0, 0],
       [2, 4, 6, 0, 0],
       [1, 2, 3, 0, 0]])

而最新修订版已通过内部使用2的幂大小进行加速（然后我通过使用实数FFT进行实际输入和使用5光滑长度而不是2的幂 进一步加速:D）。

8

请查看scipy.signal.fftconvolve、signal.convolve和signal.correlate（有一个signal.correlate2d，但似乎返回的是一个偏移的数组，而不是居中的数组）。

我将我的接受答案更改为此，如下所述https://dev59.com/bHNA5IYBdhLWcg3wEpkU#1768140 - endolith
你好，只是一个无关的问题。 correlate2d在形状为2048x2048的2D数组上运行需要多长时间？ - lordparthurnaax
5
我也看到了，但似乎它不再包含在SciPy中了？
import scipy.stsci.convolve Traceback (most recent call last): File "<stdin>", line 1, in <module> ImportError: 没有名为convolve的模块
 - endolith
嗨 - 我已经复制了我的提示符输出。你的是什么版本？ - ars
显然有些问题：http://pastebin.com/mdd2bc6d知道它的存在是好的。 - endolith
奇怪。从你的ipython提示中，我看到你正在使用Python 2.6版本。而我使用的是Python 2.5.2版本。我不知道为什么scipy会有不同的版本发布。也许重新安装scipy并查看问题是否仍然存在会更容易一些？ - ars
它在我的Windows机器上使用2.6版本可以运行，但在其他Ubuntu机器上无法运行，因此这必须是Ubuntu的打包问题。https://bugs.launchpad.net/bugs/397217 - endolith
你可以使用scipy.signal中的correlate2d：它使用与stsci.convolve相同的实现技术（没有FFT）。2.6问题很奇怪 - 可能与distutils有关。 - David Cournapeau
4
我编写了一个交叉相关/卷积包装器，它负责填充和nans，并包含一个简单的平滑包装器，链接在这里。虽然它不是一个流行的软件包，但除了numpy(或fftw以获得更快的fft)之外，它也没有其他依赖项。
此外，我还实现了一个FFT速度测试代码，链接在这里，以防有人感兴趣。令人惊讶的是，至少在我的机器上，它显示出numpy的fft比scipy的更快。
编辑：将代码移动到N维版本，链接在这里。
3
根据SciPy文档，它并不是基于FFT的，正如我在问题中提到的那样。http://www.scipy.org/SciPyPackages/Ndimage - endolith
1
Convolve包也可以从stsci_python存储库中获取。它包括correlate2d函数，该函数具有fft=True开关，正如您之前提到的那样。https://www.stsci.edu/svn/ssb/stsci_python/stsci_python/trunk/convolve/lib/Convolve.py - Vicki Laidler
哦！如果我删除对_correlate的引用，我可以直接导入那个Python文件。FFT相关操作都是在Python中完成的。现在它已经正常工作了。 :) 谢谢！ - endolith
看起来 stsci 被从 SciPy 中移除了（这就是为什么它不工作），而 stsci_python 版本现在是权威版本，所以我将其移动到被接受的答案。 - endolith
1
此外，一维卷积/相关操作没有进行FFT加速。 :( - endolith
2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接