user3886429 user3886429 - 14 days ago 8
Python Question

using Fourier transforms to do convolution?

according to the Convolution theorem(links) , we can the Fourier transform operator to convolution.

Using python and scripy , my code is below but not correct.
Can you help me and explain it?

import tensorflow as tf
import sys
from scipy import signal

from scipy import linalg
import numpy as np

x = [[1 , 2] , [7 , 8]]

y = [[4 , 5] , [3 , 4]]


print "conv:" , signal.convolve2d(x , y , 'full')

new_x = np.fft.fft2(x)
new_y = np.fft.fft2(y)


print "fft:" , np.fft.ifft2(np.dot(new_x , new_y))


the result of code:

conv: [[ 4 13 10]
[31 77 48]
[21 52 32]]

fft: [[ 20.+0.j 26.+0.j]
[ 104.+0.j 134.+0.j]]


I'm confused!

Answer

The problem may be in the discrepancy between the discrete and continuous convolutions. The convolution kernel (i.e. y) will extend beyond the boundaries of x, and these regions need accounting for in the convolution.

scipy.signal.convolve will by default pad the out of bounds regions with 0s, which will bias results: https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.signal.convolve2d.html

The Fourier multiplication will not do this by default - you could test this by making padded x, y arrays and comparing the results.

The discrepancy between such techniques should diminish as the kernel size becomes much less than the image dimensions.

As a further note - you should not use the dot product between new_x, new_y. Instead, just multiply the arrays with the * operator.

Hope this helps.

Comments