CODEWITHSUNDEEP
pythonnumpyscipyfftconvolution
beckstev
beckstev

Reputation: 93

Using the convolution theorem and FFT does not lead to the same result as the scipy.convolve function

I want to get familiar with the fourier based convolutions. Therefore, I created a small example using numpy.fft and scipy.signal.convolve. However, the results of the two operations are different and I do not know why. Does someone has an idea?

I have already tried to use the different modes of scipy.signal.convolve.

The example:

import numpy as np
from scipy.signal import convolve

# Generate example data
data = np.array([1, 1, 1, 1, 1, 1])
kernel = np.array([0, 1, 2, 1, 0, 0])

# Using scipy.signal.convolve
A = convolve(kernel, data, mode='full')
B = convolve(kernel, data, mode='valid')
C = convolve(kernel, data, mode='same')

# Using the convolution theorem 
D = np.fft.ifft(np.fft.fft(kernel) * np.fft.fft(data))

The results are:

A = array([0, 1, 3, 4, 4, 4, 4, 3, 1, 0, 0])
B = array([4])
C = array([3, 4, 4, 4, 4, 3])

D = array([4.+0.j, 4.+0.j, 4.+0.j, 4.+0.j, 4.+0.j, 4.+0.j])

Upvotes: 1

Views: 2158

Answers (1)

Paul R
Paul R

Reputation: 212969

You need to pad data and kernel with N-1 zeroes to avoid circular convolution...

import numpy as np
from scipy.signal import convolve

# Generate example data
data = np.array([1, 1, 1, 1, 1, 1])
kernel = np.array([0, 1, 2, 1, 0, 0])

# Using scipy.signal.convolve
A = convolve(kernel, data, mode='full')

# Using the convolution theorem - need to pad with N-1 zeroes
data = np.array([1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0])
kernel = np.array([0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0])

D = np.fft.ifft(np.fft.fft(kernel) * np.fft.fft(data))

print (A)
print (D)

Result:

[0 1 3 4 4 4 4 3 1 0 0]
[2.4e-16+0.j 1.0e+00+0.j 3.0e+00+0.j 4.0e+00+0.j 4.0e+00+0.j 4.0e+00+0.j
 4.0e+00+0.j 3.0e+00+0.j 1.0e+00+0.j 3.2e-16+0.j 1.6e-16+0.j]

Upvotes: 2

Related Questions