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:

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.

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

Rather than using recursion, use a stack.

Pseudo-code:

Add initial pixel to polygon
Add initial pixel to stack
while(stack is not empty) {
    pop pixel off the stack
    foreach (neighbor n of popped pixel) {
        if (n is close enough in color to initial pixel) {
            Add n to polygon
            Add n to stack
        }
    }
}

This will use a lot less memory than the same solution using recursion.

Answer 2

Have you looked at blob detection algorithms? For example, http://opencv.willowgarage.com/wiki/cvBlobsLib if you can integrate OpenCV into your application. Coupled with thresholding to create binary images for each color (or color range) in your image, you could easily find the blobs that are the same color. Repeat for each color in the image, and you have a list of blobs sorted by color.

If you cannot use OpenCV directly, perhaps the paper referenced by that library ("A linear-time component labeling algorithm using contour tracing technique", F.Chang et al.) would provide a good method for finding blobs.

Answer 3

Just send your 'Image' to BuildPixelArray function and then call the FindRegions. After that the 'colors' variable will be holding your colors list and pixel coordinates in every list member.

I've copied the source from one of my projects, there may be some undefined variables or syntax erors.

    public class ImageProcessing{
    private int[,] pixelArray;
    private int imageWidth;
    private int imageHeight;
    List<MyColor> colors;

    public void BuildPixelArray(ref Image myImage)
    {
        imageHeight = myImage.Height;
        imageWidth = myImage.Width;
        pixelArray = new int[imageWidth, imageHeight];
        Rectangle rect = new Rectangle(0, 0, myImage.Width, myImage.Height);
        Bitmap temp = new Bitmap(myImage);
        BitmapData bmpData = temp.LockBits(rect, ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
        int remain = bmpData.Stride - bmpData.Width * 3;
        unsafe
        {
            byte* ptr = (byte*)bmpData.Scan0;
            for (int j = 15; j < bmpData.Height; j++)
            {
                for (int i = 0; i < bmpData.Width; i++)
                {
                    pixelArray[i, j] = ptr[0] + ptr[1] * 256 + ptr[2] * 256 * 256;
                    ptr += 3;
                }
                ptr += remain;
            }
        }
        temp.UnlockBits(bmpData);
    }

    public void FindRegions()
    {
        colors = new List<MyColor>();

        for (int i = 0; i < imageWidth; i++)
        {
            for (int j = 0; j < imageHeight; j++)
            {
                int tmpColorValue = pixelArray[i, j];
                MyColor tmp = new MyColor(tmpColorValue);
                if (colors.Contains(tmp))
                {
                    MyColor tmpColor = (from p in colors
                                        where p.colorValue == tmpColorValue
                                        select p).First();

                    tmpColor.pointList.Add(new MyPoint(i, j));
                }
                else
                {
                    tmp.pointList.Add(new MyPoint(i, j));
                    colors.Add(tmp);
                }
            }
        }
    }
}

public class MyColor : IEquatable<MyColor>
{
    public int colorValue { get; set; }
    public List<MyPoint> pointList = new List<MyPoint>();
    public MyColor(int _colorValue)
    {
        colorValue = _colorValue;
    }
    public bool Equals(MyColor other)
    {
        if (this.colorValue == other.colorValue)
        {
            return true;
        }
        return false;
    }
}
public class MyPoint
{
    public int xCoord { get; set; }
    public int yCoord { get; set; }

    public MyPoint(int _xCoord, int _yCoord)
    {
        xCoord = _xCoord;
        yCoord = _yCoord;
    }
}

Answer 4

If you're getting a stack overflow I would guess that you're not excluding already-checked pixels. The first check on visiting a square should be whether you've been here before.

Also, I was working on a related problem not too long ago and I came up with a different approach that uses a lot less memory:

A queue:

AddPointToQueue(x, y);
repeat
   x, y = HeadItem;
   AddMaybe(x - 1, y); x + 1, y; x, y - 1; x, y + 1;
until QueueIsEmpty;

AddMaybe(x, y):
if Visited[x, y] return;
Visited[x, y] = true;
AddPointToQueue(x, y);

The point of this approach is that you end up with your queue basically holding a line wrapped around the mapped area. This limits memory usage better than a stack can.

If relevant it also can be trivially modified to yield the travel distance to any square.

Answer 5

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/

Answer 6

Try using AForge.net. I would go for Filter by colors, Threshold and then you could do some Morphology to decrement the black/White zones to lose contact between the objects. Then you could go for the Blobs.