/FFT_Conv2D

2D Convolution apply in Frequency Domain

Primary LanguageCMIT LicenseMIT

Fast 2D Convolution

Implementation of 2D convolution using Fast Fourier Transformation (FFT). Convolution in time space is equal to multiplication in Frequency space.

formula

This equation is expressed below.

Run

The FFTW3 library in external_lib is compiled for Windows. For Ubuntu, FFTW 3.3.5 should be installed.
Run steps for Windows:

mkdir build && cd build
copy ..\external_lib\fftw-3.3.5-dll64\libfftw3f-3.dll .
cmake ..
make

Or run with Clion
Note: A copy of libfftw3f-3.dll must be in the executable directory

Defined Convulation Skils

✅ full: (default) returns the full 2-D convolution
✅ same: returns the central part of the convolution that is the same size as "input"(using zero padding)
✅ valid: returns only those parts of the convolution that are computed without the zero - padded edges.

full same valid

Result

This process may faster than Time Domain Convolution. When using large images (exp: 1024 x 1024 or 512 x 512 etc.) is about 2 times faster than Time Domain Convolution. This measurement is based on trial and error, you should observe speed up yourself.
Example usage of FFTConv2D() function is specified in main.