Jak wykryć nieregularne krawędzie w obrazie?

Question

Biorąc pod obraz poniżej, jakiego algorytmu mogę użyć do wykrycia, czy regiony jeden i dwa (oznaczone kolorem) mają ramkę?

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

Jeśli istnieje C# przykład tam, że byłoby super, ale ja naprawdę po prostu patrząc na dowolnym przykładzie kodu.

Edit: Korzystanie porady Jaro, w wymyśliłem Po ...

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

    // ... 
} 

kliknięcie na dwa kształty, które mają wspólnej granicy powraca dość szybko, ale bardzo kształtach odległość lub kształtach z dużym liczba pikseli zajmuje czasem 3 lub więcej sekund. Jakie mam opcje optymalizacji?

Answer 1

2 regiony posiadające granicę oznaczają, że na pewnym niewielkim obszarze powinny znajdować się 3 kolory: czerwony, czarny i zielony.

Pojawia się bardzo nieefektywne rozwiązanie: przy użyciu Color pixelColor = myBitmap.GetPixel(x, y); można skanować obszar dla tych 3 kolorów. Oczywiście obszar musi być większy niż szerokość granicy.

Jest oczywiście dużo miejsca na optymalizacje (np. Chodzenie w odstępach co 50 pikseli i ciągłe zmniejszanie dokładności). Ponieważ czarny jest najmniej używanym kolorem, najpierw należy przeszukać czarne obszary.

Należy wyjaśnić, co mam napisane w różnych uwag w tym temacie:

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

To bardzo proste. Wyszukiwanie w ten sposób zajmuje tylko około 2 + 4 ms (skanowanie i znajdowanie najbliższych punktów).

Można również przeprowadzić rekursywne wyszukiwanie: najpierw z dokładnością = 1000, następnie dokładnością = 100 i ostatecznie precyzją = 10 dla dużych obrazów. FindClosestPoints praktycznie poda szacunkowy obszar prostokątny, w którym powinna się znajdować granica (zazwyczaj są to granice).

Następnie można zastosować podejście wektorowe, które opisałem w innych komentarzach.

Answer 2

Czytam twoje pytanie, pytając, czy te dwa punkty istnieją w różnych regionach. Czy to jest poprawne? Jeśli tak, prawdopodobnie użyłbym wersji Flood Fill. Nie jest to trudne do zaimplementowania (nie rekurencyjnie, prawie na pewno zabraknie miejsca na stosie) i będzie w stanie spojrzeć na złożone sytuacje, takie jak region w kształcie litery U, który ma granicę między dwoma punktami, , ale w rzeczywistości nie są to różne regiony. Zasadniczo uruchom wypełnienie powodziowe i sprawdź, czy współrzędne odpowiadają docelowej współrzędnej (lub, gdy jest wystarczająco blisko, by zadowolić twoją satysfakcję, w zależności od przypadku użycia).

[Edytuj] Oto an example wypełnienia powodzi, które napisałem dla mój projekt. Projekt jest objęty licencją CPAL, ale implementacja jest dość specyficzna dla tego, z czego go używam, więc nie martw się o kopiowanie jego części. I nie używa rekursji, więc powinna być w stanie skalować do danych pikseli.

[Edytuj2] źle zrozumiałem zadanie. Nie mam przykładowego kodu, który spełnia dokładnie to, czego szukasz, ale mogę powiedzieć, że porównywanie pikseli na piksel w dwóch regionach nie jest czymś, co chcesz zrobić.Możesz zmniejszyć złożoność, dzieląc każdy region na większą (może 25x25 pikseli) i porównując najpierw te sektory, a jeśli któryś z nich jest wystarczająco blisko, wykonaj porównanie pikseli w pikselach w obrębie tych dwóch sektorów.

[Edytuj 2.5] [Quadtree] 3 może być w stanie Ci pomóc. Nie mam z tym dużego doświadczenia, ale wiem, że jest popularny w wykrywaniu kolizji 2D, który jest podobny do tego, co tu robisz. Może warto się czegoś dowiedzieć.