[uw.cgl] Mean Value Filter

megauthi@watcgl.waterloo.edu (Marc E. Gauthier) (03/21/91)

In article <1991Mar20.003336.14691@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.
>Does anyone know how this "sophisticated" implementation work?
	Thinking about it for a few minutes, you can figure out a very
	simple way to do this, but what I've come up with requires
	approximately 2 additions, 2 subtractions, and 1 scaling,
	per pixel.
	First apply along one dimension (say, X); compute the sum (not
	necessarily the mean; just add up n pixels) for the first pixel
	(I will skip over how you handle edges; you could define pixels
	outside the picture as 0 valued), then for each successive pixel
	across the line, all you have to do is add the value of the pixel
	which enters the window, and subtract the value of the pixel which
	exits the window (in effect, a "sliding" window).  Then simply
	repeat for the other dimension (Y); it's easy to verify that what
	you will get for each pixel is the sum of all pixels in the n x n
	window that surrounds it (if you start adding at the right place);
	now all you have to do is scale these values (divide by nxn).
	If nxn is a power of 2 (e.g. a window of 16x16), then scaling is
	very cheap, since for integers you can shift the bits, and for
	floats you adjust the exponent.  (If you use integers you might
	want to scale more often to keep numbers within your integers'

	If you find a way to do it with 2 ops per pixels (!), please post.

>Thank you all in advance!
>Robert Chann

Marc E. Gauthier   megauthier@watcgl.waterloo.edu   University of Waterloo		    885-1211 x3469 or x4548