Làm thế nào để sử dụng các bộ phân chia trong nhãn thành phần được kết nối?

Question

Tôi đang gặp một số khó khăn khi sử dụng Disjoint Sets trong Ghi nhãn thành phần được kết nối. Tôi đã xem xét nhiều ví dụ và cũng trên this question trong đó Bo Tian cung cấp triển khai thực hiện rất tốt các Bộ tách rời dưới dạng danh sách được liên kết với C++. Tôi đã thực hiện ghi nhãn thành phần kết nối (nhãn là số nguyên đơn giản) trong chương trình của tôi nhưng tôi có một thời gian thực sự khó giải quyết tương đương giữa các nhãn với bộ phân tách.

Bất cứ ai có thể giúp tôi về điều đó - có thể sử dụng triển khai của Bo Tian? Tôi nghĩ rằng cũng sẽ giúp đỡ người khác khi họ đến thời điểm này.

EDIT

thuật toán của tôi đi qua các hình ảnh và khi nó tìm thấy hai nhãn hai pixel được kết nối với các nhãn khác nhau nó có để làm cho một lưu ý trong 'registry tương đương' (đó sẽ là rời nhau thiết lập rừng) . Sau khi lặp đi lặp lại toàn bộ hình ảnh, tôi phải giải quyết tương đương (bằng cách vượt qua hình ảnh thứ hai) xem sổ đăng ký và sau đó đánh dấu các điểm ảnh này có nhãn tương đương ở mức tối thiểu trong tập hợp.

Answer 1

Kiểm tra điều này tutorial on DJS. Chỉ có sửa đổi là trong thời gian công đoàn bạn phải kết nối lớn hơn với ít hơn, vì vậy gốc luôn luôn là tối đa của tập hợp.

Answer 2

Các nguồn cung cấp rừng rời nhau thiết lập hai hoạt động:

• Liên minh, trong đó có hai đối tượng và liên kết chúng, và
• Tìm, trong đó có hai đối tượng và trả về ID của nhóm họ đang ở.

Rừng được thiết lập riêng được sử dụng chủ yếu để duy trì phân vùng nhóm đối tượng thành một nhóm các cụm khác nhau, mỗi cụm liên kết với nhau (nghĩa là, mỗi đối tượng ở nhiều nhất một nhóm). Các khu rừng phân chia sau đó cho phép bạn có hiệu quả cho biết những gì các đối tượng trong mỗi nhóm, hoặc (trong khoảng O (n) thời gian) để xác định các ID cụm cho mỗi đối tượng.

Để sử dụng rừng tập hợp rời nhau, bạn sẽ bắt đầu bằng cách đặt từng đối tượng vào cụm của riêng nó. Từ thời điểm đó trở đi, mỗi lần bạn muốn đánh dấu hai đối tượng khác nhau nằm trong cùng một cụm, bạn sẽ sử dụng hoạt động union để liên kết chúng với nhau. Cuối cùng, bạn sẽ gọi số tìm số trên mỗi điểm để xác định cụm thuộc về cụm nào và từ đó có thể đọc tất cả mọi thứ thuộc về nhóm nào.

Hy vọng điều này sẽ hữu ích!

Answer 3

Bạn nói đúng, ghi nhãn các bộ kết nối chỉ bằng một nửa công việc đã hoàn thành. Việc tìm kiếm các bộ phân chia bằng cách sử dụng các sự tương đương cũng là một phần khó khăn. Tôi phải đối mặt với kịch bản chính xác.

Một cách để tìm các tập phân tách (sau khi gắn nhãn) bằng cách sử dụng thuật toán Union-Find. Hãy xem bài viết sau. Bạn sẽ hiểu từ đầu như thế nào ghi nhãn và tìm các bộ phân chia được thực hiện. Minh họa cũng được đưa ra với các ma trận đầu vào và đầu ra mẫu.

http://www.codeding.com/articles/connected-sets-labeling

Answer 4

Có một blog về ghi nhãn thành phần được kết nối với các thiết lập rời nhau:

http://www.keithlantz.net/2011/04/c-implementation-of-the-connected-component-labeling-method-using-the-disjoint-set-data-structure/