1
$\begingroup$

I am trying to get a better understanding of DFT of an image. Assume that we have an image of size $N\times N$, denoted as $f(m, n), m, n = 0, 1, \ldots, N$, and its Fourier transform $F(k, l), k, l = 0,1, \ldots, N-1$. It is often said that $F(N-1, N-1)$ represents the highest frequency. But what exactly does it mean?

If I was transforming a $1D$ signal, the "base" functions (I quote "base" because from my understanding of linear algebra DFT is not really a change of basis) are $e^{-i2\pi \frac{km}{N}}$ where $m$ is index of signal in space domain and $k$ is index in Fourier domain. For $k=N-1$ I get $F(N-1) = f(0)e^{0}+f(1)e^{-i2\pi \frac{N-1}{N}} + f(2)e^{-i4 \pi \frac{N-1}{N}} + \ldots f(N-1)e^{-i(N-1) \pi \frac{N-1}{N}}$. Now, some of the "base" functions in $F(N-1)$ are contained in other $F(k), k < N-1$, but definitely not the last one $e^{-i(N-1) \pi \frac{N-1}{N}}$. So does the "highest frequency" mean that the range of the arguments of the exponentials in $F(N-1)$ is larger than in any other $F(k), k<N-1$?

$\endgroup$

1 Answer 1

0
$\begingroup$

It might be helpful to think of the DFT as correlating the signal $f(n)$ with a set of “basis” functions, these being complex exponentials of the form: $$W_k(n) = e^{-i2\pi \frac{k}{N}n}, \quad 0\leq n<N$$ where $\frac{k}{N}$ is the discrete frequency used to build a particular function of this set.
For example, the 3rd bin of the DFT of $f(n)$ contains the result of correlating $f(n)$ with a complex exponential of frequency $\frac{3}{N}$.

The higher $k$ is, the higher the base exponential’s frequency is. When the DFT gets to the case where $k = N-1$, it simply means it’s correlating $f(n)$ with the complex exponential of highest frequency allowed by the DFT size $N$.

$\endgroup$
3
  • $\begingroup$ So can I understand W_k(n) as a discretized signal starting at time n=0 and evolving to n=N-1? $\endgroup$
    – Avec
    Commented Aug 23, 2023 at 12:58
  • $\begingroup$ I feel like I can imagine it for signals evolving in time, because there is some start and an end, but what does it mean for images that have spatial coordinates instead? $\endgroup$
    – Avec
    Commented Aug 23, 2023 at 14:30
  • $\begingroup$ Mathematically, a 2-dimensional DFT can be obtained by applying a bunch of 1-dimensional DFTs. This is outside of the scope of this question, but you can consider each row of your matrix (your image) to be a 1D signal. See this $\endgroup$
    – Jdip
    Commented Aug 23, 2023 at 14:53

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.