interpreting a wave from clipped sensor data

March 11, 2009 6:56 PM

interpreting a wave from sensor data - what to do about maxed out sensors that are clipping the wave - an absurdly complex question

hello hive mind,

this is the most ridiculously complex question I have ever asked here,
but the ability of metafites to slice through unreasonably convoluted quandaries with graceful ease,
has lead me to fear I have not been doing my share to feed the hive with sufficiently challenging questions

I shall now attempt to remedy this.

I am writing a small program to reads in sample data from a sensor, which is measuring the force on an object which is moving backwards and forwards.
These force values seem - to my surprise- to usually be a bit like a sawtooth wave, I just figured they would be a sine wave.

I've never done anything like this before so I've done a lot of re-inventing of the wheel along the way.

The samples from the sensor have a timestamp.

The samples are:

fairly evenly time spaced, but not perfect.
are digitised to one of 256 values, so are not perfectly accurate

the wave is a quite uneven:

it usually seems to be closer to a sawtooth that a sinewave, but its hard to tell sometimes especially when its clipped
amplitude and frequency wobble all over the place

My program tries to make sense of the wave in realtime.

The program takes particular notice of:

the high and low peaks and
the zero crossings,

From this it creates a sort of sawtooth description of the wave.
The zero isn't perfectly calibrated, but i think its good enough.


To know when the wave has reached a high peak, I wait until the size of the sample value starts to fall, and figure that the highest point was the peak.
This usually works, although sometimes there are wobbles in the signal that confuse the algorithm into thinking the wave has peaked early.
To get around this I have used a threshold "minimum fall from peak value" before I designate a peak has occurred.


Now for the tricky park:

Often the sensor gets maxed out, so my wave gets clipped, which makes it hard to work out where the peak is.

And it makes it really hard to work it out in realtime while the samples are still in the clipped zone.

If a peak is clipped, the next one is usually clipped too.


this what I am currently doing:

if a wave peak was clipped, then next time I cross zero:

I extrapolate a line from the zero crossing point before the peak, through the last good unclipped sample before the peak
I extrapolate another line from the zero crossing point after the peak, through the first good unclipped sample after the peak.

where these lines cross, is where I assume the peak was

this seems to work ok, but if I had some way of better analysing the waveform I'd use it.
This was just the best I came up with (also it all needs to happen in realtime on a not very fast chip)

When my wave moves to the opposite peak, I have a pretty good estimation of the previous peak.

If when approaching the next peak the sensor maxes out, then I assume, that peak is going to be somewhere on the trajectory I am currently on:

If I extrapolate a line from:
the zero point

through:
the last good unclipped sample before the peak.

that the peak will fall somewhere on this line

but I need to know how far along the trajectory the peak will be.
To predict this I've assumed that the peak force on the object occurs at the extremes of its motion, which also mean that the peak force occurs when the object is stationary
As the object is going from rest to motion to rest again, I assume that acceleration impulse and the deceleration impulse from peak to peak must be of equal magnitude.

using:

the time of the previous peak
the size of the previous peak
the time of the zero crossing

I can estimate the impulse which accelerates object

and that the impulse which stops the object must have the same magnitude


rate of increase of deceleration force = good sample value /(good sample time - zero time);

time object will decelerate = square root( (zero time - previous peak time) * previous peak height / rate of increase of deceleration force)




This produces an answer that's not ridiculously wrong, but not bang on either.

so I use this as a tentative value until, next time the samples fall back to zero, when I recalculate the peak size and time.

neither my predicted or later retrospectively calculated answers are perfect, but the retrospective ones 'look' better

I'm not sure where my biggest errors are:

perhaps its treating the wave as a sawtooth?
perhaps its placing too much faith in a single sample when extrapolating trends?

I've been trying to compare my predicted peaks, with the peaks I calculate later after the peak is finished, and try to adaptively adjust the predictions

Any suggestions on what I could do better?
How I could best adaptively adjust my predictions?


cheers
mathew

oh p.s. there is nothing i can do to the sensors or their placement to prevent them from clipping

posted by compound eye to science & nature (13 comments total)

it's not clear what your computational limits are here; would you be able to do line fitting instead (throwing away the clipped areas)? this would lessen your dependency on the single zero-crossing sample, which might be introducing some noise. You could fit a line to a chunk of data before the clipping, fit a line to a chunk of data after the clipping, and then find the intersection.

also, i don't think i understand what your ultimate goal is here. are you trying to determine (for example) the dominant frequency of the wave? Or something else? Your question reads to me like you've picked your current path on the way to something else that you haven't described, because you think if you can sort this out then you'll solve the other problem. Sometimes it's useful to state the ultimate goal, because then other people can propose entirely different strategies.

For example, if you're looking for a dominant frequency, it's often simpler to compute the Fourier transform (using FFT is common in digital signal processing. In that case, i'd start by searching for details about tricks for coping with clipped signals in an Fourier transform. Or you could just discard the clipped data, and look around for tricks about Fourier transforms with missing data.

Sorry that this doesn't fully answer the question; hope it gets you closer, though!
posted by dkg at 7:18 PM on March 11

We did something similar in a lab I worked at. The histogram was expected to be Gaussian, but it saturated (we were working with silicon-germanium transistors) at voltages above a certain threshold, so we extrapolated based on what data we did have.

This is what I would do: Filter out the incoming signal and determine its frequency -- this is easier than it sounds. Find a free FFT somewhere -- if you're programming in C or Labview, they're abundant. What this will do is give you essentially an array that tells you where the "power" of the signal is relative to frequency -- you want to isolate the strongest low signal.

Once you have this information, it's simple to figure out where the peak is. The only thing you need to some statistics on the ramp-up of the sawtooth. Write some code to calculate the average and variance of the zero -> peak time (I am assuming the wave rises quickly, then decays slowly and linearly; if it's the other way around, measure peak -> zero time).

Okay, so now you know the frequency (and hence the period) of the signal and the rise time. As it starts to saturate, use the average rise time as the slope to generate one linear equation (standard y = mx + b) that models the signal going from zero up to peak; then create another one once you get the second zero point that will model a line from the peak back down to zero. The slope for this is going to be up to you to determine -- you can do it by guessing where the peak will be based on previous measurements (again, the avg rise time is useful). Find the intersection of the two lines (a simple matrix multiplication), and viola, you have your peak value.
posted by spiderskull at 7:20 PM on March 11

Are you applying a nyquist filter?
posted by the duck by the oboe at 7:20 PM on March 11

One clarification request: From your description, it sounds like you're looking at a triangle wave, rather than a sawtooth wave. Is that correct?

It's hard to advise about this without more context about your instrumental setup. Since I don't know what sort of object you're measuring, I can't say whether your approximation of the clipped peak location is accurate. Is there any symmetry? What is the shape of the unclipped peaks?

If you have reason to expect that the peaks should have a consistent shape, you could find a functional form that fits the unclipped peak, then take your function and refit it to the unclipped parts of the clipped peaks; that could give you a peak location.

An alternate (but similar) strategy: you could take a Fourier transform of an unclipped peak (just one period), then scale the length and amplitude of your decomposition until if fits the unclipped parts of a clipped peak, then recompose it to get an unclipped approximation of your clipped wave.

As you probably are aware, this calculation
"time object will decelerate = square root( (zero time - previous peak time) * previous peak height / rate of increase of deceleration force)"
does depend on the unknown clipped regions being linear. How linear are your unclipped peaks? You could try your analysis on an unclipped peak, and see how far off it is, if you want an estimate of the error.

If you want to give more details about your setup, I could try to help more. Good luck.
posted by Salvor Hardin at 7:29 PM on March 11

Others have requested more about your instrumental setup; I'll ask about the thing you're measuring. Is it possible that the thing which moves back and forth is subject to friction? You could see fits and starts, and all kinds of weird results, if the item in question is not moving smoothly.

One way you could determine this is by increasing your sampling rate and really looking closely at the raw output, before you try to muck about with anything else. I'll make a completely absurd suggestion here: do y'all think you can pull off a wee bit of laser interferometry? The reason I ask is, if you're looking at acceleration, that's a change in velocity, which is in turn a change in position. Looking closely at position and making sure that what you expect to happen there is actually happening, before you start crunching through derivatives of position, might save you a lot of time later. Apologies if you're already done this. If not, you could see that the item might be making little hiccups of motion, like a rubber shoe pushed along concrete, that would throw off all of your other expectations.

This might not be an issue with your analysis or your sensors.
posted by adipocere at 7:59 PM on March 11

Hello!

thank you for taking the time to help.

and sorry Salvor Hardin, not a sawtooth wave but a triangle wave,
although I have been treating it as if it were a triangle wave with an extra point on the zero line,
so that the rate above and below zero is not necessarily the same.

I did that because just because it seemed like something useful to try, as the wave isn't necessarily symmetrical above and below the zero line.
I don't have the experience to know what a standard approach is.


I've put a plot of some sample data here

http://www.sagenb.org/home/pub/347/

the same data is here as an xml file

http://cell.electrostallion.com/images/sample.xml


Imagine you're waving you wand in the air at someone on the other side of a large paddock, there is a linear accelerometer strapped to your wrist, and you are doing your very best to wave evenly and smoothly
The motion is mostly horizontal, but it is definitely in a slight arc, and subject to all kinds of human weirdness.

My goal is to keep track of the your hand's position along the path as best as possible using only this force data. I don't expect to be able to track its absolute position just:

an estimate of the amplitude of the movement
a realtime estimate of displacement along the path since you hand was last at rest


the accelerometer has no rotational information, and so far I have not tried to isolate gravity, although given that the centre of the arc will be pretty much constant maybe that's possible?

I realise that there are better ways to track an objects speed and position than using accelerometer data on a single axis, but in this case force is the only thing I am able to measure.

If its not already clear, I have happily strayed into an area I know very little about and am more that happy for people to suggest any really basic maths/science/techniques I should make sure I have read up on


cheers

mathew


duck by the oboe, I haven't applied a nyquist filter, the fundamental is much bigger than anything else, and the frequency of that movement should never be fast enough to have problems with aliasing

dkg, thank you for the link to the Fourier transform link, to be honest I'm not really sure what computation limits I have, I think I have more power than I assumed, so I'll look into fitting a path to through the points and see how it goes.
I've never implemented an algorithm for that myself, only every used the built in function in mathematica, if anyone has suggestions for algorithms I should look at i'd welcome your suggestions.

adipocere: there's definitely weird wobbles, but not from friction, I think I should do more to try and isolate gravity.

Salvor Hardin: I'm going to experiment with your and spiders suggestions about trying to understand the shape of the wave and scaling up a model wave till it fits the unclipped data

thanks for you all your help

cheers

mathew
posted by compound eye at 9:56 PM on March 11

By "realtime" do you mean you're trying to infer the sensor's position on a time scale less than a cycle, or a time scale greater than a cycle? If less (e.g. for one of those handheld persistence of vision displays) then maybe you could use the last few cycles' data to guess at what the current cycle should look like, but I can't offhand think of a technique that's better than what you're doing now. If greater (e.g. you're trying to do inertial navigation but there's a lot of vibration) then I think you're out of luck because you lose too much information during the clipped parts pf the data.

The other question is, what kind of accuracy is important to you? Moment-to-moment error, or overall error, long-term drift, ... ?
posted by hattifattener at 11:22 PM on March 11

hello hatti

I just want to determine the position of the object during the cycle, relative to its position last time it was stationary.


moment to moment error is the most important.


long term drift isn't such a problem

can anyone point me to something that will explain how to find a line of best fit to a bunch of points?

cheers

mathew
posted by compound eye at 3:19 AM on March 12

or c algorithms?
posted by compound eye at 3:51 AM on March 12

should anyone else ever stumble here look for the same thing, I found this:

from math import *
n=input("Enter number of points:")
sum_x=0
sum_y=0
sum_xx=0
sum_xy=0
for i in range(1,n+1):
print "For point %s"%i
x=input("Enter x:")
y=input("Enter y:")
sum_x=sum_x+x
sum_y=sum_y+y
xx=pow(x,2)
sum_xx=sum_xx+xx
xy=x*y
sum_xy=sum_xy+xy

#Calculating the coefficients
a=(-sum_x*sum_xy+sum_xx*sum_y)/(n*sum_xx-sum_x*sum_x)
b=(-sum_x*sum_y+n*sum_xy)/(n*sum_xx-sum_x*sum_x)

print "The required straight line is Y=%sX+(%s)"%(b,a)
posted by compound eye at 4:19 AM on March 12

When you design something, some of the things you ask are:

How to make it work.
How to make it adequate.
How to make it optimum.

Each time you make a decision anywhere in the design process, you constrain your later decisions.

Sometimes an approach is a dead end. Only experience will tell you when this condition is likely to be the case.

Sounds to me like you are trying to polish up something that fails the second task... how to make it adequate. It may be that there are deficiencies in your approach of how to make something that kinda works.

It may be possible to hack around the limitations of your current approach, and get something that works but you don't really know why (which I call the Lee DeForest approach to design), but if you and I were in the same room, I'd interrogate you until the lowest level conceptual task at hand were identified, and then go through SEVERAL approaches to achieving that before making hardware.

Our past decisions are our own worst enemies sometimes. Reconsider your approach and if it comes up that your current approach is the best, then hack. But don't let ignorance, laziness, lack of creativity, lack of knowledge of alternate solutions, fear, etc. stop you from a clear analysis of what is to be measured.

Making data appear where there is no data always carries the chance you are wrong. If wrong is not critical (i.e., close is good enough) then it might not be an issue, but to effectively deal with measuring the world and making inferences about it, having a crystal clear understanding of what is happening is job #1 in making something that works reliably. Do you have that? Are you measuring the right thing? Are your choices constraining your solution alternatives? What do you REALLY need and can you get it by imagining a component that provides you with that information? What components provide that type of info or more? Is this a cost issue first and foremost or have you chosen what you chose based on criteria like 'It's what it is in my parts kit'?


You seem to be admitting that not much of this is behaving like you expected. That's a red flag to me that your understanding of it lags your debugging of it, which is a sure recipe for a tough slog and not the best way to attack this problem.
posted by FauxScot at 5:46 AM on March 12

Seems like the correct solution is to correct the problem with the sensor clipping. If it's mechanical, mount it differently. If it's a microphone, turn down the gain.
posted by gjc at 7:11 AM on March 12

Thanks faux, that good advice well articulated.

This project is an art project, not research, so adequate is adequate.

gjc, your suggestion would be the right one on any other day, its allied with faux's suggestion to
'go through SEVERAL approaches to achieving that before making hardware'.

But in this case the hardware isn't my hardware, its pre-existing and I am just trying to see if i can do something interesting with the data it generates.

That said it's certainly possible start from scratch on how interpret the data and in particular which features of the data I pay attention to. There are particular patterns in the data that I have chosen as being the right ones to watch, there are lots of other relationships I have been ignoring.

So I might start all over again and see where I get to

thanks for the advice and encouragement
posted by compound eye at 3:35 PM on March 12