AVR-Chat

I'm playing with an idea to make sense of analog sensors.
This is borrowed from a technique for background supression in video cameras.
Having trouble figuring an economical way to do the means and standard
deviations.

Take a single analog input, sampled at some appropriate rate.

Allocate N (call it five for now..) slots for mean and standard
deviation, and "strength".

When a new sample arrives, for each of five means, test wether the
sample falls within two standard deviations of a mean.
If so, then "strengthen" that mean, and recalculate it's standard deviation.
If not, then kill the "weakest" mean, and start a new one with this
samples value as the mean, and some appropriate guess at standard
deviation.

I've got code that buffers 50 samples on two inputs, and calculates
mean and standard deviation, and "alarms" when either of the input
falls outside 2sd, but the thing is computationally intensive, and I'm
told that the video guys do NOT keep N frames of data (which makes
sense, as it would get enormous FAST). Rather they have some method of
figuring a mean and standard deviation without history data...

Does that make any sense?
How could I implement a function like that?


-- 

"The very powerful and the very stupid have one thing in common. Instead of
altering their views to fit the facts, they alter the facts to fit their
views... which can be very uncomfortable if you happen to be one of the
facts that needs altering." Doctor Who, Face of Evil

Heard that this is a common technique.

Mean of N samples is (1/N) sum(Xi) where Xi is one of the samples X0, X1,
... XN-1

Now if you are doing a total mean rather than a windowed mean (most recent
N samples), then the new mean value is

Mean = (N*MeanPrevious + Xnew)/(N+1)

Not sure that there is a way to do this for standard deviation because if
the mean changes, then all the difference values change. That is the  hard
 part.

Jim Wagner
Oregon Research Electronics

> I'm playing with an idea to make sense of analog sensors.
> This is borrowed from a technique for background supression in video
> cameras.
> Having trouble figuring an economical way to do the means and standard
> deviations.
>
> Take a single analog input, sampled at some appropriate rate.
>
> Allocate N (call it five for now..) slots for mean and standard
> deviation, and "strength".
>
> When a new sample arrives, for each of five means, test wether the
> sample falls within two standard deviations of a mean.
> If so, then "strengthen" that mean, and recalculate it's standard
> deviation.
> If not, then kill the "weakest" mean, and start a new one with this
> samples value as the mean, and some appropriate guess at standard
> deviation.
>
> I've got code that buffers 50 samples on two inputs, and calculates
> mean and standard deviation, and "alarms" when either of the input
> falls outside 2sd, but the thing is computationally intensive, and I'm
> told that the video guys do NOT keep N frames of data (which makes
> sense, as it would get enormous FAST). Rather they have some method of
> figuring a mean and standard deviation without history data...
>
> Does that make any sense?
> How could I implement a function like that?
>
>
> --
>
> "The very powerful and the very stupid have one thing in common. Instead
> of
> altering their views to fit the facts, they alter the facts to fit their
> views... which can be very uncomfortable if you happen to be one of the
> facts that needs altering." Doctor Who, Face of Evil
>

> Mean of N samples is (1/N) sum(Xi) where Xi is one of the samples X0, X1,
> ... XN-1

Right, I've got that working, but they're telling me that they do NOT
maintain any history other than their mean and standard deviation
values!
I'm also told (last 10 mins) that they are not using the words "mean"
and "standard deviation" in the classical sense.

> Now if you are doing a total mean rather than a windowed mean (most recent
> N samples), then the new mean value is
>
> Mean = (N*MeanPrevious + Xnew)/(N+1)

Right.

> Not sure that there is a way to do this for standard deviation because if
> the mean changes, then all the difference values change. That is the  hard
>  part.

That's what's bugging me.. It looks like I could chew up an AVR
processing a small number of sensors this way, yet they do it with
multiple megapixel images in realtime. (granted, on quad-core
machines... but...)

Are there other measures of "spread" of data besides standard deviation
that would be useful?

Jim

>> Mean of N samples is (1/N) sum(Xi) where Xi is one of the samples X0,
>> X1,
>> ... XN-1
>
> Right, I've got that working, but they're telling me that they do NOT
> maintain any history other than their mean and standard deviation
> values!
> I'm also told (last 10 mins) that they are not using the words "mean"
> and "standard deviation" in the classical sense.
>
>> Now if you are doing a total mean rather than a windowed mean (most
>> recent
>> N samples), then the new mean value is
>>
>> Mean = (N*MeanPrevious + Xnew)/(N+1)
>
> Right.
>
>> Not sure that there is a way to do this for standard deviation because
>> if
>> the mean changes, then all the difference values change. That is the
>> hard
>>  part.
>
> That's what's bugging me.. It looks like I could chew up an AVR
> processing a small number of sensors this way, yet they do it with
> multiple megapixel images in realtime. (granted, on quad-core
> machines... but...)
>

On Thu, Jan 15, 2009 at 11:38 AM,  <wagnerj@proaxis.com> wrote:
> Are there other measures of "spread" of data besides standard deviation
> that would be useful?

Probably.. there's a paper on this that may help, but the math is beyond me.
Here's some examples of how it's used in video processing.
http://www.svcl.ucsd.edu/projects/dytexbkgnd/

It looks to me like it's also workable on discrete analog sensors, in
detecting anomalies, which is what got me excited about taking it on
as a project.

You have been comparing to what is done for video. My sketchy knowledge
here is that video is often dealt with in blocks. Some of the compression
and detection processing compares old blocks to new ones (at the same
image coordinates). So, rather than save all the pixels of old images,
they save statistics of those blocks. It still requires FAST processing
and lots of memory.

I'll take a look at your reference and see if there is anything I can
glean from it. This (sensor "quality") IS an area I have had to deal with
several times.

Jim

> On Thu, Jan 15, 2009 at 11:38 AM,  <wagnerj@proaxis.com> wrote:
>> Are there other measures of "spread" of data besides standard deviation
>> that would be useful?
>
> Probably.. there's a paper on this that may help, but the math is beyond
> me.
> Here's some examples of how it's used in video processing.
> http://www.svcl.ucsd.edu/projects/dytexbkgnd/
>
> It looks to me like it's also workable on discrete analog sensors, in
> detecting anomalies, which is what got me excited about taking it on
> as a project.
>

On Thu, Jan 15, 2009 at 12:46 PM,  <wagnerj@proaxis.com> wrote:
> You have been comparing to what is done for video. My sketchy knowledge
> here is that video is often dealt with in blocks.

This particular thing is done by pixel, and no information is shared
about neighboring pixels at this level.

> Some of the compression
> and detection processing compares old blocks to new ones (at the same
> image coordinates).

Right, that's later on.

On Jan 15, 2009, at 10:25 AM, wagnerj@proaxis.com wrote:

> Heard that this is a common technique.
>
> Mean of N samples is (1/N) sum(Xi) where Xi is one of the samples  
> X0, X1,
> ... XN-1
>
> Now if you are doing a total mean rather than a windowed mean (most  
> recent
> N samples), then the new mean value is
>
> Mean = (N*MeanPrevious + Xnew)/(N+1)

I'd keep a what I'd claim to be the Sum of X samples laying around.  
Then I would say that Sum(N) = Sum(N-1) - Mean(N-1) + Sample(N); and  
then Mean(N) = Sum(N) / X.

If you kept a history of X samples then you could keep a running sum  
subtracting the old out and adding the new in. But without a history  
to draw on you could subtract out the previous average as a good  
approximation before adding the new.

The difference between what I suggest and what you proposed is that I  
wouldn't multiply the old mean by the number of samples, I'd keep the  
raw sum laying around as it has a tad more precision and this skips a  
multiply step.

Make sure that the precision of Sum is great enough to hold X Samples  
at max values.

When using integer math you might consider adding 0.5X to Sum before  
dividing by X so that it rounds "normally".

--
David Kelly N4HHE, dkelly@HiWAAY.net
========================================================================
Whom computers would destroy, they must first drive mad.

RMS is the power level of the signal, so I guess peak to RMS is standard deviation. The formulas look similar to me, deal with the square of the signal.

-----Original Message-----
From: wagnerj@proaxis.com
To: AVR-Chat@yahoogroups.com
Sent: Thu, 15 Jan 2009 11:38 am
Subject: Re: [AVR-Chat] GMM



Are there other measures of "spread" of data besides standard deviation
that would be useful?

Jim

>> Mean of N samples is (1/N) sum(Xi) where Xi is one of the samples X0,
>> X1,
>> ... XN-1
>
> Right, I've got that working, but they're telling me that they do NOT
> maintain any history other than their mean and standard deviation
> values!
> I'm also told (last 10 mins) that they are not using the words "mean"
> and "standard deviation" in the classical sense.
>
>> Now if you are doing a total mean rather than a windowed mean (most
>> recent
>> N samples), then the new mean value is
>>
>> Mean = (N*MeanPrevious + Xnew)/(N+1)
>
> Right.
>
>> Not sure that there is a way to do this for standard deviation because
>> if
>> the mean changes, then all the difference values change. That is the
>> hard
>>  part.
>
> That's what's bugging me.. It looks like I could chew up an AVR
> processing a small number of sensors this way, yet they do it with
> multiple megapixel images in realtime. (granted, on quad-core
> machines... but...)
>



------------------------------------

Yahoo! Groups Links






[Non-text portions of this message have been removed]

On Thu, Jan 15, 2009 at 9:58 PM,  <BobGardner@aol.com> wrote:
> RMS is the power level of the signal, so I guess peak to RMS is standard deviation. The formulas look similar to me, deal with the square of the signal.

Ok, but having RMS and peak, how would you calculate it again on a new
sample, with only the previous RMS and peak to work from.
Peak is easy..

I do a rolling rms the same way I do a rolling avg...?I have an array of n samples, and a total. I subtract the sample at the current index from the total, add in the new sample, so now I have a new total with only two adds instead of n. I can get a new avg with a shift if n is 32 or 64 etc. To do the rms, you keep the sample squared in the array. Obviously this requires a multiply. Take the mean with a shift, same as with the avg, then take the sqrt.?

-----Original Message-----
From: David VanHorn <microbrix@gmail.com>
To: AVR-Chat@yahoogroups.com
Sent: Fri, 16 Jan 2009 9:43 am
Subject: Re: [AVR-Chat] GMM



On Thu, Jan 15, 2009 at 9:58 PM,  <BobGardner@aol.com> wrote:
> RMS is the power level of the signal, so I guess peak to RMS is standard 
deviation. The formulas look similar to me, deal with the square of the signal.

Ok, but having RMS and peak, how would you calculate it again on a new
sample, with only the previous RMS and peak to work from.
Peak is easy..

------------------------------------

Yahoo! Groups Links






[Non-text portions of this message have been removed]