### Fourier-Transform for Time Series: About Image Convolution and SciPy

#### Fourier-transform convolution also applies to images

This post is the second of the Fourier-transform for time series, check the first here:

Fourier transform for time-series: fast convolution explained with numpy

**Quick review of the previous post**

In the first post, I explained how the Fourier-transform can be used to convolve signals **very efficiently**. I showed that convolution using the Fourier-transform in *numpy* is many orders of magnitude faster that the standard algebraic approach, and that it corresponds to a certain type of convolution called **circular convolution.**

In this post, I want to emphasize what the circular convolution means and how it all applies to images. Images are also a good way to extend the 1-dimension intuition into 2 dimensions.

*All images were made by the author.*

**Image convolution with scipy**

If you’ve ever worked with images for image processing, you most likely have encountered functions to apply convolution. Convoluting images is used everywhere — image enhancement, denoising, segmentation, feature extraction, compression — and is at the base of Convolutionnal Neural Networks, the gold standard of deep learning model to process visual data.

In *Python*, image convolution can be done quite simply using *scipy* and its *ndimage* subpackage. At this point, I recommend taking a quick look at the documentation of the `convolve` function, and then come back here.

scipy.ndimage.convolve – SciPy v1.11.1 Manual

The use is very simple: you can pass two images to convolve them together. Let’s see an example:

https://medium.com/media/95671d18885cb9a0942193bd010f533b/href

Note that *scipy* proposes several ways to handle the boundaries using the parameter ‘*mode*’: as we will see below, the mode ‘*wrap*’ corresponds to circular convolution and hence to convolution using a Fourier-transform approach. Other approaches exist, like ‘*reflect*’ that reflects the images inside-out, or ‘*constant*’ that repeats the outermost value. Notice also how ‘*wrap*’ works: it repeats the whole signal, as if it was periodic.

### Convolution of 2D images

Let’s start coding to see the differences between different convolution modes.

First, we create a class to represent 2D periodic images: remember from the previous post that when using Fourier-transform tool, the signal are considered to be periodic. This class is just syntactic sugar to plot such 2d periodic arrays.

We show the “*base*” image in the [0, V, 0, H] rectangle, as well as its 8 first replicas around. As stated in the previous post, the signal is considered periodic hence with infinite support, but we only need and use a single period.

https://medium.com/media/be3302ef85e3f07baf58e1aaa91b22da/href

Let’s now create a sample image to play with: it shall contain random noise, a sinusoidal pattern, a slope pattern, and a few square spots. We also create the periodic version of this sample image: it represents the periodic image that the Fourier-transform considers when applying its operators:

https://medium.com/media/6177b4cf8304dcead3f0d8d209b189ae/hrefInput image we are going to convolve, represented as a periodic array. The “base” image is in the center, with its replicas all around.

Let’s now create a kernel to use for the convolution: we’ll use a simple constant kernel, also called averaging kernel since the convolution with this kernel just gives the local average of the input image.

We then start playing with *scipy* convolution function and its differents *modes* to handle the boundaries, and wrap the result as a periodic array for easy plotting: notice how the middle of the convoluted image is always the same whatever the *mode* used, but the boundaries vary.

https://medium.com/media/8d6498ad902afddfbcbc1772f655ed9c/hrefResults of 4 different types of ‘mode’ to handle boundaries with scipy convolution function. Each result image is displayed as a periodic array.

Now we can use a Fourier-transform approach to compute the convolution: as shown in the previous post, we just need to take the inverse Fourier-transform of the product of the Fourier-transform of both signals, the image and the kernel:

Base equation to compute the convolution of 2 signals using a Fourier-transform approach.https://medium.com/media/5f0386e2e0eba1615c149b233714176d/hrefResult of the convolution using a Fourier-transform approach, not scipy.

Comparing the result with the “wrap” mode of scipy, we can see that the results look a lot alike, just with a slight shift:

Comparison between scipy convolution with mode=’wrap’, and Fourier-transform approach. They are almost identical. Using the periodic array representation, we can see that it is just a matter of shit.

This is just a matter of indexing, and we can get the exact same results using a shifted-centered kernel:

https://medium.com/media/92b96962577beb92625c3c10a4d8f42c/hrefComparison between convolution with scipy mode=’wrap’ (left), and 2 Fourier-trasnform approach: with kernel padded on the sides (middle), and centered kernel (right). The left and right image are identical.

Using proper centering, we then got identical results between *scipy*’s convolution with mode=’*wrap*’, and theFourier-transform approach.

Out of curiosity, let’s see which approach is faster:

Time comparison between scipy and Fourier-transform to compute the convolution between our 2 images: Fourier-transform is about 15-times faster than scipy.

Again, the Fourier-transform approach was faster, and in this case **faster than a scipy function,** which is nice.

### Wrap up

We have seen in this post how the circular convolution translates to images, and how it is equivalent to scipy convolution function using mode=’wrap’.

In the next post, we’ll dive in the use of window functions in the context of Fourier-transform to reduce spectral leakage and improve spectral analysis.

### Subscribe to get future posts about Fourier transform directly onto your feed!

Also, check out my other posts and if you like any of them, please subscribe it helps me a lot to reach my goal of 100 subscribers:

Fourier transform for time-series: fast convolution explained with numpyPCA/LDA/ICA : a components analysis algorithms comparisonPCA-whitening vs ZCA-whitening : a numpy 2d visual300-times faster resolution of Finite-Difference Method using numpyInteractive plotting the well-know RC-circuit in JupyterWrapping numpy’s arrays

If those articles seem interesting to you, remember to follow me, the new articles will appear on your feed.

Fourier-transform for time series : about image convolution and scipy was originally published in Towards Data Science on Medium, where people are continuing the conversation by highlighting and responding to this story.