By 2D Fourier Transform,

$F(u,v) = \frac{1}{N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) W_N^{xu} W_N^{yv}$

Row Transform∶

$F(u,v) = \frac{1}{N} \sum_{x=0}^{N-1} W_N^{xu} \sum_{y=0}^{N-1} f(x,y)W_N^{yv} \\ F(u,v) = \frac{1}{N} \sum_{x=0}^{N-1} W_N^{xu} F(x,v)$

Column Transform∶

$F(u,v)=\frac{1}{N} \sum_{x=0}^{N-1}F(x,v) W_N^{xu}$

2D Fourier Transform of input image can be obtained by performing row-wise 1D transform followed by column-wise 1D Fourier Transform.

Fast Fourier Algorithm to find DFT of an image:

• Perform row-wise transform using FFT Flowgraph.
• Perform column-wise transform using FFT Flowgraph.
• Scale by 1/N.