How does pyqtgraph compute FFT?

[Timo77]

I have a concern about the FFT that is calculated with a right click on plots.  It is my rudimentary understanding of the FFT algorithm that it expects samples equally spaced in the time domain.  The application I wrote takes data from external hardware sensors that send data in roughly equal time intervals, but not exactly.  Does the algorithm implemented account for this potentially uneven time sampling or not? 

 

The reason I have doubt is that I implemented a sine wave fitting algorithm that visibly does a very good job lining up with the data, but upon comparison in the transform view, the two peaks (peak of sine wave and peak of data) are often off by 10-20% or so.

 

Timo

[Luke Campagnola]

On Fri, Aug 16, 2013 at 4:17 PM, Timo77 <timob...@gmail.com> wrote:

I have a concern about the FFT that is calculated with a right click on plots.  It is my rudimentary understanding of the FFT algorithm that it expects samples equally spaced in the time domain.  The application I wrote takes data from external hardware sensors that send data in roughly equal time intervals, but not exactly.  Does the algorithm implemented account for this potentially uneven time sampling or not? 

 

The reason I have doubt is that I implemented a sine wave fitting algorithm that visibly does a very good job lining up with the data, but upon comparison in the transform view, the two peaks (peak of sine wave and peak of data) are often off by 10-20% or so.

You are correct; internally this just uses np.fft, which expects uniform sampling. I am vaguely aware of methods for computing the Fourier transform from non-uniform data, but have not implemented these. To get around this, I might recommend resampling your data using scipy.interpolate.griddata, but whether this produces acceptable results will depend on the details of your data.

Luke

 

[Timo77]

If I want to keep my raw data in the plot view, but pass the interpolated data to pyqtgraph's implementation of numpy.fft for calculating frequencies, where would I find that portion of the code, and would that be reasonable to do?  Or is the plot view somehow inextricably linked to the FFT part.

Timo

[Luke Campagnola]

The relevant code is in graphicsItems/PlotDataItem.py, getData():

            if self.opts['fftMode']:

                f = np.fft.fft(y) / len(y)

                y = abs(f[1:len(f)/2])

                dt = x[-1] - x[0]

                x = np.linspace(0, 0.5*len(x)/dt, len(y))

As you can see, only the first and last time values are used to determine the frequency values. Since this is pretty well buried inside the method, it will be difficult to change without modifying the code directly. For your project, this could simply be modified in-place. For pyqtgraph, though, it is important to keep the current FFT pathway available since this is required for rapidly-updating spectrogram plots. Perhaps something like this works:

            if self.opts['fftMode']:

                dx = np.diff(x)

                uniform = not np.any(np.abs(dx-dx[0]) > (abs(dx[0]) / 1000.))

                if not uniform:

                    import scipy.interpolate as interp

                    x2 = np.linspace(x[0], x[-1], len(x))

                    y = interp.griddata(x, y, x2, method='linear')

                    x = x2

                f = np.fft.fft(y) / len(y)

                y = abs(f[1:len(f)/2])

                dt = x[-1] - x[0]

                x = np.linspace(0, 0.5*len(x)/dt, len(y))

The downside to this is it adds a bit more latency when deciding whether the data is uniform.  A good long-term solution would be to provide a flag like self.opts['xDataIsUniform'] which would allow the user to indicate whether this data needs to be resampled before computing the FFT. I'll see about including this in the next release..

Luke

--
-- [ You are subscribed to pyqt...@googlegroups.com. To unsubscribe, send email to pyqtgraph+...@googlegroups.com ]
---
You received this message because you are subscribed to the Google Groups "pyqtgraph" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pyqtgraph+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Timo77]

Thank you for your input on this topic.  I will try doing as you recommend and see what kind of latency I'm up against.

Kind Regards,

[paul.b...@gmail.com]

More generally, there are methods for handling non-uniform time sampling data. You might try the Lomb-Scargle method.  A python version can be found here: http://www.astropython.org/snippet/2010/9/Fast-Lomb-Scargle-algorithm.  I suspect that this would be more accurate (depending on the variance in sampling times) than interpolation, but it is not likely to be as fast. 

There are also some Bayesian methods but implementation in python seems to be sparse so far. 

--Paul