Find khu vực nhất định một tập hợp các điểm

Question

Cho một danh sách các x, tọa độ y và chiều rộng được biết đến & chiều cao như thế nào có thể các SỐ của vùng kín được xác định (trong C#)?

Ví dụ:

Trong hình ảnh này 5 vùng kín được định nghĩa:

1. khuôn mặt (1)
2. Eyes (2)
3. Nose (1)
4. phải của khuôn mặt (1)

Danh mục x, y điểm sẽ là bất kỳ điểm ảnh màu đen, kể cả miệng.

Answer 1

Bạn có thể sử dụng thuật toán đơn giản này, dựa trên ý tưởng của lũ đầy helper bitmap:

// backColor is an INT representation of color at fillPoint in the beginning. 
// result in pixels of enclosed shape. 
private int GetFillSize(Bitmap b, Point fillPoint) 
{ 
    int count = 0; 
    Point p; 
    Stack pixels = new Stack(); 
    var backColor = b.GetPixel(fillPoint.X, fillPoint.Y); 
    pixels.Push(fillPoint); 
    while (pixels.Count != 0) 
    { 
     count++; 

     p = (Point)pixels.Pop(); 
     b.SetPixel(p.X, p.Y, backColor); 

     if (b.GetPixel(p.X - 1, p.Y).ToArgb() == backColor) 
      pixels.Push(new Point(p.X - 1, p.Y)); 

     if (b.GetPixel(p.X, p.Y - 1).ToArgb() == backColor) 
      pixels.Push(new Point(p.X, p.Y - 1)); 

     if (b.GetPixel(p.X + 1, p.Y).ToArgb() == backColor) 
      pixels.Push(new Point(p.X + 1, p.Y)); 

     if (b.GetPixel(p.X, p.Y + 1).ToArgb() == backColor) 
      pixels.Push(new Point(p.X, p.Y + 1)); 
    } 

    return count; 
} 

CẬP NHẬT

Đoạn mã trên chỉ hoạt động này vùng kín quadruply liên kết. Đoạn mã sau hoạt động với các vùng kín được liên kết octuply.

// offset points initialization. 
Point[] Offsets = new Point[] 
{ 
    new Point(-1, -1), 
    new Point(-0, -1), 
    new Point(+1, -1), 
    new Point(+1, -0), 
    new Point(+1, +1), 
    new Point(+0, +1), 
    new Point(-1, +1), 
    new Point(-1, +0), 
}; 

... 

private int Fill(Bitmap b, Point fillPoint) 
{ 
    int count = 0; 
    Point p; 
    Stack<Point> pixels = new Stack<Point>(); 
    var backColor = b.GetPixel(fillPoint.X, fillPoint.Y).ToArgb(); 
    pixels.Push(fillPoint); 
    while (pixels.Count != 0) 
    { 
     count++; 

     p = (Point)pixels.Pop(); 
     b.SetPixel(p.X, p.Y, Color.FromArgb(backColor)); 

     foreach (var offset in Offsets) 
      if (b.GetPixel(p.X + offset.X, p.Y + offset.Y).ToArgb() == backColor) 
       pixels.Push(new Point(p.X + offset.X, p.Y + offset.Y)); 
    } 

    return count; 
} 

Hình ảnh bên dưới minh họa rõ ràng ý tôi. Ngoài ra người ta có thể thêm nhiều điểm xa hơn để bù đắp mảng để có thể lấp đầy các khu vực bằng khoảng trống.

Answer 2

Có một vài trường hợp đặc biệt trong hình ảnh mẫu. Bạn sẽ phải quyết định làm thế nào để đối phó với họ.

Nói chung, bạn sẽ bắt đầu bằng cách chuyển đổi hình ảnh raster thành một loạt các đa giác. Sau đó, nó là một vấn đề khá tầm thường để tính toán diện tích (Xem bình luận của Servy)

Các trường hợp đặc biệt sẽ là mặt của khuôn mặt và miệng. Cả hai đều là hình dạng mở, không đóng. Bạn cần phải tìm ra cách để đóng chúng lại.

Answer 3

Tôi đã thành công lớn khi sử dụng OpenCV. Có một thư viện cho .net gọi Emgu CV

Dưới đây là một câu hỏi bao gồm thay thế cho Emgu CV: .Net (dotNet) wrappers for OpenCV?

thư viện đó chứa các chức năng để xác định đường nét và tìm kiếm các thuộc tính về họ. Bạn có thể tìm kiếm cvContourArea để tìm thêm thông tin.

Nếu bạn đang tìm kiếm giải pháp nhanh cho vấn đề cụ thể này và muốn viết mã của riêng bạn thay vì sử dụng lại mã khác, tôi không có thuật toán tôi có thể làm điều đó. Lấy làm tiếc.

Answer 4

Tôi nghĩ điều này đi xuống để đếm số pixel (không phải màu đen) trong mỗi khu vực. Nếu bạn chọn một pixel không phải là màu đen, hãy thêm pixel đó vào một số HashSet<>, xem các pixel trên, dưới, bên trái và bên phải pixel bạn đã chọn cũng không phải là màu đen hay không.

Mỗi lần bạn tìm thấy new pixel không phải màu đen (bằng cách lên/xuống/trái/phải), thêm chúng vào bộ của bạn. Khi bạn đã tìm thấy tất cả, đếm chúng.

Khu vực của khu vực của bạn là count/(pixelWidthOfTotalDrawing * pixelHeightOfTotalDrawing) nhân với diện tích hình chữ nhật đầy đủ (tùy thuộc vào đơn vị bạn muốn).

Nhận xét: Tôi không nghĩ rằng hình này trông giống như đa giác. Đó là lý do tại sao tôi đã có chức năng "lấp đầy sơn" của phần mềm vẽ đơn giản trong tâm trí của tôi.