Question

How many summations and multiplications are needed to calculate a 2D Fourier Transformation of an image size 64x64 pixels using a 1D Fourier Transformation?

Answer 1

hmm sounds like some Linear Algebra stuff, no idea what "Fourier"

Answer 2

I mean Discrete Fourier Transformations (DFT). ( http://en.wikipedia.org/wiki/Discrete_Fourier_transform) It's for my Image Processing course.

Answer 3

Pretty wild... Wavelengths and such, interesting about the transformations for images though.. In linear Algebra there are ways to transform dimensions from one to another.

Answer 4

I think it has something to do with the complexity of the DFT.
Looking at Wikipedia:

"computing the DFT of N points in the naive way, using the definition, takes O(N2) arithmetical operations, while an FFT can compute the same DFT in only O(N log N) operations. "

I assume then that it would take \[N * N^2\] summations for the DFT.

For the FFT (Fast Fourier Transformation), I assume it would be \[N * N \log N = N^2 \log N\]. Replacing N with 64 should be the answer. Do you agree?

Answer 5

Well they say "points" not pixels, so I'm not sure.... Are we considered each pixel to be a point? 64x64 points?

Answer 6

Fourier transormations have many applications, but for this question, I think it's safe to say points can be considered pixels :)

Answer 7

makes sense with the N^2, I wonder hmm....

Answer 8

Now we have to know about 1D vs 2D...

Answer 9

I think one can consider the image as a 2D array with 64 rows and cols. Then it's a matter of applying a 1D DFT over each row, and then over each column.

Answer 10

I guess so I'm not really that sure, I wish I could help more. As mentioned near the middle they talk about Eigenvalues/vectors which is Linear Algebra :p, so I could help in that little tidbit :p

Answer 11

No problem, thanks anyways!