Top Ad unit 728 × 90

Latest news

recent

Connected component labeling 1 - (2 pass)

Những ai đã, đang làm việc với các ứng dụng surveillance và xử lý ảnh thì chắc hẳn sẽ hiểu tầm quan trọng của lớp thuật toán gắn nhãn các thành phần liên kết (Connected Component Labeling). Đây là các thuật toán dùng để phân hoạch một tập hợp các phần tử thành những nhóm được gán nhãn phân biệt dựa trên một mối quan hệ liên kết nào đó giữa chúng. Trong trường hợp dữ liệu là ảnh và phần tử cần phân loại là các pixel thì mối liên hệ thường xét là liên kết những pixel liền kề (mỗi pixel có tối đa 8 pixel hàng xóm neighbor pixel) cùng tính chất (cùng màu, cùng khoảng giá trị, ...). Bài viết sẽ bắt đầu cho loạt bài về chủ đề có liên quan nhằm giới thiệu các phương pháp chủ yếu hiện nay và sẽ kết thúc bằng một giải pháp ứng dụng được đề xuất bởi tác giả trong một paper sắp được công bố. Nội dung bài viết về phần giới thiệu các giải thuật Connected Component Labeling sẽ được dịch, tổng hợp, trình bày lại dựa trên blog của giáo sư Steve Eddins, và các nguồn tham khảo từ internet. Phần ứng dụng sẽ được viết bởi tác giả (Bioz). Vì hầu như các ứng dụng của Connected Component Labelling đều dựa trên ảnh nhị phân và cũng để đơn giản cho bước tiếp cận ban đầu chúng ta sẽ bắt đầu từ việc xử lý trên dữ liệu input là ảnh chỉ có hai màu phân biệt, trắng đại diện cho đối tượng (object), phần tử (component) hay gọi chung là foreground cần gán nhãn, còn đen đại diện cho nền (background).

Đầu tiên chúng ta sẽ bắt đầu với một giải thuật tương đối đơn giản được giới thiệu bởi Haralick và Shapiro (Computer and Robot Vision, vol. I, Addison-Wesley, 1992). Nó gồm hai bước duyệt qua từng phần tử của ảnh và một bước trung gian gọi là quá trình phân lớp tương thích (equivalence class resolution).
Nhiệm vụ của lần duyệt (Scan) ảnh đầu tiên là gán nhãn tạm thời cho các điểm ảnh thuộc về đối tượng. Chúng ta sẽ minh họa cho tiến trình này bằng một ví dụ dưới đây.
Dữ liệu đầu vào của chúng ta là một ảnh nhị phân có dạng ma trận (BW) như sau:

Và kết quả cần tìm là một ma trận nhãn (L) tương ứng cho từng điểm ảnh thuộc về foreground.

Chúng ta sẽ duyệt từng pixel của ảnh theo cột từ trái sang phải và từ trên xuống dưới (tiến trình này có thể được tiến hành theo hàng). Trong quá trình duyệt nếu gặp một điểm ảnh là foreground (giá trị = 1) thì ta sẽ tiến hành xem xét các điểm lân cận liền kề đã duyệt qua của nó. Hai hình dưới đây minh họa cho điểm ảnh foreground đầu tiên ta sẽ gặp trong quá trình duyệt ảnh và các pixel lân cận được xem xét.


Do các điểm ảnh xem xét chưa được gán nhãn và giá trị nhãn hiện tại là 0 nên điểm ảnh foreground hiện tại sẽ được gán nhãn bằng một nhãn mới (1). Dưới đây sẽ là điểm ảnh foregournd kế tiếp chúng ta gặp trong trình tự duyệt điểm ảnh.

Để ý rằng một trong những điểm lân cận xem xét của nó đã được gán nhãn 1 vì vậy nó cũng sẽ có nhãn là 1. Cứ tiếp tục như thế cho tới điểm ảnh ở dòng 2 cột 4, không có điểm ảnh nào lân cận xem xét đã được gán nhãn vì vậy nó được gán bằng một nhãn mới (2).

Tiếp tục quá trình scan đến điểm ảnh kế tiếp ở dòng 3 cột 4 chúng ta thấy một điều thú vị đã xãy ra.

 Một trong những điểm lân cận thuộc diện xem xét của nó đã được gán nhãn là 1 tuy nhiên một điểm khác cũng được gán nhãn là 2, trong trường hợp này thuật toán thực hiện việc gán nhãn tùy ý ( 1 hoặc 2) nhưng đánh dấu lại rằng hai nhãn 1 và 2 cùng tham chiếu tới 1 đối tượng. Trường hợp này xãy ra một lần nữa khi chúng ta tới dòng 4 cột 8.

 Vì vậy cặp nhãn 3 và 4 cũng là cặp tương thích được đánh dấu.
Khi lần scan thứ nhất được kết thúc chúng ta thu được một ma trận nhãn như sau

 và bảng các nhãn tương thích:
1 -- 2
3 -- 4
Kế đó Equivalence Class Resolution là quá trình quyết định những nhãn nào thực sự đánh dấu chung đối tượng nào. Kết quả nhận được từ xử lý này là 1--2 sẽ ánh xạ đến 1 và 3--4 sẽ ánh xạ tới 2. Lần duyệt ảnh thứ hai sẽ tái gán nhãn lại cho các pixel dựa trên bảng ánh xạ đã có từ (Equivalence Class Resolution).

 Như vậy là chúng ta đã kết thức ý tưởng đầu tiên cho nhóm thuật giải 2 Pass để giải quyết vấn đề Connected Component Labeling.


Binh Nguyen - Bioz
Connected component labeling 1 - (2 pass) Reviewed by Bioz on 10:50: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.