0
$\begingroup$

Please tell me if i understand it correctly and if not, where am i wrong? Say we have an image like this: $ \begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1\\ 2 & 4 & 3 & 1\\ 4 & 1 & 2 & 3 \end{matrix} $

If we calculate the DFT of it by columns, we have two matrices, one of real and one of imaginary numbers:

Real = $ \begin{matrix} 11 & -1 & -5 & -1 \\ 10 & -2 & 2 & -2\\ 10 & 0 & 2 & 0\\ 9 & 3 & 1 & 3 \end{matrix} $ Imaginary = $ \begin{matrix} 0 & 0 & 0 & 0 \\ 0 & -2 & 0 & 2\\ 0 & 0 & 0 & 0\\ 0 & 2 & 0 & -2 \end{matrix} $

But what next? How do i calculate the DFT of rows now, if i have 2 matrices?

$\endgroup$

2 Answers 2

0
$\begingroup$

It sounds like you're computing the Fourier transform with your own software, and that it is using only real numbers. The accepted way to compute the Fourier transform is to do it all with complex numbers; instead of calculating the sine and cosine part separately, calculate both simultaneously using

$$\mathcal F \{x\} = \sum_n x_n e^{-\frac{j 2 \pi}{N} n}$$

This means using a complex number data type, but most modern software supports this.

Note:

The real way to do this these days is to use an FFT package. Any modern software that is even remotely useful for scientific programming already has a package that does this, or has one available. It's a really good idea to learn how the FFT is done, and maybe even write your own FFT routine once, just so you really know how it's done. But unless you're really deep into algorithm-writing, once you've done that use a package.

$\endgroup$
3
  • $\begingroup$ Ok, but in this case, what formula do i use, to compute the rows of a matrix of complex numbers? As i assume xn in you formula, are real numbers only. $\endgroup$ Dec 30, 2022 at 19:19
  • $\begingroup$ What I posted is the definition of the discrete Fourier transform. Note that $e^{j \theta} = \cos \theta + j \sin \theta$ -- that's where the complex numbers come in. Note, too, that for $x_n \in \mathbb R$, $x_n = x_n + j0$, so you can treat it as complex. Note, finally, that this subject has been flogged in the literature for decades. References abound. You're getting close to asking "how do I do the Fourier transform", which, for a DSP group, is like asking "how do I divide two numbers?" I suggest some self-study; if you get stuck on a particular point, you're welcome to come ask. $\endgroup$
    – TimWescott
    Dec 30, 2022 at 20:49
  • 1
    $\begingroup$ Thank you, however it's not like i didn't do any self-study. Most sources i've found either explain the topic in a really unclear way for me, or require knowledge that i don't have and don't really see a point in getting, as signal processing is not really the topic that i want to bound my future with. Nonetheless, again, thanks for the help. $\endgroup$ Dec 30, 2022 at 21:55
0
$\begingroup$

For calculating:

You will need to use the matrices as "complex" matrices, you will have to make de Fourier transform in the other axis, but now using the Fourier transform of a complex vector for each row.

If you merge 1D Fourier transform results you will merge frequencies that are on the "x" or "y" axis. And create a 2D Fourier transform that represents frequencies in all directions.

You can use the following formula to calculate 2D Fourier transform, using the matrix values as complex:

$$ F(u,v) = \sum_{x=0}^N\sum_{y=0}^M{ f(x,y)e^{-j 2 \pi (x\frac{u}{N}+y\frac{y}{N})} } $$

This way the information about frequencies in diagonal directions is included.

For displaying:

Actually for displaying the complex result you will have to display 2 images. Usually you use the magnitude and the phase. You can achieve that by displaying the magnitude of each "complex pixel" in one image and the phase of the "complex pixels" in another image. That would be the result of the next pixelwise operations of your matrices:

$$ Mag = \sqrt{ Real^2 + Imag^2 } $$ $$ Phase = atan\left( \frac{Imag}{Real} \right) $$

Usually the phase part is not as easy to understande as magnitude, and magnitude is the result you would want to look at. But the phase is very important and trying to do the inverse transform without the phase would result in another image very different to the original.

edit: Sorry I told 2D fourier transform is not a combination of 1D Fourier transform. Thank you TimWescott For correcting me.

$\endgroup$
1
  • 1
    $\begingroup$ Your definition for the 2D Fourier transform, $ F(u,v) = \sum_{x=0}^N\sum_{y=0}^M{ f(x,y)e^{-j 2 \pi (x\frac{u}{N}+y\frac{y}{N})} } $, is, almost by inspection, separable into $ F(u,v) = \sum_{x=0}^N\left ( \sum_{y=0}^M{ f(x,y)e^{-j 2 \pi (y\frac{y}{N})} } \right )$ e^{-j 2 \pi (x\frac{u}{N}}. That's the definition of taking the Fourier transform on the columns of a matrix, then on the rows, or visa-versa. $\endgroup$
    – TimWescott
    Dec 30, 2022 at 22:23

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.