Xref: utzoo comp.dsp:1449 comp.graphics:16755
Newsgroups: comp.dsp,comp.graphics
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!caen!news.cs.indiana.edu!msi.umn.edu!umeecs!zip!spencer
From: spencer@eecs.umich.edu (Spencer W. Thomas)
Subject: Re: Mean Value Filter
In-Reply-To: rick@hanauma.stanford.edu's message of 20 Mar 91 22:48:01 GMT
Message-ID: <SPENCER.91Mar21113139@spline.eecs.umich.edu>
Sender: news@zip.eecs.umich.edu
Organization: University of Michigan EECS Dept
References: <1991Mar20.003425.14767@sunee.waterloo.edu>
	<1991Mar20.224801.7413@leland.Stanford.EDU>
Date: 21 Mar 91 11:31:39

   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)