Learning OpenCV

Discrete Fourier Transform (DFT)

For any set of values that are indexed by a discrete (integer) parameter, it is possible to define a discrete Fourier transform (DFT)^[81] in a manner analogous to the Fourier transform of a continuous function. For N complex numbers

, the one-dimensional DFT is defined by the following formula (where

):

A similar transform can be defined for a two-dimensional array of numbers (of course higher-dimensional analogues exist also):

In general, one might expect that the computation of the N different terms f_k would require O(N²) operations. In fact, there are a number of fast Fourier transform (FFT) algorithms capable of computing these values in O(N log N) time. The OpenCV function cvDFT() implements one such FFT algorithm. The function cvDFT() can compute FFTs for one- and two-dimensional arrays of inputs. In the latter case, the two-dimensional transform can be computed or, if desired, only the one-dimensional transforms of each individual row can be computed (this operation is much faster than calling cvDFT() many separate times).

void cvDFT( const CvArr* ...