Next: A 2D DFT Example Up: fourier Previous: Physical Meaning of 2-D

# Matrix Form of 2D DFT

Consider the 2-D DFT of an signal ( ):

where we have defined

where . Note that the dimension of the spectrum is also .

As the summation above is with respect to the row index while the column index can be treated as a parameter, this expression can be considered as a one-dimensional Fourier transform of the nth column of the 2-D signal matrix , which can be written in column vector (vertical) form as:

where is a Fourier transform matrix. Putting all these columns together, we can write

We also note that the summation in the expression for is with respective to the column index of while the row index number can be treated as a parameter, the expression is one-dimensional Fourier transform of the kth row of , which can be written in row vector (horizontal) form as

where is a Fourier transform matrix. Putting all these rows together, we can write

or more concisely

But since , we have

This transform expression indicates that 2D DFT can be implemented by transforming all the rows of and then transforming all the columns of the resulting matrix . The order of the row and column transforms is not important.

Similarly, the inverse 2D DFT can be written as

Again note that is a symmetric unitary matrix:

It is obvious that the complexity of 2D DFT is which can be reduced to if FFT is used.

Next: A 2D DFT Example Up: fourier Previous: Physical Meaning of 2-D
Ruye Wang 2015-11-12