Complexity of a 2d Discrete Fourier Transform

I have a question regarding a 2D Fourier transformation. I'm currently in the progress of understandig the maths behind this, and there's something I dont onderstand. As far as I'm concerned, the DFT has a complexity of O(N*N). If I look at t开发者_如何学Pythonhe following algorithm:

I don't understand how it works. Are we going to do this caluculation for every pixel in the tranformed image?

example

1. We have an image of 2*2.
2. For each pixel in this image we're going to do the DFT F(x,y)
3. I'll create a new image, and each pixel is the magnitude of the corrosponding complex value

Is this how it works or am I missing something? Because the way I see it now, it has a complexity of O(N^4)

The equation means "to get the value of F at pixel (u, v), evaluate (the formula on the right-hand-side)." So, to get the entire transformed image, it's evaluated for every pixel in the transformed image.

To compute a DFT, using the formula, you need to do an O(1) calculation for every input value for every output value. (There are other, faster algorithms for some kinds 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 and the number of output pixels is also M*N.

edit: A 2D matrix DFT can be calculated in O(NM^2 + MN^2) by transforming the rows and columns in separate steps. The algorithm is here: http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node6.html