Convolving a periodic image with python

Question

I want to convolve an n-dimensional image which is conceptually periodic.

What I mean is the following: if I have a 2D image

>>> image2d = [[0,0,0,0],
...            [0,0,0,1],
...            [0,0,0,0]]

and I want to convolve it with this kernel:

>>> kernel = [[ 1,1,1],
...           [ 1,1,1],
...           [ 1,1,1]]

then I want the result to be:

>>> result = [[1,0,1,1],
...           [1,0,1,1],
...           [1,0,1,1]]

How to do this in python/numpy/scipy?

Note that I am not interested in creating the kernel, but mainly the periodicity of the convolution, i.e. the three leftmost ones in the resulting image (if that makes sense).

Answer 1

This kind of 'periodic convolution' is better known as circular or cyclic convolution. See http://en.wikipedia.org/wiki/Circular_convolution.

In the case of an n-dimensional image, as is the case in this question, one can use the scipy.ndimage.convolve function. It has a parameter mode which can be set to wrap for a circular convolution.

result = scipy.ndimage.convolve(image,kernel,mode='wrap')

>>> import numpy as np
>>> image = np.array([[0, 0, 0, 0],
...                   [0, 0, 0, 1],
...                   [0, 0, 0, 0]])
>>> kernel = np.array([[1, 1, 1],
...                    [1, 1, 1],
...                    [1, 1, 1]])
>>> from scipy.ndimage import convolve
>>> convolve(image, kernel, mode='wrap')
array([[1, 0, 1, 1],   
       [1, 0, 1, 1],
       [1, 0, 1, 1]])

Answer 2

This is already built in, with scipy.signal.convolve2d's optional boundary='wrap' which gives periodic boundary conditions as padding for the convolution. The mode option here is 'same' to make the output size match the input size.

In [1]: image2d = [[0,0,0,0],
    ...            [0,0,0,1],
    ...            [0,0,0,0]]

In [2]: kernel = [[ 1,1,1],
    ...           [ 1,1,1],
    ...           [ 1,1,1]]

In [3]: from scipy.signal import convolve2d

In [4]: convolve2d(image2d, kernel, mode='same', boundary='wrap')
Out[4]: 
array([[1, 0, 1, 1],
       [1, 0, 1, 1],
       [1, 0, 1, 1]])

The only disadvantage here is that you cannot use scipy.signal.fftconvolve which is often faster.

Answer 3

image2d = [[0,0,0,0,0],
           [0,0,0,1,0],
           [0,0,0,0,0],
           [0,0,0,0,0]]
kernel = [[1,1,1],
          [1,1,1],
          [1,1,1]]
image2d = np.asarray(image2d)
kernel = np.asarray(kernel)

img_f = np.fft.fft2(image2d)
krn_f = np.fft.fft2(kernel, s=image2d.shape)

conv = np.fft.ifft2(img_f*krn_f).real

>>> conv.round()
array([[ 0.,  0.,  0.,  0.,  0.],
       [ 1.,  0.,  0.,  1.,  1.],
       [ 1.,  0.,  0.,  1.,  1.],
       [ 1.,  0.,  0.,  1.,  1.]])

Note that the kernel is placed with its top left corner at the position of the 1 in the image. You would need to roll the result to get what you are after:

k_rows, k_cols = kernel.shape
conv2 = np.roll(np.roll(conv, -(k_cols//2), axis=-1),
                -(k_rows//2), axis=-2)
>>> conv2.round()
array([[ 0.,  0.,  1.,  1.,  1.],
       [ 0.,  0.,  1.,  1.,  1.],
       [ 0.,  0.,  1.,  1.,  1.],
       [ 0.,  0.,  0.,  0.,  0.]])