2D FFT how is it done?

Question

I have a texture that I want to perform the 2DFFT on and I am trying to understand the "Row/Column" or "Column/Row" idea but I am unsure if I have understood it correctly. Hoping some one can explain it a bit better from my current understanding because it seems my current understanding of it requires a lot of FFTs which does not seem right to me.

If I have a 256 by 256 texture and I perform a 2DFFT on the image. Lets say I chose columns/row order so I do columns first, so does that mean I first perform:

256 1DFFT's... one for each column "image.x", containing 256 samples:

1DFFT for x = 0 -> Samples: image[0,0], image[0,1] ... image[0,255]
1DFFT for x = 1 -> Samples: image[1,0], image[1,1] ... image[1,255]
...
1DFFT for x = 255 -> Samples: image[255,0], image[255,1] ... image[255,255]

Then I have to do another 256 1DFFT's along the rows "image.y", containing 256 samples:

1DFFT for y = 0 -> Samples: image[0,0], image[1,0] ... image[255,0]
1DFFT for y = 1 -> Samples: image[0,1], image[1,1] ... image[255,1]
...
1DFFT for y = 255 -> Samples: image[0,255], image[1,255] ... image[255,255]

So in total I do 256 + 256 = 512 1DFFTs ? Is that correct?

Answer 1

Yes, you are right. It is a lot of FFTs, but remember it is a lot of samples as well.

If you have a FFT algorithm with complexity $O(n \cdot log(n))$, then for the 2D scenario you will have an algorithm with complexity $O(M \cdot (N \cdot log(N)) + N\cdot (M \cdot log(M)))$

but if you express this in terms of $M \cdot N$, what you get is. $O(M \cdot N \cdot (log(N) + log(M)))$ and finally with the log sum identity you get $O(M \cdot N \cdot log( M \cdot N ))$

The complexity in terms of number of samples is the same