Làm cách nào để phát hiện đường viền không đều trong hình ảnh?

Question

Đưa ra hình ảnh dưới đây, tôi có thể sử dụng thuật toán nào để phát hiện xem khu vực một và hai (được xác định bằng màu sắc) có đường viền không?

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

Nếu có một ví dụ C# trên mạng, đó sẽ là tuyệt vời, nhưng tôi thực sự chỉ là tìm kiếm bất kỳ mã ví dụ.

Edit: Sử dụng những lời khuyên Jaro, tôi đã đưa ra những điều sau ...

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

    // ... 
} 

Nhấp vào hai hình dạng mà làm chung đường biên giới trở lại khá nhanh chóng, nhưng khoảng cách hình dạng rất hay hình dạng với một lớn số lượng pixel mất 3+ giây ở lần. Tôi có những lựa chọn nào để tối ưu hóa điều này?

Answer 1

2 vùng có đường viền có nghĩa là trong một khu vực nhỏ nhất định phải có 3 màu hiện diện: đỏ, đen và xanh lục.

Vì vậy, một giải pháp rất không hiệu quả thể hiện chính nó: sử dụng Color pixelColor = myBitmap.GetPixel(x, y); bạn có thể quét một khu vực cho 3 màu đó. Khu vực này phải lớn hơn chiều rộng của đường viền của khóa học.

Có rất nhiều phòng để tối ưu hóa (như đi các bước 50 pixel và giảm độ chính xác liên tục). Vì màu đen là màu ít được sử dụng nhất, trước tiên bạn sẽ tìm kiếm xung quanh các vùng màu đen.

này nên giải thích những gì tôi đã viết trong ý kiến ​​khác nhau trong chủ đề này:

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

Nó rất đơn giản. Tìm kiếm theo cách này chỉ mất khoảng 2 + 4 ms (quét và tìm các điểm gần nhất).

Bạn cũng có thể thực hiện tìm kiếm đệ quy: đầu tiên với độ chính xác = 1000, sau đó độ chính xác = 100 và cuối cùng là độ chính xác = 10 cho hình ảnh lớn. FindClosestPoints thực tế sẽ cung cấp cho bạn một khu vực hình chữ nhật ước tính, nơi biên giới nên được đặt (thường là biên giới là như thế).

Sau đó, bạn có thể sử dụng phương pháp tiếp cận véc tơ mà tôi đã mô tả trong các nhận xét khác.

Answer 2

Tôi đã đọc câu hỏi của bạn khi hỏi liệu hai điểm này có tồn tại ở các vùng khác nhau hay không. Điều này có đúng không? Nếu vậy, tôi có lẽ sẽ sử dụng một biến thể của Flood Fill. Nó không phải là siêu khó thực hiện (không thực hiện nó đệ quy, bạn gần như chắc chắn sẽ chạy ra khỏi không gian ngăn xếp) và nó sẽ có thể nhìn vào các tình huống phức tạp như một khu vực hình chữ U có biên giới giữa hai điểm, nhưng không thực sự là các vùng khác nhau. Về cơ bản chạy lũ lấp đầy, và trở lại đúng khi phối hợp của bạn phù hợp với tọa độ mục tiêu (hoặc có lẽ khi nó đủ gần cho sự hài lòng của bạn, tùy thuộc vào trường hợp sử dụng của bạn)

[Edit] Đây là an example điền đầy lũ mà tôi đã viết cho dự án của tôi. Dự án được cấp phép CPAL, nhưng việc triển khai thực hiện khá cụ thể với những gì tôi sử dụng cho dù sao, vì vậy đừng lo lắng về việc sao chép các phần của nó. Và nó không sử dụng đệ quy, do đó, nó sẽ có thể mở rộng dữ liệu pixel.

[Edit2] Tôi đã hiểu nhầm công việc. Tôi không có bất kỳ mã ví dụ nào thực hiện chính xác những gì bạn đang tìm kiếm, nhưng tôi có thể nói rằng so sánh pixel trên mỗi pixel toàn bộ hai vùng không phải là thứ bạn muốn làm.Bạn có thể giảm độ phức tạp bằng cách phân vùng từng khu vực thành một lưới lớn hơn (có thể là 25x25 pixel) và so sánh các khu vực đó trước tiên và nếu bất kỳ khu vực nào đủ gần, hãy so sánh pixel/pixel ngay trong hai khu vực đó.

[Edit2.5] [Quadtree] 3 cũng có thể giúp bạn. Tôi không có nhiều kinh nghiệm với nó, nhưng tôi biết nó phổ biến trong phát hiện va chạm 2D, tương tự như những gì bạn đang làm ở đây. Có thể đáng nghiên cứu.