Top Ad unit 728 × 90

Latest news

recent

Connected component labeling 2 - (Union Find)

Tiếp tục bài viết trước, tôi giới thiệu một thuật giải rất nổi tiếng được ứng dụng để giải quyết vấn đề CCL đó là Union Find. Nhìn một cách tổng quan, giải pháp có sử dụng Union-Find này cũng trải qua 2 lần duyệt ảnh nên nó thuộc nhóm các thuật giải CCL 2 pass. Tuy nhiên việc ứng dụng Union Find đã giải quyết vấn đề tối ưu cấu trúc dữ liệu, giúp làm tăng đáng kể tốc độ xử lí, thóat ra khỏi những hướng đi cũ. Không giống như phương pháp đã trình bày, thuật toán này không tiến hành đánh nhãn ngay trong bước 1 mà chỉ thực hiện việc xây dựng cây để kết nối các nốt (mỗi foreground pixel là một nốt với một nhãn được khởi tạo tăng dần ban đầu) . Kết quả cuối cùng thu được của lần duyệt hình đầu tiên (Union) là một cây duy nhất thể hiện mối liên kết giữa các nhãn, các cặp nhãn tương thích như đã đề cập ở bài viết trước sẽ có quan hệ nốt cha và con. Bước 2 (Find) sẽ tiến hành việc đánh nhãn dựa trên kết quả thu về từ bước 1. Do điểm đặc biệt làm nên hiệu quả của Union-Find chính là ở cấu trúc dữ liệu nó sử dụng nên đôi khi người ta còn đánh đồng giải thuật này là cấu trúc Union-Find (Union-Find structures). Trong thực hành, cấu trúc này thường được biểu diễn dựa trên một mảng 1 chiều kí hiệu là PARENT, trong đó chỉ mục (index) của mảng lần lượt đại diện cho các nốt có nhãn tương ứng, giá trị của phần tử tại từng chỉ mục thể hiện nhãn nốt cha của nốt có nhãn là chỉ mục đó. Trong trường hợp giá trị bằng chỉ mục (hay 0), có nghĩa là nốt được đại diện bởi giá trị chỉ mục đó là nốt gốc (root: không có cha). Để làm chi tiết thêm những gì đã trình bày chúng ta sẽ cùng nhau từng bước xử lý một ví dụ như sau.
Cho hình nhị phân và ma trận nhãn của foreground pixel đã được khởi tạo tăng dần như là minh họa dưới đây. (bên trái là ảnh nhị phân, bên phải là ma trận nhãn đã được khởi tạo)


Ma trận nhãn sẽ được duyệt theo chiều từ trên xuống và trái sang phải tương tự như cách duyệt đã trình bày ở bài trước. Với những cặp nhãn tương thích (đã trình bày ở bài trước), nhãn nhỏ hơn sẽ là cha và nhãn lớn hơn sẽ là node con. Chúng ta sẽ có cấu trúc Union-Find thể hiện qua mảng PARENT như sau:
Như vậy về mặt thực hành mảng PARENT ở trên chính là kết quả của quá trình duyệt ảnh (mảng label) lần thứ nhất với tiến trình Union. 1-2, 1-3, 1-4, 1-5, 5-7, 5-6 là những cặp nhãn tương thích được tìm thấy trong quá trình duyệt. Trước khi tiến hành lần duyệt thứ hai để đánh nhãn chính xác cho từng điểm ảnh, tiến trình Find cho từng nhãn cần được thực hiện để xác định đâu là cha thực sự của các nốt trong PARENT. Ví dụ khi ta tiến hành Find trên nốt có nhãn là 7 ta sẽ tìm ra 1 mới là cha của 7 chứ không phải 5. Quá trình này bắt đầu từ xét giá trị PARENT[7], ta thấy PARENT[7] = 5 có nghĩa là nốt cha của 7 có nhãn là 5, ta xét tiếp PARENT[5], ta thấy PARENT[5] = 1 có nghĩa là nốt cha của 5 có nhãn là 1, ta xét tiếp PARENT[1], ta thấy PARENT[1] = 1 có nghĩa là 1 là nốt gốc, quá trình xét ngưng vì đã tìm ra 1 mới chính là cha thực sự cần tìm của 7. Sau khi áp dụng Find cho toàn bộ nốt ta có PARENT như sau:
Lúc này tiến trình quét ảnh lần hai chỉ làm một nhiệm vụ hết sức đơn giản là đánh nhãn lại cho từng điểm ảnh bằng cách gán giá trị nhãn củ L = PARENT[L].

Chú ý rằng bài viết này được trình bày nhằm giúp các bạn hiểu rỏ thế nào là ứng dụng ý tưởng của cấu trúc Union-Find trong CCL, trong thực tế triển khai, các tiến trình Union, find, đánh nhãn có thể được tối ưu bằng cách lồng ghép, hay cải tiến bằng các kỉ thuật khác nhau để cho hiệu xuất cao nhất.

Binh Nguyen - Bioz
Connected component labeling 2 - (Union Find) Reviewed by Bioz on 2:52:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.