Алгоритм для нахождения нарисованного региона на холсте

Вместо того чтобы использовать рекурсию, используйте стек.

Псевдокод:

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
        }
    }
}

Это будет использовать гораздо меньше памяти, чем то же решение с использованием рекурсии.

Рассматривали ли вы алгоритмы обнаружения блобов? Например, http://opencv.willowgarage.com/wiki/cvBlobsLib если вы можете интегрировать OpenCV в свое приложение. В сочетании с пороговой фильтрацией для создания бинарных изображений для каждого цвета (или цветового диапазона) в вашем изображении, вы могли бы легко найти сгустки, которые имеют одинаковый цвет. Повторите процедуру для каждого цвета в изображении, и вы получите список пятен, отсортированных по цвету.

Если вы не можете использовать OpenCV напрямую, возможно, статья, на которую ссылается эта библиотека ("A linear-time component labeling algorithm using contour tracing technique", F.Chang et al.), предоставит хороший метод для поиска пятен.

Просто отправьте ваше 'Image' в функцию BuildPixelArray, а затем вызовите FindRegions. После этого переменная 'colors' будет содержать список ваших цветов и координаты пикселей в каждом члене списка.

Я скопировал исходник из одного из моих проектов, здесь могут быть некоторые неопределенные переменные или синтаксические ошибки.

    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;
    }
}

Если вы получаете переполнение стека, я бы предположил, что вы не исключаете уже проверенные пиксели. При посещении площади в первую очередь следует проверить, бывали ли вы здесь раньше.

Кроме того, я не так давно работал над связанной проблемой, и я придумал другой подход, который использует намного меньше памяти:

Очередь:

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);

Суть этого подхода в том, что вы в конечном итоге ваша очередь в основном содержит линию, обернутую вокруг отображаемой области. Это ограничивает использование памяти лучше, чем стек.

Если необходимо, его также можно тривиально изменить, чтобы получить расстояние перемещения до любого квадрата.