Need algorithm to "stabilize" input data

Hi all,
I need an algorithm that "stabilizes" the input data I get from a sensor.
The sensor does not capture "perfect" data, and sometimes the data
oscillates around the real value I'm looking for. For example, consider
the following input:

|  *
|** **  ** **          *
|     **  *  *
|             *                       *
|              *                *** ** **
|               *  **          *   *
|                **  ** **** **
|                           *
|-----------|----|-----x------|-|-------|------
A           B    C     S      D E       F

In this chart, the asterisks represent the data I get from the sensor.
What I would like to obtain is a chart where the segments A-B, C-D and E-F
are flat (i.e., the oscillation around the "real" value is removed).
Furthermore, I need an algorithm that works in real-time, that is while
the sensor captures the data (I don't have the future samples), and I
can't wait for them.

Sometimes the sensor really gets a wrong sample, for example as in S. The
"wrong" samples should be thrown away.

I tried several simple approaches (for example averaging the old samples),
but none of the was good enough for my needs. I think this is a common
problem, is anyone aware of existing algorithms to solve this problem?

Every help is appreciated
Thanks a lot
Andrea

I noticed that the chart does not look very nice... :-(

I try to put it here again:

<pre>|  *
|** **  ** **          *
|     **  *  *
|             *                       *
|
|              *                *** ** **
|               *  **          *   *
|                **  ** **** **
|                           *
|-----------|----|-----x------|-|-------|-----
A           B    C     S      D E       F</pre>

If this should not work, please look at this picture:
http://www.pecore.ch/Ciaccia/chart.png

Sorry for all the mess ;-)

"Ciaccia" <ciacciax@yahoo.com> wrote in message 
news:u5WdnWAbheWLfGTanZ2dnUVZ_hadnZ2d@giganews.com...
> Hi all,
> I need an algorithm that "stabilizes" the input data I get 
> from a sensor.
> The sensor does not capture "perfect" data, and sometimes the 
> data
> oscillates around the real value I'm looking for. For 
> example, consider
> the following input:
>
> |  *
> |** **  ** **          *
> |     **  *  *
> |             *                       *
> |              *                *** ** **
> |               *  **          *   *
> |                **  ** **** **
> |                           *
> |-----------|----|-----x------|-|-------|------
> A           B    C     S      D E       F
>
> In this chart, the asterisks represent the data I get from 
> the sensor.
> What I would like to obtain is a chart where the segments 
> A-B, C-D and E-F
> are flat (i.e., the oscillation around the "real" value is 
> removed).
> Furthermore, I need an algorithm that works in real-time, 
> that is while
> the sensor captures the data (I don't have the future 
> samples), and I
> can't wait for them.
>

Depending on how you identify A-B, C-D, etc., you might be able 
to use the median of each of these intervals to filter the 
data.  (By way of a quick review, sort a window of N samples, 
emit the one in the middle of the sorted list, and then advance 
your N-sample window by one sample.)  It can require a lot of 
processing, but I've found this filter to be very effective at 
dealing with outliers and similar anomalies.

If you can tolerate some delay in your processed data stream, 
you can make your filter "think" it is able to work on future 
samples.  That is, if you can tolerate D units of delay, then, 
after you obtain sample K, you do some processing to emit 
output K-D.  Compared to its output, your filter is looking D 
units into the future.  Not all real-time systems can tolerate 
much delay; it depends on what you are doing with the sensor 
data.

On 7 Apr, 10:53, "Ciaccia" <ciacc...@yahoo.com> wrote:
> Hi all,
> I need an algorithm that "stabilizes" the input data I get from a sensor.
....
> I tried several simple approaches (for example averaging the old samples),
> but none of the was good enough for my needs. I think this is a common
> problem, is anyone aware of existing algorithms to solve this problem?

Kalman filter?

Rune

Hi,

  I think a simple hysteresis filter should do.

  step 1 : perform very simple LPF.

  step 2 : perform hystersis option.

  I think your states are pretty much well defined.
  Also these states will be guided by thresholds.
  Meaning if the signal falls within r1 to r2 range
  consider it at state 1. and a state is not changed
  for some instantaneous or erroneaous transitions.

  Check for a stable change for sometime.

  Hysteresis logics are normally implemented using
  counter arithmetic and thresholds. It is a form
  of a state machine.

Regards 
Bharat Pathak

Arithos Designs
www.Arithos.com

  

You can also use a circular buffer of size "N".  Determine the average
of the values in the buffer every time a new sample is added.  This
works well in environments where the data is oscillating around a
threshold.

Kind Regards,
Jaco

On Mon, 07 Apr 2008 03:53:42 -0500, "Ciaccia" <ciacciax@yahoo.com>
wrote:

>Hi all,
>I need an algorithm that "stabilizes" the input data I get from a sensor.
>The sensor does not capture "perfect" data, and sometimes the data
>oscillates around the real value I'm looking for. For example, consider
>the following input:
>
>|  *
>|** **  ** **          *
>|     **  *  *
>|             *                       *
>|              *                *** ** **
>|               *  **          *   *
>|                **  ** **** **
>|                           *
>|-----------|----|-----x------|-|-------|------
>A           B    C     S      D E       F
>
>In this chart, the asterisks represent the data I get from the sensor.
>What I would like to obtain is a chart where the segments A-B, C-D and E-F
>are flat (i.e., the oscillation around the "real" value is removed).
>Furthermore, I need an algorithm that works in real-time, that is while
>the sensor captures the data (I don't have the future samples), and I
>can't wait for them.

Do you know how fast the change can be in the "real" data ? ie the
width of B-C, D-E? If they're slow enough sharp low-pass filter may
work. By "I can't wait for them (future samples)" do you mean that you
can not tolerate any latency (ie buffer to see what the "future"
samples look like) 

>On Mon, 07 Apr 2008 03:53:42 -0500, "Ciaccia" <ciacciax@yahoo.com>
>wrote:
>
>>Hi all,
>>I need an algorithm that "stabilizes" the input data I get from a
sensor.
>>The sensor does not capture "perfect" data, and sometimes the data
>>oscillates around the real value I'm looking for. For example, consider
>>the following input:
>>
>>|  *
>>|** **  ** **          *
>>|     **  *  *
>>|             *                       *
>>|              *                *** ** **
>>|               *  **          *   *
>>|                **  ** **** **
>>|                           *
>>|-----------|----|-----x------|-|-------|------
>>A           B    C     S      D E       F
>>
>>In this chart, the asterisks represent the data I get from the sensor.
>>What I would like to obtain is a chart where the segments A-B, C-D and
E-F
>>are flat (i.e., the oscillation around the "real" value is removed).
>>Furthermore, I need an algorithm that works in real-time, that is while
>>the sensor captures the data (I don't have the future samples), and I
>>can't wait for them.
>
>Do you know how fast the change can be in the "real" data ? ie the
>width of B-C, D-E? If they're slow enough sharp low-pass filter may
>work. By "I can't wait for them (future samples)" do you mean that you
>can not tolerate any latency (ie buffer to see what the "future"
>samples look like) 

Hi all,
First I would like to thank everyone for the suggestions! I tried the
algorithm working with the median John (3rd post) suggested, and works
pretty well (even if not in all cases).

The situation my program has to deal with is very simple, I try to
summarize it:
-I don't know how fast the data changes (going from one "state" to another
could take 2 samples or 30)
-the width of a flat "segment" has at least a given length (say 4
samples)
-there are not pre-defined statuses (as Bharat suggested). 
-every time a new sample is captured, my program needs to print an output
(i.e., I cannot wait for the next samples that will captured to print a
result) If not "sure", return the more likely outcome

I understand this problem is somehow complex, consider the following
scenario. 
time 0: the sensor captures 10
time 1: the sensor captures 9
time 2: the sensor captures 8
time 3: the sensor captures 7
time 4: the sensor captures 7
time 5: the sensor captures 6
time 6: the sensor captures 7

If I look at the captured data at time 6, I can easily see that the
interval from time 0 to time 2 is a (descending) transition phase, and
that at time 3 starts a "flat" phase that goes from time 3 to time 7 (the
phase I am interested in).

If at time 3 I look at the available data, I cannot say if the samples at
time 3 is a sample of the descending transition phase, or if it is the
start of the flat phase. At time 4, having more information available, I
could say "it's possible that at time 3, a flat phase started". Continuing
with the logic, at time 6 I can say for sure at time 3 started a flat
phase, since I can look at the past samples.

My goal (even if I understand is not fully achievable) is to minimize the
"latency" I need to find the flat phases and print them. I guess I must
play statistically or create an hidden model, since at time 4 I cannot be
sure a flat phase started at three...

Maybe I should add probabilities to my computations...
Any hints?

"Ciaccia" <ciacciax@yahoo.com> writes:

> Hi all,
> I need an algorithm that "stabilizes" the input data I get from a sensor.
> The sensor does not capture "perfect" data, and sometimes the data
> oscillates around the real value I'm looking for. For example, consider
> the following input:
>
> |  *
> |** **  ** **          *
> |     **  *  *
> |             *                       *
> |              *                *** ** **
> |               *  **          *   *
> |                **  ** **** **
> |                           *
> |-----------|----|-----x------|-|-------|------
> A           B    C     S      D E       F
>
> In this chart, the asterisks represent the data I get from the sensor.
> What I would like to obtain is a chart where the segments A-B, C-D and E-F
> are flat (i.e., the oscillation around the "real" value is removed).
> Furthermore, I need an algorithm that works in real-time, that is while
> the sensor captures the data (I don't have the future samples), and I
> can't wait for them.

Then your task is impossible because, e.g., in the segment E-F at the
third data point (0-indexed), you don't yet know whether data points 0,
1, and 2 are correct and 4 is the deviant or vice-versa.

If you could wait until the segment endpoints, e.g., B, D, and F, and
have knowledge of the segment begin points and endpoints, then you can
simply take a majority vote of the histogram over the segment.
-- 
%  Randy Yates                  % "Watching all the days go by...    
%% Fuquay-Varina, NC            %  Who are you and who am I?"
%%% 919-577-9882                % 'Mission (A World Record)', 
%%%% <yates@ieee.org>           % *A New World Record*, ELO
http://www.digitalsignallabs.com

Correction:

Randy Yates <yates@ieee.org> writes:
> [...]
> and 4 is the deviant [...]

  and 3 is the deviant [...]
-- 
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://www.digitalsignallabs.com