[Numpy-discussion] strange behavior convolving via fft

[Chris Colbert]

at least I think this is strange behavior.

When convolving an image with a large kernel, its know that its faster to
perform the operation as multiplication in the frequency domain. The below
code example shows that the results of my 2d filtering are shifted from the
expected value a distance 1/2 the width of the filter in both the x and y
directions. Can anyone explain why this occurs? I have been able to find the
answer in any of my image processing books.

The code sample below is an artificial image of size (100, 100) full of
zeros, the center of the image is populated by a (10, 10) square of 1's. The
filter kernel is also a (10,10) square of 1's. The expected result of the
convolution would therefore be a peak at location (50,50) in the image.
Instead, I get (54, 54). The same shifting occurs regardless of the image
and filter (assuming the filter is symetric, so flipping isnt necessary).

I came across this behavior when filtering actual images, so this is not a
byproduct of this example. The same effect also occurs using the full FFT as
opposed to RFFT.

I have links to the images produced by this process below.

Thanks for any insight anyone can give!

Chris


In [12]: a = np.zeros((100,100))

In [13]: a[45:55,45:55] = 1

In [15]: k = np.ones((10,10))

In [16]: afft = np.fft.rfft2(a, s=(256,256))

In [19]: kfft = np.fft.rfft2(k, s=(256,256))

In [21]: result = np.fft.irfft2(afft*kfft).real[0:100,0:100]

In [23]: result.argmax()
Out[23]: 5454

www.therealstevencolbert.com/dump/a.png
www.therealstevencolbert.com/dump/afft.png
www.therealstevencolbert.com/dump/kfft.png
www.therealstevencolbert.com/dump/result.png
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20090511/106e32c8/attachment.html>