2
$\begingroup$

I have recently left the safe and easy MATLAB environment and begun to use CUDA-C/C++ for image processing. Since CUDA doesn't allow 2D arrays to be passed into kernels I am now used to linearizing my gray-scale images (2D matrices) into 1D arrays before processing them. I seem to have no problem applying 1D-DFT's to my linearzied arrays. This leads me to wonder why people use 2D-DFT's at all? Why not just linearize your matrices into 1D-arrays and apply 1D-DFT's?

Can 1D-DFT's always operate on 2D-data by simply laying the matrix out into a 1D array?

$\endgroup$
  • $\begingroup$ I'm pretty sure this is the starting point for how 2D DFTs are done using the FFT. See en.wikipedia.org/wiki/Fast_Fourier_transform But I think you have to do the DFT on each row and column, not stack them. $\endgroup$ – geometrikal Jul 6 '15 at 1:14
  • $\begingroup$ Josh, It seems my answer solved your problem. Could you please mark it as te answer? Thank You. $\endgroup$ – Royi Oct 7 at 20:14
3
$\begingroup$

The DFT is "Separable Operator" (Also the classic Fourier Transform) and hence can be applied on the Rows and Columns of the image separately (It can be generalized to N dimension and not only 2).
Yet, if you create 1D signal from your image (Let's say by Column Stack) and apply 1D DFT you don't get the information you would by using 2D DFT (By going on the Row and them Columns).

Remember, Fourier Transform is all about synthesizing the signal using different functions. In this case if it is 2D signal you want to build it using 2D Signals.

You need to play with the indices to first apply it on each row and later on each column.

$\endgroup$
  • $\begingroup$ I forgot about the separability property. Well, I am currently implementing a Log-Gabor transform in this same way and it is not separable (not positive on that, I'm sure it's non-orthogonal though). $\endgroup$ – Josh Jul 5 '15 at 19:54
  • $\begingroup$ I was not implementing it that way. Thank you for your help. $\endgroup$ – Josh Jul 10 '16 at 23:22
0
$\begingroup$

Apparently the exact formal relationship between 1D DTFT's and 2D DDFT's (Discrete Domain FT) is called Lexicographic Ordering.

You simply sample the 2D DTFT with parallel lines of angle $1/N$ where the original matrix has $N \times N$ samples. Image of Lexicographic Ordering for converting 2D DTFT to 1D DTFT

$\endgroup$

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.