# 2D FFT how is it done?

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?

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 ))$$
• Ah i see, yeah just calculated for 512 by 512 thats ${1.4 {\times} 10^6}$.