4
$\begingroup$

Suppose I have a $4x4$ image with the following values as its grey-level intensity for each pixel like this:

enter image description here

I want to get its Fourier spectrum. Usually, I would just punch into Matlab and run a fft for everything to be calculated automatically. Now, if I don't have Matlab, and I have to do it by hand and with just an ordinary scientific calculator, can I still do it?

I know I could do the brute force way on the Fourier transform's equation like this: enter image description here

In this case, $N=M=4$.

So, $f(x,y)$ returns the intensity value of the above image at position $x$ and $y$. Eg, $f(1,1)=1$, $f(2, 0)=3$

But this will be insane to work out the summations so many times on paper. Most calculators can't do summations with complex numbers too.

I have tried doing it with Fourier transform's separability property, but doesn't seem to work as I still have to go through the tedious summations.

What other ways can I use to calculate Fourier transform on a simple image without using Matlab, particularly for the values in the first row of the example image above?

$\endgroup$
5
$\begingroup$

Your particular case can be solved without a calculator. Fourier transforms are linear operations. You can decompose your input as:

$$3 \left( \begin{array}{cccc} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right) + \left( \begin{array}{cccc} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right) $$

The first matrix is constant on the Y axis, so its 2D FFT is only the 1D-FFT of one row, times 4, and 0 everywhere else. The 1D FFT of $(0, 0, 1, 1)$ is $(2, -1+j, 0, -1-j)$, so this gives you, for the first term:

$$3 \times 4 \times \left( \begin{array}{cccc} 2 & -1+j & 0 & -1-j \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right)$$

As for the second term, there's only one value so there's only one component in the sum - it's just one of the basis functions, the checkerboard pattern:

$$\left( \begin{array}{cccc} 1 & -j & -1 & j \\ -j & -1 & j & 1 \\ -1 & j & 1 & -j \\ j & 1 & -j & -1 \end{array} \right)$$

Summing these two, you get:

$$\left( \begin{array}{cccc} 25 & -12+11j & -1 & -12-11j \\ -j & -1 & j & 1 \\ -1 & j & 1 & -j \\ j & 1 & -j & -1 \end{array} \right)$$

Note that this differs from Paul R's answer because of the normalization and sign conventions nobody agrees with... Divide by 4 and take the conjugate and you'll find the same result as his.

$\endgroup$
2
$\begingroup$

Wolfram Alpha is very useful for this kind of task - it gives the result for your 4x4 FFT above as:

{{6.25+0. i, -3.-2.75 i, -0.25+0. i, -3.+2.75 i},
 {0.+0.25 i, -0.25+0. i, 0.-0.25 i, 0.25+0. i},
 {-0.25+0. i, 0.-0.25 i, 0.25+0. i, 0.+0.25 i},
 {0.-0.25 i, 0.25+0. i, 0.+0.25 i, -0.25+0. i}}
$\endgroup$
  • $\begingroup$ Why the anonymous down-vote for this answer, I wonder ? $\endgroup$ – Paul R May 10 '13 at 7:57
0
$\begingroup$

From wikipedia (http://en.wikipedia.org/wiki/Fast_Fourier_transform)

Since 1968, however, the lowest published count for power-of-two N was long achieved by the split-radix FFT algorithm, which requires $4N \log_2 N -6N + 8$ real multiplications and additions for $N > 1$.

For $N=4$ that is 16 operations.

For an image that is specifically 4x4, you could make use of the fact that the exponential part of the sum only has values containing $1,-1,i,-i$. This is because the exponent can only have values that are a multiple of $\pi/2$ times $-i$.

$\endgroup$
  • $\begingroup$ Thanks. Other than fft, is there other ways of using any properties of fourier transform to evaluate the values in the fourier spectrum, particularly for values in the first row of the above example? Also, I'm not quite sure about the fact that you had mentioned on the exponential part. How is it that the values only be $0$, $\pm1$, $\pm i$? Sorry, my understanding on fourier transform isn't very comprehensive, and I usually rely a lot on matlab for the calculations. Examples on this will also be greatly appreciated. Thanks!. $\endgroup$ – xenon May 8 '13 at 0:41
  • $\begingroup$ Actually i made a mistake, the only values are $1,-1,i,-i$, only for $N=M=4$ though. The spectrum requires the entire signal to computer, so you can't just isolate the first row. $\endgroup$ – geometrikal May 8 '13 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.