sbanner1@uvicctr.UUCP (S. John Banner) (07/18/87)
Hello,
I have recently been called upon to write a program that takes
a bitmap image, and converts it to a second bitmap image, such that
no two points within a given radius of each other are left on. I
have had a couple of suggestions given to me, but they all seem to
have some problems that I have knoticed (most noteably, grey scales
will get turned to "black", or "white"). What I am currently using,
is an algorithm where you read in a bunch of lines, then scan through
the image, point by point until you get to an on pixel, then blank
out everything within the given radius, and continue on. The one
other restriction on the algorithm, is that the program should not
have to read in the entire bitmap (only a small fraction of the map
will fit, I currently keep about 10 or so scan lines in memory at any
given time, though I am sure that I can fit more, but just how many
more I don't know, as the resolution may get quite high).
Thanks in advance,
S. John Banner
...!uw-beaver!uvicctr!sol!sbanner1
...!ubc-vision!uvicctr!sol!sbanner1
ccsjb@uvvm
sbanner1@sol.UVIC.CDN
PS. (and I will summarize to the net, unless there is a great out
cry not to... :-). sjbspf@clyde.UUCP (07/20/87)
In article <275@uvicctr.UUCP> sbanner1@uvicctr.UUCP (S. John Banner) writes: > > I have recently been called upon to write a program that takes >a bitmap image, and converts it to a second bitmap image, such that >no two points within a given radius of each other are left on. >... an algorithm where you read in a bunch of lines, then scan through >the image, point by point until you get to an on pixel, then blank >out everything within the given radius, and continue on. >... the program should not have to read in the entire bitmap (only a >small fraction of the map will fit...) The central problem with this approach is that you will get a different result depending upon where in the image you start and in which direction you traverse it. I don't know what you intend to do with the product, but I would think this is undesirable. If you can get enough of the image in memory to use a statistical, rather than a "first-encountered" approach, your result would be invariant under changes in starting point. Essentially, you would calculate the central pixel (suitably defined for your purposes) and then turn off any on pixels in its neighborhood. Steve Frysinger
jbm@aurora.UUCP (Jeffrey Mulligan) (07/22/87)
in article <11244@clyde.ATT.COM>, spf@moss.ATT.COM says: + + In article <275@uvicctr.UUCP> sbanner1@uvicctr.UUCP (S. John Banner) writes: +> +> I have recently been called upon to write a program that takes +>a bitmap image, and converts it to a second bitmap image, such that +>no two points within a given radius of each other are left on. +>... an algorithm where you read in a bunch of lines, then scan through +>the image, point by point until you get to an on pixel, then blank +>out everything within the given radius, and continue on. +>... the program should not have to read in the entire bitmap (only a +>small fraction of the map will fit...) + + The central problem with this approach is that you will get a + different result depending upon where in the image you start and in + which direction you traverse it. I don't know what you intend to do with + the product, but I would think this is undesirable. If you can get + enough of the image in memory to use a statistical, rather than + a "first-encountered" approach, your result would be invariant under + changes in starting point. Essentially, you would calculate the central + pixel (suitably defined for your purposes) and then turn off any on pixels + in its neighborhood. + + Steve Frysinger Both of these algorithms clip the gray scale range instead of remapping it. Let's say that you want to map white (all bits on) to 25% gray (1/4 of the bits on). Naturally black->black (no bits on). Then the problem is simply to reduce the "on" pixel density everywhere, not simply where it is greater than 1/4. Doing it this way will preserve the contrast of the original image, while reducing the luminance by a factor of four. One way to do this would be to simply scan the original image, turning "on" a pixel in the output image after encountering four "on" pixels in the input images. You could get fancy and place the new pixel at the centroid of the four original pixels, and scan the image in a way that is isotropic with respect to x and y, such as that proposed by Koenderink and Van Doorn (Proc IEEE v67 n10 p1465 1979). -- Jeff Mulligan (jbm@ames-aurora.arpa) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-5150
kent@xanth.UUCP (Kent Paul Dolan) (07/23/87)
John, Having read your original and followup posting, and several replies, I thought I'd stick my oar in, too. ;-) Back when I used to be involved with the creation of nautical charts, we worked with an 800 dots per inch laser onto film plotter, and had a similar problem, turning black areas into grey areas. Our solution depended on the original data being "blobby", rather than "speckled"; i.e., the original had no isolated dots. We used a physical solution, a half tone screen, just because it was _much_ cheaper than trying to process our data after the potential for run length coding was destroyed (our graphics format was 1.6 billion pixels, 7 bits deep, so we had a bit of a storage nightmare without run length encoding). Anyway, for your purposes, and if it is appropriate, just develop a mask pattern that achieves the separation you want, and then go through and turn all the masked out pixels to white, whatever their original color was, and only allow the data through where the mask allows. This saves lots of computation, since you don't really have to consider more than one pixel at a time. If you get in the color business later on, there is an analogous use of half tone screens for color. As I remember, the trick is to rotate the mask a number of degrees that avoids moire fringes. Consult your local tech library's color press printing literature for more detail than I am competent to give. Kent, the man from xanth.