Thuật toán và cấu trúc dữ liệu để tìm và lưu trữ vùng lân cận của siêu mô hình trong C++

Question

Tôi có hình ảnh, giữ kết quả phân đoạn, như hình này.

Tôi cần tạo biểu đồ vùng lân cận của các bản vá lỗi, được tô màu bằng các màu khác nhau. Kết quả là tôi muốn có một cấu trúc, đại diện sau đây

Số này đại diện cho các bản vá lỗi riêng biệt và các dòng đại diện cho các vùng lân cận. Hiện tại tôi không thể tìm ra nơi bắt đầu, từ khóa nào đến google.

Có ai có thể đề xuất bất kỳ điều gì hữu ích không?

Hình ảnh được lưu trữ trong cv của OpenCV :: Lớp Mat, như đối với biểu đồ, tôi định sử dụng thư viện Boost.Graph.

Vì vậy, vui lòng cung cấp cho tôi một số liên kết đến mẫu mã và thuật toán hoặc từ khóa.

Cảm ơn.

Cập nhật. Sau giờ nghỉ giải lao và một số cuộc thảo luận, những điều sau đây đã đến với tâm trí của tôi.

1. Tạo biểu đồ lưới lớn, trong đó mỗi nút tương ứng với mỗi pixel hình ảnh và liên kết kết nối 8 hoặc 4 hàng xóm.
2. Gắn nhãn mỗi nút biểu đồ với giá trị pixel tương ứng.
3. Cố gắng hợp nhất các nút bằng một nhãn.

Vấn đề khác của tôi là tôi không quen với BGL (nhưng cuốn sách đang trên đường :)).

Vì vậy, bạn nghĩ gì về giải pháp này?

Update2 Có thể, điều này link có thể trợ giúp.

Tuy nhiên, vẫn không tìm thấy giải pháp.

Answer 1

Bạn có thể giải quyết nó như thế:

1. Xác định khu vực (con số của bạn trong đồ thị dưới)

   • làm cho một mảng 2D mà các cửa hàng số khu vực
   • bắt đầu tại (0/0) và đặt nó thành 1 (số vùng)
   • đặt toàn bộ khu vực là 1 bằng cách sử dụng thuật toán chèn lấp hoặc thứ gì đó.
   • trong khi xảy ra lũ lụt, bạn có thể gặp phải các tọa độ có màu sắc khác nhau. lưu trữ chúng bên trong hàng đợi. bắt đầu điền từ những tọa độ và số vùng tăng nếu điền trước đó của bạn được thực hiện.

   .

2. Hãy liên kết giữa các vùng

   • lặp qua mảng 2D của bạn.
   • nếu bạn có số lân cận, lưu trữ cặp số (có thể theo cách được sắp xếp, bạn cũng phải kiểm tra xem cặp đã tồn tại hay chưa). Bạn chỉ phải kiểm tra phần tử bên dưới, bên phải và đường chéo bên phải, nếu bạn tiến từ trái sang phải.

Mặc dù tôi phải thừa nhận tôi không biết một điều về chủ đề này .. chỉ là ý tưởng đơn giản của tôi ..

Answer 2

Tôi nghĩ rằng nếu các bản vá lỗi màu của bạn mà ngẫu nhiên, bạn có thể sẽ cần một thuật toán bạo lực để làm những gì bạn muốn. Ý tưởng có thể là:

• Thực hiện đèo sức mạnh đầu tiên. Điều này phải xác định tất cả các bản vá lỗi. Ví dụ: tạo một ma trận A có cùng kích thước với hình ảnh và khởi tạo nó thành 0. Đối với mỗi pixel vẫn bằng 0, hãy bắt đầu từ nó và đánh dấu nó là bản vá mới và thử phương pháp tiếp cận vũ lực để tìm toàn bộ mức độ của bản vá. Mỗi tế bào ma trận sau đó sẽ có một giá trị bằng với số lượng bản vá trong đó.
• Số bản vá phải là 2^N, ví dụ 1, 2, 4, 8, ...
• Tạo một ma trận B khác có kích thước của hình ảnh, nhưng mỗi ô chứa hai giá trị. Điều này sẽ đại diện cho kết nối giữa các pixel. Đối với mỗi ô của ma trận B, giá trị đầu tiên sẽ là sự khác biệt tuyệt đối giữa số bản vá trong pixel và số bản vá của một pixel liền kề. Giá trị đầu tiên là sự khác biệt với pixel dưới đây, thứ hai với pixel ở bên trái.
• Chọn tất cả các giá trị duy nhất trong ma trận B, bạn có tất cả các kết nối có thể.

Điều này hoạt động vì mỗi khác biệt giữa các số bản vá là duy nhất. Ví dụ, nếu trong B bạn kết thúc với số 3, 6, 7 nó sẽ có nghĩa là có các liên hệ giữa các bản vá (4,1), (8,2) và (8,1). Giá trị 0 của khóa học có nghĩa là có hai điểm ảnh trong cùng một miếng vá cạnh nhau, vì vậy bạn chỉ cần bỏ qua chúng.

Answer 3

Bạn có thể sử dụng BFS để đánh dấu các khu vực.

Để hiển thị cv :: Mat to BGL bạn nên viết nhiều mã. Tôi nghĩ rằng việc viết các bfs của riêng bạn đơn giản hơn rất nhiều.

Hơn bạn cho mỗi hai negbours ghi điểm của mình là std::set<std::pair<mark_t, mark_t>>. Và hơn là xây dựng đồ thị từ đó.