All geek questions in one place

Complexity 2d discrete Fourier transform

I have a question about two-dimensional Fourier transform. I'm currently developing math behind this, and I don’t understand something. As far as I know, DFT has complexity O(N*N). If I look at the following algorithm:

alt text

I do not understand how this works. Will we do this calculation for each pixel in the transformed image?

Example

  • We have a 2 * 2 image.
  • For each pixel in this image we are going to execute DFT F (x, y)
  • I will create a new image, and each pixel will be the value of a complex value that causes corrosion.

How does it work, or am I missing something? Since I see it now, it has complexityO(N^4)

+3
source share
1 answer

The equation means "get the value of F in the pixel (u, v), evaluate (the formula on the right side)." Thus, in order to obtain the entire transformed image, it was evaluated for each pixel in the transformed image.

To calculate the DFT using the formula, you need to do an O (1) calculation for each input value for each output value. (There are other, faster algorithms for some types of data.) In your 2D DFT case, the algorithm has complexity O ((M * N) ^ 2), because the number of input pixels is M * N and the number of output pixels are also M * N.

edit: 2D- DFT O (NM ^ 2 + MN ^ 2), . : http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html

+3

Source: https://habr.com/ru/post/1778627/

More articles:


All Articles