2D FFT explanation

Up a level : Fast Fourier transform
Previous page : 2D Fourier transforms
Next page : 2D FFT the code

The 2D FFT – how it works

The in data is a list of x– and y-coordinates that can be generated by the mouse pointer movements, touch movements, as a pasted list or it is generated by some function.

If the number of data points is not a power of two the data will be interpolated to make the number of points the nearest power of two above the current number.

The Analysis

Say the input in the horizontal direction for a given angular velocity is in the form

$\displaystyle x=A\cos (\omega t)+B\sin (\omega t)$

and say the data in the vertical direction is in the form

$\displaystyle y=C\cos (\omega t)+D\sin (\omega t)$

Say we combine these into one complex set of data, z=x+iy, and we then do an FFT on the data. We would get one constant for the real part, and one for the complex part, i.e. we have two degrees of freedom. The problem is that the input has four degrees of freedom; A, B, C and D. This is the second problem for using one FFT for the whole data set. The first problem was mentioned on the previous page.

To solve this we will treat the input as two separate signals, one horizontal and one vertical, where the horizontal data is treated as an array of data points x+0i and the vertical data in the form 0+yi. This is just an arbitrary choice. The key thing is that the FFTs will be able to recover the values of A, B, C and D.

The circles

Next, we need to turn this to motions of oppositely turning dials. Each of those can be described by a cos and a sin component. Say we have

$\displaystyle \left\{ {\begin{array}{*{20}{c}} {x=P\cos (\omega t)-Q\sin (\omega t)} \\ {y=P\sin (\omega t)+Q\cos (\omega t)} \end{array}} \right.$

and

$\displaystyle \left\{ {\begin{array}{*{20}{c}} {x=R\cos (\omega t)-S\sin (\omega t)} \\ {y=-R\sin (\omega t)-S\cos (\omega t)} \end{array}} \right.$

The figure below is meant to illustrate the above. The two dials have rotated by the angles α and – α.

We can now combine the equations for x respective y from both the dials to get

$\displaystyle \left\{ {\begin{array}{*{20}{c}} {x=P\cos (\omega t)-Q\sin (\omega t)+R\cos (\omega t)-S\sin (\omega t)} \\ {y=P\sin (\omega t)+Q\cos (\omega t)-R\sin (\omega t)-S\cos (\omega t)} \end{array}} \right.$

We can then compare the above and the equations for the input data.

$\displaystyle \left\{ {\begin{array}{*{20}{c}} {x=A\cos (\omega t)-B\sin (\omega t)} \\ {y=C\sin (\omega t)+D\cos (\omega t)} \end{array}} \right.$

They must be equal component by component. This gives us a set of simultaneous equations

$\displaystyle \left\{ {\begin{array}{*{20}{c}} {\grave{A}=P+R} \\ {B=-Q-S} \\ {C=Q-S} \\ {D=P-R} \end{array}} \right.$

This enables us to get the starting values for the relative coordinates of the pointers,

$\displaystyle \begin{array}{l}P=(A+D)/2,\\Q=(-B+C)/2,\\R=(A-D)/2,\\S=(-B-C)/2\end{array}$

This is done for every pair integer multiple of the fundamental frequency up to the number of samples/2 (up to the Nyqvist frequency).

The data can then be used to calculate the magnitude and starting angle for each dial.

Up a level : Fast Fourier transform
Previous page : 2D Fourier transforms
Next page : 2D FFT the code

Last modified: Feb 22, 2025 @ 01:38