Algorithm - Monochrome Bitmap Outline

I'm looking for an algorithm to draw the outline of a monochrome bitmap.  I have come up with a fairly decent algorithm myself and could keep refining it, but I was wondering if there are any algorithms (or code samples) for this sort of thing that I'm not aware of but should be before I continue to refine mine.

Basically I'm using a simple scanline algorithm and need to figure out a way to get square corners.  I'm thinking that I need to scan the bitmap a different way, I probably need to do something like look at the pixels ahead and to the top and bottom to determine if I need to set a pixel at a "corner", unfortunately I don't believe it's that simple.

Given this:

000000
001100
001100
000000

This is what I get:

001100
010010
010010
001100

This is what I should get:

011110
010010
010010
011110

Any help (i.e. thinking outside the box) is appreciated.

Dave B.
Thursday, March 18, 2004

This is actually very simple.

a) Dilate the image
b) Subtract the original image from the dilated image

Your mileage may very depending on the dilate algorithm used.

Elephant
Thursday, March 18, 2004

Are you trying to do something like auto crop?

Li-fan Chen
Thursday, March 18, 2004

I hope they aren't.  You can get bounding boxes much easier than outlining an image to get it's size/dimensions.

Elephant
Thursday, March 18, 2004

I'll look into dilating the bitmap.

No, I'm not doing anything with auto-cropping or bounding boxes.

Dave B.
Thursday, March 18, 2004

Hi Dave,

It's been a loooong time since Image Processing 101, but I believe that you're looking for 'Image masks' (if memory serves correctly).
You create a new image by considering a region (usually 3x3) around the location of each old pixel, and taking a weighted average of the pixel values to obtain the value of the new pixel.
Example:
Old image has pixels with values
a b c
d e f
g h i

The 'mask' we will be using looks like this:
1/8 1/8 1/8
1/8  0  1/8
1/8 1/8 1/8

The new value of the pixel at 'e' will be
a/8 + b/8 + c/8 + ... + i/8

Different types of 'masks' allow you to define different types of processing (vertical edge detection, blur, remove specks, etc).
The 1/8 factor is there for 'normalization': a mask should not darken or brighten the total image.

Google search for 'image mask array' for ideas.

Yves
Friday, March 19, 2004

If my aforementioned method doesn't work, you could try:

a) invert
b) erode
c) invert
d) subtract original image

Elephant
Friday, March 19, 2004

If a pixel is 0 and any of its neibours is 1
then set corresponding pixel in the new image to 1
else set corresponding pixel in the new image to 0

Just me (Sir to you)
Friday, March 19, 2004

After all those suggestions, I can only add "nick someone else's code off the web". Re-use, re-use, re-use.

Friday, March 19, 2004

I second Yves's suggestion.  I've only barely dabbled in those kinds of image transforms, but they're real easy to use once they click.

Brian
Friday, March 19, 2004

  Recent Topics

  Fog Creek Home