Алгоритм поиска окрашенной области на холсте

Question

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

В настоящее время я пытаюсь проследить серию одиночных цветных капель на холсте растровых изображений.

например. Пример растрового изображения я пытающийся след будет выглядеть следующим образом: alt text http://www.refuctored.com/polygons.bmp

После успешного прослеживая очертания 3 капли на изображении, я бы класс, который держал цвет сгустка, привязанный к список точек, представляющий контур blob (не все пиксели внутри капли).

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

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

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

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

До сих пор моя попытка была пронизана провалом, и пару дней вытягивали мои волосы, пытаясь переписать алгоритмы немного по-разному каждый раз, чтобы решить проблему. До сих пор я не увенчался успехом. Кто-нибудь еще имел подобную проблему, такую ​​как моя, у которой есть хороший алгоритм для поиска краев?

Answer 1

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

Альтернативой является использование алгоритма марширующих квадратов - но это, кажется, еще один или два случая, когда он терпит неудачу: http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/

Answer 2

Вместо использования рекурсии используйте стек.

Псевдо-код:

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

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

Answer 3

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

Если вы не можете использовать OpenCV напрямую, возможно, документ, на который ссылается эта библиотека («Алгоритм подписи по методу линейного времени, использующий технологию трассировки контуров», F.Chang и др.), Обеспечит хороший метод поиска капли.

Answer 4

Просто отправьте свое «изображение» в функцию 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; 
    } 
} 

Answer 5

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

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

Очередь:

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

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

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

Answer 6

Попробуйте использовать AForge.net. Я бы пошел на Фильтр по цветам, Порог, а затем вы могли бы сделать некоторую морфологию, чтобы уменьшить черные/белые зоны, чтобы потерять контакт между объектами. Тогда вы могли бы пойти на Blobs.