¿Cómo puedo detectar bordes irregulares en una imagen?

Question

Dada la imagen a continuación, ¿qué algoritmo podría usar para detectar si las regiones uno y dos (identificadas por el color) tienen un borde?

http://img823.imageshack.us/img823/4477/borders.png

Si hay un ejemplo # C por ahí, que sería impresionante, pero estoy realmente sólo en busca de cualquier código de ejemplo.

Editar: Consejo de utilización de Jaro, me ocurrió lo siguiente ...

public class Shape 
{ 
    private const int MAX_BORDER_DISTANCE = 15; 

    public List<Point> Pixels { get; set; } 

    public Shape() 
    { 
     Pixels = new List<Point>(); 
    } 

    public bool SharesBorder(Shape other) 
    { 
     var shape1 = this; 
     var shape2 = other; 

     foreach (var pixel1 in shape1.Pixels) 
     { 
      foreach (var pixel2 in shape2.Pixels) 
      { 
       var xDistance = Math.Abs(pixel1.X - pixel2.X); 
       var yDistance = Math.Abs(pixel1.Y - pixel2.Y); 

       if (xDistance > 1 && yDistance > 1) 
       { 
        if (xDistance * yDistance < MAX_BORDER_DISTANCE) 
         return true; 
       } 
       else 
       { 
        if (xDistance < Math.Sqrt(MAX_BORDER_DISTANCE) && 
         yDistance < Math.Sqrt(MAX_BORDER_DISTANCE)) 
         return true; 
       } 
      } 
     } 

     return false; 
    } 

    // ... 
} 

Al hacer clic en dos formas que comparten una frontera vuelve bastante rápido, pero muy distantes formas o formas con una gran el número de píxeles toma 3+ segundos a veces. ¿Qué opciones tengo para optimizar esto?

Answer 1

2 regiones que tienen borde significa que dentro de una cierta área pequeña debe haber 3 colores presentes: rojo, negro y verde.

De modo que se presenta una solución muy ineficaz: usando Color pixelColor = myBitmap.GetPixel(x, y); puede escanear un área para esos 3 colores. El área debe ser más grande que el ancho del borde, por supuesto.

Por supuesto, hay mucho espacio para optimizaciones (como ir en pasos de 50 píxeles y disminuir la precisión continuamente). Como el negro es el color menos usado, primero debe buscar en las áreas negras.

Esto debe explicar lo que he escrito en varios comentarios en este tema:

namespace Phobos.Graphics 
{ 
    public class BorderDetector 
    { 
     private Color region1Color = Color.FromArgb(222, 22, 46); 
     private Color region2Color = Color.FromArgb(11, 189, 63); 
     private Color borderColor = Color.FromArgb(11, 189, 63); 

     private List<Point> region1Points = new List<Point>(); 
     private List<Point> region2Points = new List<Point>(); 
     private List<Point> borderPoints = new List<Point>(); 

     private Bitmap b; 

     private const int precision = 10; 
     private const int distanceTreshold = 25; 

     public long Miliseconds1 { get; set; } 
     public long Miliseconds2 { get; set; } 

     public BorderDetector(Bitmap b) 
     { 
      if (b == null) throw new ArgumentNullException("b"); 

      this.b = b; 
     } 

     private void ScanBitmap() 
     { 
      Color c; 

      for (int x = precision; x < this.b.Width; x += BorderDetector.precision) 
      { 
       for (int y = precision; y < this.b.Height; y += BorderDetector.precision) 
       { 
        c = this.b.GetPixel(x, y); 

        if (c == region1Color) region1Points.Add(new Point(x, y)); 
        else if (c == region2Color) region2Points.Add(new Point(x, y)); 
        else if (c == borderColor) borderPoints.Add(new Point(x, y)); 
       } 
      } 
     } 

     /// <summary>Returns a distance of two points (inaccurate but very fast).</summary> 
     private int GetDistance(Point p1, Point p2) 
     { 
      return Math.Abs(p1.X - p2.X) + Math.Abs(p1.Y - p2.Y); 
     } 

     /// <summary>Finds the closests 2 points among the points in the 2 sets.</summary> 
     private int FindClosestPoints(List<Point> r1Points, List<Point> r2Points, out Point foundR1, out Point foundR2) 
     { 
      int minDistance = Int32.MaxValue; 
      int distance = 0; 

      foundR1 = Point.Empty; 
      foundR2 = Point.Empty; 

      foreach (Point r1 in r1Points) 
       foreach (Point r2 in r2Points) 
       { 
        distance = this.GetDistance(r1, r2); 

        if (distance < minDistance) 
        { 
         foundR1 = r1; 
         foundR2 = r2; 
         minDistance = distance; 
        } 
       } 

      return minDistance; 
     } 

     public bool FindBorder() 
     { 
      Point r1; 
      Point r2; 

      Stopwatch watch = new Stopwatch(); 

      watch.Start(); 
      this.ScanBitmap(); 
      watch.Stop(); 
      this.Miliseconds1 = watch.ElapsedMilliseconds; 

      watch.Start(); 
      int distance = this.FindClosestPoints(this.region1Points, this.region2Points, out r1, out r2); 
      watch.Stop(); 
      this.Miliseconds2 = watch.ElapsedMilliseconds; 

      this.b.SetPixel(r1.X, r1.Y, Color.Green); 
      this.b.SetPixel(r2.X, r2.Y, Color.Red); 

      return (distance <= BorderDetector.distanceTreshold); 
     } 
    } 
} 

Es muy simple. La búsqueda de esta manera solo toma aproximadamente 2 + 4 ms (escaneando y buscando los puntos más cercanos).

También puede hacer la búsqueda recursivamente: primero con precisión = 1000, luego precisión = 100 y finalmente precisión = 10 para imágenes grandes. FindClosestPoints prácticamente le dará un área rectangular estimada donde el borde debe estar situado (generalmente los bordes son así).

Entonces podría utilizar el enfoque vectorial que he descrito en otros comentarios.

Answer 2

Leí su pregunta preguntando si los dos puntos existen en diferentes regiones. ¿Es esto correcto? Si es así, probablemente usaría una variación de Flood Fill. No es superdifícil de implementar (no lo implemente recursivamente, seguramente se quedará sin espacio en la pila) y podrá ver situaciones complejas como una región en forma de U que tiene un borde entre dos puntos, pero en realidad no son regiones diferentes. Básicamente ejecute relleno de inundación y devuelva verdadero cuando su coordenada coincida con la coordenada objetivo (o tal vez cuando esté lo suficientemente cerca para su satisfacción, según su caso de uso)

[Editar] Aquí está an example de relleno de inundación que escribí para un proyecto mío El proyecto tiene licencia de CPAL, pero la implementación es bastante específica para lo que yo uso de todos modos, así que no se preocupe por copiar partes de él. Y no usa recursividad, por lo que debería poder escalar a datos de píxeles.

[Editar2] He entendido mal la tarea. No tengo ningún código de ejemplo que haga exactamente lo que estás buscando, pero puedo decir que comparar las dos regiones por pixel por píxel no es algo que quieras hacer.Puede reducir la complejidad dividiendo cada región en una cuadrícula más grande (quizás 25x25 píxeles) y comparando primero esos sectores, y si alguno de ellos está lo suficientemente cerca, haga una comparación de píxel por píxel solo dentro de esos dos sectores.

[Editar2.5] [Quadtree] 3 podría ser capaz de ayudarlo también. No tengo mucha experiencia con eso, pero sé que es popular en la detección de colisiones 2D, que es similar a lo que estás haciendo aquí. Puede valer la pena investigar.