使用 fftconvolve 计算包裹的二维相关性

Question

我有一组二维数组，我必须计算它们的二维相关性。我一直在尝试很多不同的东西（甚至用 Fortran 编程），但我认为最快的方法是使用 FFT 计算它。

根据我的测试和 this answer，我可以使用 scipy.signal.fftconvolve，如果我试图用 boundary='fill' 重现 scipy.signal.correlate2d 的输出，它工作正常。所以基本上这个

scipy.signal.fftconvolve(a, a[::-1, ::-1], mode='same')

等于这个（略有偏移除外）

scipy.signal.correlate2d(a, a, boundary='fill', mode='same')

问题是数组应该在包装模式下计算，因为它们是二维周期数组（即 boundary='wrap'）。因此，如果我试图重现

的输出

scipy.signal.correlate2d(a, a, boundary='wrap', mode='same')

我不能，或者至少我不知道该怎么做。（而且我想使用 FFT 方法，因为它更快。）

显然 Scipy 曾经有 something like that 可以解决这个问题，但显然它落在后面了，我找不到了，所以我认为 Scipy 可能有放弃了对它的支持。

无论如何，有没有办法使用 scipy 或 numpy 的 FFT 例程来计算周期数组的相关性？

Answer 1

可以使用 FFT 实现包裹相关。下面是一些代码来演示如何：

In [276]: import numpy as np

In [277]: from scipy.signal import correlate2d

创建一个随机数组 a 以用于：

In [278]: a = np.random.randn(200, 200)

使用scipy.signal.correlate2d计算二维相关性：

In [279]: c = correlate2d(a, a, boundary='wrap', mode='same')

现在使用 numpy.fft 中的 2D FFT 函数计算相同的结果。（此代码假设 a 是正方形。）

In [280]: from numpy.fft import fft2, ifft2

In [281]: fc = np.roll(ifft2(fft2(a).conj()*fft2(a)).real, (a.shape[0] - 1)//2, axis=(0,1))

验证两种方法是否给出相同的结果：

In [282]: np.allclose(c, fc)
Out[282]: True

正如您指出的那样，使用 FFT 快得多。对于这个例子，它大约快了 1000 倍：

In [283]: %timeit c = correlate2d(a, a, boundary='wrap', mode='same')
1 loop, best of 3: 3.2 s per loop

In [284]: %timeit fc = np.roll(ifft2(fft2(a).conj()*fft2(a)).real, (a.shape[0] - 1)//2, axis=(0,1))
100 loops, best of 3: 3.19 ms per loop

这包括 fft2(a) 的重复计算。当然，fft2(a) 应该只计算一次：

In [285]: fta = fft2(a)

In [286]: fc = np.roll(ifft2(fta.conj()*fta).real, (a.shape[0] - 1)//2, axis=(0,1))

使用 fftconvolve 计算包裹的二维相关性

Computing wrapped 2D correlation with fftconvolve

python

numpy

fft

scipy

correlation