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

This is a discussion on What kind of algorithm do I need to apply for this ? within the Tech Board forums, part of the Community Boards category; I have a device that measures acceleration (more accurately this ). I can show this realtime plot from the data ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    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.
    Name:  snapshot7.jpg
Views: 558
Size:  32.9 KB
    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.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,052
    How are you planning on "actually using" this data?

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    1,203
    Is the given amount of time fixed?

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,468
    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. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by anduril462 View Post
    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'.


    Quote Originally Posted by Shakti View Post
    Is the given amount of time fixed?
    Possibly.
    I have to keep a small window of data I can process at a time.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,439
    Quote Originally Posted by anduril462 View Post
    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 read two values ahead to plot your graph.
    • 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.
    Last edited by Mario F.; 12-14-2013 at 01:42 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to apply Regex in C++?
    By Mestertik in forum C++ Programming
    Replies: 21
    Last Post: 10-30-2013, 01:42 PM
  2. Program to apply windows registry settings
    By john3j in forum C Programming
    Replies: 5
    Last Post: 09-21-2012, 08:08 PM
  3. Apply style to multiple windows
    By gaurav_13191 in forum Windows Programming
    Replies: 5
    Last Post: 07-07-2011, 11:59 PM
  4. Replies: 6
    Last Post: 10-29-2010, 10:39 AM
  5. How to apply selection sort in a two-dimensional array
    By yigster in forum C++ Programming
    Replies: 16
    Last Post: 04-28-2010, 11:56 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21