rchann@sunee.waterloo.edu (Robert Chann) (03/20/91)
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? Thank you all in advance! Robert Chann (rchann@sunee.waterloo.edu) -- Thank you for your attention. Have a nice day! ------------------------------------------------------------------------------- Robert Chann E-mail: rchann@sunee.waterloo.edu -------------------------------------------------------------------------------
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
rick@hanauma.stanford.edu (Richard Ottolini) (03/21/91)
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.
mcmahan@netcom.COM (Dave Mc Mahan) (03/21/91)
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
spencer@eecs.umich.edu (Spencer W. Thomas) (03/21/91)
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)