🚀 go-pugleaf

In article <1991Mar20.003425.14767@sunee.waterloo.edu> rchann@sunee.waterloo.edu (Robert Chann) writes:
>I'm trying to implement a mean value filter.  That is, using an nxn
>window, each picture element is substituted by the mean value of the 
>(nxn) neighbouring picture elements.
>Apparently, by using a "sophisticated" implementation, no more than
>approximately two additions per pel are required for the filtering.
>The number of addition is nearly independent of the filter window
>size and no multiplication is necessary.

Simple.
Use a rolling window.  Add elements of the leading edges and subtract elements
of the trailing edges.

 In a previous article, rchann@sunee.waterloo.edu (Robert Chann) writes:
>Hi,
>
>I'm trying to implement a mean value filter.  That is, using an nxn
>window, each picture element is substituted by the mean value of the 
>(nxn) neighbouring picture elements.
>
>Apparently, by using a "sophisticated" implementation, no more than
>approximately two additions per pel are required for the filtering.
>The number of addition is nearly independent of the filter window
>size and no multiplication is necessary.
>
>Does anyone know how this "sophisticated" implementation work?

Well, I think so.  I understand 'mean' to be the 'average'.  This means that
a pel will be the 'average' of all it's neighbors.  I know how to do it with
one addition per pel, plus overhead required to get at the numeric value for
each pel.  All you have to do is add them together, and divide by the number
of pels.  This will be independent of kernal size.  Most of the overhead
you will run into will be converting whatever graphics image format into a
regular old binary value that can be summed.  This can be easy or hard, but
depends entirely on the format of your data.

Is this what you want?

>Robert Chann
>(rchann@sunee.waterloo.edu)

  -dave

-- 
Dave McMahan                            mcmahan@netcom.com
					{apple,amdahl,claris}!netcom!mcmahan

   In article <1991Mar20.003425.14767@sunee.waterloo.edu> rchann@sunee.waterloo.edu (Robert Chann) writes:
   >I'm trying to implement a mean value filter.  That is, using an nxn
   >window, each picture element is substituted by the mean value of the 
   >(nxn) neighbouring picture elements.
   >Apparently, by using a "sophisticated" implementation, no more than
   >approximately two additions per pel are required for the filtering.
   >The number of addition is nearly independent of the filter window
   >size and no multiplication is necessary.

You want to use a "summed area table".  This is described in most
standard graphics texts (the ones that deal with texture mapping,
anyway).  Briefly, given a texture T(i,j), compute 
 S(i,j) = sum(k=1..i,l=1..j,T(k,l))
Then sum(i=a..b,j=c..d,T(i,j)) = S(b,d) - S(b,c-1) - S(a-1,d) + S(a-1,b-1).

S can be efficiently computed with two additions per pixel:
for ( j = 0; j <= jmax; j++ )
	S(0,j) = 0;
for ( i = 1; i <= imax; i++ ) {
	S(i,0) = 0;
	sum = 0;
	for ( j = 1; j <= jmax; j++ ) {
		sum += T(i,j);	/* Sum is the sum of this row. */
		S(i,j) = S(i-1,j) + sum;
	}
}
--
=Spencer W. Thomas 		EECS Dept, U of Michigan, Ann Arbor, MI 48109
spencer@eecs.umich.edu		313-936-2616 (8-6 E[SD]T M-F)

In article <1991Mar20.224801.7413@leland.Stanford.EDU> rick@hanauma.stanford.edu (Richard Ottolini) writes:
>In article <1991Mar20.003425.14767@sunee.waterloo.edu> rchann@sunee.waterloo.edu (Robert Chann) writes:
>>I'm trying to implement a mean value filter.  That is, using an nxn
>>approximately two additions per pel are required for the filtering.

>Simple.
>Use a rolling window.  Add elements of the leading edges and subtract elements
>of the trailing edges.


Yes, indeed, and watch the mean value slowly diverge in some direction
or other until its uncorrelated with the actual mean value.  Now, you
might get away with this for a 512 x 512 image or so, because you won't have
too much roundoff error, but don't try it on anything much bigger.

Don't forget roundoff error!

If you do the filter recursively (and that's what you're doing), 
don't forget that it has no controllability.
-- 
       -------->From the pyrolagnic keyboard of jj@alice.att.com<--------
Copyright alice!jj 1991,  all rights reserved,  except transmission  by USENET and
like free facilities granted.  Said permission is granted only for complete copies
that include this notice.    Use on pay-for-read services specifically disallowed.