I have a series of measurements of a signal source, which emits a periodic signal at an unknown interval time of p seconds. Detecting the signal is not easy so I am missing quite a few signals in the data. Data is also noisy so there are errors in the data of up to +/- 10% per signal.

Example measurements x might look like this:

72.3, 185.1, 364.2, 570.2, 679.2, 1060.7

The result I am looking for, is the period hidden in the measurments, p = ~100 in this example case and possibly the best offset c = ~70.

Typically I have 4-7 measurements in a series I would like to analyse, so it seems an analytic answer is more appropriate than a sound analysis (FFT).

Ideas I have considered:

But I am very unsure whether I might have missed an obvious solution from the sound analysis camp (autocorrelation, Harmonic Spectrum Product, DFT, e.g. https://stackoverflow.com/questions/4716620/algorithm-to-determine-fundamental-frequency-from-potential-harmonics).

So I am turning to the wisdom of SO. How would you go about solving this problem most elegantly? Library suggestions are fine (C++).

  • $\begingroup$ What is the signal and how are you detecting it? $\endgroup$ – endolith Jul 23 '12 at 0:36
  • $\begingroup$ The signal are 2D blobs from a single line of a marker grid detected using an HD camera using a blob-detector. The blobs are fitted on a line and their x-offsets are shown above (subpixel accuracy is from the blob-detector). $\endgroup$ – Christopher Oezbek Jul 23 '12 at 9:50

This really reminds me of the problem of beat induction in music signals, in which you have to infer a latent periodic grid from note onset measurements. The grid is "latent" - it's not because a track is at 120 BPM that it strictly has a quarter note every 500ms - the composer can choose to phrase the melody with half notes, then eighth notes... And then there's accentuation (which would change the intensity of pulses) and swing (which would shuffle them a bit temporally)...

If you really want to work from what you describe in your question - the list of timestamps - you need to compute a histogram of time deltas, convolve it by a gaussian window to smooth it (to consolidate together deltas which are close to each other), and then evaluate as possible period candidates integer divisors of the histogram peak. This is described in section 4.3 of this paper.

While it might work well in your case, I strongly encourage you not to detect events, but rather try to estimate the period from your underlying raw signals. The reason is that the detection process is discarding some valuable information which might help the period estimation process. For example, you record "spikes" at 72.3, 185.1, 364.2, 570.2, 679.2, 1060.7... But what is there at 270? It will be useful for the periodicity detection system to be informed that there might be a little spike at 270 just below your event detection threshold.

My own experience with beat tracking / induction is that it works much better "pre-detection" (with a continuous onset detection function keeping "weak" source of informations such as ghost notes) than "post-detection" (where all "weak" events have been thresholded).


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.