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' range.) If you find a way to do it with 2 ops per pixels (!), please post. >Thank you all in advance! > >Robert Chann >(rchann@sunee.waterloo.edu) -Marc -- Marc E. Gauthier megauthier@watcgl.waterloo.edu University of Waterloo 129.97.128.64 885-1211 x3469 or x4548