why Matlab fft2 is much faster than OpenCV dft

Question

I just did test to compare the speed bewteen the dft function of OpenCV and fft2 in Matlab. I load the same image, use fft2() and dft() to do the transform and measure the time they consumed. I found that for the image the dft() costed over 2 second in the win32 release version while the fft2() only took round 0.2s. How come? The OpenCV version I used is 2.4.8 while the Matlab version is 2013 a. Here is my codes for testing

Matlab:

tic
X1 = fft2(im);
toc

OpenCV in C++:

start1 = clock();
dft(src,src,DFT_COMPLEX_OUTPUT);
end1 = clock();
cout<<(double)(end1 - start1)/CLOCKS_PER_SEC<<endl;

MATLAB uses highly optimized proprietary implementations for linear algebra, functional analysis and other commonly used functions and algorithms. The answer is simply that MATLAB's implementation is better. — buzjwa, Mar 08 '17 at 11:34
I agree with you, but can you add some details you know about the implementation? Anyway, thank you and it really changes my impression on Matlab that it is a slow script language. — Xiaotian Hu, Mar 08 '17 at 11:36
I don't work at MathWorks so I have no inside information to share with you :) — buzjwa, Mar 08 '17 at 11:37
@XiaotianHu MATLAB can as fast (or faster) as any low level language *if used correctly*, specially for matrix operations. It's called MATrix LABoratory for a reason — Ander Biguri, Mar 08 '17 at 11:40
Related: https://stackoverflow.com/questions/6058139/why-is-matlab-so-fast-in-matrix-multiplication — Ander Biguri, Mar 08 '17 at 11:47

score 1 · Answer 1 · answered Mar 08 '17 at 11:21

1

In general fft is a fast implementation of dft.

DFT is a linear transform which takes as input a complex signal x of length N and gives as output a complex signal X of length N, X=Wx. W is a complex NxN matrix with entiries W_k,n=exp(-2pikn/N), where 0 < k , n < N.

FFT is a collection of algorithms for fast computation of the DFT. Typically the number of operations required by the FFT is on the order of N*logN. The most famous FFT algorithms are for the case that N is a power of 2, but there are FFT for prime orders and for different other factorizations.

answered Mar 08 '17 at 11:21

Konstantinos Monachopoulos

1,045
2
14
29

So, you mean that function dft() is not implemented by FFT or similar algorithm? – Xiaotian Hu Mar 08 '17 at 11:29
[From openCV docs](http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_imgproc/py_transforms/py_fourier_transform/py_fourier_transform.html): A fast algorithm called Fast Fourier Transform (FFT) is used for calculation of DFT. – Ander Biguri Mar 08 '17 at 11:38
1

Well, I know it, but in my impression, all the DFT is implemented by FFT algorithm otherwise it would be too slow to use isn't it? So, I think the dft() function in OpenCV is also implemented by FFT, and it cannot explain why fft2() function in Matlab is much faster than dft() in OpenCV. – Xiaotian Hu Mar 08 '17 at 11:42
@XiaotianHu FDT is not that slow. Its just FFT is very fast! Still I agree with you, I'd expect openCV to be as fast as MATLAB. IT may not be the case though – Ander Biguri Mar 08 '17 at 11:45
I think OpenCV can incorporate the FFTW and then its DFT might run much faster. – Xiaotian Hu Mar 08 '17 at 12:14

score 0 · Accepted Answer · edited May 23 '17 at 11:53

I've asked this and similar questions for very long time fft vs dft and Matlab vs c++. The answer I found is,

Matlab has some built-in software such as MKL, Lapack and BLAS.
They use c or Fortran libraries behind the scene.
They use the best implementations. For example, fft2 in Matlab is FFTW based. (Fastest Fourier Transform in the West)
They are always improving. Newer versions are noticeably faster than older ones in for some functions.

On the other hand,

You are not using the latest version of OpenCV which should have some effect on the performance.
You are not using the DFT as suggested, you can improve the speed by getting the optimal dimensions. If your image dimensions are not optimal, it may significantly increase the running time.

Final note: it is not recommended to use tic, toc, instead use timeit.

why Matlab fft2 is much faster than OpenCV dft

2 Answers2

Linked