-1
$\begingroup$

I have this question on mathematics forum too, Notations, I thought of posting here, which ever place I get an answer, I will try to close it in the other. I need some help and clarifications for my notations in 3D centered fft. Consider the 1D centered fft of a 2D image of size $(N+1)\times (N+1)$, where $N$ is even, along X axis it can be computed using 1D FFT along each row such that, \begin{eqnarray} F^{}_x (r,c) = \sum\limits_{n=-N/2}^{N/2} f(r,n) e^{-i\frac{2\pi c n}{N+1}}, \nonumber \\ -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2 \end{eqnarray} Next we operate on each column such that the 2D centered FFT can be written as, \begin{eqnarray} F^{}_{xy}(r,c) = \sum\limits_{n=-N/2}^{N/2}F^{}_x (n,c) e^{-i\frac{2\pi r n}{N+1}},\nonumber \\ -N/2 \leq r \leq N/2 , -N/2 \leq c \leq N/2 \end{eqnarray}

The order of operation is not important. We can even begin with each column operation first then each row operation the calculation would not be affected.

I hope so far my notations are correct. Now comes the confusing 3D part (it has row, column and depth indexes), consider 1D fft operation along each row or X-axis, \begin{eqnarray} & F^{}_x (r,c,d) = \sum\limits_{n=-N/2}^{N/2} f(r,n,d) e^{-j\frac{2\pi c n}{N+1}}, \nonumber \\ & r,c,d = -\frac{N}{2},\cdots, \frac{N}{2} \nonumber \\ %& -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2, -N/2 \leq d \leq N/2 \nonumber \\ \end{eqnarray}

Next taking 1D fft along each column or Y-axis we have the equation,

\begin{eqnarray} & F^{}_{xy} (r,c,d) = \sum\limits_{n=-N/2}^{N/2} F^{}_x(n,c,d) e^{-j\frac{2\pi r n}{N+1}}, \nonumber \\ & r,c,d = -\frac{N}{2},\cdots, \frac{N}{2} \nonumber \\ %& -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2, -N/2 \leq d \leq N/2 \nonumber \\ \end{eqnarray}

Now how do I represent the final 1D operation along Z-axis or each depth index ? Can I write something like this ? \begin{eqnarray} &(i) \qquad F^{}_{xyz} (r,c,d) = \sum\limits_{n=-N/2}^{N/2} F^{}_{xy}(n,c,d) e^{-j\frac{2\pi r n}{N+1}}, \qquad \qquad or\\ &(ii)\qquad F^{}_{xyz} (r,c,d) = \sum\limits_{n=-N/2}^{N/2} F^{}_{xy}(r,n,d) e^{-j\frac{2\pi c n}{N+1}}, \nonumber \qquad \qquad or\\ &(iii)\qquad F^{}_{xyz} (r,c,d) = \sum\limits_{n=-N/2}^{N/2} F^{}_{xy}(r,c,n) e^{-j\frac{2\pi d n}{N+1}}, \nonumber \\ & r,c,d = -\frac{N}{2},\cdots, \frac{N}{2} \nonumber \\ %& -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2, -N/2 \leq d \leq N/2 \nonumber \\ \end{eqnarray} Are the above equations representation for 1D fft along z-axis correct ? Can someone help to clarify my confusion ?

$\endgroup$
5
  • $\begingroup$ The M.SE question was asked on 31 August. $\endgroup$
    – David Roberts
    Sep 4, 2015 at 7:03
  • $\begingroup$ your choice (iii) is correct, to get $F_x$ you sum over the second argument, to then get $F_{xy}$ you sum over the first argument, and then to get $F_{xyz}$ you still need to sum over the third argument. $\endgroup$ Sep 4, 2015 at 7:04
  • $\begingroup$ Thanks Carlo. But there in lies my confusion of the answer, can I now write things more differently like this, to get $F_x$ I will sum over first argument (instead of second according to matrix indexes), $F_y$ over second and $F_z$ over third, will that be more consistent and correct ? This is confusing since I couldn't find this type of notation in any text, etc. $\endgroup$ Sep 4, 2015 at 7:38
  • $\begingroup$ Your question really looks like you're more confused about your data structures than you are about FFTs. $\endgroup$
    – user13113
    Sep 7, 2015 at 5:55
  • $\begingroup$ @ Hurkyl , actually I know how to code, so I already wrote a program to do this 3D fft interms of 1D fft. But its when you start to follow those conventions and try to formulate it in math the confusion arises. For 2D its different , the way we index an array is exactly how I am writing equations. But for 3D it gets confusing, at least for me :) $\endgroup$ Sep 7, 2015 at 6:48

1 Answer 1

-1
$\begingroup$

First I should discuss a little about the reason for such notations that I am looking for. I wish to decompose the 3D operation into a bunch of 1D operations so I can do something in parallel.

The Fast Fourier Transformation (FFT) of three-dimensional (3D) data is of particular importance for many numerical simulations used in High Performance Computing codes. In order to do this for large data it is required to make the code parallelizable.

Hence I wanted clarification for my 3D notations in the form of 1D FFTs. If you come from 2D to 3D this confusion arises, since we index images differently.

After scouring through the internet and looking for texts with similar notation I came at this one, Parallel 3D FFT. With this reference I was able to understand what notation I should finally use.

So now the correct notations are For 1D fft operation along X-axis, \begin{eqnarray} & F^{}_x (r,c,d) = \sum\limits_{n=-N/2}^{N/2} f(n,c,d) e^{-j\frac{2\pi r n}{N+1}}, \nonumber \\ & r,c,d = -\frac{N}{2},\cdots, \frac{N}{2} \nonumber \\ %& -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2, -N/2 \leq d \leq N/2 \nonumber \\ \end{eqnarray}

Next taking 1D fft along Y-axis we have the equation,

\begin{eqnarray} & F^{}_{xy} (r,c,d) = \sum\limits_{n=-N/2}^{N/2} F^{}_x(r,n,d) e^{-j\frac{2\pi c n}{N+1}}, \nonumber \\ & r,c,d = -\frac{N}{2},\cdots, \frac{N}{2} \nonumber \\ %& -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2, -N/2 \leq d \leq N/2 \nonumber \\ \end{eqnarray} Finally the 1D fft along Z-axis gives, \begin{eqnarray} &F^{}_{xyz} (r,c,d) = \sum\limits_{n=-N/2}^{N/2} F^{}_{xy}(r,c,n) e^{-j\frac{2\pi d n}{N+1}}, \nonumber \\ & r,c,d = -\frac{N}{2},\cdots, \frac{N}{2} \nonumber \\ %& -N/2 \leq r \leq N/2, -N/2 \leq c \leq N/2, -N/2 \leq d \leq N/2 \nonumber \\ \end{eqnarray}

$\endgroup$
1
  • $\begingroup$ I totally agree for -1, this answer is not useful :) $\endgroup$ Sep 8, 2015 at 1:50

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.