Function dft_def

pub fn dft_def(
    src: &impl ToInputArray,
    dst: &mut impl ToOutputArray,
) -> 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: where and
• Inverse the Fourier transform of a 1D vector of N elements: where
• Forward the 2D Fourier transform of a M x N matrix:
• Inverse the 2D Fourier transform of a M x N matrix:

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:

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:

   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 [match_template] and [filter_2d] . 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 [dft_flags]
• 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

Note

This alternative version of dft function uses the following default values for its arguments:

• flags: 0
• nonzero_rows: 0