[−][src]Function opencv::core::dft

pub fn dft(
    src: &dyn ToInputArray, 
    dst: &mut dyn ToOutputArray, 
    flags: i32, 
    nonzero_rows: i32
) -> Result<()>

Performs a forward or inverse Discrete Fourier transform of a 1D or 2D floating-point array.

The function cv::dft performs one of the following:

  • Forward the Fourier transform of a 1D vector of N elements: block formula where inline formula and inline formula
  • Inverse the Fourier transform of a 1D vector of N elements: block formula where inline formula
  • Forward the 2D Fourier transform of a M x N matrix: block formula
  • Inverse the 2D Fourier transform of a M x N matrix: block formula

In case of real (single-channel) data, the output spectrum of the forward Fourier transform or input spectrum of the inverse Fourier transform can be represented in a packed format called CCS (complex-conjugate-symmetrical). It was borrowed from IPL (Intel* Image Processing Library). Here is how 2D CCS spectrum looks: block formula

In case of 1D transform of a real vector, the output looks like the first row of the matrix above.

So, the function chooses an operation mode depending on the flags and size of the input array:

  • If #DFT_ROWS is set or the input array has a single row or single column, the function performs a 1D forward or inverse transform of each row of a matrix when #DFT_ROWS is set. Otherwise, it performs a 2D transform.
  • If the input array is real and #DFT_INVERSE is not set, the function performs a forward 1D or 2D transform:
  • When #DFT_COMPLEX_OUTPUT is set, the output is a complex matrix of the same size as input.
  • When #DFT_COMPLEX_OUTPUT is not set, the output is a real matrix of the same size as input. In case of 2D transform, it uses the packed format as shown above. In case of a single 1D transform, it looks like the first row of the matrix above. In case of multiple 1D transforms (when using the #DFT_ROWS flag), each row of the output matrix looks like the first row of the matrix above.
  • If the input array is complex and either #DFT_INVERSE or #DFT_REAL_OUTPUT are not set, the output is a complex array of the same size as input. The function performs a forward or inverse 1D or 2D transform of the whole input array or each row of the input array independently, depending on the flags DFT_INVERSE and DFT_ROWS.
  • When #DFT_INVERSE is set and the input array is real, or it is complex but #DFT_REAL_OUTPUT is set, the output is a real array of the same size as input. The function performs a 1D or 2D inverse transformation of the whole input array or each individual row, depending on the flags #DFT_INVERSE and #DFT_ROWS.

If #DFT_SCALE is set, the scaling is done after the transformation.

Unlike dct , the function supports arrays of arbitrary size. But only those arrays are processed efficiently, whose sizes can be factorized in a product of small prime numbers (2, 3, and 5 in the current implementation). Such an efficient DFT size can be calculated using the getOptimalDFTSize method.

The sample below illustrates how to calculate a DFT-based convolution of two 2D real arrays:

ⓘThis example is not tested
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;
// use "nonzeroRows" hint for faster processing
dft(tempA, tempA, 0, A.rows);
dft(tempB, tempB, 0, B.rows);

// multiply the spectrums;
// the function handles packed spectrum representations well
mulSpectrums(tempA, tempB, tempA);

// transform the product back from the frequency domain.
// Even though all the result rows will be non-zero,
// you need only the first C.rows of them, and thus you
// pass nonzeroRows == C.rows
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);

// all the temporary buffers will be deallocated automatically
}

To optimize this sample, consider the following approaches:

  • Since nonzeroRows != 0 is passed to the forward transform calls and since A and B are copied to the top-left corners of tempA and tempB, respectively, it is not necessary to clear the whole tempA and tempB. It is only necessary to clear the tempA.cols - A.cols ( tempB.cols - B.cols) rightmost columns of the matrices.
  • This DFT-based convolution does not have to be applied to the whole big arrays, especially if B is significantly smaller than A or vice versa. Instead, you can calculate convolution by parts. To do this, you need to split the output array C into multiple tiles. For each tile, estimate which parts of A and B are required to calculate convolution in this tile. If the tiles in C are too small, the speed will decrease a lot because of repeated work. In the ultimate case, when each tile in C is a single pixel, the algorithm becomes equivalent to the naive convolution algorithm. If the tiles are too big, the temporary arrays tempA and tempB become too big and there is also a slowdown because of bad cache locality. So, there is an optimal tile size somewhere in the middle.
  • If different tiles in C can be calculated in parallel and, thus, the convolution is done by parts, the loop can be threaded.

All of the above improvements have been implemented in #matchTemplate and #filter2D . Therefore, by using them, you can get the performance even better than with the above theoretically optimal implementation. Though, those two functions actually calculate cross-correlation, not convolution, so you need to "flip" the second convolution operand B vertically and horizontally using flip .

Note:

  • An example using the discrete fourier transform can be found at opencv_source_code/samples/cpp/dft.cpp
  • (Python) An example using the dft functionality to perform Wiener deconvolution can be found at opencv_source/samples/python/deconvolution.py
  • (Python) An example rearranging the quadrants of a Fourier image can be found at opencv_source/samples/python/dft.py

Parameters

  • src: input array that could be real or complex.
  • dst: output array whose size and type depends on the flags .
  • flags: transformation flags, representing a combination of the #DftFlags
  • nonzeroRows: when the parameter is not zero, the function assumes that only the first nonzeroRows rows of the input array (#DFT_INVERSE is not set) or only the first nonzeroRows of the output array (#DFT_INVERSE is set) contain non-zeros, thus, the function can handle the rest of the rows more efficiently and save some time; this technique is very useful for calculating array cross-correlation or convolution using DFT.

See also

dct , getOptimalDFTSize , mulSpectrums, filter2D , matchTemplate , flip , cartToPolar , magnitude , phase

C++ default parameters

  • flags: 0
  • nonzero_rows: 0