hi all.

It's been a while since I last visited, for a number of reasons.

I have a programming problem (two actually) I would like to run past the various experts found herein. I can work out simplistic solutions to both of them, but don't really have the experience to get the best results.

OK, problem the first: There is a system which samples a signal at about 333Hz. The raw output of this system is a stream of 16 bit values which vary over a range of around 1000 to 8000 (decimal) when correct, but occasionally there is a spurious value which can be wildly outside this range. Not noise precisely, but erroneous values due to the nature of the system. It is desired that the output of the system be a smoothed, scaled output at approximately 20Hz, with these rogue values removed.

Currently, I am doing it in a simplistic way by averaging together 15 samples, discarding any values that fall outside the 1000-8000 range, and summing then dividing by all the values left. On a good run this gives an average of 15 values, on a bad one it might be 8 or 9. The average is then divided by 375 to scale it to the correct range. This procedure, while fairly braindead, works reasonably well in that the results are mostly within 2LSB of the correct value.

However, occasionally a value that is legal but wrong gets through, which screws things up somewhat. The thing is that the output can't actually change by more than a certain amount every cycle, due to mechanical constraints in the mechanism this system is getting it's data from, but sometimes it will generate a value which is outside the "step size" for want of better expression.

I'm sure there is at least one far superior method of processing the raw data to get the results I need. What is it?

Problem the next: Consider a system consisting of three receivers fixed at the corners of a triangle of some given size (about 40cm on a side in this case, if that's relevant). Above this triangle in such a way that it forms a pyramid is a single transmitter. This can move in three axes, but will always remain above the plane formed by the three receivers. Additionally, the movement of the transmitter is essentially in a plane parallel to the plane of the triangle for the most part, but that plane can move towards and away from the receiver plane within certain limits.

The raw output of the system is an absolute distance from the transmitter to each of the receivers. The desired processed output is an X,Y coordinate pair for each set of measurements. Think of the transmitter as the handle of a joystick, the vertical axis of which is parallel to the plane of the triangle. I want to get the output of that joystick.

Any ideas?

pca

Assuming these values are on some sort of sine wave, couldn't one compare each sample and throw out the result if the difference is greater than a certain percentage. (or rather than through it out, use an average of the two samples surrounding the corrupt data as an approximation.)

One problem I see with this is that there may be 5-10 samples in a row that are corrupt, no way to know.

By the way, I am NOT a programming expert by any stretch of the imagination, just thinking out loud.

It's not a sine motion, as it can change direction and amplitude randomly in both axes, although there are constraints on how much it can differ between samples. Probably around 25% or so, although I haven't characterised it completely yet.

pca

You didn't detail how to determine where the transmitter was in relation to a single receiver. Since we're talking about 40cm, time delay probably isn't a viable option. Did you leave out pertinent data, or is that the question?

Oh, wait. I think I misunderstood your question. You're saying that you're currently able to get distance from each receiver, right? And you just want to calculate the absolute position (well, relative to some arbitrary point) from that data, right?

The system already works out the distances to a resolution of around 1mm. That bit works perfectly. The output is currently three values giving the distance in mm from the transmitter to each receiver, updating at several 10s of Hz.

And yes, I have left out some things, which are currently beyond the public's need to know

pca

Removing the "noise" from your signal is all about characterizing your noise. If it's single samples that are bogus, and you can write an accurate "bogus" predictor (e.g., reject all samples outside of your [1000,8000] range), then do that first. If your noise is uglier than that, then you've got more work to do, but it should be focused entirely on detecting bogus vs. non-bogus samples. Then, do your downsampling after you've removed the noise. (You might need to keep a bit vector or something to label the samples that you removed, so they don't influence the averaging you do afterward.)

(In some cases, like digital cameras, they can potentially / beneficially combine the "denoising" operation with other things like demosaicing, so it's hard to say that you should *always* do the denoising by itself, first, but that seems better suited to the way you've characterized your noise.)

If you want to get fancier, you would want to get into some kind of statistical model. Given where you think things where last time and what you've observed, you try to predict where things must be the next time around. Rather than tracking your state as a single number, you track it as a probability distribution. If an observation is highly unlikely to have occured given the state you think you're in, you might just reject it altogether.

We did something like this as part of an in-building navigation system we built using signal strength measurements from 802.11 base stations. We took measurements in each and every office (two nights of fun work) and then you just start walking around and comparing your observed measurements to the database and to where you thought you were beforehand. The system knows the tolopology of the building, allowing it to reject any spurious readings that might otherwise indicate, for example, that you were on the opposite side of the building from where you were on the previous reading.

Gory details here:

http://www.cs.rice.edu/~ahae/papers/mobicom2004.pdf

Thanks. My mad maths skillz are not really mad (more mildly annoyed at the best of times), but I'll fumble my way through that and see if I can code something that works.

pca

Damn. I was trying to solve it with trigonometry. Your way makes a lot more sense.

The problem with calling in a squad of trigognomes would seem to be that a number of angles are not known. Peter's method, assuming I can produce some C code that will actually compile, seems like it will work. I hope.

pca

Interesting paper.

So, I guess I will have to modify the averaging code. I can fairly easily check if the difference between the current value and the last value is unexpectedly larger than the difference between the previous value and the one before that, I suppose. It may well work if the bad value is simply replaced with the last good one, as the actual sampling rate is much higher than the desired output rate.

If I then maintain a rolling average rather than just calculating individual blocks of 15 samples averaged together, I'd guess that this would also smooth out the result.

Hmm. I'll have to experiment a little. Thanks.

pca

It sounds to me like your programming problem has been solved long ago. You're just not thinking in the right domain.

What you've got there is a peak limiter combined with a high frequency noise filter. This is audio processor programming.

I can recommend some great VST plugins if you want.

Hmm. Good point.

But, it's got to run on a processor with 768 bytes of ram. That limits the resources a little

pca

I'm sure there's prior art, of course, even in assembler, if you look in the right places.

I'm not really a maths expert, but would a least squares calculation allow you to detect erroneous values?

I used to do a bunch of this stuff in engineering school, and later with stress and vibration test results.

Spurious data points are usually removed using statistical methods, most commonly with the Student T distribution, particularly if the order of the system is known.

Rather than keeping track of a range, you want to use the data stream to keep track of the standard deviation of the samples. Using your estimated standard deviation, and a choice of how "sure" you want to be that a given point is an outlier, you can use a simple formula to detect them.

This might get you down the right track:

Studentized Residuals

On the other hand, if you don't have a statistics background, maybe not.

Here is a more friendly intro, with a link to a paper on the subject: Outliers

Best,

Jim