scipy.ndimage.filters.convolve and multiplying Fourier Transforms give different results

Question

Here's my code:

from scipy.ndimage import filters
import numpy

a = numpy.array([[2,43,42,123,461],[453,12,111,123,55] ,[123,112,233,12,255]])
b = numpy.array([[0,2,2,3,0],[0,15,12,100,0],[0,45,32,22,0]])

ab = filters.convolve(a,b, mode='constant', cval=0)

af = numpy.fft.fftn(a)
bf = numpy.fft.fftn(b)

abf = af*bf

abif = numpy.fft.ifftn(abf)

print numpy.around(ab)
print numpy.around(abif)

The results are:

[[ 1599  2951  7153 13280 18311]
 [ 8085 51478 13028 40239 30964]
 [18192 32484 23527 36122  8726]]

[[ 37416.+0.j  32251.+0.j  46375.+0.j  32660.+0.j  23986.+0.j]
 [ 30265.+0.j  33206.+0.j  62450.+0.j  19726.+0.j  17613.+0.j]
 [ 40239.+0.j  38095.+0.j  24492.+0.j  51478.+0.j  13028.+0.j]]

How can I fix my way of doing convolution using FFT so to guarantee that it gives the same result as scipy.ndimage.filters.convolve?

Thank you.

Answer 1

This turned out to be a fascinating question. It seems that convolution using the Discrete Fourier Transform (as implemented by numpy.fft.fftn) is equivalent to a circular convolution. So all we need to do is use the 'wrap' convolution mode, and set the origin appropriately:

>>> filters.convolve(a, b, mode='wrap', origin=(-1, -2))
array([[37416, 32251, 46375, 32660, 23986],
       [30265, 33206, 62450, 19726, 17613],
       [40239, 38095, 24492, 51478, 13028]])
>>> numpy.fft.ifftn(numpy.fft.fftn(a) * numpy.fft.fftn(b))
array([[ 37416.+0.j,  32251.+0.j,  46375.+0.j,  32660.+0.j,  23986.+0.j],
       [ 30265.+0.j,  33206.+0.j,  62450.+0.j,  19726.+0.j,  17613.+0.j],
       [ 40239.+0.j,  38095.+0.j,  24492.+0.j,  51478.+0.j,  13028.+0.j]])
>>> (filters.convolve(a, b, mode='wrap', origin=(-1, -2)) ==
...  numpy.around(numpy.fft.ifftn(numpy.fft.fftn(a) * numpy.fft.fftn(b))))
array([[ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True]], dtype=bool)

The difference has only to do with the way filters.convolve handles edges. A way to use fftn to perform convolution in other modes didn't strike me right away; for a clever (and hindsight-obvious) approach to that problem, see Warren Weckesser's excellent answer.

Answer 2

As @senderle points out, when you use the FFT to implement the convolution, you get the circular convolution. @senderle's answer shows how to adjust the arguments of filters.convolve to do a circular convolution. To modify the FFT calculation to generate the same result as your original use of filters.convolve, you can pad the arguments with 0, and then extract the appropriate part of the result:

from scipy.ndimage import filters
import numpy

a = numpy.array([[2.0,43,42,123,461], [453,12,111,123,55], [123,112,233,12,255]])
b = numpy.array([[0.0,2,2,3,0], [0,15,12,100,0], [0,45,32,22,0]])

ab = filters.convolve(a,b, mode='constant', cval=0)

print numpy.around(ab)
print

nrows, ncols = a.shape
# Assume b has the same shape as a.
# Pad the bottom and right side of a and b with zeros.
pa = numpy.pad(a, ((0, nrows-1), (0, ncols-1)), mode='constant')
pb = numpy.pad(b, ((0, nrows-1), (0, ncols-1)), mode='constant')
paf = numpy.fft.fftn(pa)
pbf = numpy.fft.fftn(pb)
pabf = paf*pbf
p0 = nrows // 2
p1 = ncols // 2
pabif = numpy.fft.ifftn(pabf).real[p0:p0+nrows, p1:p1+ncols]

print pabif

Output:

[[  1599.   2951.   7153.  13280.  18311.]
 [  8085.  51478.  13028.  40239.  30964.]
 [ 18192.  32484.  23527.  36122.   8726.]]

[[  1599.   2951.   7153.  13280.  18311.]
 [  8085.  51478.  13028.  40239.  30964.]
 [ 18192.  32484.  23527.  36122.   8726.]]