Come posso rilevare i bordi irregolari in un'immagine?

Question

Data l'immagine in basso, quale algoritmo posso utilizzare per rilevare se le regioni 1 e 2 (identificate dal colore) hanno un bordo?

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

Se c'è un esempio # C là fuori, che sarebbe terribile, ma sono davvero solo in cerca di qualsiasi codice di esempio.

Edit: Usando il consiglio di Jaro, mi si avvicinò con il seguente ...

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

    // ... 
} 

clic su due forme che condividono una frontiera ritorna abbastanza rapidamente, ma forme molto a distanza o forme con una grande il numero di pixel richiede 3+ secondi a volte. Che opzioni ho per l'ottimizzazione di questo?

Answer 1

2 regioni con bordo indica che all'interno di una determinata area piccola devono essere presenti 3 colori: rosso, nero e verde.

Quindi una soluzione molto inefficace si presenta: utilizzando Color pixelColor = myBitmap.GetPixel(x, y); è possibile eseguire la scansione di un'area per quei 3 colori. L'area deve essere più larga della larghezza del bordo, naturalmente.

C'è ovviamente molto spazio per le ottimizzazioni (come andare avanti con incrementi di 50 pixel e diminuire continuamente la precisione). Poiché il nero è il colore meno utilizzato, cercherete prima nelle aree nere.

Questo dovrebbe spiegare quello che ho scritto in vari commenti in questo argomento:

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

E 'molto semplice. La ricerca in questo modo richiede circa 2 + 4 ms (scansione e ricerca dei punti più vicini).

Si potrebbe anche eseguire la ricerca in modo ricorsivo: prima con precisione = 1000, quindi precisione = 100 e infine precisione = 10 per immagini di grandi dimensioni. FindClosestPoints ti darà praticamente una zona rettangolare stimata in cui posizionare il bordo (di solito i bordi sono così).

Quindi è possibile utilizzare l'approccio vettoriale che ho descritto in altri commenti.

Answer 2

Ho letto la domanda chiedendo se i due punti esistono in diverse regioni. È corretto? In tal caso, probabilmente utilizzerei una variazione di Flood Fill. Non è molto difficile da implementare (non implementarlo ricorsivamente, quasi sicuramente a corto di spazio nello stack) e sarà in grado di guardare a situazioni complesse come una regione a forma di U che ha un bordo tra due punti, ma non sono in realtà regioni diverse. In pratica, esegui flood fill e restituisci true quando le tue coordinate corrispondono alla coordinata target (o forse quando è abbastanza vicino per la tua soddisfazione, a seconda del tuo caso d'uso)

[Modifica] Ecco an example di riempimento di piena che ho scritto per un mio progetto. Il progetto è concesso in licenza CPAL, ma l'implementazione è piuttosto specifica per quello che uso comunque, quindi non preoccuparti di copiarne parti. E non usa la ricorsione, quindi dovrebbe essere in grado di ridimensionare i dati dei pixel.

[Modifica2] Ho frainteso il compito. Non ho alcun codice di esempio che faccia esattamente quello che stai cercando, ma posso dire che confrontare i pixel per pixel delle due regioni non è qualcosa che vuoi fare.Puoi ridurre la complessità suddividendo ciascuna regione in una griglia più grande (forse 25x25 pixel) e confrontando prima quei settori, e se qualcuno di questi è abbastanza vicino, fai un confronto pixel per pixel solo all'interno di questi due settori.

[Modifica2.5] [Quadtree] 3 potrebbe essere in grado di aiutare anche voi. Non ho molta esperienza con esso, ma so che è popolare nel rilevamento delle collisioni 2D, che è simile a quello che stai facendo qui. Potrebbe valere la pena di ricercare.