Write an expression for a 2D-DFT. What is its relationship with one dimension DFT? How one-dimensional FFT algorithm can be used to compute two dimensional DFT of a digital image.
1 Answer

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.
Please log in to add an answer.