The filtering (or convolution) process in Convolutional Neural Networks can be implemented using Fourier Transforms. Convolutions in image (or spatial) space are equivalent to multiplications in frequency space, and multiplications can be performed much more efficiently than convolutions.
The algorithm for using Fourier Transforms to calculate a convolution between an image and a filter kernel is as follows:
Assuming a 100x100 input image, and a 3x3 filter kernel (such as a Sobel Edge-Detection filter).
- Calculate the 2D Fourier Transform (FT) of the image (C library, Python library)
Pad the filter kernel so that it is the same size as the image, and that the filter kernel is centred at image coordinate (0, 0). This means that some parts of the kernel will be placed in the other corners of the padded filter image. For example, consider a 3x3 kernel where the filter coefficients are [[a, b, c], [d, e, f], [g, h, i]], in this case the coefficients map to pixel positions on the padded kernel as follows:
- a -> (99, 99) //bottom right
- b -> (0, 99) //bottom left
- c -> (1, 99)
- d -> (99, 0) //top right
- e -> (0, 0) //top left
- f -> (1, 0)
- g -> (99, 1)
- h -> (0, 1)
- i -> (1, 1)
Set all the other padded filter kernel pixels to zero
Calculate the 2D Fourier Transform of the padded filter kernel.
Perform an element-wise multiplication of the image FT and the padded filter kernel FT. Note that this is a complex multiplication as the FT consists of complex numbers. The result of this multiplication is therefore also an array of complex numbers.
Calculate the Inverse Fourier Transform of the result from step 4. This will return a real valued image which is the original image convolved with the filter kernel.
The advantage for performing the kernel convolutions in this way is that it is much faster than performing an element-wise convolution directly. This speeds up the training process for neural networks with Convolutional layers.