1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ah i see, yeah just calculated for 512 by 512 thats ${1.4 {\times} 10^6}$. $\endgroup$
    – WDUK
    Commented Feb 25, 2021 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.