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 -------------------------------------------------------------------------------
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)
jj@alice.att.com (jj, like it or not) (03/22/91)
In article <1991Mar20.224801.7413@leland.Stanford.EDU> rick@hanauma.stanford.edu (Richard Ottolini) writes: >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 >>approximately two additions per pel are required for the filtering. >Simple. >Use a rolling window. Add elements of the leading edges and subtract elements >of the trailing edges. Yes, indeed, and watch the mean value slowly diverge in some direction or other until its uncorrelated with the actual mean value. Now, you might get away with this for a 512 x 512 image or so, because you won't have too much roundoff error, but don't try it on anything much bigger. Don't forget roundoff error! If you do the filter recursively (and that's what you're doing), don't forget that it has no controllability. -- -------->From the pyrolagnic keyboard of jj@alice.att.com<-------- Copyright alice!jj 1991, all rights reserved, except transmission by USENET and like free facilities granted. Said permission is granted only for complete copies that include this notice. Use on pay-for-read services specifically disallowed.