3

I'm wondering why the dft function in OpenCVC++ is a lot slower than fft2 for 2D matrices.

The following C++ code is from the documentation:

void fft2(const Mat in, Mat &complexI) {
    Mat padded;
    int m = getOptimalDFTSize(in.rows);
    int n = getOptimalDFTSize(in.cols); 
    copyMakeBorder(in, padded, 0, m - in.rows, 0, n - in.cols, BORDER_CONSTANT, Scalar::all(0));

    Mat planes[] = {Mat_<float>(padded), Mat::zeros(padded.size(), CV_32F)};
    merge(planes, 2, complexI);
    dft(complexI, complexI);
}

int main(){
    Mat a(5000, 5000, CV_32F);
    randn(a, 0, 1);
    Mat res;
    clock_t start = clock();
    fft2(a,res);
    cout << clock() - start;
}

MATLAB code:

mat1 = rand(5000,5000);
tic, a = fft2(mat1); toc

The result for both codes is same; however, the C++ code is taking 1502 ms whereas the MATLAB code is taking 660ms. It seems some optimizations are missing in OpenCV. I'm wondering how I can speed up the OpenCVcode.

I'm working on Visual Studio 2015 using OpenCV 2.4.10 and MATLAB R2016a. The computer is Windows 7, 32 GB RAM, Intel Xeon 3.4 GHz. Both tests were conducted on the same machine.

I found bunch of FFT codes but they seem hard to apply to matrices. Is there an easy solution for matrices?

Adriaan
  • 17,741
  • 7
  • 42
  • 75
smttsp
  • 4,011
  • 3
  • 33
  • 62
  • `fft2` is sort-of a matrix operation, has been precompiled (hence `open fft2` won't show any useful code) and is thus very fast. As to why it's faster than the C++ code, I don't know. You might want to read [Why is MATLAB so fast in matrix multiplication?](http://stackoverflow.com/questions/6058139/why-is-matlab-so-fast-in-matrix-multiplication) – Adriaan Jun 18 '16 at 18:03
  • you should ask why fftpack hence fortran is fast. And also you can call fftpack in C – percusse Jun 18 '16 at 18:06
  • Oh, as an afterthought: `tic/toc` is not recommended for time measurements in MATLAB, you should use [`timeit`](http://mathworks.com/help/matlab/ref/timeit.html) – Adriaan Jun 18 '16 at 18:10
  • 1
    @Adriaan the link has some nice explanations. I will check timeit – smttsp Jun 18 '16 at 18:32
  • @percusse, Is this code very fast? `http://www.netlib.org/fftpack/fft.c` – smttsp Jun 18 '16 at 18:37
  • That and also `fftw`. Matlab always uses well-estableshed fortran librarires if available instead of in house coding. – percusse Jun 18 '16 at 18:39
  • [Matlab uses FFTW](http://www.mathworks.com/help/matlab/ref/fftw.html), optimized with Intel MKL library to be very fast. – Ahmed Fasih Jul 20 '16 at 12:18

1 Answers1

1

OpenCV's FFT implementation is probably not as optimized as Matlab's.
If you FFT performance is what you require, then take a look at specialized FFT libraries like FFTW.

Adi Shavit
  • 16,743
  • 5
  • 67
  • 137
  • Can I only get the corresponding .c and .h files on FFTW. Or do you think I should fully install it. It looks quite complicated to do that, isn't it? Also, if I install it, would it be easy to change when it is needed to be shifted to another OS? – smttsp Jun 19 '16 at 12:52
  • @smttsp I would follow the install instructions. FFTW is kinda black magic, it does run-time code path selection optimized for your CPU and RAM to find the fastest subroutines, and for the FFT size you request. It’s worth a little bit of up-front setup time IMO! – Ahmed Fasih Jul 20 '16 at 12:20