Как определить нерегулярные границы изображения?

Question

Учитывая изображение ниже, какой алгоритм я могу использовать, чтобы определить, имеют ли регионы один и два (обозначены цветом) границу?

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

Если есть # пример C там, что было бы удивительным, но я на самом деле просто ищет любой пример кода.

Edit: Используя советы Яро, я придумал следующее ...

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

    // ... 
} 

Кликнув на две формы, которые действительно разделяют границы возвращается довольно быстро, но очень формы расстояния или формы с большим количество пикселей занимает 3+ секунды. Какие параметры у меня есть для оптимизации этого?

Answer 1

2 региона с границей означает, что в пределах небольшой площади должно быть 3 цвета: красный, черный и зеленый.

Так что очень неэффективное решение представляет собой: с использованием Color pixelColor = myBitmap.GetPixel(x, y); вы можете отсканировать область для этих трех цветов. Площадь, конечно, должна быть больше ширины границы.

Существует, конечно, множество возможностей для оптимизации (например, переход на 50 пикселей и постоянное снижение точности). Поскольку черный цвет является наименее используемым, сначала вы будете искать вокруг черных областей.

Это должно объяснить, что я написал в различных комментариях в этой теме:

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

Это очень просто. Поиск этого способа занимает всего около 2 + 4 мс (сканирование и поиск ближайших точек).

Вы также можете выполнить поиск рекурсивно: сначала с точностью = 1000, затем точность = 100 и, наконец, точность = 10 для больших изображений. FindClosestPoints практически даст вам приблизительную прямоугольную область, где должна быть расположена граница (обычно это границы).

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

Answer 2

Я прочитал ваш вопрос, спрашивая, существуют ли две точки в разных регионах. Это верно? Если это так, я бы, вероятно, использовал вариант Flood Fill. Это не очень сложно реализовать (не реализуйте его рекурсивно, вы почти наверняка исчерпаете пространство стека), и он сможет смотреть на сложные ситуации, такие как U-образная область с границей между двумя точками, но на самом деле не разные регионы. В основном выполняйте заливку заливки и возвращайте true, когда ваша координата соответствует целевой координате (или, возможно, когда она достаточно близко для вашего удовлетворения, в зависимости от вашего варианта использования)

[Изменить] Вот an example3 заливной заливки, которую я написал для мой проект. Проект имеет лицензию CPAL, но реализация довольно специфична для того, что я использую в любом случае, поэтому не беспокойтесь о ее копировании. И он не использует рекурсию, поэтому он должен иметь возможность масштабировать данные пикселей.

[Edit2] Я неправильно понял задачу. У меня нет кода примера, который делает именно то, что вы ищете, но я могу сказать, что сравнение пиксельных пикселей для всех двух регионов - это не то, что вы хотите сделать.Вы можете уменьшить сложность, разбив каждый регион на большую сетку (возможно, 25x25 пикселей) и сначала сравнив эти сектора, а если кто-либо из них достаточно близко, сравните пиксельные пиксели только в этих двух секторах.

[Edit2.5] [Quadtree] 3 может помочь вам. У меня нет большого опыта в этом, но я знаю, что он популярен в 2D-обнаружении столкновения, который похож на то, что вы здесь делаете. Возможно, стоит исследовать.