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
  

Does this assume x and y are of the same size? I see no zero-padding.

This works! I am using with powers of 2 square image sizes Thanks

padding !

This isn't technically convolution. For real 'y', this is equivalent to correlation and only for real symmetric 'y' kernels is this equivalent to convolution. There is no flipping of the kernel in convolution, a common misconception because of the way it is often illustrated. See for example https://dsp.stackexchange.com/questions/29065/do-i-have-to-flip-my-kernel-when-performing-an-fft-based-convolution/29066

This isn't technically convolution. For real 'y', this is equivalent to correlation and only for real symmetric 'y' kernels is this equivalent to convolution. There is no flipping of the kernel in convolution, a common misconception because of the way it is often illustrated. See for example https://dsp.stackexchange.com/questions/29065/do-i-have-to-flip-my-kernel-when-performing-an-fft-based-convolution/29066

I agree with you!

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.