🚀 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.

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)