python - 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

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.]]