1D and 2D FFT-based convolution functions in Python, using numpy.fft

fft_convolution.py

from numpy.fft import fft, ifft, fft2, ifft2, fftshift
import numpy as np

def fft_convolve2d(x,y):
    """ 2D convolution, using FFT"""
    fr = fft2(x)
    fr2 = fft2(np.flipud(np.fliplr(y)))
    m,n = fr.shape
    cc = np.real(ifft2(fr*fr2))
    cc = np.roll(cc, -m/2+1,axis=0)
    cc = np.roll(cc, -n/2+1,axis=1)
    return cc

def fft_convolve1d(x,y): #1d cross correlation, fft
    """ 1D convolution, using FFT """
    fr=fft(x)
    fr2=fft(np.flipud(y))
    cc=np.real(ifft(fr*fr2))
    return fftshift(cc)
  
if __name__ == "__main__":
  print
  

The padding isn't there. So it will not work on Mats of the different size and/or shape

I am getting this error when trying this out:

    cc = np.roll(cc, -m / 2 + 1, axis=0)

  File "<__array_function__ internals>", line 5, in roll

  File "C:\Anaconda\lib\site-packages\numpy\core\numeric.py", line 1242, in roll
    result[res_index] = a[arr_index]

TypeError: slice indices must be integers or None or have an __index__ method

I'm not sure what the problem is.

@CamiloMartinezM I wrote this as a quick sample for someone years ago. I'm guessing that I was probably using Python 2 at the time, and you may be using Python 3 now? I would try casting the indices argument in np.roll to an integer explicitly.

I think the original purpose of this code snippet was some tinkering that I was doing with a Conway's Game Of Life simulator in Python. I implemented the engine using FFT-based convolutions provided by the same code seen above: https://github.com/thearn/game-of-life

I think either numpy or scipy have built-in implementations that would be suitable (and probably more performant) for this now. These likely include things like padding options.