# Thread: What kind of algorithm do I need to apply for this ?

1. ## What kind of algorithm do I need to apply for this ?

I have a device that measures acceleration (more accurately this).
I can show this realtime plot from the data I can get.

The rate is about 100 hz.
And I recieve a signed byte for each axis.

To actually use this data, I need to detect when the data has not changed much(vibrations below a threshold are acceptable) for an given amount of time.
(The level may not be zero.)
Also, depending on that level, I need an algorithm for detecting a sudden pulse and also adjust the level to the possible new value after the pulse ends.

I have little experience with numerical computing, so...would like some advise instead of devising a brute force algorithm.

2. How are you planning on "actually using" this data?

3. Is the given amount of time fixed?

4. I'm no expert in the field either, so there may be better solutions I'm not aware of, though I wouldn't consider this a "brute force" approach either. Also, of course, the specific details really depend on your system, what exactly you want to measure/detect, etc, but in general, the following should work.

The simplest solution to measure change is to just keep a previous and current value. Update them every time you take a sample. If the difference between the two is more than your threshold, then you have acceleration.

You may want more sample depth though. At 100Hz, you have samples every 10ms. But you may only be concerned with acceleration that is sustained for 50ms or more. For that you need an array of samples. You need to check the delta in acceleration between each pair of samples, and if all of the deltas (or, e.g., at least 3 of the 5 deltas) exceed the threshold, then you have sustained movement. Alternatively, you may want to look at the average deltas. Sum up all the deltas and divide by number of deltas (num_samples - 1) and compare that to the threshold.

I would use a circular buffer (implemented as an array) to store samples and do my calculations on. Keep in mind that 50ms of samples is 5 sampling periods, but that is 5 * 10ms between samples. Thus, you need 6 samples for 5 deltas.

If you need to account for the steady-state acceleration changes, so that readings of, e.g. 10, from the sensors is the new "normal" (instead of 0), then you can use that circular buffer to keep a running average. Add up all the readings and divide by num_samples. I'm not quite sure why you need that though. A delta is a delta. So if your threshold is 5, then whether your readings are -3 and 4 or 22 and 29, you are seeing the same change in accelerations, both deltas exceed your threshold.

5. Originally Posted by anduril462
You need to check the delta in acceleration between each pair of samples, and if all of the deltas (or, e.g., at least 3 of the 5 deltas) exceed the threshold, then you have sustained movement. Alternatively, you may want to look at the average deltas. Sum up all the deltas and divide by number of deltas (num_samples - 1) and compare that to the threshold.
Thanks, I'll try this out and see if this gives me appreciable results.

Btw, this data will be used to make a new input device.
I have not settled on exact details...but it would be using user defined 'gestures'.

Originally Posted by Shakti
Is the given amount of time fixed?
Possibly.
I have to keep a small window of data I can process at a time.

6. Originally Posted by anduril462
If you need to account for the steady-state acceleration changes, so that readings of, e.g. 10, from the sensors is the new "normal" (instead of 0), then you can use that circular buffer to keep a running average. Add up all the readings and divide by num_samples. I'm not quite sure why you need that though. A delta is a delta. So if your threshold is 5, then whether your readings are -3 and 4 or 22 and 29, you are seeing the same change in accelerations, both deltas exceed your threshold.
Is this a live plot?

If I understand it right, I think it's because Manasij needs to adjust the vertical axis of plot at runtime as changes in acceleration magnitude happen, giving him a live plot that can represent both tiny and large changes in acceleration in a readable manner.

If I'm right, I'm trying to think of an algorithm. Here's a sketchy (not fully mulled over) presentation:

• You need a simple single instance tuple. No need for arrays.
• You need to store the maximum and minimum acceleration values as data is being feed to your plot.
• You need to store whether there is currently acceleration or deceleration. A +1/-1 should be enough, calculated from the new value minus the old value.
• You keep changing this tuple until there is a change in acceleration.
• You calculate a running median (not average) of this store. This is the value you use live to adjust your vertical axis at runtime. This average is essentially telling you the central point of your acceleration magnitude.
• When there is a change in acceleration, you set the maximum and minimum values to the two new values you are feed.
• You repeat.

This way you avoid having to keep a threshold (tolerance) value. Your plot is scaled according to conditions. I believe that at 100hz you are being feed data fast enough for the visual changes in scale to be smooth.

EDIT: Forget about the running median. This is a single tuple that is storing the current maximum and minimum value of an acceleration/deceleration event. It makes no sense to calculate a running anything. You just calculate the average between the two values before changing them with the next value being feed to you.

7. Yes, it is a live plot.
(I've wasted hours looking at the pretty patterns of acceleration produced when the sensor is placed on my cellphone playing music on vibrate !)

Your approach (the first part) sounds like the the delta-modulation I've studied in my networking class.
After that, I can't understand what is being done with the median.
Can you clarify a little bit?

8. This is a signal processing problem of course.

Extremely short-time temporal calculations, such as measuring the change between one sample and the next, are far too susceptible to noise to be all that useful.

A simple technique is to measure the total "energy" in the signal over a certain period of time. To do this, accumulate samples in a buffer (for instance, 10 samples for 100 ms window), and then compute the sum of the squares of the values in the buffer. Then compare to some threshold. The windows can overlap if you want.

For your other problem, which is computing the scale of the signal so you can plot it, has to be solved carefully. If you adapt too quickly to the signal, you will end up jittering your scale factor right along with the small-scale signal changes (which include some level of noise). Your graph will then jerk to and fro in a seizure-inducing way. Compute two exponential moving averages: one of the signal itself, and one of the absolute value of the signal. These two values can be used to compute a scale factor for displaying the data. Yes, the signal may sometimes overshoot your current window, that's just a fact of life. If you try to hard to correct for the overshoot you will end up jittering too much.