Algorithm for finding a painted region on a canvas

Question

Update: I am attempting to pull a little clutter out of this post and sum it up more concisely. Please see the original edit if needed.

I am currently attempting to trace a series of single colored blobs on a Bitmap canvas.

e.g. An example of the bitmap I am attempting to trace would look like the following: alt text http://www.refuctored.com/polygons.bmp

After successfully tracing the outlines of the 3 blobs on the image, I would have a class that held the color of a blob tied to a point list representing the outline of the blob (not all the pixels inside of the blobs).

The problem I am running into is logic in instances where a neighboring pixel has no surrounding pixels other than the previous pixel.

e.g The top example would trace fine, but the second would fail because the pixel has no where to go since the previous pixels have already been used.

alt text http://www.refuctored.com/error.jpg

I am tracing left-to-right, top-to-bottom, favoring diagonal angles over right angles. I must be able to redraw an exact copy of the region based off the data I extract, so the pixels in the list must be in the right order for the copy to work.

Thus far, my attempt has been riddled with failure, and a couple days of pulling my hair out trying to rewrite the algorithms a little different each time to solve the issue. Thus far I have been unsuccessful. Has anyone else had a similar issue like mine who has a good algorithm to find the edges?

Answer 1

One simple trick to avoiding these cul-de-sacs is to double the size of the image you want to trace using a nearest neighbor scaling algorithm before tracing it. Like that you will never get single strips.

The alternative is to use a marching squares algorithm - but it seems to still have one or two cases where it fails: http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/