5
$\begingroup$

I need to detect the time window where a 1D-signal is above a certain threshold. If it dips below the threshold briefly I'd like to merge the two windows, if it dips below for a longer time, split them. The data are received digitally as array $S[t]$ with equally-spaced $t$ intervals and represent precipitation forecasts from a weather model.

I want to find $t_{on}$ / $t_{off}$ in signals like the following:

signal example enter image description here

I know this isn't terribly hard and I can probably come up with an algorithm myself, but I thought this is a problem that smarter people than me have already thought about.

The algorithm will be implemented in software and run on general-purpose datacenter servers (no specialised hardware). It doesn't have to be crazy fast, "reasonable" is good enough (we have a few 100k time series to process at once every now and then; each series has probably less then 1000 points).

I'd welcome algorithm suggestions, Google keywords, book/article recommendations. I'm rather new to data processing, in case it isn't blatantly obvious.

Edit: Thanks everyone for the great comments and answers. This question really couldn't have turned out much better. What I'm worrying about the most is how to handle pathological cases, like "oscillations" around the threshold.

Oscillation1 Oscillation2

My own idea was having separate on/off-thresholds, with $ thresh_{off} = f * thresh_{on} $ (with $f$ in the range of [0.5, 0.99]). I also really like Marten's idea of temporarily modifying the threshold value after the signal crosses the threshold in a hysteresis-like manner.

Are there other strategies to handle this issue that I should know about?

Are there other potential issues that I need to know about?

Improve this question
$\endgroup$
  • $\begingroup$ Is your input digital or analog? The details are not clear. The algorithm is embedded in your question - compare each data point, marked with the time of sampling/viewing to the threshold. Get the list of ON/Off times. Decide what periods of under threshold are acceptable for mergers... and so on. Do you have specialized hardware or you need to use software on servers? $\endgroup$ – Moti Aug 26 '15 at 21:16
  • $\begingroup$ @Moti: Updated my question. tl/dr: digital input as array S[t] at equidistant t, representing weather model precipitation forecasts. No specialized HW, runs as SW on general purpose servers. I see the obvious algorithm, are there well known merge policy strategies? Tons of people must have solved that problem before me, but I couldn't Google any good discussion about it. As I said, can do it myself, but isn't there literature on this? $\endgroup$ – Christian Aichinger Aug 26 '15 at 22:48
  • $\begingroup$ Since you do not need it in real time, the fastest processing from a system point of view will be to process each vector on its own, and run as many as needed processes of sets in parallel, on separate systems. If you know what gap is cancelled (does it go both ways - when you have a small crossing - is it neglected?) $\endgroup$ – Moti Aug 26 '15 at 23:38
  • $\begingroup$ @Moti: It should go both ways. A "small dip" could be defined via limits on any/all of $\Delta t$, $abs \Delta (S - thresh)$, and $\Delta Integral$. The interesting part is not which regions to eliminate, it's what neighbor to merge them into (see my comment to Richard's answer). $\endgroup$ – Christian Aichinger Aug 26 '15 at 23:52
  • $\begingroup$ It seems you developed the rules of merger. What you mean by merging from the left? Is the algorithm non symmetric? It make sense to merge as you move through data points with time (merge right). $\endgroup$ – Moti Aug 27 '15 at 6:06
5
$\begingroup$

There is a book by Basseville and Nikiforov called "Detection of Abrupt Changes : Theory and Application" that they released to the public as a PDF several years ago (it's out of print, now, I believe).

That book looks at the basic CUSUM (cumulative sum) algorithm and how to choose appropriate thresholds for it.

enter image description here

Improve this answer
$\endgroup$
  • $\begingroup$ This is actually the proper way for doing this.... Included the reference (which i actually printed from the PDFs :) ).......... $\endgroup$ – Brethlosze Nov 4 '16 at 18:09
  • $\begingroup$ @mohsensajjadi Thanks for the update! :-) $\endgroup$ – Peter K.♦ Nov 14 '18 at 13:52
2
$\begingroup$

For discarding events where the signal is not very different from the threshold (special case: oscillation), have you considered using a hysteresis?

If the signal rises above the threshold ($t_{on}$-event), temporarily decrease the threshold (by either a factor (a few percent) or an absolute value, the best value will depend on the your system/model). This way, it is 'harder' for the signal to drop below the threshold again.

Whenever the signal drops below the decreased threshold (the $t_{off}$-event), immediately revert the threshold to its original value.

This is a very effective (and often used) way of preventing oscillation and bouncing.

Also, if a peak or dip is very short (shorter than the defined minimum duration), but also very high in amplitude, do you consider it "irrelevant"? This method solves that problem is well.

Edit: To clarify it a bit more, here is one of your pictures that I have added to, to show the hysteresis principle.

principle of hysteresis with two separate threshold values for the on and off events

The blue horizontal line is the secondary threshold. $t_{on}$ occurs at time $A$, as expected. Since the signal does not drop below the second threshold (although it does drop below the original threshold), $t_{off}$ only occurs at time $B$.

The hard part is to find the proper values of both thresholds. It is perhaps good to even increase the original threshold a bit, to avoid too long 'on'-durations. This totally depends on the system of interest.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks Marten, hysteresis is a very interesting concept that I hadn't thought about. My original plan was to use two separate (static) thresholds: $ thresh_{on} $ and $ thresh_{off} $, separated by maybe 5% or so. I'll see what works best once I get my hands on some actual data. $\endgroup$ – Christian Aichinger Aug 28 '15 at 18:18
  • $\begingroup$ Actually, having two separate threshold values is exactly the same: the hysteresis method is based on applying two separate threshold values for the 'on' and 'off' events. If you observe the signals 'live' in a y/t viewer or plot, it is sometimes clearer to see only one threshold line (which changes with each event) instead of having two lines. But the principle is one and the same. $\endgroup$ – Marten Koetsier Aug 29 '15 at 6:14
  • $\begingroup$ Ah, I thought you suggested making $ thresh_{off} $ change with time since the last event: $ thresh_{off}(t - last\_ t_{on}) $ (e.g. rectangle function, exponential decay). Not sure whether it's useful for my problem, but it's something to consider. $\endgroup$ – Christian Aichinger Aug 29 '15 at 6:44
0
$\begingroup$

Assuming you're working with discrete samples, it seems to me that you must execute two separate tests on your time-domain samples. One test is 'thresholding–in-amplitude' and the other test is 'thresholding–in-time-duration'. Let's assume your complete data sequence contains three wide amplitude peaks that exceed your amplitude threshold. Test# 1 is measuring time instants t_on_1, t_off_1, t_on_2, t_off_2, t_on_3, and t_off_3.

Test#2 is measuring the two "dip" time intervals between your three peaks: dip_1 = (t_on_2 -t_off_1) and dip_2 = (t_on_3 -t_off_2). Then you must determine if either of the two "dip" time intervals is less than some specified time-duration threshold. And if, for example, the "dip" time interval between the 2nd and 3rd peaks is too small (value dip_2 is less than the specified time-duration threshold) then you set t_off_2 = t_off_3 and discard the original measured t_off_2, t_on_3, and t_on_3 values. Finally you can claim your data sequence had only two amplitude peaks. Hope that makes sense.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks, makes sense. I had a similar idea, but I'm struggling with what you hand-wave: why merge to the right (toward t3, not t1)? I could just as well merge to the left and the results would be different. $\endgroup$ – Christian Aichinger Aug 26 '15 at 23:23
  • $\begingroup$ Oh shoot. I don't understand your comment. In my scenario, let's say that t_on_1 = 5, t_off_1 = 45, t_on_2 = 90, t_off_2 = 100, t_on_3 = 102, and t_off_3 = 150. Next you decide t_on_3 minus t_off_2 is too small (a single brief dip) and should be ignored. So you set t_off_2 equal to t_off_3 = 150. And you are now finished and can claim the signal had only two peaks represented by t_on_1 = 5, t_off_1 = 45, t_on_2 = 90, t_off_2 = 150. $\endgroup$ – Richard Lyons Aug 27 '15 at 12:40

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.