As far as I understand, the 2d fourier transform is calculated as following:
step 1:
| a b c | -> 1D FFT -> | A B C | (calculate discrete fourier transform seperately for all three rows)
| d e f | -> 1D FFT -> | D E F |
| g h i | -> 1D FFT -> | G H I |
step 2:
| A B C | -> transpose -> | A D G |
| D E F | -> transpose -> | B E H |
| G H I | -> transpose -> | C F I |
step 3:
| A D G | -> 1D FFT -> | J M P |
| B E H | -> 1D FFT -> | K N Q |
| C F I | -> 1D FFT -> | L O R |
step 4:
| J M P | -> transpose -> | J K L |
| K N Q | -> transpose -> | M N O |
| L O R | -> transpose -> | P Q R |
If this example was a 3x3 image, the pixel for e would be calculated based on the pixel values for d e f and the fourier transform results of b e h. I don't understand why the fourier transform results of the other rows are required in the second calculation, instead of the raw pixel values. Wouldn't that mean that the fourier transform is being applied twice to the same value? And if B in the abovementioned step 3 already contains information relating to the entire row of a b c, what does that mean for the end result N in step 4? Why is this result identical to the result if you were to calculate the column b e h in step 1 and then the row D E F afterwards?
Also, if you perform a discrete fourier transform on the rows d e f and receive D E F as a result, what exactly do those values represent? Do you get three real numbers, or three sets of real and complex numbers, and if so why do you get the same amount of values as a return instead of just half of them?
Finally, what does the final resulting matrix
| J K L |
| M N O |
| P Q R |
represent? What information about the image is encoded in there and why is it relevant to some image-processing applications?
