Re: Calculating Variance in real-time
From: Michael Newberry (mnewberry_at_axres.com)
Date: 06/29/04
- Next message: MingChieh: "How to sort a 8-bit gray level image quickly by its gradient?"
- Previous message: Paolo Bellutta: "Re: Calculating Variance in real-time"
- In reply to: Paolo Bellutta: "Re: Calculating Variance in real-time"
- Next in thread: ip4ram_at_yahoo.com: "Re: Calculating Variance in real-time"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 29 Jun 2004 22:54:33 GMT
Well, it could be that I am misunderstanding the problem and that you are
correct. The original poster was not particularly clear about what he was
doing.
Michael
"Paolo Bellutta" <bellutta@horsepower.csail.mit.edu> wrote in message
news:40e1f1cd$0$570$b45e6eb0@senator-bedfellow.mit.edu...
> Michael Newberry <mnewberry@axres.com> wrote:
> > Paolo,
>
> > Of course, the mean and variance are computed from sums of values and
> > squares---the "one pass" method is the only sensible way to do it. And
also,
> > the ordering is irrelevant for his 0-dimensional statistics (i.e., stats
do
> > not involve position on the image). But he cannot remove and replace the
> > values and squares in the running sums unless he knows exaclty which
values
> > are changing. In other words, he needs to know exactly which image
pixels at
> > what locations changed value in one image relative to the previous
image.
> > This is required if he is to remove the old values and replace the new
> > values into the running sums to efficiently update the mean and std dev.
If
> > he does not know which pixels remained constant between images, he does
not
> > know which values to keep in the running sums. I thought those issues
were
> > pretty obvious.
>
> No, it was not obvious to me. I did not gather from the OP that he wanted
to
> compute the PIXEL variance. Even so, the same technique can be applied if
> you keep an "image" with the running sums and running sum of squares. If
> this is a sliding window you still need to store the N previous images,
> but still it is a feasible proposition for a reasonably sized image.
>
> I apologize I was thinking that the OP wanted to compute the image
variance
> not a pixel-by-pixel variance.
>
> Paolo
>
> > Michael
>
> > "Paolo Bellutta" <bellutta@horsepower.csail.mit.edu> wrote in message
> > news:40e105bd$0$561$b45e6eb0@senator-bedfellow.mit.edu...
> >> Michael Newberry <mnewberry@axres.com> wrote:
> >> > Paolo,
> >>
> >> > With all due respect, what you are saying is not going to work. There
is
> > not
> >> > assumed any correlation between one image and the next. Any pixel of
an
> >> > image has no relation with the corresponding pixel in any other
image.
> > So
> >> > any stored imformation has no relevance to the new incoming image and
a
> >> > queue has no purpose here. There is absolutely nothing gained by
storing
> >> > pixel values from one image to the next.
> >>
> >> Michael, I am assuming you want to compute mean and variance of all the
> > pixels
> >> of N images. I think this is what the OP was asking. In this context
> > pixels
> >> are just data points, and you can rearrange them any way you want.
> > Moreover,
> >> it is a well known fact you can derive variance from th esum of the
values
> > of
> >> all pixels and the sum of the square of their values. Given these two
> > facts
> >> you *can* use this method. It is very fast, I have been using this for
> > years.
> >>
> >> Paolo
> >> > Michael
> >> > .
> >> > "Paolo Bellutta" <bellutta@yahoo.com> wrote in message
> >> > news:40ddd3cc$0$577$b45e6eb0@senator-bedfellow.mit.edu...
> >> >> Michael Newberry <mnewberry@axres.com> wrote:
> >> >> > Vladimir,
> >> >>
> >> >> > He is talking about a different problem. I have used your method.
and
> > it
> >> >> > works splendidly when taking different samples in the same image
> > because
> >> >> > most of the sample values do not change when you move the sample
> > region.
> >> >> > herefore there are relatively few replacements and the
re-calculation
> > is
> >> >> > quick. However, Ram has a different problem of measuring variance
in
> > an
> >> >> > image stream, and I assume that the pixel values are not repeated
> > from
> >> > one
> >> >> > image to the next. So he has to compute a new mean and variance
each
> >> > time.
> >> >>
> >> >> No, he can still use this technique. It is unclear to me if the OP
> > needs
> >> >> to compute the mean and variance of all images together or only of
the
> >> > last
> >> >> N images, still here's how you do it:
> >> >>
> >> >> In the hypotesis of computing mean and variance of all images you
begin
> >> >> by setting SUM and SUM2 to 0 (zero). For eeach new image you
compute
> >> >> sum(I[x,y]) and sum(I[x,y] * i[x,y]), you add this value to SUM and
> > SUM2
> >> >> and compute mean and variance from these.
> >> >>
> >> >> In the hypotesis of computing mean and variance of the last N images
> > you
> >> >> store in a circular queue the values of SUM and SUM2 for the last N
> > images
> >> >> and for each new image you deduct from your accumulators the SUM and
> > SUM2
> >> >> of the oldest image in the queue (this first item in the queue) and
add
> >> >> the SUM and SUM2 of the new image. You also store the SUM and SUM2
of
> >> >> the new image in your circular queue. You now can compute mean and
> >> > variance
> >> >> from your accumulators.
> >> >>
> >> >> Paolo
> >> >>
> >> >> > Let's say the statistics are measured over a width and height. Ram
> > wants
> >> > to
> >> >> > measure the whole image. I think there are basically 2 ways to get
to
> > a
> >> >> > faster calculation:
> >> >>
> >> >> > 1. Increase the calculation speed, and/or
> >> >> > 2. Reduce the sample size (number of pixels).
> >> >>
> >> >> > This leads to a few methods:
> >> >>
> >> >> > 1. Use faster and/or specialized hardware to make the
> > computation.
> >> >> > 2. Sample a subregion. Remember that computation time goes as
> > sample
> >> >> > width^2, so sampling only the central 1/2 will take about 1/4 the
> > time
> >> > to
> >> >> > calculate.
> >> >> > 3. Use a subsample---that is, fewer pixels---as being
> > representative
> >> > of
> >> >> > the entire image. This is related to option 2, except that the
pixels
> >> > might
> >> >> > be more intelligently chosen, such as in small, strategically
> > positioned
> >> >> > rectangle regions, or as spaced raster lines.
> >> >>
> >> >> > Personally, I would look carefully at item 3. Try to justlify to
> >> > yourself
> >> >> > why you need to sample *every* one of the pixels in each M x N
image.
> >> >>
> >> >> > Michael
> >> >>
> >> >> > "Vladimir Drzik" <vdrzik@nextra.sk> wrote in message
> >> >> > news:11861a3c.0406240110.5a51023@posting.google.com...
> >> >> >> ip4ram@yahoo.com wrote in message
> >> >> > news:<137664.0406230859.4ba8a7fe@posting.google.com>...
> >> >> >> > I have a series of of images(640 x 480) coming in and need to
> >> >> >> > calculate the mean and variance of R,G,B components of each
> > pixel.The
> >> >> >> > problem is
> >> >> >> >
> >> >> >> > 1. I have no way to store the sequence of images.All I am
allowed
> > to
> >> >> >> > store is mean and variance(and the number of frames,ofcourse).I
> > have
> >> >> >> > to calculate the new mean and new variance when a new data
comes
> >> >> >> > in.(New mean = (n*old_mean + new data)/(n+1)).
> >> >> >> >
> >> >> >> > 2.I derived a formula for calculating new variance,based on the
> > new
> >> >> >> > data, old mean,old variance and new mean(which can be
calculated
> > as
> >> >> >> > above).But the problem is this formula is pretty complex in
terms
> > of
> >> >> >> > multiplication(as it needs to be calculated 640 * 480 * 3
times).
> >> >> >> >
> >> >> >> > Is there any formula/mathematical approximations for new
variance
> > in
> >> >> >> > terms of old variance,old mean,new mean,and new data? i.e new
> >> > variance
> >> >> >> > = Function(old mean,old variance,new data).
> >> >> >> >
> >> >> >> > Example:
> >> >> >> > say data is 1,2,2,2,2,1,2,3. We have the old mean and old
variance
> >> >> >> > calculated for this data (n = 8).When a new data ,say 5, comes
in,
> >> > how
> >> >> >> > do we update/approximate the new variance in terms of old mean
and
> >> > old
> >> >> >> > variance(assuming we do not have access to data,since data
cannot
> > be
> >> >> >> > stored).
> >> >> >> >
> >> >> >> > Thanks in advance
> >> >> >> > Ram
> >> >> >>
> >> >> >> Hi Ram,
> >> >> >>
> >> >> >> At http://mathworld.wolfram.com/SampleVarianceComputation.html ,
> > there
> >> >> >> is the expression you want. I don't know if it's less complex
than
> > the
> >> >> >> expression you derived.
> >> >> >>
> >> >> >> However, there is another approach, which (seems to me) requires
> > less
> >> >> >> computation. Instead of storing current mean and variance, store
> > only
> >> >> >> current sum of all values (Sx) and sum of squares of all values
> > (Sxx).
> >> >> >> Then, at each moment, variance can be computed as
> >> >> >> (N*Sxx - Sx*Sx) / (N*N)
> >> >> >> where N is the number of samples. Of course, current mean can be
> >> >> >> computed as
> >> >> >> Sx / N
> >> >> >> but you don't need this value for variance computation.
> >> >> >>
> >> >> >> Regards,
> >> >> >>
> >> >> >> Vladimir
> >> >>
> >> >>
> >>
> >>
>
>
- Next message: MingChieh: "How to sort a 8-bit gray level image quickly by its gradient?"
- Previous message: Paolo Bellutta: "Re: Calculating Variance in real-time"
- In reply to: Paolo Bellutta: "Re: Calculating Variance in real-time"
- Next in thread: ip4ram_at_yahoo.com: "Re: Calculating Variance in real-time"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
