CODEWITHSUNDEEP
pythonscipyfft
Kevinj22
Kevinj22

Reputation: 1066

Which output from Circular Convolution is initially correct? The FFT convolution or the scipy signal wrap convolution

Doing a circular convolution via the FFT VS via scipy convolve2d using "wrap" boundary settings gives the same results, but at different positions in the output matrix.

Of these two methods which has the positions initially correct (i.e which one should I shift to match the other) ?

import numpy as np
import scipy
from scipy import signal
from numpy.fft import ifft2, fft2

imgSize = 4
filtSize = 3
padFilt = imgSize - filtSize
testImg = np.random.uniform(0,1,(imgSize,imgSize))
filter = np.random.normal(0,3.0,(filtSize,filtSize))


circConv = scipy.signal.convolve2d(testImg, filter, boundary="wrap", mode="same")

filterFFT = np.pad(filter,((0,padFilt),(0,padFilt)),'constant')
fftConv = np.real(ifft2(fft2(testImg) * fft2(filterFFT)))

# Roll the FFT output to match the wrap output
fftConv = np.roll(fftConv, (-((filterFFT.shape[0] - 1) // 2), -((filterFFT.shape[1] - 1) // 2)), axis=(0, 1))
print(circConv)
print(fftConv)

Upvotes: 0

Views: 426

Answers (1)

Paul Panzer
Paul Panzer

Reputation: 53029

Depends on where your coordinate origin is. If it is top left go with fft. If it is in the center go with convolve.

>>> a = (1, 0, 0, 0, 0)
>>> a = np.outer(a, a)
>>> a
array([[1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])
>>> np.real(ifft2(fft2(a) * fft2(a)))
array([[1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0.]])
>>> 
>>> a = (0, 0, 1, 0, 0)
>>> a = np.outer(a, a)
>>> a
array([[0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])
>>> scipy.signal.convolve2d(a, a, boundary="wrap", mode="same")
array([[0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]])

Upvotes: 1

Related Questions