Algoritmo para encontrar una región pintada en un lienzo

Question

Actualización: Estoy tratando de sacar un poco de desorden de esta publicación y resumirlo de manera más concisa. Por favor vea la edición original si es necesario.

Actualmente estoy intentando rastrear una serie de blobs de un solo color en un lienzo de mapa de bits.

p. Un ejemplo del mapa de bits que estoy tratando de traza se vería como la siguiente: alt text http://www.refuctored.com/polygons.bmp

Después de trazar con éxito los contornos de las 3 manchas en la imagen, me gustaría tener una clase que tenía el color de una burbuja atada a una lista de puntos que representa el contorno del blob (no todos los píxeles dentro de los blobs).

El problema con el que me estoy encontrando es la lógica en los casos en que un píxel vecino no tiene píxeles circundantes distintos del píxel anterior.

e.g El ejemplo superior trazaría bien, pero el segundo fallaría porque el píxel no tiene dónde ir ya que los píxeles anteriores ya se han utilizado.

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

Estoy de Rastreo de izquierda a derecha y de arriba a abajo, favoreciendo ángulos diagonales sobre ángulos rectos. Debo poder volver a dibujar una copia exacta de la región en función de los datos que extraigo, por lo que los píxeles de la lista deben estar en el orden correcto para que la copia funcione.

Hasta ahora, mi intento ha estado plagado de fallas, y un par de días de jalarme tratando de volver a escribir los algoritmos un poco diferentes cada vez para resolver el problema. Hasta ahora no he tenido éxito. ¿Alguien más tuvo un problema similar al mío que tiene un buen algoritmo para encontrar los bordes?

Answer 1

Un truco sencillo para evitar estos callejones sin salida es duplicar el tamaño de la imagen que desea rastrear utilizando un algoritmo de escalamiento vecino más cercano antes de rastrearlo. De esa manera, nunca obtendrás tiras individuales.

La alternativa es utilizar un algoritmo de cuadrados de marcha - pero parece que todavía tienen uno o dos casos en los que se produce un error: http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/

Answer 2

En lugar de utilizar recursion, use una pila.

Pseudo-código:

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

Esto utilizará mucho menos memoria que la misma solución utilizando la recursividad.

Answer 3

¿Has mirado los algoritmos de detección de blobs? Por ejemplo, http://opencv.willowgarage.com/wiki/cvBlobsLib si puede integrar OpenCV en su aplicación. Junto con el umbral para crear imágenes binarias para cada color (o rango de color) en su imagen, puede encontrar fácilmente los blobs que son del mismo color. Repita para cada color en la imagen, y tiene una lista de blobs ordenados por color. Si no puede usar OpenCV directamente, tal vez el documento al que hace referencia esa biblioteca ("Algoritmo de etiquetado de componentes de tiempo lineal utilizando la técnica de seguimiento de contorno", F.Chang et al.) Proporcionaría un buen método para encontrar blobs.

Answer 4

Simplemente envíe su 'Imagen' a la función BuildPixelArray y luego llame a FindRegions. Después de eso, la variable 'colores' mantendrá su lista de colores y las coordenadas de píxeles en cada miembro de la lista.

He copiado la fuente de uno de mis proyectos, puede haber algunas variables indefinidas o errores de sintaxis.

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

Si obtiene un desbordamiento de pila supongo que no está excluyendo los píxeles ya controlados.El primer control al visitar una plaza debe ser si ya has estado aquí antes.

Además, yo estaba trabajando en un problema relacionado no hace mucho tiempo y me encontré con un enfoque diferente que utiliza mucha menos memoria:

Una cola:

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

El punto de este enfoque es que terminas con tu cola básicamente sosteniendo una línea alrededor del área asignada. Esto limita el uso de memoria mejor que una pila.

Si es relevante, también se puede modificar trivialmente para obtener la distancia de recorrido a cualquier cuadrado.

Answer 6

Intente utilizar AForge.net. Yo elegiría Filtrar por colores, Umbral y luego podría hacer algo de Morfología para disminuir las zonas negras/blancas para perder el contacto entre los objetos. Entonces podrías ir por los Blobs.