look at GPU implementations (especially nvidia cuda code), convolution is a poster child for parallel processing.

https://devtalk.nvidia.com/default/topic/802753/2d-cuda-convolution/

There is a lightweight FFT library in different

languages under the MIT license. It does also have

convolution.

https://www.nayuki.io/page/free-small-fft-in-multiple-languages

BTW, why can't you use external libraries?

Do you have to reinvent FFT?

Regards,

Joachim

Thanks for all! I realized how to do this.

Let A = image, B = kernel, C = convolution result.

C = inverse_dft(dft(A) * dft(B))

OpenCV example is:

void convolveDFT(InputArray A, InputArray B, OutputArray C)

{

// reallocate the output array if needed

C.create(abs(A.rows - B.rows)+1, abs(A.cols - B.cols)+1, A.type());

Size dftSize;

// calculate the size of DFT transform

dftSize.width = getOptimalDFTSize(A.cols + B.cols - 1);

dftSize.height = getOptimalDFTSize(A.rows + B.rows - 1);

// allocate temporary buffers and initialize them with 0's

Mat tempA(dftSize, A.type(), Scalar::all(0));

Mat tempB(dftSize, B.type(), Scalar::all(0));

// copy A and B to the top-left corners of tempA and tempB, respectively

Mat roiA(tempA, Rect(0,0,A.cols,A.rows));

A.copyTo(roiA);

Mat roiB(tempB, Rect(0,0,B.cols,B.rows));

B.copyTo(roiB);

// now transform the padded A & B in-place;

dft(tempA, tempA, 0, A.rows);

dft(tempB, tempB, 0, B.rows);

// multiply the spectrums;

mulSpectrums(tempA, tempB, tempA);

// inverse transform

dft(tempA, tempA, DFT_INVERSE + DFT_SCALE, C.rows);

// now copy the result back to C.

tempA(Rect(0, 0, C.cols, C.rows)).copyTo(C);

}

Now I can do DFT with links that you gave me. 

You can use the following library

http://www.fftw.org/

FFTW is a C subroutine library for computing the discrete Fourier transform

(DFT) in one or more dimensions, of arbitrary input size, and of both real and

complex data (as well as of even/odd data, i.e. the discrete cosine/sine

transforms or DCT/DST).

The FFTW package was developed at MIT by Matteo Frigo and Steven G. Johnson.

Finally, i used in my project FFTW because it is really fastest library for fft